Course instructor: Prof. Shylaja SS
Syllabus and Class Notes
| Unit | Syllabus | Vibha’s Notes |
|---|---|---|
| Unit 1 | - Algorithms - Fundamentals of Algorithmic Problem Solving - Analysis of Algorithm Efficiency - Analysis Framework - Asymptotic Notations and Basic Efficiency Classes - Mathematical Analysis of Non-Recursive and Recursive Algorithms - Algebraic structures - Rings, Fields and Groups |
DAA Unit 1.pdf |
| Unit 2 | Brute Force: - Selection Sort, Bubble Sort, Sequential Search - Brute Force String Matching - Exhaustive Search Divide-and-Conquer: - Master Theorem - Merge Sort, Quick Sort - Binary Search - Binary Tree Traversals - Multiplication of Large Integers - Strassen’s Matrix Multiplication |
DAA Unit 2.pdf |
| Unit 3 | Decrease-and-Conquer: - Insertion sort, topological sort - Algorithms for generating combinatorial objects - Decrease by a constant factor algorithms Transform-and-Conquer: - Pre-sorting, heap sort - Red-Black trees, 2-3 trees, B-trees |
DAA Unit 3.pdf |
| Unit 4 | Space and Time Tradeoffs: - Sorting by Counting - Input Enhancement in String Matching - Horspool’s and Boyer-Moore Algorithms. Greedy Technique: - Prim’s Algorithm, Kruskal’s Algorithm and union-find algorithm - Dijkstra’s Algorithm, Huffman Trees |
DAA Unit 4.pdf |
| Unit 5 | Limitations of Algorithm Power: - Lower-Bound Arguments, Decision Trees - P, NP, and NP- Complete, NP-Hard Problems Coping with the Limitations of Algorithm Power: - Backtracking, Branch-and-Bound Dynamic Programming: - Computing a Binomial Coefficient - The Knapsack Problem and Memory Functions - Warshall’s and Floyd’s Algorithms |
DAA Unit 5.pdf |