Syllabus
Unit I
Introduction to Data Structures: Need and Relevance – Abstract Data Types and Data Structures – Principles, and Patterns. Basic complexity analysis – Best, Worst, and Average Cases – Asymptotic Analysis -Analyzing Programs – Space Bounds, recursion- linear, binary, and multiple recursions. 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 Stacks and Queues: Stack ADT – Array based Stacks, Linked Stacks – Implementing Recursion using Stacks, Stack Applications. Queues – ADT, Array based Queue, Linked Queue, Double-ended queue, Circular queue, applications.
Unit II
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 Lists – Implementation – Complexity.
Unit III
Search trees Binary search tree, AVL tree and its rotation Segment Trees – B-Trees. Implementation. 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.Persistent data structures, fusion trees, Bloom filter, Game Trees (Case Study)
Objectives and Outcomes
Pre-Requisite(s): 23MATXXX Discrete Mathematics
Course Objectives
- This course aims to provide the students, an in-depth understanding of structure and implementation of the common data structures used in computer science.
- It imparts the ability to solve problems by choosing and applying the right data structures.
- It also imparts the ability to improve the efficiency of programs by applying the right data structures.
Course Outcomes
CO1: Understand the concept and functionalities of Data Structures and be able to implement them efficiently.
CO2: Identify and apply appropriate data structures and their libraries to solve problems and improve them
efficiency
CO3: Analyze the complexity of data structures and associated algorithms.
CO4: Analyze the impact of various implementation and design choices on the data structure performance.
CO-PO Mapping
| PO/PSO |
PO1 |
PO2 |
PO3 |
PO4 |
PO5 |
PO6 |
PO7 |
PO8 |
PO9 |
PO10 |
PO11 |
PO12 |
PSO1 |
PSO2 |
PSO3 |
| CO |
| CO1 |
3 |
|
1 |
|
3 |
|
|
1 |
|
1 |
|
|
3 |
1 |
– |
| CO2 |
3 |
3 |
1 |
2 |
|
|
|
1 |
|
1 |
|
|
3 |
1 |
– |
| CO3 |
1 |
3 |
1 |
2 |
|
|
|
1 |
|
1 |
|
|
3 |
1 |
– |
| CO4 |
2 |
2 |
1 |
2 |
3 |
|
|
1 |
|
1 |
|
|
3 |
1 |
– |
Evaluation Pattern
Evaluation Pattern: 50:50
| Assessment |
Internal |
External |
| Midterm |
20 |
|
| *Continuous Assessment Theory (CAT) |
20 |
|
| *Continuous Assessment LAB (CAL) |
30 |
|
| **End Semester |
|
30 (50 Marks; 2 hours exam) |
*CAT includes Quizzes and Tutorials
*CAL – Can be Lab Assessments, Project, Case Study and Report
**End Semester can be theory examination/ lab-based examination
Text Books / References
Textbook(s)
Michael T Goodrich and Roberto Tamassia and Michael H Goldwsasser, “Data Structures and Algorithms in Python++”, John Wiley publication, 2013.
Reference(s)
- Michael T Goodrich and Roberto Tamassia and Michael H Goldwsasser, “Data Structures and Algorithms in Java”, Fifth edition, John Wiley publication, 2010.
- Tremblay J P and Sorenson P G, “An Introduction to Data Structures with Applications”, Second Edition, Tata McGraw-Hill, 2002.
- Clifford A. Shaffer, “Data Structures and Algorithm Analysis”, Third Edition, Dover.
- Dinesh P. Mehta, Dinesh P. Mehta, Sartaj Sahni, “Handbook of Data Structures and Applications”, Chapman and Hall/CRC, 2004.
- George Heineman Gary Pollice, Stanley Selkow, “Algorithms in a Nutshell”, O′Reilly; 2nd edition, 2016.
