Design and Analysis of Algorithms

This course covers the design and analysis of fundamental algorithms used in practice. It focuses on three major aspects of algorithms. The first aspect is how to measure the time/space complexity of existing algorithms for basic problems. The worst-case and average-case scenarios will be studied using asymptotic notations such as big-oh, big-omega, and theta. The second aspect is understanding well-known paradigms for designing algorithms, including divide-and-conquer, dynamic programming, and greedy approaches. The third aspect covers designing efficient (also known as polynomial-time) algorithms for several fundamental problems in computer science along with their time complexities. The course also includes complexity theory, where one can observe some decisional problems, referred to as hard problems, for which deterministic polynomial-time algorithms are believed to be intractable.

This course is structured into eight modules. It begins by reviewing essential topics in discrete mathematics in Module 1. Module 2 formally introduces worst-case and average-case complexity measurements using various asymptotic notations, and presents algorithms by induction along with different variants of binary search algorithms. Module 3 covers recursion, the divide-and-conquer approach to algorithms, and time complexity using the master theorem. Moving on to Module 4, the course presents various sorting algorithms, comparing their time complexities, and introduces selection algorithms. Module 5 teaches basic graph traversal algorithms such as breadth-first search and depth-first search along with their applications. Module 6 introduces dynamic programming techniques for problem-solving, focusing on problems like the longest common subsequence, knapsack, and matrix chain multiplication. Module 7 presents a greedy approach for solving problems such as single-source shortest paths and minimum spanning trees. Finally, Module 8 exposes students to complexity classes (P and NP), NP-Hard, NP-Completeness, polynomial-time reduction, and provides the statement of Cook’s theorem.

By the end of this course, each student will have the opportunity to:

• Understand and apply asymptotic notations to measure the time and space complexity of algorithms in worst-case and average-case scenarios.
• Learn and apply key algorithm design paradigms, including divide-and-conquer techniques, dynamic programming approaches, and greedy techniques, to solve complex problems effectively.
• Implement and analyze graph traversal techniques, such as breadth-first search (BFS) and depth-first search (DFS), and their applications.
• Implement and analyze graph algorithms for real-world problems, such as finding the shortest path and minimum spanning tree.
• Understand complexity classes (P, NP, NP-Hard, and NP-Complete) and polynomial-time reductions.

After completing this course, students should be able to:

• Explain asymptotic notations and their uses in analyzing the worst-case and average-case time/space complexity. | Know/Knowledge Outcome
• Demonstrate the time and space complexity of well-known algorithms for sorting, searching, graph problems, matrix multiplication, and polynomial evaluation. | Comprehend Outcome
• Design and implement efficient algorithms for solving computational problems, such as sorting, searching, and graph-related problems. | Comprehend Outcome
• Understand the principles behind the divide-and-conquer, dynamic programming, and greedy paradigms, including when and how they can be applied to solve problems. | Comprehend Outcome
• Comprehend the complexity of problems within different classes (e.g., P vs NP) and understand the implications of NP-Hard and NP-Complete problems. | Comprehend Outcome
• Apply graph algorithms to solve practical problems like network flow, shortest paths, and minimum spanning tree construction. | Apply Outcome

• Introduction to Algorithms by Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stein.
• Introduction to Algorithms: A Creative Approach by Udi Manber.

• The Design and Analysis of Computer Algorithms by Alfred Aho, Jeffrey Ullman, and John Hopcroft.
• Fundamentals of Computer Algorithms by Sahni Horowitz.