ALGORITHM DESIGN AND ANALYSIS (4 Credits)

Learning Outcomes:

1. Explain fundamental concept of analysis algorithms.
2. Apply algorithm techniques and methods.
3. Solve a problem using specific algorithm.
4. 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