Algorithm and Data Structure

Subject belongs to Paper IV from the Inter-departmental/Inter-disciplinary Basket of M.E. of Software Engineering 1st Year 1st Semester.

Class:

3 Periods/Lecture & 1 Lectures/Week

- Theory Class

Marks Distribution: 100 Marks for written exam

Syllabus Outline:

1. Preliminaries:
   1. Order Notation, Recurrence, Counting and Probability
   2. Elementary Data Structures such as Lists, Stacks, Queues, Binary Search Tree
2. Data Structures:
   1. Rooted Tree, Hash Table, AVL Tree, Red Black Tree
   2. Augmenting Data Structures e.g., Interval Trees and Their Applications
3. Sorting Algorithms:
   1. External Sorting, Branch & Bound Method
   2. Dynamic Programming, Greedy Algorithms, Amortized Analysis
4. Advanced data structures:
   1. Sets, B Trees, B+ Tree
5. Graph Algorithms:
   1. Traversals, Minimal Spanning Trees, Single Pair Shortest Path
   2. All Pair Shortest Paths, Maximal Flow
   3. NP-Completeness, Approximation Algorithms

References:

1. Data Structures and Algorithms - Aho, Ullman, Hopcroft
2. Algorithms and Data Structures - Kurt Mehlhorn and Peter Sanders
3. Data Structures and Algorithm Analysis - Clifford A. Shaffer