Data Structure and Algorithm Analysis

Objectives: Course objectives is to provide fundamental knowledge of Data Structure and its
design. To provide the knowledge of various algorithms.

1.0 Concept of data structure ( 2 hours)
1.1 Abstract Data Type
1.2 Implementation of Data structure

2.0 The Stack and Queue ( 6 hours)
2.1 Stack as an ADT
2.2 Stack operation
2.3 Stack application: Evaluation of Infix, Postfix, and Prefix expressions
2.4 Queue as an ADT
2.5 Operations in queue, Enqueue and Dequeue
2.6 Linear and circular queue
2.7 Priority queue

3.0 List ( 3 hours)
3.1 Definition
3.1.1 Static and dynamic list structure
3.1.2 Array implementation of lists
3.1.3 Queues as list

4.0 Linked lists ( 6 hours)
4.1 Link list as an ADT
4.2 Dynamic implementation
4.3 Operations in linked list
4.4 Linked stacks and Queues
4.5 Doubly linked lists and its applications

5.0 Recursion ( 4 hours)
5.1 Principle of recursion
5.2 TOH and Fibonacci sequence
5.3 Applications of recursion

6.0 Trees ( 6 hours)
6.1 Concept
6.2 Operation in Binary tree
6.3 Tree search, insertion/deletions
6.4 Tree traversals (pre-order, post-order and in-order).
6.5 Height, level, and depth of a tree
6.6 AVL balanced trees and Balancing algorithm
6.7 The Huffman algorithm
6.8 B-Tree

7.0 Sorting ( 5 hours)
7.1 Types of sorting: internal and external
7.2 Insertion and selection sort
7.3 Exchange sort
7.4 Merge and Radix sort
7.5 Shell sort
7.6 Heap sort as priority queue
7.7 Big 'O' notation and Efficiency of sorting

8.0 Searching ( 5 hours)
8.1 Search technique
8.2 Sequential, Binary and Tree search
8.3 General search tree
8.4 Hashing
8.4.1 Hash function and hash tables
8.4.2 Collision resolution technique

9.0 Graphs ( 8 hours)
9.1 Representation and applications
9.2 Graphs as an ADT
9.3 Transitive closure
9.4 Warshall's algorithm
9.5 Graphs types
9.6 Graph traversal and Spanning forests
9.6.1 Depth First Traversal and Breadth First traversal
9.6.2 Topological sorting: Depth first, breadth first topological sorting
9.6.3 Minimum spanning trees
9.6.4 Kruskal's and Round-Robin algorithms
9.7 Shortest-path algorithm
9.7.1 Greedy algorithm
9.7.2 Dijkstra's Algorithm

Laboratory:
There shall be 12 lab exercises based on C or C++
1. Implementations of stack
2. Implementations of linear and circular queues
3. Solutions of TOH and Finbonacci Recursion
4. Implementations of linked list: singly and doubly linked
5. Implementation of trees: AVL trees, 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. Implementations of Heap

References:
1. Y. Langsam, M.J. Augenstein and A. M. Tenenbaum, "Data Structures using C and C++", PHI
2. G. W. Rowe, "Introduction to Data Structure and Algorithms with C and C++", PHI
3. R.L. Kruse, B. P. Leung, C. L. Tondo, "Data Structure and Program design in C", PHI
4. G. Brassard and P. Bratley, "Fundamentals of Algorithms", PHI