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:

  • Wednesday: 9AM-9:55AM, Thursday: 10AM-10:55AM, Friday: 11AM-11:55AM

  • Venue: 1201

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, insertion-sort, selection sort, bubble-sort, 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, red-black trees, AVL trees, splay trees, B-trees;

  • 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 1-4, 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, Addison-Wesley, 1997.

TAs:

  • Surajit Das (Email: d.surajit@iitg.ernet.in)

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: