C++ Algorithms and Data Structures I

This repository contains my solutions for the "Algorithms 1" course at Universidad ORT Uruguay. The focus of this work is the practical implementation of fundamental Abstract Data Types (ADTs) and algorithms from scratch in C++.

---

Core Concepts Demonstrated

This project showcases a solid understanding of core computer science fundamentals, including:

• Abstract Data Type (ADT) Implementation: Building foundational data structures without relying on standard libraries.
• Time Complexity Analysis: Implementing operations to meet specific performance requirements (e.g., constant O(1), logarithmic O(log n)).
• Hashing & Hash Tables: Implementing dictionary and table structures using open hashing for O(1) average time complexity on key operations.
• Linear & Non-Linear Data Structures: Working with Stacks, Queues, Lists, Binary Search Trees, and Priority Queues.
• Algorithm Design: Creating functions to solve problems using the implemented ADTs, while respecting constraints like immutability of parameters.

---

Implementations & Exercises Breakdown

Below is a summary of the implemented ADTs and the algorithms designed for them.

🥞 Stack (PilaInt)

• Unbounded Stack Implementation: A stack implementation with worst-case O(1) time complexity for push, top, pop, and cantidadElementos operations.
• EstaContenida Algorithm: A function that checks if all elements of a stack p1 are contained within a stack p2, correctly handling duplicate values.

FIFO Queue (ColaInt)

• Unbounded Queue Implementation: A queue implementation where enqueue, front, dequeue, and cantidadElementos operations run in worst-case O(1) time.

🌳 Binary Search Tree (NodoABInt) & Lists (ListaOrdInt)

• Enlistar Algorithm: A function that traverses a Binary Search Tree (BST) a single time to convert it into a sorted list (ListaOrdInt).
• UnionListaOrd Algorithm: Merges two sorted lists into a new sorted list without modifying the input lists.
• Optimized Sorted List: An implementation of a sorted list where add, remove, and exists operations run in O(log n) average time.

#️⃣ Hash-Based Structures (Dictionary & Table)

• Dictionary (DiccionarioIntImp): An unbounded dictionary implemented with open hashing, achieving O(1) average time for add, remove, and belongs operations.
• Table (TablaIntStringImp): An unbounded hash table (key-value store) also implemented with open hashing for O(1) average time on add, remove, isDefined, and retrieve operations.

🔢 Multiset & Priority Queue

• Multiset (MultisetIntImp): A full implementation of an unbounded multiset ADT.
• Set Theory Algorithms:
  • ObtenerRepetidos: Returns a list of elements that appear more than once in the multiset.
  • Xor: Returns a new multiset containing elements that are in one of the two input multisets, but not in both.
• Priority Queue (ColaPrioridadImp): A bounded implementation of a Priority Queue.
• MenorPrioridad Algorithm: A function that returns a new priority queue containing only the elements with the lowest priority level from an input queue.

---

Technology Used

• Language: C++

---

Key Learnings

This project was a deep dive into the practical trade-offs of different data structures. It solidified my understanding of how to implement complex ADTs from scratch and how their underlying design directly impacts the efficiency of algorithms. This work represents a strong foundation in the principles of efficient and well-structured code.