Muhammad Shahid Farid

Course Overview

The primary objective of this course is to promulgate thinking and to teach students how to design and analyze algorithms — how to design algorithms, make them efficient in terms of time and space, improve and optimize algorithms, choose proper data structures, attack a problem, and recognize that not all problems are solvable and that many problems can be reduced to well-researched standard problems.

Course Outline

1. Lecture 1Introduction to Course, Review of Data Structure and some Discrete Mathematics concepts Role of Algorithms in Computing
2. Lecture 2Insertion Sort and its line by line analysis and its correctness
3. Lecture 3Asymptotic Notations: Big O, Little O, Big Omega, little omega etc
4. Lecture 4Introduction to Divide and Conquer Approach ,Merge Sort and its analysis.
5. Lecture 5Recurrences and methods to solve recurrence equations:The Substitution Method,Recursion Tree Method,The Master Method
6. Lecture 6Description of Quick sort, Performance of Quick sort
7. Lecture 7Heaps, Maintaining a Heap Property, Building a Heap
8. Lecture 8Heap sort AlgorithmPriority Queues
9. Lecture 9Balanced trees (B-Tree or Red-Black Tree) and its insertion, searching algorithms
10. Lecture 10Deletion from a balanced tree
11. Lecture 11Counting Sort, Radix Sort, Bucket Sort
12. Lecture 12Minimum and maximum, Selection in expected linear time, Selection in worst-case linear time
13. Lecture 13Introduction to Dynamic Programming, Matrix Chain Multiplication
14. Lecture 14Assembly-line Scheduling
15. Lecture 15Longest common subsequence
16. Lecture 16Optimal binary search trees
17. Lecture 17Greedy Algorithm, An activity-selection problem
18. Lecture 18Elements of greedy Strategy, Knapsack Problem, Variant of Knapsack problem
19. Lecture 19Huffman Code
20. Lecture 20Some Concepts about Graph, Representation of Graph
21. Lecture 21Breadth First Search and its applications ,
22. Lecture 22Depth First Search and its applications
23. Lecture 23Topological Sort and Strongly Connected Components
24. Lecture 24Minimum Spanning Tree, Kruskal Algorithm
25. Lecture 25Prims Algorithm
26. Lecture 26Single-source Shortest Paths, Bellman Ford Algorithm
27. Lecture 27Single-source Shortest Path in DAGs, Dijkstra's Algorithm
28. Lecture 28All-Pairs Shortest Path Problem, Floyd Warshall Algorithm
29. Lecture 29Introduction to Flow Networks
30. Lecture 30The Ford-Fulkerson Method
31. Lecture 31NP Completeness, Polynomial time and solution and verification
32. Lecture 32Final discussion on P vs. NP and course conclusions

Exam / Sessional Instruments

Text Books

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. “Introduction to Algorithms”, MIT Press, Third Edition.