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 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
in the top left corner of browser. Then select Add-ons in the menu. Then click Extensions. Then search adblock in the webpages that loads next. Click Install to the right of Adblock Plus in the results. Wait for a while, until the extension is downloaded. When download is complete, adblocker will get installed soon. Thus ad blocker is now installed on your firefox browser. If you still see any ads displayed, right click on it and select AdBlock plus-> Block this ad. For details watch the following video.
in the top left corner of browser. Then select Get extensions in menu. Then click Extensions. Then search adblock in the webpages that loads next. Click AdBlock plus in the results. Then click Add to Opera button on the page that loads. Wait for a while until the extension is installed. Thus ad blocker is now installed on your Opera browser. If you still see any ads displayed, right click on it and select AdBlock plus-> Block this ad. For details watch the following video.
in the top right corner of browser. Then select settings. Then click Extensions. Now, click Get more extensions. Then search adblock in the webpages that loads. Click Extensions on the left. Then click Add to chrome button on the right side of AdBlock. Wait for a while until a small file is downloaded. The chrome browser will open the file itself and install ad blocker. Thus ad blocker is installed in your google chrome browser. If you still see any ads displayed, right click on it and select AdBlock -> Block this ad.
