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