Algorithm Design and Analysis- I (CSC303)
10 units: Introduction and basic concepts, Amortized complexity analysis, Sorting, Heaps, Lower bound · L-T-P 3-1-0.
Detailed syllabus
Unit 1: Introduction and basic concepts (5 hours)
Algorithm, Asymptotic notations (big-Oh, big- Omega, big-Theta, small-oh) and their significance, introduction to RAM model of computation, complexity (Time Complexity, Space Complexity) analysis of algorithms, worst case and average case. Solving Recurrences – Substitution method, Recurrence tree method and Master Method.
Unit 2: Amortized complexity analysis (3 hours)
aggregate analysis, accounting method and potential method. Examples: storage allocation problem, binary counting problem.
Unit 3: Sorting (4 hours)
Comparison-based sorting: quick sort, merge sort, and their worst and average case analysis. Sorting in linear time: Radix sort, Count Sort.
Unit 4: Heaps (3 hours)
Heap, applications of heaps: priority queue and heap sort, etc.
Unit 5: Lower bound (2 hours)
Lower bound for a problem. Computing the lower bound for sorting (comparison based sorting) and computing the lower bound for computing convex hull using the lower bound for sorting problem.
Unit 6: Search trees (8 hours)
Binary search tree, Balanced binary search tree, AVL tree, Red Black tree, M-way tree, M-way search tree, B tree, B+ Tree.
Unit 7: Hashing (4 hours)
Hash functions, Collision, Collision resolution techniques: linear probing, quadratic probing, double hashing, chaining, Rehashing. Hash Function for Hierarchical Memory Model.
Unit 8: Divide and Conquer Problem (5 hours)
Multiplication of two n-bit integers, Strassen‘s Matrix Multiplication problem, Closest pair of points, linear time median finding algorithm, Convex hull and its computation.
Unit 9: Greedy Algorithm (4 hours)
Greedy algorithms and their correctness proof: Interval scheduling problem, Interval partitioning problem, Minimizing the Lateness of Intervals problem, Fractional Knapsack Problem.
Unit 10: Dynamic Programming (4 hours)
Matrix Chain Multiplication, 0-1 Knapsack Problem, Longest Common Subsequence Problem.
Source: official document