COL106: Data Structures and Algorithms


Course Information

Instructors: Huzur Saran and Keerti Choudhary

Lectures: Tues, Thurs, Fri   11:00-12:00   (LH325)

Labs: Mon, Tues, Thurs, Fri   3:00-5:00 PM   (LHC504 & LHC505)

Reference Book:
Data Structures and Algorithms in Java  by M. T. Goodrich, R. Tamassia

TA Lab Duties:
Monday: Nausheen, Harish Yadav, Nitesh Dohre, Tarun Kumar Sharma
Tuesday: Raunak Jain, Tooba Khan, Abesh Jha, Pratik Prawar
Thursday: Rishi Shah, Rishi Sarraf, Chintan Sheth, Ronak Ladhar
Friday: Sarthak, Kashish Jain, Manav Bansal, Harshvardhan Baheti

Logistics

Evaluation: The tentative course evaluation policy is:

  • Lab assignments (best 5 out of 6):  25%
  • Minor I, II:  16% + 16%
  • Major:  33%
  • Quizzes (2 or more):  10%

Passing criteria: 30% in course total

Audit-pass criteria: 45% in course total

Acadmic Honesty: Cheating or allowing anyone to copy in exams/lab-assignments would lead to strict disciplinary action. Typical penalty would include Fail grade in the course.

Lectures


Lec. No. Topic
01 Introduction, Asymptotic Bounds
02 Arrays, Linked-lists
03 Stacks, Balanced Parentheses, Dynamic Arrays and their application in implementing stacks
04 Expression Evaluation using Stack, Analysis of Dynamic Arrays, Solving maze using stacks
05 Queues, Computing Shortest Route in Maze
06 Shortest Route in Maze contd., Deque data structure, Range minima problem
07 Insertion sort, Merge sort, Quick sort
08 Analysis of Quick sort, Bucket sort, Count sort, Radix sort
09 Hashing, Hash table, Hash function `Division'
10 Hash function `MAD (Multiply-Add-Divide)', String hashing, Polynomial hash codes
11 Skip Lists
12 Skip Lists (contd.)
13 Quiz
14 Trees; Preorder, Inorder, Postorder traversals
15 Binary Search Trees; Insert, Delete, Search in BST; Order Statistics in BST
16 AVL Trees: Rotations, Insertions
17 AVL Trees (contd.): Deletions
18 Multi-way trees, 2-3-4 Trees
19 B-Trees
20 Heaps + Quiz
21 Heaps (contd.)
22 Kd Trees
23 Graphs
24 Breadth First Search (BFS) Tree
25 Applications of BFS Tree
26 2-3-4-Trees Revisited (Assignment 4 discussion)
27 Applications of BFS Tree (contd.) + Quiz
28 Problem-sheet-3 discussion
29 Discussion of Minor Exam; Order Statistics in AVL trees
30 Characterisation of DFS tree in undirected graphs; Computing Bridge edges
31 DFS traversal algorithm in undirected and directed graphs
32 Computing Topological ordering in DAGs
33 Computing Cut vertices; Problem-sheet-4 discussion + Quiz
34 Minimum Spanning Tree Problem
35 Union Find Data Structure
36 Dijkstra's algorithm
37 Dijkstra's algorithm (contd.)
38 Bellman-Ford algorithm
39 Floyd Warshall algorithm
40 Quiz

Course Content

Here is a tentative list of topics that will be covered in the course:
  • Arrays, Stacks, Queues, Linked-lists
  • Dynamic Arrays, Aysmptotic Complexity
  • Sorting: merge, quick, radix, heap
  • Dictionaries: Skip-lists, Hashing
  • Trees, Tree Traversal, Binary Search Tree
  • Priority Queues, Binary Heaps
  • AVL tree / Red-Black tree
  • 2-4 trees, B-trees, Multiway search tree, Kd-trees, and applications
  • Introduction to Graphs, Adjacency matrix and List representation
  • Breadth first search and applications
  • Depth first search in directed and undirected graphs and applications
  • Dijkstra's algorithm for shortest path, Minimum Spanning Tree

Setting-up Java

Java set up: It is advised that you install JDK 11.0.17. You must ensure that your submission code runs in JDK 11.0.17 environment.

Note: You are expected to learn Java (and use object oriented programming) on your own. For this you should refer to the Java module below and the exercises in it (thanks to Prof. Amitabha Bagchi for making these available).

Java Module
Supporting Code