Data Structure and Algorithms
Course Objectives:  To provide fundamental knowledge of various data structures and their implementation
 To provide the fundamental knowledge of various algorithms and their analysis
 Concept of data structure (2 hours)
 Introduction: data types, data structures and abstract data types
 Introduction to algorithms
 The Stack and Queue (6 hours)
 Stack operation
 Stack application: Evaluation of Infix, Postfix and Prefix expressions
 Operations in queue, Enqueue and Dequeue
 Linear and circular queue
 Priority queue
 List (3 hours )
 Definition
 Static and dynamic list structure
 Array implementation of lists
 Queues as list
 Linked lists (5 hours )
 Dynamic implementation
 Operations in linked list
 Linked stacks and queues
 Doubly linked lists and its applications
 Recursion (4 hours )
 Principle of recursion
 TOH and Fibonacci sequence
 Applications of recursion
 Trees (7 hours )
 Concept
 Operation in Binary tree
 Tree search, insertion/deletions
 Tree traversals (preorder, postorder and inorder)
 Height, level and depth of a tree
 AVL balanced trees and Balancing algorithm
 The Huffman algorithm
 BTree
 Red Black Tree
 Sorting (5 hours )
 Types of sorting: internal and external
 Insertion and selection sort
 Exchange sort
 Merge and Redix sort
 Shell sort
 Heap sort as a priority queue
 Big ‘O’ notation and Efficiency of sorting
 Searching ( 5 hours )
 Search technique
 Sequential, Binary and Tree search
 General search tree
 Hashing
 Hash function and hash tables
 Collision resolution technique
 Growth Functions ( 2 hours)
 Asymptotic notations: notations and their properties
 Graphs ( 6 hours )
 Representation and applications
 Transitive closure
 Warshall’s algorithm
 Graphs type
 Graph traversal and Spanning forests
 Depth First Traversal and Breadth First Traversal
 Topological sorting: Depth first, Breadth first topological sorting
 Minimum spanning trees, Prim’s, Kruskal’s and RoundRobin algorithms
 Shortestpath algorithm
 Greedy algorithm
 Dijkstra’s Algorithm
Practical:
There shall be 10 to 12 lab exercises based on C or C++
 Implementation of stack
 Implementations of linear and circular queues
 Solutions of TOH and Fibonacci sequence by Recursion
 Implementations of linked list: singly and doubly linked list
 Implementation of trees: AVL trees, and balancing
 Implementation of Merge sort
 Implementation of search: sequential, Binary and Tree search
 Implementation of Graphs: Graph Traversals
 Implementation of hashing
 Implementation of Heap
References
 Y. Langsam, M. J. Augenstein and A. M Tenenbaum, “Data Structures using C and C++”, PHI
 T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, “Introduction to Algorithms”, PHI
 G.W. Rowe, “Introduction to Data Structure and Algorithms with C and C++”, PHI
 R. L. Kruse, B. P. Leung, C. L. Tondo, “Data Structure and Program design in C”, PHI
 G. Brassard and P. Bratley, “Fundamentals of Algorithms”, PHI
Evaluation Scheme:
The questions will cover all the chapters of the syllabus. The evaluation scheme will be as indicated in the table below:
Chapters 
Hours 
Marks Distribution* 
1 
2 
4 
2 
6 
10 
3 
3 
6 
4 
5 
10 
5 
4 
8 
6 
7 
12 
7 
5 
8 
8 
5 
8 
9 
2 
4 
10 
6 
10 
Total 
45 
80 
*Note: There may be a minor deviation in the marks distribution.
