• ES Español
• EN English

5.26. Analysis and Design of Algorithms (Mandatory)

5.26.1. Justification ↑ Back to top

Algorithms are the heart of computer science. This course provides the mathematical and analytical tools necessary to evaluate the efficiency of algorithms in terms of time and space. Students will explore fundamental data structures, complexity analysis, and various design paradigms—such as brute force, greedy, and dynamic programming. Understanding these techniques is essential for building software that is not only functional but also scalable and resource-efficient.

5.26.2. Generales Goals ↑ Back to top

1. Master the use of asymptotic notation to analyze algorithm performance.
2. Apply foundational data structures to solve computational problems.
3. Use algorithmic strategies like Greedy, Divide and Conquer, and Dynamic Programming.
4. Analyze the complexity of algorithms in best, average, and worst cases.
5. Develop the ability to select the most appropriate algorithm for a given problem.

5.26.3. Contribution to Outcomes ↑ Back to top

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

AG-C12) Applies computer science theory and software development fundamentals to produce computer-based solutions. (Usage)

5.26.4. Content ↑ Back to top

5.26.4.1. Foundational Data Structures (6 hours) [Skills AG-C08,AG-C12] ↑ Back to top

Bibliography: (Cormen et al., 2022; Kleinberg and Tardos, 2005)

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 [Explain]
4. Explain how collision avoidance and collision resolution is handled in hash tables [Explain]
5. Explain the heap property and the use of heaps as an implementation of a priority queue [Explain]

5.26.4.2. Foundational Algorithms (6 hours) [Skills AG-C08,AG-C12] ↑ Back to top

Bibliography: (Cormen et al., 2022; Kleinberg and Tardos, 2005)

Topics

