Details of CS3201 (Spring 2021)
| Level: 3 | Type: Laboratory | Credits: 4.0 |
| Course Code | Course Name | Instructor(s) |
|---|---|---|
| CS3201 | Programming and Data Structures II | Dwaipayan Roy, Kripabandhu Ghosh |
| Syllabus |
|---|
| Topics:
Linked lists: Singly and doubly linked list (non-circular and circular). Stack and queue using linked list. [10 hours] Trees: Binary tree - traversal (inorder, preorder, postorder), searching (DFS, BFS), Search tree: Binary Search Tree - insertion, deletion, searching. [8 hours] Applications of tree: Heap - insertion, deletion and sorting. Priority queue revisited. Huffman encoding. [8 hours] Advanced trees (brief introduction only, no details): Height balanced trees (AVL, Red-black), B-tree, B+ tree, TRIE, minimum spanning trees, shortest paths. [6 hours] Hashing: Hash functions: properties and standards hash functions; Collision and resolution techniques - Probing (linear and quadratic) and Chaining (linear and coalesced). [3 hours] Advanced topic: Dynamic programming. [1 hours] |
| Prerequisite |
|---|
| CS3101 OR, knowledge of C programing language with basic data structures and algorithms |
| References |
|---|
| Books and references:
T. H. Cormen, C. L. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, MIT Press. R. Sedgewick, Algorithms in C (Parts 1-5), Addison Wesley. Udi Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley. Michael T. Goodrich and Roberto Tamassia, Algorithm Design: Foundations, Analysis, and Internet Examples, John Wiley Gilles Brassard and Paul Bratley, Algorithmics : theory and practice Data Structures Through C in Depth. S.K.Srivastava, Deepali Srivastava. |
Course Credit Options
| Sl. No. | Programme | Semester No | Course Choice |
|---|---|---|---|
| 1 | IP | 2 | Elective |
| 2 | IP | 4 | Elective |
| 3 | IP | 6 | Not Allowed |
| 4 | MR | 2 | Not Allowed |
| 5 | MR | 4 | Not Allowed |
| 6 | MS | 10 | Elective |
| 7 | MS | 4 | Not Allowed |
| 8 | MS | 6 | Elective |
| 9 | MS | 8 | Elective |
| 10 | RS | 1 | Elective |
| 11 | RS | 2 | Not Allowed |