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](DAA%20Unit%201.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 |
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 |