उत्सव, विकास अनि ब्लग जिन्दगी

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

Font Resize