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
    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. Mathematical background
    2. Model
    3. What to analyze?
    4. Running time calculations

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

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

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

    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. 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. 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
    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. 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

LEAVE A REPLY

Please enter your comment!
Please enter your name here