• ES Español
• EN English

5.19. Algorithms and Data Structures (Mandatory)

5.19.1. Justification ↑ Back to top

This course provides a comprehensive study of fundamental data structures and algorithms with emphasis on implementation using advanced C++ features. Building on prior C++ knowledge, students will implement generic data structures using templates and traits, ensuring type flexibility and performance. The course covers linear structures (vectors, various linked lists), tree structures (binary, AVL, B-trees), heaps, hash tables, tries, and concurrent data structures. Special focus is placed on modern C++ techniques including variadic templates for generic operations and concurrent programming for thread-safe data structures.

5.19.2. Generales Goals ↑ Back to top

1. Implement generic data structures using templates and traits.
2. Master advanced tree structures and balanced trees.
3. Understand and implement concurrent data structures.
4. Apply variadic templates for generic operations on containers.
5. Analyze algorithmic complexity of all implemented structures.
6. Design efficient data structures for specific problem constraints.

5.19.3. Contribution to Outcomes ↑ Back to top

AG-C08) Problem Analysis: Identifies, formulates, and analyzes complex computing problems. (Usage)

AG-C09) Design and Development of Solutions: Designs, implements, and evaluates solutions for complex computing problems. (Usage)

5.19.4. Content ↑ Back to top

5.19.4.1. Advanced Foundation for Data Structures (8 hours) [Skills AG-C08,AG-C09] ↑ Back to top

Bibliography: (Stroustrup, 2013; Vandevoorde et al., 2017a)

Topics

1. Template metaprogramming review and advanced traits.
2. Type traits and SFINAE for conditional compilation.
3. Variadic templates and parameter packs.
4. Perfect forwarding and universal references.
5. Lambda expressions with generic captures.
6. Policy-based design and CRTP (Curiously Recurring Template Pattern).
7. Concept-based constraints (C++20 concepts if applicable).

Learning Outcomes

1. Design type traits for customizing data structure behavior [Usage].
2. Implement variadic templates for generic container operations [Usage].
3. Apply policy-based design to create configurable data structures [Assessment].
4. Use perfect forwarding to implement efficient constructors [Usage].

5.19.4.2. Foundational Data Structures (8 hours) [Skills AG-C08,AG-C09] ↑ Back to top

Bibliography: (Cormen et al., 2009; Stroustrup, 2013)

Topics

1. Abstract Data Type (ADT) and operations on an ADT:
2. Dictionary operations (insert, delete, find) enumerate
3. Arrays:
4. Numeric vs non-numeric, character strings
5. Single (vector) vs multidimensional (matrix) enumerate
6. Records/Structs/Tuples and Objects
7. Linked lists (for historical reasons):
8. Single vs Double and Linear vs Circular enumerate
9. Stacks
10. Queues and deques:
11. Heap-based priority queue enumerate
12. Hash tables/maps:
13. Collision resolution and complexity (e.g., probing, chaining, rehash) enumerate
14. Trees:
15. Binary, n-ary, and search trees
16. Balanced (e.g., AVL, Red-Black, Heap) enumerate
17. Sets

Learning Outcomes

1. For each ADT/Data-Structure in this unit:
2. Explain its definition, properties, representation(s), and associated ADT operations.
3. Explain step-by-step how the ADT operations associated with the data structure transform it. enumerate [Usage]
4. For each algorithm in this unit explain step-by-step how the algorithm operates [Usage]
5. Implement vector with customizable allocation policy using templates [Usage].
6. Design generic linked list nodes with trait-based memory management [Usage].
7. Compare time/space complexity of different linear structures [Assessment].
8. Apply variadic templates to initialize containers with multiple elements [Usage].

5.19.4.3. Foundational Data Structures (8 hours) [Skills AG-C08,AG-C09] ↑ Back to top

Bibliography: (Cormen et al., 2009; Knuth, 1997a)

Topics

1. Trees:
2. Binary, n-ary, and search trees
3. Balanced (e.g., AVL, Red-Black, Heap) enumerate
4. Binary tree template implementation with iterator support.
5. Binary search tree with trait-based comparison operators.
6. Tree traversal algorithms (iterative and recursive).
7. Expression trees and their applications.
8. Template-based node structures with configurable payload.

Learning Outcomes

1. Given requirements for a problem, develop multiple solutions using various data structures and algorithms. Subsequently, evaluate the suitability, strengths, and weaknesses selecting an approach that best satisfies the requirements [Assessment]
2. Explain factors beyond computational efficiency that influence the choice of algorithms, such as programming time, maintainability, and the use of application-specific patterns in the input data [Familiarity]
3. Implement generic binary tree with configurable traversal order [Usage].
4. Design expression tree evaluator using visitor pattern [Usage].
5. Analyze tree operation complexities for different balancing strategies [Assessment].

5.19.4.4. Balanced and Multi-way Trees (8 hours) [Skills AG-C08,AG-C09] ↑ Back to top

Bibliography: (Cormen et al., 2009; Knuth, 1997a; Sedgewick and Wayne, 2011)

Topics

