ALGORITHM DESIGN AND ANALYSIS (4 Credits)

Learning Outcomes:

On successful completion of this course, student will be able to: LO1 – Explain fundamental concept of analysis algorithms; LO2 – Apply algorithm techniques and methods; LO3 – Solve a problem using specific algorithm; LO4 – Compare several algorithm design methods.

Topics:

1. Analysis of Data Structures: Stack, Queue, Tree, and Binary Tree;
2. Approximation algorithms: Subset-sum;
3. Divide and Conquer: Recurrence;
4. Mathematical induction and recursive function;
5. Review I;
6. Graph algorithms: Strongly connected components;
7. Approximation algorithms: Vertex-cover;
8. Analysis of Data Structures: Graph (Basic Search & Traversal), Priority Queue, and Heap;
9. Divide and Conquer;
10. Greedy methods: Huffman code;
11. Analyzing Algorithms;
12. Dynamic Programming: Rod Cutting;
13. Review II;
14. Characterizing Running Times;
15. Amortized analysis;
16. NP-Completeness Problems;
17. Greedy methods;
18. Approximation algorithms: Traveling salesperson;
19. Graph algorithms: Shortest path;
20. Randomized Algorithm: Hiring Problem;
21. Dynamic Programming: Longest common subsequence;
22. Dynamic Programming: Matrix Chain Multiplication;
23. The Role of Algorithms in Programming;
24. Dynamic Programming: Optimal binary search tree;
25. NP-Completeness;
26. Greedy methods: Activity-selection problem.