Lecture notes as doc files and ppt slides for design and analysis of algorithms for free download.
Module I
Introduction and Complexity
What is an algorithm – Properties of an Algorithm, Development of an algorithm, Pseudo-code Conventions, Recursive Algorithms – Performance Analysis - Space and Time Complexity –Asymptotic Notations – ‘Oh’, ‘Omega’, ‘Theta’, Worst, Best and Average Case Complexity, Running Time Comparison, Common Complexity Functions -Recurrence Relations – Solving Recurrences using Iteration and Recurrence Trees – Example Problems – Profiling - Amortized Complexity.
Module II
Divide and Conquer - Control Abstraction, Finding Maximum and Minimum, Costs associated element comparisons and index comparisons, Binary Search, Divide and Conquer Matrix Multiplication, Stressen’s Matrix Multiplication, Quick Sort, Merge Sort. – Refinements.
Module III
Greedy Strategy - Control Abstraction, General Knapsack Problem, Minimum Cost Spanning Trees – PRIM’s Algorithm, Kruskal’s Algorithm, Job sequencing with deadlines.
Dynamic Programming - Principle of Optimality, Multistage Graph Problem, Forward Approach, Backward Approach, All-Pairs Shortest Paths, Traveling Salesman Problem.
Module 3 Greedy algorithms - PPT slides
Module 3 - Dynamic programming final ppt slide
Knapsack problem doc
Module 3 - Dynamic programming final ppt slide
Knapsack problem doc
Module IV
Backtracking – State Space Tree - Fixed Tuple and Variable Tuple Formulation - Control Abstraction – Generating Function and Bounding Function - Efficiency of the method - Monte Carlo Method – N-Queens Problem, Sum of Subsets.
Branch and Bound Techniques – FIFO, LIFO, and LC Control Abstractions, 15-puzzle.
Module V
Sophisticated Algorithms - Approximation Algorithms – Planar Graph Coloring, Vertex cover - String Matching Algorithms – Rabin Karp algorithm - Topological Sort - Deterministic and Non-Deterministic Algorithms.
Lower Bound Theory - Comparison Trees for Searching and Sorting, lower bound on comparison based algorithms, Sorting, Selection & Merging; Oracles and Adversary Arguments –Merging,Basic concepts of randomized algorithm-Las Vagas algorithm for search.
Module 5 - Lowerbound slides ppt
Module 5 - Lowerbound slides ppt
