|
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, 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.
[Weiss] M. A. Weiss, Data Structures and Problem Solving Using Java, Addison-Wesley, 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, CLRS: 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, CT2 | CLRS: Ch 22 |
| 30 | 25th October 2017 | Topological Sort, Strongly Connected Components | CLRS: Ch 22 |
| 31 | 26th October 2017 | Hashing | CLRS: CH 11, TLA: Ch 7.4 |
| 32 | 27th October 2017 | Hashing | CLRS: CH 11, TLA: Ch 7.4 |
| 33 | 1st November 2017 | Hash functions, Binary Search Tree (BST) | CLRS: Ch 11, CLRS: Ch 12 |
| 34 | 2nd November 2017 | BST Deletion, AVL Tree | CLRS: Ch 12 |
| 35 | 3rd November 2017 | AVL Tree Insertion | Weiss: Ch 4.4, TLA: 7.2 |
| 36 | 8th November 2017 | AVL Tree Deletion, CT3 | Weiss: Ch 4.4, TLA: 7.2 |
| 37 | 9th November 2017 | Splay Tree | Weiss: Ch 4.5 |
| 38 | 10th November 2017 | B-Tree | CLRS: Ch 18 |
| 39 | 15th November 2017 | B-Tree Insertion | CLRS: Ch 18 |
| 40 | 16th November 2017 | B-Tree Deletion | CLRS: Ch 18 |
| 41 | 17th November 2017 | B+ Tree, Red-Black Tree Introduction | TLA: Ch 7.2, CLRS: Ch 13 |
| 42 | 18th November 2017 | CT4 |
|
|