Design and Analysis Of Algorithms Lecture Notes

Design and Analysis Of Algorithms


1. Introduction

2. Mathematics for Algorithmic

• Sets


•  Functions and Relations


• Vectors and Matrices


• Linear Inequalities and Linear Equations

3. Greedy Algorithms

• Knapsack Problem
  
  
  
  • O-I Knapsack
  
  
  • Fractional Knapsack


• Activity Selection Problem


• Huffman's Codes


• Minimum Spanning Tree


• Kruskal's Algorithm


• Prim's Algorithm


• Dijkstra's Algorithm

4. Divide & Conquer Algorithms

5. Dynamic Programming

• Matrix-chain Multiplication


• Knapsack Problem DP Solution


• Activity Selection Problem DP Solution

6. Amortized Analysis

• Aggregate Method


• Accounting Method


• Potential Method


• Dynamic Table

7. Hash Table

8. Binary Search Tree

9. Graph Algorithms

• Breadth First Search (BFS)


• Depth First Search (DFS)


• Topological Sort


• Strongly Connected Components


• Euler Tour


• Generic Minimum Spanning Tree


• Kruskal's Algorithm


• Prim's Algorithm


• Single Source Shortest Path
  
  
  
  • Dijkstra's Algorithm
  
  
  • Bellman-Ford Algorithm

10.String Matching

• Naïve String Matching


• Knuth-Morris-Pratt Algorithm


• Boyer-Moore Algorithm

11. Sorting

• Bubble Sort


• Insertion Sort


• Selection Sort


• Shell Sort


• Heap Sort


• Merge Sort


• Quick Sort

12. Linear-Time Sorting

• Counting Sort


• Radix Sort


• Bucket Sort

13. Computational Geometry

14. Computational Complexity

• Information-Theoretic Argument


• Adversary Argument


• NP-Completeness And Reduction

15. Approximate Algorithms

• Vertex Cover


• The Traveling Salesman Problem

16. Linear Programming