MC7104 DATA STRUCTURES AND ALGORITHMS Syllabus
COURSE OBJECTIVES
To understand the linear and non linear data structures available in solving problems
To know about the sorting and searching techniques and its efficiencies
To get a clear idea about the various algorithm design techniques
Using the data structures and algorithms in real time applications
Able to analyze the efficiency of algorithm
UNIT I LINEAR DATA STRUCTURES
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
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
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
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
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.
COURSE OUTCOMES:
Able to select and apply the data structure to suit any given problem.
Able to design their own data structure according to the application need.
Able to apply the algorithm design techniques to any of the real world problem.
Able to develop any new application with the help of data structures and algorithms.
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
COURSE OBJECTIVES
To understand the linear and non linear data structures available in solving problems
To know about the sorting and searching techniques and its efficiencies
To get a clear idea about the various algorithm design techniques
Using the data structures and algorithms in real time applications
Able to analyze the efficiency of algorithm
UNIT I LINEAR DATA STRUCTURES
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
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
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
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
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.
COURSE OUTCOMES:
Able to select and apply the data structure to suit any given problem.
Able to design their own data structure according to the application need.
Able to apply the algorithm design techniques to any of the real world problem.
Able to develop any new application with the help of data structures and algorithms.
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