MC7104 DATA STRUCTURES AND ALGORITHMS Syllabus

MC7104                    DATA STRUCTURES AND ALGORITHMS                              L T P C

3 1 0 4

 COURSE OBJECTIVES

1. To understand the linear and non linear data structures available in solving problems

2. To know about the sorting and searching techniques and its efficiencies

3. To get a clear idea about the various algorithm design techniques

4. Using the data structures and algorithms in real time applications

5. Able to analyze the efficiency of algorithm

UNIT I LINEAR DATA STRUCTURES                                                                                 9+3

Introduction - Abstract Data Types (ADT) – Arrays and its representation –Structures – Stack – Queue

– Circular Queue - Applications of stack – Infix to postfix conversion – evaluation of expression –

Applications of Queue - Linked Lists – Doubly Linked lists – Applications of linked list – Polynomial

Addition

UNIT II TREE STRUCTURES                                                                                              9+3

Need for non-linear structures – Trees and its representation – Binary Tree – expression trees –

Binary tree traversals – left child right sibling data structures for general trees – applications of trees –

Huffman Algorithm - Binary search tree.

UNIT III BALANCED SEARCH TREES, SORTING AND INDEXING                                9+3

AVL trees –B-Trees - Sorting – Bubble sort - Quick Sort - Insertion Sort – Heap sort – Hashing -

Hashing functions - Collision Resolution Techniques - Separate chaining - Open addressing - Multiple

hashing.
UNIT IV GRAPHS                                                                                                                  9+3

Definitions – Representation of graph - Graph Traversals - Depth-first traversal – breadth-first

traversal - applications of graphs - Topological sort – shortest-path algorithms – minimum spanning

tree – Prim's and Kruskal's algorithms – biconnectivity – Euler circuits.

UNIT V ALGORITHM DESIGN AND ANALYSIS                                                                 9+3

Algorithm Analysis – Asymptotic Notations - Divide and Conquer – Merge Sort – Binary Search -

Greedy Algorithms – Knapsack Problem – Dynamic Programming – Warshall’s Algorithm for

Finding Transitive Closure – Backtracking – Sum of Subset Problem – Branch and Bound –

Travelling Salesman Problem.

TOTAL 45+15: 60 PERIODS

COURSE OUTCOMES:

1. Able to select and apply the data structure to suit any given problem.

2. Able to design their own data structure according to the application need.

3. Able to apply the algorithm design techniques to any of the real world problem.

4. Able to develop any new application with the help of data structures and algorithms.

5. Able to write efficient algorithm for a given problem and able to analyze its time complexity.

REFERENCES:

1. M. A. Weiss, “Data Structures and Algorithm Analysis in C++”, Pearson Education Asia, 2013.

2. Tanaenbaum A.S.,Langram Y. Augestein M.J “ Data Structures using C” Pearson

Education , 2004

3. Anany Levitin “Introduction to the Design and Analysis of Algorithms” Pearson Education

2003.

4. E. Horowitz, S.Sahni and Dinesh Mehta, “Fundamentals of Data structures in C++”, University

Press, 2007.

5. E. Horowitz, S. Sahni and S. Rajasekaran, “Computer Algorithms/C++”, Second Edition, University

Press, 2007.

6. Reema Thareja, “Data Structures using C”, Oxford Press, 2012.

7. V. Aho, J. E. Hopcroft, and J. D. Ullman, “Data Structures and Algorithms”, Pearson Education,

1983.

8. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, "Introduction to algorithms", Second

Edition