ALGORITHM DESIGN AND ANALYSIS (4 Credits)

Learning Outcomes:

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

Topics:

1. Introduction of design and analysis of algorithms;
2. Mathematical induction and recursive function;
3. Algorithms and complexity functions;
4. Complexity of algorithms analysis;
5. Stack and queue;
6. Tree and binary tree;
7. Priority queue and heap;
8. Graph;
9. Divide and conquer;
10. Greedy methods;
11. Dynamic Programming: Fibonacci Sequence Problem;
12. Dynamic Programming: Coin Change Problem;
13. Dynamic Programming: Multistage Graph;
14. Dynamic Programming: Travelling Salesman;
15. Dynamic Programming: Knapsack Problem;
16. String Matching;
17. Huffman Code;
18. Graph Colouring;
19. Basic Search and Traversal;
20. Backtracking;
21. Branch and Bound;
22. Strongly Connected Components;
23. Review.

Course Outline – COMP6049