COURSE SUMMARY
Course Title:
Data Structures and Algorithms
Course Code:
15CSE201
Year Taught:
2015
2016
2017
2018
Semester:
3
Type:
Subject Core
Degree:
School:
School of Engineering
Campus:
Bengaluru
Chennai
Coimbatore
Amritapuri

'Data Structures and Algorithms' is a course offered in the third semester of B. Tech. in Computer Science and Engineering program at School of Engineering, Amrita Vishwa Vidyapeetham.

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

#### TEXTBOOK

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

#### REFERENCES

• 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.