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

Elementary Algorithms | Problems & instances, efficiency of algorithms, average & worst case analyses, elementary operation, reasons for analyzing efficiency |

Asymptotic Notation | Big „oh‟ notation, other asymptotic notation, conditional asymptotic notation, asymptotic notation with several parameters, operations on asymptotic notation |

Models of Computation | Random Access Machines, computational complexity of RAM programs, a stored program model, abstractions of RAM - straight-line programs, Turing Machines, relationship between Turing Machines and RAM. |

Analysis of Algorithms | Analyzing control structures, barometer instructions, examples of their use, average-case analysis, amortized analysis |

Solving Recurrences | 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 |

Greedy Algorithms | General characteristics of greedy algorithms and examples, applications: Kruskal‟s and Prim‟s algorithms, shortest path problem, knapsack problem, scheduling problem |

Dynamic Programming | General characteristics and examples, principle of optimality, applications: binomial coefficients, making change, knapsack problem, Floyd‟s algorithm, chained matrix multiplication. Approach using recursion, memory functions |

Graph Algorithms | Depth-first search, breadth-first search, topological ordering & sorting, backtracking, application of backtracking: knapsack problem. Branch & bound, application: the assignment problem, general considerations |

Computational Complexity | Introduction, information-theoretic arguments: complexity and sorting, complexity and algorithmic, introduction to NP completeness, the classes P and NP, polynomial reductions, NP complete problems |

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

5th Algorithm Analysis & Design.pdf | 110.31 KB |