K.K.Biswas
CT42 Design
and Analysis of Algorithms
------------------------------------------
1. Analyzing algorithms 4
hours
1.1. Order of growth
1.2. Worst case analysis
1.3. Big Oh, Big Theta, Big Omega
1.4. Recurrence relations
1.5. Back tracking – 8
2. Graphs 4
hours
2.1. Representation of graphs
2.2. Paths and cycles
2.3. Breadth first search
2.4. Depth first search
2.5. Topological sort
2.6. Strongly connected components
3. Sorting 6
3.1. Quicksort
3.1.1. Description
3.1.2. Analysis of quicksort
3.2. Counting sort
3.3. Radix sort
3.4. Bucket sort
3.5. Heap sort
3.5.1. Maintaining heap property
3.5.2. Building a heap
3.5.3. Heapsort algorithm
3.5.4. Priority queues
4. Data Structures 8
4.1. Hash Tables
4.1.1. Hash Functions
4.1.2. Open addressing –
probing schemes
4.2. Binary Search Trees
4.2.1. AVL balanced trees
4.2.2. Insertion and deletion in AVL trees
4.2.3. Red Black trees – insertions
4.3. Other Tree structures
4.3.1 B Trees
4.3.2 B+ Trees
4.4. Disjoint sets
4.4.1. Operations on disjoint sets
4.4.2. Applications to connected components
4.4.3. Linked list representations
4.4.4. Time analysis
5. Divide and Conquer Algorithms 3
5.1. Merge sort
5.2. Analyzing divide and conquer algorithms
5.3. Finding closest pair of points
6. Greedy Algorithms 4
6.1. Kruskal’s algorithm
6.2. Prim’s algorithm
6.3. Dijkstra’s algorithm
6.4. Huffman codes
6.5. Knapsack problem
7. Dynamic Programming 6
7.1. Computing Fibonacci Numbers
7.2. Matrix chain multiplication
7.3. Longest common subsequence problem
7.4. Floyd –Warshall
algorithm
7.5. Flow Networks – max flow min cut
8. String Matching 3
8.1. simple text search
8.2. Rabin Karp algorithm
8.3. Knuth Morris Pratt algorithm
9. NP
completeness 1
9.1. Polynomial time
9.2. NP completeness proofs
9.3. NP complete problems
Books
Recommended :