Teaching Group:
Instructor: Dr. Pallavi Jain
Assistant Professor
IIT Jodhpur
Teaching Assistants: Dixit Dutt Bohra (P23CS0003)
Pranjal Pandey (M23CSA018)
Teaching Group:
Instructor: Dr. Pallavi Jain
Assistant Professor
IIT Jodhpur
Teaching Assistants: Dixit Dutt Bohra (P23CS0003)
Pranjal Pandey (M23CSA018)
Course Content:
You can find the syllabus here on page 40.
Prerequisites:
Maths for Computing/Discrete Mathematics
Data Structures and Algorithms
Class Schedule:
Monday, Wednesday, Friday: 8:00 - 8:50 AM
Location: LHB 106
Attendance Requirements: as per institute policy.
Office Hours:
TA office hours:
Dixit Dutt Bohra - Mon, Wed, Thu : 2:00 -5:00 PM
Pranjal Pandey - Tue, Fri : 2:00 -5:00 PM, and Sat 4:00 -7:00 PM
If you want to discuss with instructor, then schedule an appointment through email.
Grading Policy:
The following grading policy is tentative.
Major Exam: 40%
Minor Exam: 20%
Class Participation: 5%
Surprise Tests: 10%
Programming Assignments (firm deadlines): 10%
programming language: C
one week time will be given
Group Projects: 15%
group size = 6
The project will require reading papers and implementation
no restriction on programming language
projects will be assigned by the end of August
deadline for project submission (code+report) (November 5, 2023)
project presentations (TBD)
References:
Introduction to Algorithms, by Cormen, Leiserson, Rivest, and Stein.
Algorithm Design, by Kleinberg and Tardos
Parameterized Algorithms, by Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk and Saket Saurabh
Lectures:
Lecture 1 (July 31, 2024): Introduction to the course and evaluation plan
Lecture 2 (August 5, 2024): Finding (second)maximum element in an array, Proof of correctness by Induction
Lecture 3 (August 7, 2024): Data structures: definition, applications, Search & Insert operations: Array, Linked List, Binart Search Tree
Lecture 4 (August 9, 2024): Balanced Binary Search Tree: Red Black Tree
Lecture 5 (August 12, 2024): Balanced Binary Search Tree: Red Black Tree
Lecture 6 (August 14, 2024): Rescheduled to 6th September
Lecture 7 (August 16, 2024): Insert Operation in Red Black Tree
Programming Assignment 1
Lecture 8 (August 21, 2024): Deletion: Binary Search Tree, Red Black Tree
Lecture 9 (August 23, 2024): Linear Time Algorithm for Order Statistics
Lecture 10 (August 28, 2024): Surprise Test, Doubts Discussion, Order Statistics using Red Black Tree
Lecture 11 (August 30, 2024): Interval Trees
Lecture 12 (September 2, 2024): Interval Trees, Introduction to 2-3-4 Trees
Lecture 13 (September 4, 2024): Insertion and Deletion in 2-3-4 Trees
Programming Assignment 2
Lecture 14 (September 9, 2024): Surprise Test, B-Trees, Disjoint Set Data Structures
Lecture 15 (September 11, 2024): Disjoint Set Data Structures
Programming Assignment 3
Lecture 16 (September 13, 2024): Amortized Analysis
Lecture 17 (September 18, 2024): Amortized Analysis
Lecture 18 (September 23, 2024): Binomial Heap
Programming Assignment 4
Minor Examination
Lecture 19 (September 25, 2024): Dynamic Programming
Lecture 20 (September 27, 2024): Dynamic Programming
Lecture 21 (September 30, 2024): Dynamic Programming
Programming Assignment 5
Lecture 22 (October 4, 2024): Network Flows
Lecture 23 (October 7, 2024): Network Flows
Lecture 24 (October 9, 2024): Network Flows
Programming Assignment 6
Lecture 25 (October 14, 2024): NP-hardness
Lecture 26 (October 16, 2024): NP-hardness
Lecture 27 (October 18, 2024): NP-hardness