Design and Analysis of Algorithms Course Materials

This repository provides the course materials for Design and Analysis of Algorithms (2026) by Earl Peter J. Gangoso, licensed under CC BY-NC 4.0. To view a copy of this license, visit https://creativecommons.org/licenses/by-nc/4.0/.

Creative Commons Attribution-NonCommercial 4.0 International: This license requires that reusers give credit to the creator. It allows reusers to distribute, remix, adapt, and build upon the material in any medium or format, for noncommercial purposes only.

Course Description and Objectives

This course introduces the concepts and techniques of designing and analyzing algorithms. It covers the basic principles of algorithm design, such as correctness, efficiency, and optimality, and the methods of algorithm analysis, such as asymptotic notations, recurrence relations, and complexity theory. It also reviews the fundamental data structures that are used to implement algorithms, such as arrays, lists, stacks, queues, trees, graphs, etc. The course explores various types and paradigms of algorithms, such as recursive, brute force, divide and conquer, decrease and conquer, transform and conquer, greedy, heuristic, and dynamic programming algorithms. The course also discusses the applications and limitations of algorithms in solving various problems in computer science and other disciplines.

Upon completion of the course, the students can:

1. Introduce common algorithm design techniques.
2. Describe the behavior and running time of various searching, sorting, and graph algorithms.
3. Analyze the efficiency of algorithms using asymptotic bounds on time and space complexity.
4. Evaluate the correctness of algorithms using proofs, formal methods, or comparison with known solutions.
5. Choose and apply the most appropriate algorithm design technique (divide and conquer, backtracking, greedy, dynamic programming) for solving problems.

Course Contents

1. Introduction to Algorithms (PDF)
2. Time and Space Complexity (PDF)
3. Review of Fundamental Data Structures (PDF)
   • Heap (PDF)
   • AVL Trees (PDF)
   • Red-Black Trees (PDF)
4. Recursive Algorithms (PDF)
5. Brute Force Algorithms (PDF)
   • Example: Traveling Salesman (PDF)
   • Example: Finding Closest Pair of Points (PDF)
6. Divide and Conquer, Decrease and Conquer, and Transform and Conquer
   • Divide and Conquer (PDF)
   • Decrease and Conquer (PDF)
   • Transform and Conquer (PDF)
7. Greedy Algorithms
   • Introduction to Greedy Algorithms (PDF)
   • MST and Shortest Path (PDF)
8. Heuristics (PDF)
9. Dynamic Programming
   • Intro to Dynamic Programming (PDF)
   • Example: Levenstein Distance and Longest Common Subsequence (PDF)

Primary References

• GeeksforGeeks. (2024, January 12). Algorithms Tutorial. GeeksforGeeks. https://www.geeksforgeeks.org/fundamentals-of-algorithms/?ref=shm
• Cormen, T. H., Charles Eric Leiserson, Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms. The MIT Press.
• Njoroge, H. (2021). Data structure and algorithms. African Virtual University. https://eng.libretexts.org/Bookshelves/Computer_Science/Databases_and_Data_Structures/Data_Structure_and_Algorithms_(Njoroge)
• 3G E-Learning. (2020). Data structures and algorithm (2nd ed.). 3G E-Learning.
• Narasimha Karumanchi. (2018). Data Structures and Algorithms Made Easy: Data Structure and Algorithmic Puzzles. Careermonk Publications.
• Sen, S., & Kumar, A. (2019). Design and Analysis of Algorithms. Cambridge University Press.