Advanced data structures and algorithms

Teaching Group:

Instructor: Dr. Pallavi Jain

 Assistant Professor

 IIT Jodhpur

Teaching Assistants: Dixit Dutt

                                    Jash Patel

Course Content: 

You can find the syllabus here on page 40.

Prerequisites: 

• Maths for Computing/Discrete Mathematics

• Data Structures and Algorithms 

Class Schedule:

      Tuesday, Thursday, Friday : 4:00 - 4:50 PM

       Location: LHB 106

Attendance Requirements: as per institute policy. 

Office Hours: 

TA office hours: TBD

If you want to discuss with instructor, then schedule an appointment through email. 

Grading Policy: 

The following grading policy is tentative.

• Major Exam : 35%

• Minor Exams: 30%

• Class Participation: 5%

• Programming Assignments (firm deadlines): 10%

  • • programming language: C

    • one week time will be given

• Group Projects: 20%

  • • group size = 6

    • The project will require reading paper 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 (August 1, 2023): Introduction to the course and evaluation plan

Lecture 2 (August 3, 2023): Data structures: definition, applications, finding (second)maximum element in an array, search operation

Lecture 3 (August 4, 2023): Search & Insert operations: Array, Linked List, Binart Search Tree, Red Black Tree

Lecture 4 (August 8, 2023): Insert Operation in Red Black Tree

Lecture 5 (August 10, 2023): Deletion: Binary Search Tree, Red Black Tree

Lecture 6 (August 11, 2023): Delection in Red Black Tree (continued)

Lecture 7 (August 17, 2023): Surprise Test 1, Dynamic Order Statistics

Lecture 8 (August 18, 2023): Rank of an element, Interval Trees

Lecture 9 (August 22, 2023): Interval Trees (continued), Correctness of search operation in Interval Trees?

Lecture 10 (August 24, 2023): Amortized Analysis 

Lecture 11 (August 25, 2023): B-Trees: definition, properties, search, insertion

Lecture 12 (August 29, 2023): B-Trees: deletion

Lecture 13 (August 31, 2023): Data structures for disjoint sets

Lecture 14 (September 1, 2023): Data structures for disjoint sets (continued)

Lecture 15 (September 4, 2023): Reductions, Vertex Coloring

Lecture 16 (September 12, 2023): Vertex Coloring (continued)

Lecture 17 (September 14, 2023): Vertex Coloring (continued)

Lecture 18 (September 15, 2023): Lower Bounds for Vertex Coloring

Lecture 19 (September 19, 2023): Lower Bounds for Maximum Independent Set 

Lecture 20 (September 21, 2023): Algorithms for Maximum Independent Set

Lecture 21 (September 22, 2023): Algorithms for Maximum Independent Set, Algorithm for Knapsack

Lecture 22 (September 26, 2023): Algorithm for Text Segmentation

Lecture 23 (September 29, 2023): Network Flows

Lecture 24 (October 3, 2023): Network Flows

Lecture 25 (October 5, 2023): Network Flows

Lecture 26 (October 6, 2023): Network Flows

Lecture 27 (October 10, 2023): Network Flows

Lecture 28 (October 12, 2023): Network Flows

Lecture 29 (October 13, 2023): Applications of Network Flows

Lecture 30 (October 19, 2023): Applications of Network Flows

Lecture 31 (October 20, 2023): Approximation Algorithms: Load Balancing Problem

Lecture 32 (October 27, 2023): Approximation Algorithms: Load Balancing Problem (continued)

Lecture 33 (October 31, 2023): Approximation Algorithms: Center Selection Problem

Lecture 34 (November 2, 2023): Approximation Algorithms: Lower Bound for approximation factor of Center Selection Problem

Lecture 35 (November 3, 2023): Approximation Algorithms: Vertex Cover Problem

Lecture 36 (November 7, 2023): Approximation Algorithms: Set Cover Problem

Lecture 37 (November 9, 2023): Approximation Algorithms: Knapsack

Lecture 38 (November 10, 2023):  Approximation Algorithms: Steiner Tree

Lecture 39 (November 14, 2023): Randomized Algorithm

Lecture 40 (November 15, 2023): Randomized Algorithm