COL106: Data Structures and Algorithms



General Information

Semester: Sem II, 2021-22.

Instructors: Amit Kumar (email: amitk AT cse.iitd.ac.in) and Parag Singla (email: parags AT cse.iitd.ac.in)

Class Timings (Slot F):
  • Tue, 11:00 am - 12:00 noon
  • Thu, 11:00 am - 12:00 noon
  • Fri, 11:00 am - 12:00 noon
  • Sat, if required (time to be announced)
Venue: Online (MS Teams)
Section A: Click Here
Section B: Click Here

Sign up for Piazza
Code: As announced in class/over email

Announcements
  • [Mar 24, 2022]: Assignment 4 is out. Due Date: Friday Apr 15th, 11:59 pm.
  • [Mar 8, 2022]: Assignment 3 is out. Due Date: Tuesday Mar 22nd, 11:59 pm.
  • [Feb 6, 2022]: Assignment 2 is out. Due Date: Sunday Feb 27th, 11:59 pm.
  • [Jan 23, 2022]: Assignment 1 is out. Due Date: Sunday Feb 6th, 11:59 pm.

    Course Objectives

    1. To learn the fundamentals of basic data strcutures
    2. To argue formally about correctness and efficiency of various data structures
    3. To learn various algorithms supporing operations on data structures
    4. Get hands on experience working with basic data structures in a Programming Language (JAVA)

    Course Content (Week-wise)
    Week Topic Slides Book Chapters
    1.1 Introduction Introduction
    1.2,1.3,2.1 Aysmptotic Complexity Asymptotic Analysis
    2.2,2.3 Linked Lists Linked Lists
    3.1,3.2 ADT, Stacks ADT, Stacks
    3.3,4.1 Queues Queues
    4.2,4.3 Trees (Introduction) Trees
    5.1,5.2,5.3 Binary Search Trees (BSTs) Binary Search Trees
    6.1,6.2,6.3 AVL Trees AVL Trees
    7.1,7.2,7.3,8.1 2-4 Trees, B-Trees 2-4 Trees, B-Trees
    8.2 Tries Tries
    8.3,9.1 Heaps Heaps
    9.2,9.3,10.1 Hashing Hashing
    10.2,10.3,11.1 Sorting Sorting
    11.2,11.3,12.1,12.2,12.3 Graphs Graphs [updated April 7, 2022]

    Additional Resources

    Review Material

    References

    1. Data Structures and Algorithms in Java, 6th Edition. Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser. 2014. Publisher: John Wiley and Sons, Inc.
      International Student Version of the book (available at a cheaper price).

    Assignment Submission Instructions
    1. You are free to discuss the assignment problems with other students in the class. But all your code should be produced independently without looking at/referring to anyone else's code or discussion notes. JAVA is the default programming languages for the course. You should use it for programming your assignments.
    2. Code should be submitted using Moodle Page. Make sure to include comments for readability. Specific submission instructions will be released for each assignment on Piazza.
    3. Honor Code: Any cases of copying will be awarded a zero on the assignment and a penalty of -10. More severe penalties may follow.
    4. Late Policy: You will get a penalty of 10% deduction in marks (per day) for every late day in submission upto a maximum of 3 days, after which you will get a zero on the assignment.

    Practice Questions

    Assignments
    1. Assignment 4. Vocabulary File
      Due Date: Friday April 15th, 2022, 11:59 pm
    2. Assignment 3
      Due Date: Tuesday Mar 22nd, 2022, 11:59 pm
    3. Assignment 2
      Due Date: Sunday Feb 27th, 2022, 11:59 pm
    4. Assignment 1
      Due Date: Sunday Feb 6th, 2022, 11:59 pm

    Grading Policy (Tentative)

    Assignment 0/Attedance in lab 2%
    Assignments [1 - 4] 25% (about equal weightage for each)
    Quizzes (4) 8%
    Minor 25%
    Major 40%