# Data Structure and Algorithm Analysis EG631CT

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.2 Stack operation
2.3 Stack application: Evaluation of Infix, Postfix, and Prefix expressions
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.2 Dynamic implementation
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.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.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