CO214: Data structures and Algorithms
| Course Number : CO214 | ||||||
|---|---|---|---|---|---|---|
| Course Title : Data structures and Algorithms | ||||||
| Credits : 3 | ||||||
| Prerequisites : Computer Programming (CO212) | ||||||
| No | Course Content | Time Allocated (hours) | ||||
| L | T | P | A | |||
| 01 | Introduction Programs = Algorithms + Data Structures, Abstract Data Types (ADT) | 1 | ||||
| 02 | Correctness and Complexity analysis Asymptotic Notations and Standard Efficiency Classes, Complexity of recursive algorithms, Time-space tradeoffs, Empirical measurements of performance, Using preconditions, post-conditions and invariants to verify correctness | 3 | 2 | |||
| 03 | Simple Search & Sort
Sequential and binary search algorithms, Quadratic time sorting algorithms (Selection, Insertion) as instances of Brute-force strategy | 3 | 1 | 2 | 2 | |
| 04 | Efficient Sorting
Review of recursion. Quick-sort, merge-sort as instances of Divide-and-conquer strategy, Radix / bin sorting | 4 | 1 | 2 | 2 | |
| 05 | Basic Data Structures:
Linked lists, Stacks and queues , Priority queues (Heaps), Heap-sort | 3 | 2 | 3 | ||
| 06 | Hashing and Sets
Hash functions and codes, Collision handling, The Set ADT, Implementing Sets using hash tables | 3 | 2 | 3 | ||
| 07 | Trees
The Tree ADT. Binary search trees, Tree traversals, Tries and B-Trees. | 4 | 2 | 4 | ||
| 08 | Graph Algorithms
Representations of graphs (adjacency list, adjacency matrix), Depth and breadth-first traversals, The Greedy algorithmic strategy: Dijkstra's shortest path, Dynamic programming: Floyd's Transitive closure, Prim's minimum spanning tree | 5 | 2 | 4 | ||
| Total | 26 | 4 | 12 | 18 | ||
| Assessment | Percentage Marks | |||||
| Continuous Assessment | 40 | |||||
| Tutorials | 10 | |||||
| Practical work | 10 | |||||
| Assignments | 20 | |||||
| Written Examinations | 60 | |||||
| Mid-semester | 20 | |||||
| End-semester | 40 | |||||