Instructor: |
Paritosh K. Pandya |
Venue & Time: |
Wednesday 09:30 to 10:55 a.m LA002 First Lecture: 27 July, 2022 |
Algorithms occur in all walks of from finding eiffcient
routes on google maps, matching students with colleges for admission,
to encrypting commercial transactions on internet. This course
investiagates design as well as analysis of algorithms. In algorithm
analysis we consider twin goals of establishing correctness and
estimating efficiency (time, memory usage). For correctness we
consider logical assertion based methods of Dijkstra and Hoare. For
performance analysis, we use asymptotic order of growth of time and
memory with input size. We also explore design strategies and
heuristics by which efficient solutions to algorithmic problems can
be found. These include, divide and conquer, greedy and dynamic
programming as well as randomization. A wide variety of algorithms
will be designed and analysed. Finally, the course will explore the
topic of inherent hardness of algorithmic problems. Complexity theory
divides the problems into complexity classes by their inherent
hardness and by inter-reducibility. The class of NP-Complete problems
will be rigorously explored.
T.H.Cormen, C.E.Leiserson, R.L.Rivest, C. Stein, Introduction to Algorithms, 3rd edition, Prentice-Hall India, 2001. (CLRS)
J. Kleinberg and E. Tardos, Algorithm Design, Pearson International Edition, 2005. (KT)
Ashish Lalwaney, Akash Kumar, Vedang Asgaonkar, Pulkit Agarwal, Ankit Misra, Dhhiraj Sah, Abhishek Singh
Piazza Discussion Forum: piazza.com/iit_bombay/fall2022/cs218m
Attendance and Tutorials: 10%
Quizzes and Assignments :
25%
Midterm Exam: 25%
Final Exam: 40%
Models of computation, algorithm analysis, time and space complexity, average and worst case analysis, lower bounds. Algorithm design techniques: divide and conquer, greedy, dynamic programming, randomization.
Problem classes P, NP, PSPACE; reducibility, NP-hard and NPcomplete problems. Approximation algorithms for some NP-hard problems.
No |
Topics |
Slides/Notes/Exercises |
References |
Additional References |
|---|---|---|---|---|
Lect 1 |
Course overview |
|
|
|
Lect 2A |
Efficiency of algorithms 1: Growth functions and order of growth. Asymptotic Complexity: Theta,O,Omega |
CLRS Sec 2.1-2 Sec 3.1 CLRS3.2 (self study) |
|
|
Lect 3-4 |
Correctness of Programs: Assertions and Annotated programs |
Lect4Annotated |
Lecture slides |
Huth and Ryan, Logics in Computer Science, Ch 1-2,4. |
Lect5 |
Discovering Sorting Methods |
CLRS 2.3
|
|
|
Lect6 |
Solving recurrences |
CLRS 4.3-5 |
|
|
Lect7 |
Divide and Conquer Algorithms: Integer multiplication, Strassen Matrix Multiplication, Maximum Subarray |
CLRS 4.1, 4.2 |
KT 5.3 (Counting inversions) CLRS 4.2 (Strassen Matrix Multiplication) |
|
Lect8-9-10 |
Greedy Algorithms |
KT Chapter 4.1, 4.2, 4.8, |
|
|
Lect11 |
Amortized Complexity |
CLRS Ch. 17 |
|
|
Lect12-13-14-15 |
Dynamic Programming |
Lect12Annotated |
CLRS Ch. 15 |
|
Lect16, Lect17, Lect18, |
P versus NP , NP-completeness, PSPACE |
Lect16Annotated |
|
(lecture video) This video is only for info not in exam. |
Lect20 |
Maxflow algorithm |
|
||
Lect21 |
Randomized algorithms |
|
|
|
Lect22 |
QUIZ |
|
|
|
Lect23 |
Guest Lecture by Prof. Rohit Gurjar |
|
Scribed notes by Dhaval Singh. |
|
Lect24 |
Bipartate Matching |
|
(lecture video) |
|
|
|
|
|
|
|
|
|
|
|