Algorithm Design Paradigms
Motivation
Concept of algorithmic efficiency
Run time analysis of algorithms
Asymptotic notations
Recurrences
Substitution Method
Recursion Tree Method
Master’s Method
Structure of divide-and-conquer algorithms
Examples: Binary search, Quick sort, Merge sort, Strassen multiplication
Analysis of run time recurrence relations
Greedy Method
Overview of greedy paradigm
Examples:
Exact optimization: Minimum Cost Spanning Tree
Approximate solution: Knapsack Problem
Single source shortest paths
Traveling Salesman
Overview
Difference between dynamic programming and divide and conquer
Applications:
Shortest path in a graph
Chain matrix multiplication
Traveling Salesman Problem
Longest common sequence
Knapsack Problem
Overview
Representation of graphs
Strongly connected components
Traversal methods:
Depth-first search (DFS)
Breadth-first search (BFS)
Backtracking
Overview
8-queen problem
Knapsack Problem
Branch and Bound
LC searching and bounding
FIFO branch and bound
LC branch and bound
Applications:
0/1 Knapsack Problem
Traveling Salesman Problem
Complexity measures
Polynomial vs non-polynomial time complexity
NP-hard and NP-complete classes with examples
[⤓]
Last updated
