Chandan Karfa
CS201: Data Structure
Announcements:
20th September 2017: There will be no class in the week of 2nd October  6 October. The first class after Midsem will on 11th October.
15th September 2017: Mid Semetster examination will be conducted in open book mode.
26th July 2017: Class starts on 27th July 2017 10AM in 1201 (Core 1)
26th July 2017: For any email regarding CS201 to me, Subject of the email MUST starts with CS201, i.e. the
subject pattern would be like “CS201: <your issue>”.
Class Timing and Venue:
Syllabus:
Performance of algorithms: space and time complexity, asymptotics;
Fundamental Data structures: linked lists, arrays, matrices, stacks, queues, binary trees, tree traversals;
Algorithms for sorting and searching: linear search, binary search, insertionsort, selection sort, bubblesort, quicksort, mergesort, heapsort, shellsort;
Priority Queues: lists, heaps, binomial heaps, Fibonacci heaps;
Graphs: representations, depth first search, breadth first search;
Hashing: separate chaining, linear probing, quadratic probing;
Search Trees: binary search trees, redblack trees, AVL trees, splay trees, Btrees;
Strings: suffix arrays, tries;
Randomized datastructures: skip lists.
Text Book:
[CLRS] T. H. Cormen, C. E. Leiserson, R L Rivest and C Stein, Introduction to Algorithms, MIT Press, 2001
[TLA] A. M. Tannenbaum, Y Langsam and M J Augenstein, Data Structures Using C, Prentice Hall India, 1996.
References:
[HSM]] E. Horowitz, S Sahani, D Mehta, Fundamentals of Data Structures in C. University Press 2008.
S. Lipschutz, Data Structures with C, McGrawHill, 2011.
R. Sedgewick, Algorithms in C Parts 14, 3rd Ed., Pearson Education, 1998.
R. Sedgewick, Algorithms in C Part 5, 3rd Edn., Pearson Education, 2002.
M. A. Weiss, Data Structures and Problem Solving Using Java, AddisonWesley, 1997.
TAs:
Grade Calculation
Surprize Quizzes  20% 
MidSem  30% 
End Sem  50%

Classes
Sl No  Date  Topic  Resources 
1  28th July 2017  Introduction  
2  29th July 2017  Time complexity  CLRS: Ch 3 
3  2nd August 2017  Time and space complexity, Array  TLA: Ch 1.2 
4  3rd August 2017  Linked list, circular list  TLA: Ch 4, HSM: Ch 4 
5  4th August 2017  Stack  TLA: Ch 2 
6  9th August 2017  Queue, Tree Introcution  TLA: Ch 4 
7  10th August 2017  Tree traversal, Tree applications  TLA: Ch 5 
8  11th August 2017  Selection Tree  HSM Ch 5.8 
9  16h August 2017  Application of Winner tree, Implementation of Huffman Encoding  HSM Ch 5.8, TLA: Ch 5.3 
10  16th August 2017 (extra class)  Threaded binary Tree, Traversal using threaded binary tree  TLA: Ch 5.2 
11  18h August 2017  Sparse Matrix using array, basic operations on sparse matrix  HSM: Ch 2.5 
12  23rd August 2017  Sparse Matrix using Linked list, Class Test 1  HSM: Ch 4.7 
13  24th August 2017  Sorting overview, Bubbleble sort, Selection sort  TLA: Ch 6.2, 6.3 
14  25th August 2017  Binary Tree based sorting, Insertion Sort, Shell Sort  TLA: Ch 6.4 
15  30th August 2017  Quick Sort, Merge sort  CLRS: Ch 7, TLA: Ch 6.5 
16  31st August 2017  Heap and Building Heaps  CLRS: Ch 6 
17  31st August 2017 (extra class)  Heap Sort, Master Theorem  CLRS: Ch 8, CLSR: Ch 4.3 
18  6th September 2017  Radix sort, Counting sort  CLRS: Ch 8 
19  7th September 2017  Priority Queue: Heap  CLRS: Ch 6 
20  8th September 2017  Binomial Tree and Binomial Heap  CLRS: Ch 19 
21  13th September 2017  Binomial Heap  CLRS: Ch 19 
22  14th September 2017  Binomial Heap, Fibonacci Heap Intro  CLRS: Ch 19 
23  14th September 2017 (extra class)  Fibonacci Heap  CLRS: Ch 20 
24  15th September 2017  Fibonacci Heap  CLRS: Ch 20 
25  11th October 2017  Fibonacci Heap: complexity analysis  CLRS: Ch 20 
26  12th October 2017  Graph Introduction, BFS  CLRS: Ch 22 
27  13th October 2017  Graph: BFS  CLRS: Ch 22 
28  17th October 2017  Graph: DFS  CLRS: Ch 22 
29  20th October 2017  Graph: DFS Analysis, DFS applications  CLRS: Ch 22 
30  25th October 2017  Hashing  CLRS: 
31  26th October 2017  Hashing  CLRS: 
32  27th October 2017  Search Trees  CLRS: 
32  1st November 2017  AVL Tree  CLRS: 

