Unit No | Topics |
---|---|

1 | Introduction to Algorithms and Asymptotic NatationsRequirement 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 |

2 |
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. |

3 | Solving RecurrencesGenerating 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. |

4 | Divide and ConquerCharacteristics, the general template, applications: binary search, merge sort, quick sort, matrix multiplication, counting inversion. |

5 | Greedy AlgotithmsGeneral 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. |

6 | Dynamic ProgrammingGeneral 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. |

7 | Graph AlgorithamsDepth-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. |

8 | Introduction to Computiational ComplexityP and NP problems, NP Hard and NP Completeness, SAT problem, Traveling Salesman Problem. |

Attachment | Size |
---|---|

Algorithm Analysis & Design.pdf | 193.32 KB |