1. AVL tree implementation with template-based balancing trait.
2. Red-black tree properties and operations.
3. B-Tree template implementation for disk-based storage.
4. 2-3 Tree and 2-3-4 Tree structures.
5. Digital trie (prefix tree) implementation.
6. Suffix trees and their applications in string processing.
7. Node splitting/merging strategies for B-trees.

Learning Outcomes

1. Implement self-balancing trees using policy-based design [Usage].
2. Design B-tree for database index applications [Usage].
3. Evaluate trade-offs between different balanced tree structures [Assessment].
4. Implement trie for efficient string prefix matching [Usage].

5.19.4.5. Foundational Data Structures (8 hours) [Skills AG-C08,AG-C09] ↑ Back to top

Bibliography: (Cormen et al., 2009; Sedgewick and Wayne, 2011)

Topics

1. Trees:
2. Binary, n-ary, and search trees
3. Balanced (e.g., AVL, Red-Black, Heap) enumerate
4. Binary heap implementation using array representation.
5. Min-heap and max-heap variants.
6. Heapify algorithms and complexity analysis.
7. Priority queue ADT implementation.
8. Binomial heap and Fibonacci heap overview.
9. Heap applications: Dijkstra's algorithm, heap sort.

Learning Outcomes

1. Explain the heap property and the use of heaps as an implementation of a priority queue [Familiarity]
2. Implement generic heap with configurable comparison trait [Usage].
3. Design priority queue supporting multiple priority update strategies [Usage].
4. Analyze heap operations complexity for different heap types [Assessment].
5. Apply heap in graph algorithm implementations [Usage].

5.19.4.6. Foundational Data Structures (8 hours) [Skills AG-C08,AG-C09] ↑ Back to top

Bibliography: (Cormen et al., 2009; Knuth, 1997a)

Topics

1. Hash tables/maps:
2. Collision resolution and complexity (e.g., probing, chaining, rehash) enumerate
3. Hash function design and properties.
4. Separate chaining implementation with linked lists.
5. Open addressing: linear probing, quadratic probing, double hashing.
6. Perfect hashing and minimal perfect hashing.
7. Cuckoo hashing and hopscotch hashing.
8. Hash table resizing strategies and load factor management.

Learning Outcomes

1. Explain how collision avoidance and collision resolution is handled in hash tables [Familiarity]
2. Design generic hash table with configurable collision resolution [Usage].
3. Implement custom hash functions for user-defined types [Usage].
4. Evaluate performance of different hashing schemes [Assessment].
5. Apply hash tables in compiler symbol table implementation [Usage].

5.19.4.7. Concurrent Data Structures (8 hours) [Skills AG-C08,AG-C09] ↑ Back to top

Bibliography: (Herlihy and Shavit, 2012; Williams, 2019)

Topics

1. Thread-safe data structure design principles.
2. Lock-based concurrent linked lists.
3. Lock-free and wait-free algorithms.
4. Concurrent hash tables with fine-grained locking.
5. Atomic operations and memory ordering.
6. Concurrent queues (bounded and unbounded).
7. Concurrent stacks and elimination techniques.

Learning Outcomes

1. Design thread-safe data structures using mutex and lock guards [Usage].
2. Implement lock-free linked list using atomic operations [Usage].
3. Analyze performance of concurrent vs sequential data structures [Assessment].
4. Apply concurrent queues in producer-consumer patterns [Usage].

5.19.4.8. Specialized Structures and Applications (8 hours) [Skills AG-C08,AG-C09] ↑ Back to top

Bibliography: (Okasaki, 1999; Sedgewick and Wayne, 2011)

Topics

1. Persistent data structures.
2. Disjoint-set union (union-find) with path compression.
3. Bloom filters and their probabilistic properties.
4. Skip lists for probabilistic balanced search.
5. Segment trees and Fenwick trees for range queries.
6. Spatial data structures: k-d trees, quadtrees.
7. Cache-oblivious data structures.

Learning Outcomes

1. Implement persistent data structures with structural sharing [Usage].
2. Design union-find with both union by rank and path compression [Usage].
3. Apply specialized structures to solve domain-specific problems [Assessment].
4. Evaluate space-time tradeoffs in probabilistic data structures [Assessment].

5.19.5. Bibliography ↑ Back to top

Stroustrup, B. (2013). The C++ Programming Language. Addison-Wesley Professional, Upper Saddle River, NJ, 4th edition.

Vandevoorde, D., Josuttis, N. M., and Gregor, D. (2017a). C++ Templates: The Complete Guide. Addison-Wesley Professional, Upper Saddle River, NJ, 2nd edition.

Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction to Algorithms. MIT Press, 3rd edition.

Knuth, D. E. (1997a). The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley, 3rd edition.

Sedgewick, R. and Wayne, K. (2011). Algorithms. Addison-Wesley, 4th edition.

Herlihy, M. and Shavit, N. (2012). The Art of Multiprocessor Programming. Morgan Kaufmann, revised 1st edition.

Williams, A. (2019). C++ Concurrency in Action. Manning Publications, Shelter Island, NY, 2nd edition.

Okasaki, C. (1999). Purely Functional Data Structures. Cambridge University Press.