1. Graphs (e.g., [un]directed, [a]cyclic, [un]connected, and [un]weighted):
2. Graph representation: adjacency list vs matrix enumerate
3. Search algorithms:
4. \(O(n)\) complexity (e.g., linear/sequential array/list search)
5. \(O(\log_2 n)\) complexity (e.g., binary search)
6. \(O(\log_b n)\) complexity (e.g., uninformed depth/breadth-first tree search) enumerate
7. Sorting algorithms (e.g., stable, unstable):
8. \(O(n^2)\) complexity (e.g., insertion, selection)
9. \(O(n \log n)\) complexity (e.g., quicksort, merge, timsort) enumerate
10. Graph algorithms:
11. Shortest path (e.g., Dijkstra's, Floyd's)
12. Minimal spanning tree (e.g., Prim's, Kruskal's) enumerate
13. Sorting algorithms:
14. \(O(n \log n)\) complexity heapsort
15. Pseudo \(O(n)\) complexity (e.g., bucket, counting, radix) enumerate
16. Graph algorithms:
17. Transitive closure (e.g., Warshall's)
18. Topological sort enumerate
19. Matching:
20. Efficient string matching (e.g., Boyer-Moore, Knuth-Morris-Pratt)
21. Longest common subsequence matching
22. Regular expression matching enumerate

Learning Outcomes

1. For each algorithm in this unit explain step-by-step how the algorithm operates [Explain]
2. For each algorithmic approach (e.g., sorting) in this unit apply a prototypical example of the approach (e.g., merge sort) [Apply]
3. 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 [Create]
4. 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 [Explain]
5. For each of the algorithms and algorithmic approaches in the KA Core topics:
6. Explain a prototypical example of the algorithm, and
7. Explain step-by-step how the algorithm operates. enumerate [Explain]

5.26.4.3. Advanced Algorithms (4 hours) [Skills AG-C08,AG-C12] ↑ Back to top

Bibliography: (Cormen et al., 2022; Kleinberg and Tardos, 2005)

Topics

1. Cryptography algorithms (e.g., SHA-256)
2. Parallel algorithms
3. Consensus algorithms (e.g., Blockchain):
4. Proof of work vs proof of stake enumerate
5. Quantum computing algorithms:
6. Oracle-based (e.g., Deutsch-Jozsa, Bernstein-Vazirani, Simon)
7. Superpolynomial speed-up via QFT (e.g., Shor's)
8. Polynomial speed-up via amplitude amplification (e.g., Grover's) enumerate
9. Fast-Fourier Transform (FFT) algorithm
10. Differential evolution algorithm

Learning Outcomes

1. An appreciation of quantum computation and its application to certain problems [Explain]

5.26.4.4. Algorithmic Strategies (24 hours) [Skills AG-C08,AG-C12] ↑ Back to top

Bibliography: (Cormen et al., 2022; Dasgupta et al., 2006)

Topics

1. Paradigms:
2. Brute-Force (e.g., linear search, selection sort, traveling salesperson, knapsack)
3. Decrease-and-Conquer:
4. By a Constant (e.g., insertion sort, topological sort)
5. By a Constant Factor (e.g., binary search)
6. By a Variable Size (e.g., Euclid's) enumerate
7. Divide-and-Conquer (e.g., binary search, quicksort, mergesort, Strassen's)
8. Greedy (e.g., Dijkstra's, Kruskal's, Knapsack)
9. Transform-and-Conquer:
10. Instance simplification (e.g., find duplicates via list presort)
11. Representation change (e.g., heapsort)
12. Problem reduction (e.g., least-common-multiple, linear programming)
13. Dynamic programming (e.g., Floyd's, Marshall, Bellman-Ford) enumerate
14. Space vs time tradeoffs (e.g., hashing) enumerate
15. Handling exponential growth (e.g., heuristic A*, branch-and-bound, backtracking)
16. Iteration vs recursion (e.g., factorial, tree search)
17. Paradigms:
18. Approximation algorithms
19. Iterative improvement (e.g., Ford-Fulkerson, simplex)
20. Randomized/Stochastic algorithms (e.g., max-cut, balls and bins) enumerate
21. Quantum computing

Learning Outcomes

1. For each of the paradigms in this unit:
2. Explain its definitional characteristics
3. Explain an example that demonstrates the paradigm including how this example satisfies the paradigm's characteristics. enumerate [Explain]
4. For each of the algorithms in the Foundational Data Structures , Foundational Algorithms , Advanced Algorithms unit, explain the paradigm used by the algorithm and how it exemplifies this paradigm [Explain]
5. Given an algorithm, explain the paradigm used by the algorithm and how it exemplifies this paradigm [Explain]
6. Give a real-world problem, evaluate appropriate algorithmic paradigms and algorithms from these paradigms that address the problem including evaluating the tradeoffs among the paradigms and algorithms selected [Evaluate]
7. Give examples of iterative and recursive algorithms that solve the same problem, explain the benefits and disadvantages of each approach [Explain]
8. Evaluate whether a greedy approach leads to an optimal solution [Evaluate]
9. Explain various approaches for addressing computational problems whose algorithmic solutions are exponential [Explain]

5.26.4.5. Complexity Analysis Framework (6 hours) [Skills AG-C08,AG-C12] ↑ Back to top

Bibliography: (Cormen et al., 2022; Sipser, 2012)

Topics

1. Complexity Analysis Framework:
2. Best, average, and worst-case performance of an algorithm
3. Empirical and relative (Order of Growth) measurements
4. Input size and primitive operations
5. Time and space efficiency enumerate
6. Empirical measurements of performance
7. Time and space tradeoffs in algorithms

Learning Outcomes

1. For each algorithm in the Foundational Data Structures , Foundational Algorithms , Advanced Algorithms unit, explain its runtime complexity class and why it belongs to this class [Explain]
2. Develop empirical studies to determine and validate hypotheses about the runtime complexity of various algorithms by running algorithms on input of various sizes and comparing actual performance to the theoretical analysis [Create]
3. Explain examples that illustrate time-space tradeoffs of algorithms [Explain]
4. Explain how tree balance affects the efficiency of binary search tree operations [Explain]

5.26.4.6. Asymptotic Notation and Complexity Classes (6 hours) [Skills AG-C08,AG-C12] ↑ Back to top

Bibliography: (Cormen et al., 2022; Sipser, 2012)

Topics

1. Asymptotic complexity analysis (average and worst-case bounds):
2. Big-O, Big-Omega, and Big-Theta formal notations
3. Foundational Complexity Classes and Representative Examples/Problems:
4. \(O(1)\) Constant (e.g., array access)
5. \(O(\log_2 n)\) Logarithmic (e.g., binary search)
6. \(O(n)\) Linear (e.g., linear search)
7. \(O(n \log_2 n)\) Log Linear (e.g., mergesort)
8. \(O(n^2)\) Quadratic (e.g., selection sort)
9. \(O(n^c)\) Polynomial (e.g., \(O(n^3)\) Gaussian elimination)
10. \(O(2^n)\) Exponential (e.g., Knapsack, Satisfiability (SAT), Traveling Sales-Person (TSP), all subsets)
11. \(O(n!)\) Factorial (e.g., Hamiltonian circuit, all permutations) enumerate enumerate

Learning Outcomes

1. For each foundational complexity class in this unit, explain an algorithm that demonstrates the associated runtime complexity [Explain]
2. Apply Big-O notation to give upper case bounds on time/space complexity of algorithms [Apply]

5.26.4.7. Complexity Analysis: Recursion, Amortization, and Tight Bounds (12 hours) [Skills AG-C08,AG-C12] ↑ Back to top

Bibliography: (Cormen et al., 2022; Sipser, 2012)

Topics

1. Little-o, Little-Omega, and Little Theta notations
2. Formal recursive analysis
3. Amortized analysis

Learning Outcomes

1. Given a problem to program for which there may be several algorithmic approaches, evaluate them and determine which are feasible, and select one that is optimal in implementation and run-time behavior [Evaluate]
2. Use recurrence relations to evaluate the time complexity of recursively defined algorithms [Apply]
3. Apply elementary recurrence relations using a form of the Master Theorem [Apply]

5.26.4.8. Computational Complexity Theory (6 hours) [Skills ] ↑ Back to top

Bibliography: (Sipser, 2012; Cormen et al., 2022)

Topics

1. Tractability and intractability:
2. P, NP, and NP-Complete Complexity Classes
3. NP-Complete Problems (e.g., SAT, Knapsack, TSP)
4. Reductions enumerate

Learning Outcomes

1. Explain the significance of NP-Completeness [Explain]
2. Explain examples of NP-complete problems [Explain]
3. Explain the classes P and NP [Explain]

5.26.5. Bibliography ↑ Back to top

Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2022). Introduction to Algorithms. MIT Press, 4th edition.

Kleinberg, J. and Tardos, É. (2005). Algorithm Design. Pearson.

Dasgupta, S., Papadimitriou, C., and Vazirani, U. (2006). Algorithms. McGraw-Hill Education.

Sipser, M. (2012). Introduction to the Theory of Computation. Cengage Learning, 3rd edition.