CSL201: Data Structures

Tentative Lecture outline with topics

Topics	No. of lectures
Introduction to object oriented programming through stacks, queues and linked lists	4
Dictionaries: skip-lists, hashing, analysis of collision resolution techniques	5
Trees, traversals, binary search trees, optimal and average BST’s	6
2-4 trees and red-black trees	4
Tries and pattern matching. Priority queues and binary heaps	5
Sorting: merge, quick, radix, selection, heap	3
Introduction to Graphs, Breadth first search and connected components.	3
Depth first search in directed and undirected graphs and strongly connected components	3
Spanning trees: Prim's and Kruskal's algorithm, union-find datastructure.	4
Dijkstra's algorithm for shortest path. shortest path tree. Shortest and longest paths in directed acyclic graphs	5

Suggested texts and reference materials

Data Structures and Algorithm in Java: Goodrich and Tamassia: John Wiley and Sons. (Text)
Introduction to Algorithms: Cormen, Leiserson, Rivest and Stein: Prentice Hall of India
Data Structures and Algorithms: Aho, Hopcroft and Ullmann: Addison Wesley.
Here is a Java book you can use

Problem Set

PS1

Assignments

Assignments are to be done individually. Any help taken from outside sources (websites, books) should be clearly mentioned. Assignment 1

Lecture Slides:

Please use Internet explorer to view these slides. Slides can be viewed only within IITD.
[1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [16], [19], [20], [21], [22], [23]
Here are the PDF versions of these slides [1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11], [12],[16],[19],[22],[23],[24],[25]
PPT slides with animation [13],[14], [15],[20],[21], pattern matching ([17],[18]), graphs, skiplists, shortest paths

Evaluation

Assignments (6, each of 5 marks), Minor 1 (15), Minor 2(15), Major (35), Class participation (5)

Attendance Policy

Attendance is compulsory in the lectures. Assignments can be done during the lab hours or at any other time.