Autumn 2021
Prof. Abhiram Ranade
Author: Miloni Atal
Pre-requisite courses: CS213 Data Structures and Algorithms is a hard pre-requisite
Pre-requisite skills: Basic Programming in C++ and Python
Course Content:
- 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, amortization, randomization.
- Problem classes P, NP, PSPACE; reducibility, NP-hard and NP-complete problems
- Approximation algorithms for some NP-hard problems.
Evaluation Structure:
- Homeworks (Problem sets, programming assignments.) : 25 marks
- Proctored exams: 3 quizes (15 marks each) + 30 marks endsem : 75 marks.
Information about Projects/Assignments: We were given 1 assignment per week based on that week’s pre-recorded lectures, with generally 3-4 questions. These were mostly theoretically questions, but we did have a few where we needed to submit some code. The questions were largely based on what was covered in the lectures, but required some additional thinking (moderate difficulty).
An assignment every week becomes hectic, but it proved to be really good for understanding and keeping up with course (ensuring you don’t loose track and don’t pile up pending lectures)
Quizzes/Midsem/Endsem papers Difficulty: 4/5
Difficulty level of Projects/Assignments: 3/5
Attendance Policy: None (Pre-recorded lectures and Doubt sessions, hence no attendance compulsion )
General funda: Make sure you understand the concepts well during the week and while doing the assignments, as the quizzes and endsems would otherwise be very difficult to tackle. Since, during exams you would have limited time and the questions are derived from what you learn in the lectures, but are not very straightforward. So, make sure you get very comfortable with the concepts.
Feedback on Lectures: We were given pre-recorded lectures every week. Most lectures very easy to understand, though some concepts were a bit tough towards the end.
Should you do this course?: Anybody who is interested in furthering their data-structures and algorithms concepts and learning more about how we can analyse and improve algorithms.
References: Algorithms - S. Dasgupta,C. H.Papadimitriou,andU. V. Vazirani (This is the main book followed for lectures and assignments) —