Home Syllabus Data Structure and Algorithm

# Data Structure and Algorithm

375
0
This course aims to provide fundamental knowledge on data structure designing and implementation for storing information, and various algorithms used in computer sciences.

## Course Contents:

##### Unit I: Introduction ————————————————————– 3 hours
1. Introduction of DSA
1. Its scope
2. Data structure and its types
3. Brief introduction to Recursion
##### Unit II: Algorithms Analysis ————————————————— 2 hours
1. Mathematical background
2. Model
3. What to analyze?
4. Running time calculations

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

3. The queue ADT (linear and Circular)

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

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

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

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

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

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. 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. 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. Greedy algorithm
2. Divide and conquer
3. Dynamic programming
4. Randomized algorithms
5. Backtracking algorithms

## Laboratory:

There shall be 10 lab exercises based on C or C++
1. Implementation of stack
2. Implementation of linear and circular queue
3. Solution of TOH and Fibonacci recursion
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. 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. Any C and C++ book