Data Structure and Algorithm

Course Contents:

Unit I: Introduction ————————————————————– 3 hours

1. 1. Introduction of DSA
   2. Abstract Data Types (ADTs)
      1. Its scope
      2. Data structure and its types
      3. Brief introduction to Recursion

Unit II: Algorithms Analysis ————————————————— 2 hours

1. 1. Mathematical background
   2. Model
   3. What to analyze?
   4. Running time calculations

Unit III: Lists, Stacks and Queues ——————————————– 6 hours

1. 1. The list ADT (linear, linked list)
   2. The stack ADT
   3. The queue ADT (linear and Circular)

Unit IV: Trees ——————————————————————— 6 hours

1. 1. Preliminaries
   2. Binary trees
   3. The search tree ADT
      1. Binary search trees
      2. ABL trees
      3. Splay trees
      4. Tree traversals (revisited)
      5. B-trees

Unit V: Hashing ——————————————————————- 6 hours

1. 1. General idea
   2. Hash function
   3. Load factor Open hashing (separate chaining)
   4. Closed hashing (Open addressing)
   5. Rehashing
   6. Extendable hashing

Unit VI: Priority Queues ——————————————————– 6 hours

1. 1. Simple implementation
   2. Binary heap
   3. Applications of priority queues
   4. D-heaps
   5. Leftist heaps
   6. Skew heaps
   7. Binomial queues

Unit VII: Sorting —————————————————————– 7 hours

1. 1. Preliminaries
   2. Indentation sort
   3. A lower bound for simple sorting algorithms
      1. Shell-sort
      2. Heap-sort
      3. Merge-sort
      4. Quick-sort
      5. Sorting large objects
   4. A general lower bound for sorting
      1. Bucket sort
      2. External sorting

Unit VIII: Graph Algorithm ————————————————— 6 hours

1. 1. Definitions
   2. Topological sort
   3. Shortest-path algorithm
   4. Network flow problems
   5. Minimum Spanning Tree Applications of Depth-first search

Unit IX: Algorithm Design Techniques ————————————– 6 hours

1. 1. Greedy algorithm
   2. Divide and conquer
   3. Dynamic programming
   4. Randomized algorithms
   5. Backtracking algorithms

Laboratory:

1. 1. Implementation of stack
   2. Implementation of linear and circular queue
   3. Solution of TOH and Fibonacci recursion
   4. Implementation of Link list: Singly, and doubly linked
   5. Implementation of tree: AVL tree, Balancing of AVL
   6. Implementation of merge sort
   7. Implementation of search: sequential, Tree and Binary
   8. Implementation of Graphs: Graph traversals
   9. Implementation of hashing
   10. Implementation of heap

Text Books:

1. 1. Langsam, Y., Augustin, M.J. and Tanenbaum, A.M: Data Structure Using C and C++, Prentice Hall of India
   2. Rowe, G.W.: Introduction to Data Structure and Algorithms with C and C++, Prentice Hall of India
   3. Mark, Allen, Weiss: Data structure and Algorithm Analysis in C++

Recommended:

1. 1. Any C and C++ book