Design and Analysis of Algorithms

This course covers the design and analysis of fundamental algorithms used in practice across three areas. The first is complexity measurement: analyzing the time and space complexity of algorithms under worst-case and average-case scenarios using asymptotic notations including big-oh, big-omega, and theta. The second is algorithm design paradigms, covering divide-and-conquer, dynamic programming, and greedy approaches. The third is the design of efficient polynomial-time algorithms for fundamental problems in computer science. The course also introduces complexity theory, examining a class of decisional problems, referred to as hard problems, for which deterministic polynomial-time algorithms are believed to be intractable.

This course introduces the design and analysis of fundamental algorithms used in computer science. Students learn to measure algorithm efficiency using asymptotic analysis, explore major algorithm design paradigms including divide-and-conquer, dynamic programming, and greedy methods, and design efficient algorithms for a range of computational problems. The course also introduces complexity theory and examines computationally hard problems through the concepts of P, NP, NP-Hard, and NP-Complete problems.

By the end of this course, students will be able 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, dynamic programming, and greedy techniques.
• Implement and analyse graph traversal algorithms, including Breadth-First Search (BFS) and Depth-First Search (DFS), and their applications.
• Implement and analyse graph algorithms for practical problems such as shortest paths and minimum spanning trees.
• Understand complexity classes (P, NP, NP-Hard, and NP-Complete) and polynomial-time reductions.

Upon successful completion of this course, students will be able to:

• Explain asymptotic notations and analyse worst-case and average-case time and space complexity. | 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 computational problems involving sorting, searching, and graph algorithms. | Comprehend Outcome
• Understand when and how divide-and-conquer, dynamic programming, and greedy paradigms should be applied. | Comprehend Outcome
• Explain complexity classes such as P, NP, NP-Hard, and NP-Complete, and their implications. | Comprehend Outcome
• Apply graph algorithms to solve practical problems such as network flow, shortest paths, and minimum spanning tree construction. | Apply Outcome

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

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