Deign And Analysis of Algorithm Handwritten Notes
At the end of course , the student will be able to:
CO 1 Design new algorithms, prove them correct, and analyze their asymptotic and absolute runtime
and memory demands.
CO 2 Find an algorithm to solve the problem (create) and prove that the algorithm solves the problem
CO 3 Understand the mathematical criterion for deciding whether an algorithm is efficient, and know
many practically important problems that do not admit any efficient algorithms.
CO 4 Apply classical sorting, searching, optimization and graph algorithms.
CO 5 Understand basic techniques for designing algorithms, including the techniques of recursion,
divide-and-conquer, and greedy.
Unit- I Introduction: Algorithms, Analyzing Algorithms, Complexity of Algorithms, Growth of
Functions, Performance Measurements, Sorting and Order Statistics – Shell Sort, Quick Sort, Merge
Sort, Heap Sort, Comparison of Sorting Algorithms, Sorting in Linear Time.
Unit-II Advanced Data Structures: Red-Black Trees, B – Trees, Binomial Heaps, Fibonacci Heaps,
Tries, Skip List
Unit-III Divide and Conquer with Examples Such as Sorting, Matrix Multiplication, Convex Hull and
Greedy Methods with Examples Such as Optimal Reliability Allocation, Knapsack, Minimum
Spanning Trees – Prim’s and Kruskal’s Algorithms, Single Source Shortest Paths – Dijkstra’s and
Bellman Ford Algorithms.
Unit-IV Dynamic Programming with Examples Such as Knapsack. All Pair Shortest Paths – Warshal’s
and Floyd’s Algorithms, Resource Allocation Problem.
Backtracking, Branch and Bound with Examples Such as Travelling Salesman Problem, Graph
Coloring, n-Queen Problem, Hamiltonian Cycles and Sum of Subsets.
Unit-V Selected Topics: Algebraic Computation, Fast Fourier Transform, String Matching, Theory of NPCompleteness, Approximation Algorithms and Randomized Algorithms