## Course Detail

 Course Name Data Structures and Algorithms Course Code 15CSE201 Program B. Tech. in Computer Science and Engineering Semester Three Year Taught 2019

### Syllabus

##### Unit 1

Introduction: Overview of Data Structures – A Philosophy of Data Structures – The Need for Data Structures – Cost and Benefits – Abstract Data Types and Data Structures – Principles, and Patterns. Basic complexity analysis – Best, Worst, and Average Cases – Asymptotic Analysis -Analyzing Programs – Space Bounds, Arrays, Linked Lists and Recursion: Using Arrays – Lists – Array based List Implementation – Linked Lists – LL ADT – Singly Linked List – Doubly Linked List – Circular Linked List – recursion- linear, binary, and multiple recursions.

Stacks and Queues: Stack ADT – Array based Stacks, Linked Stacks – Implementing Recursion using Stacks, Queues – ADT, Array based Queue, Linked Queue, Doubleended queue, Circular queue.

##### Unit 2

Trees: Tree Definition and Properties – Tree ADT – Basic tree traversals – Binary tree – Data structure for representing trees – Linked Structure for Binary Tree – Array based implementation. Priority queues: ADT – Implementing Priority Queue using List – Heaps. Maps and Dictionaries: Map ADT – List based Implementation – Hash Tables – Dictionary ADT – Skip List – Complexity.

##### Unit 3

Search trees – Binary search tree, AVL tree, Trees – K-D Trees – B-Trees. Sorting and Selection – Linear Sorting – Heap Sort – Divide and Conquer Strategy – Analysis using Recurrence Tree based Method – Merge Sort – Quick Sort – Studying Sorting through an Algorithmic Lens – Selection – External Memory Sorting and Searching. Graphs: ADT- Data structure for graphs – Graph traversal- Transitive Closure- Directed Acyclic graphs – Weighted graphs – Shortest Paths – Minimum spanning tree – Greedy Methods for MST.

### Text Books

1. Goodrich M. T. and Tamassia R., “Data Structures and Algorithms in Java”, Fifth edition, Wiley publication, 2010.
2. Clifford A. Shaffer, “Data Structures and Algorithm Analysis”, Third Edition, Dover Publications, 2012.

### Resources

• Goodrich M. T., Tamassia R. and Michael H. Goldwasser, “Data Structures and Algorithms in Python++”, Wiley publication, 2013
• Tremblay J. P. and Sorenson P. G., “An Introduction to Data Structures with Applications”, Second Edition, Tata McGraw-Hill, 2002.

DISCLAIMER: The appearance of external links on this web site does not constitute endorsement by the School of Biotechnology/Amrita Vishwa Vidyapeetham or the information, products or services contained therein. For other than authorized activities, the Amrita Vishwa Vidyapeetham does not exercise any editorial control over the information you may find at these locations. These links are provided consistent with the stated purpose of this web site.