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 :

The Role of Algorithms in Programming; Mathematical induction and recursive function; Analyzing Algorithms; Characterizing Running Times; Analysis of Data Structures: Stack, Queue, Tree, and Binary Tree; Analysis of Data Structures: Graph (Basic Search & Traversal), Priority Queue, and Heap; Divide and Conquer; Divide and Conquer: Recurrence; Randomized Algorithm: Hiring Problem; Greedy methods; Greedy methods: Activity-selection problem; Greedy methods: Huffman code; Amortized analysis; Review I; Dynamic Programming: Rod Cutting; Dynamic Programming: Matrix Chain Multiplication; Dynamic Programming: Longest common subsequence; Dynamic Programming: Optimal binary search tree; Graph algorithms: Strongly connected components; Graph algorithms: Shortest path; NP-Completeness; NP-Completeness Problems; Approximation algorithms: Vertex-cover; Approximation algorithms: Traveling salesperson; Approximation algorithms: Subset-sum; Review II