This course is designed to introduce the students to design and analyse algorithms in terms of efficiency and correctness. The course focuses on highlighting difference between various problem solving techniques for efficient algorithm design.
At the end of the course, students should be able to:
Algorithm Design Techniques: Iterative technique: Applications to Sorting and Searching (review), their correctness and analysis. Divide and Conquer: Application to Sorting and Searching (review of binary search), merge sort, quick sort, their correctness and analysis.
Dynamic Programming: Application to various problems (for reference; Weighted Interval Scheduling, Sequence Alignment, Knapsack), their correctness and analysis. Greedy Algorithms: Application to various problems, their correctness and analysis.
More on Sorting and Searching: Heapsort, Lower Bounds using decision trees, sorting in Linear Time – Bucket Sort, Radix Sort and Count Sort, Medians & Order Statistics, complexity analysis and their correctness.
Advanced Analysis Technique: Amortized analysis.
Graphs: Graph Algorithms – Breadth First Search, Depth First Search and its Applications.