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