Algorithm Design and Analysis

Course Code: COMP6049001 Course Name: Algorithm Design and Analysis

---

Course Description

This course trains students to reason rigorously about computation: analyzing algorithm efficiency through asymptotic notation, proving correctness through formal methods, and decomposing unfamiliar problems by identifying structural properties and matching them to appropriate solution paradigms including Divide and Conquer, Greedy methods, Dynamic Programming, and Backtracking. The course culminates in complexity theory, where students distinguish tractable from intractable problems, verify NP membership, and establish NP-hardness through reduction from known NP-complete instances.

---

Learning Outcomes

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

Code	Cognitive Level	Outcome
LO1	(C6) Evaluation	Evaluate the time and space complexity of algorithms using asymptotic notation and formal analysis methods, and prove algorithm correctness using loop invariants, induction, or exchange arguments
LO2	(C4) Analysis	Analyze unfamiliar computational problems by identifying their structural properties, classifying them into known algorithmic categories (graph, string, combinatorial), and recommending a solution strategy with justification
LO3	(C5) Synthesis	Design solutions to unfamiliar computational problems by selecting and applying appropriate strategies, including Divide and Conquer, Greedy, Dynamic Programming, and Backtracking
LO4	(C6) Evaluation	Assess the computational complexity of problems by distinguishing tractable from intractable cases, verify NP membership through polynomial-time verification, and recognize NP-hardness by mapping problem structure to known NP-complete instances

---

Evaluation

Component	Type	Weight
Theory: Assignment	Theory	20%
Theory: Mid Exam	Theory	30%
Theory: Final Exam	Theory	30%
Theory: Case Study (AOL)	Theory	20%
Total		100%

---

Textbooks

1. Cormen, T. H., Leiserson, C. H., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms. Massachusetts Institute of Technology.
2. Skiena, S. S. (2020). The Algorithm Design Manual. New York: Springer.

---

Course Content

1. Role of Algorithms & Practical Problem Solving
2. Algorithm Correctness
3. Analyzing Algorithms
4. Characterizing Running Times
5. Data Structures Analysis I
6. Data Structures Analysis II
7. Amortized Analysis
8. Divide and Conquer
9. Analyzing Divide and Conquer Recurrences
10. Randomized Algorithms & Hash Tables
11. Greedy Algorithm I
12. Greedy Algorithm II
13. String Matching
14. Review I
15. Dynamic Programming I
16. Dynamic Programming II
17. Dynamic Programming III
18. Dynamic Programming IV
19. Graph Algorithms I
20. Graph Algorithms II
21. Backtracking
22. NP-Completeness
23. NP-Complete Problems
24. Approximation Algorithms I
25. Approximation Algorithms II
26. Review II

---

Summary

Attribute	Detail
Course Code	COMP6049001
Course Name	Algorithm Design and Analysis
Core Focus	Rigorous algorithm analysis, correctness proofs & NP-completeness
References	Introduction to Algorithms (CLRS, 2022); The Algorithm Design Manual (Skiena, 2020)
Assessment Components	4 (Assignment, Mid Exam, Final Exam, Case Study AOL)
Total Topics	26