**Instructors** : Ashutosh Gupta

**Timings** : 8:30 Monday, 9:30 Tuesday, 10:35 Thursday (Slot 1)

**Venue** : LH 101 (discussions on Piazza Join (Access code was given in class))

**TAs** : TBA

For non gmail email addresses Append "iitb.ac.in" in the text inside the parenthesis

- Text book: Introduction to Algorithms, third edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
- Course syllabus: Slides define the syllabus. The content only before the problem section in slides is in the syllabus. In terms of problems, you must solve tutorial problems. All the other problems are optional. Any new concept defined there is not part of the course. If the concept appears in the exam, we will redefine it in the question paper.
- We do not provide solutions of the problems that are not in the tutorials. We can discuss your approach with you. Some TAs may give you answer to some of the problems. It is their choice. However, they are not obligated to provide written detailed answer.

- TAs will do a tutorial on a given set of problems at their chosen slot. Please discuss with your TA.

- Attendance quiz: 5% (half marks for attempt and half marks for 3+ options correct)
- Quizzes : 25% (2 quizzes)
- Midterm : 30% (2 hours)
- Final : 40% (3 hours)

- Attendance quiz: 5%
- Lab exams : 60% (3 exams)
- Project : 35% (take home)

May change later.

- Lab exam 1: 2023-08-25 (week 4)
- Lab exam 2: 2023-10-06 (Week 9)[moved from week 8 to 9]
- Project description declared: 2023-10-13 (Week 10)
- Lab exam 3: 2023-10-28 (Week 12)
- Porject submission deadline: 2023-11-10 (Week 14)

- TBA

- Monday lecture is moved to saturday
- Introduction, Binary search, Big-O, and containers
- Lecture 1, Lecture 2,
- Tutorial problems: 1.11, 1.12, 1.13, 2.5, and 2.6

- Stack:implementation, growth, applications
- Queue: Array implementation, Linked list implementation
- Circular linked list, Doubly linked lists
- Lecture 3, Lecture 4
- Tutorial problems: 3.3, 3.4, 3.5, 4.10, 4.11, and 4.12

- Dictonary and Hashing
- Tuesday Holiday
- Lecture 5
- Tutorial problems: 5.9, 5.10, 5.11, and 5.12

- Trees and tree walks, binary search tree(BST)
- Search, Minimum, successor on BST
- Lecture 6, and Lecture 7
- Tutorial problems: 6.11, 6.12, 6.13, 7.4, 7.5, and 7.6

- Syllabus: everything that is covered in lectures before the quiz.
- Venue: SIC201, CC101, CC103 and CC105
- You may bring an A4 sized cheat-sheet.
- Write only on single side. We will collect the sheet at the end.
- Bring your student id.

- Insert and delete in binary search tree
- Average insertion time in binary search tree
- Insert and delete in red-black tree
- Lecture 8, Lecture 9
- Tutorial problems: 8.10, 8.11, 8.12, and 9.9

- Pattern matching, KMP algorithm, Trie, and suffix trees
- Lecture 10, Lecture 11
- Tutorial problems: 10.4, 10.5, 10.6, 11.7, and 11.8

- Priority queue, heap, and operations on heap
- Lecture 12
- Slides have a section tutorial problems.

- Syllabus: everything that is covered in lectures before the midsem.
- You may have an A4 sheet of paper with any text.
- Write only on single side. We will collect the sheet at the end.
- Bring your student id.