Introduction to Algorithms and Asymptotic Natations
Requirement of algorithms, Why to analyse algorithms, Problems & instances, efficiency of algorithms, time and space complexity, average & worst case analyses, Big ‘oh’ notation, other asymptotic notation, conditional asymptotic notation, asymptotic notation with several parameters, operations on asymptotic notation
Analysis of Algorithms
Types of algorithms: Iterative v/s Recursive, analysing control structures, barometer instructions, examples of their use, average-case analysis, amortized analysis, Basic sorting algorithms and analysis: Bubble sort, Insertion sort, Selection sort, Heap sort and priority queue.
Generating recurrence relations from algorithms, Intelligent guesswork, homogeneous recurrences, inhomogeneous recurrences, change of variable, range transformations, asymptotic recurrences, substitution method, iteration method, recurrence trees, master method & master theorem.
Divide and Conquer
Characteristics, the general template, applications: binary search, merge sort, quick sort, matrix multiplication, counting inversion.
General characteristics of greedy algorithms and examples, applications: Kruskal’s and Prim’s algorithms, introduction to shortest path problem variants, single source shortest path problem, knapsack problem, scheduling problem.
General characteristics and examples, principle of optimality, applications: binomial coefficients, making change, knapsack problem, Floyd’s algorithm, chained matrix multiplication, LCS problem, approach using recursion, memory functions.
Depth-first search, breadth-first search, topological ordering & sorting, backtracking, application of backtracking: knapsack problem, Queen’s problem. Branch & bound, application: the assignment problem, general considerations.
Introduction to Computiational Complexity
P and NP problems, NP Hard and NP Completeness, SAT problem, Traveling Salesman Problem.
|Algorithm Analysis & Design.pdf||193.32 KB|