19CSE212: Data Structures and Algorithms
(Even Semester 2022-2023)
B.Tech - CSE IV Sem - A, Batch 2021-2025
Instructor: Dr. Mansi Sharma
L-T-P-C: 3-0-3-4
Lectures: Wednesday (Slot 2), Thursday (Slot 3), Friday (Slot 5)
Lab Sessions: Wednesday (Slot 6-7)
Room No. - ABIII GF A103
Course Objectives
● This course aims to provide 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.
Pre-Requisite(s): 19CSE111 Fundamentals of Data Structures
Syllabus
Unit 1
Refresher of Data Structures - 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. -Sorting and Selection – Linear Sorting –Divide and Conquer based sorting – Analysis using Recurrence Tree based Method - Merge Sort - Quick Sort - Studying Sorting through an Algorithmic Lens. 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 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 Lists - Implementation - Complexity.
Unit 3
Search trees – Binary search tree, AVL tree, Trees – 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.
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 their 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
CO5: Conceptualize and build data structures based on application needs
Lab Assignments
Lab 1 Assignment (Feb 15th 2023) - Posted on AUMS
HPOJ Lab 2 Assignment (Feb 22nd 2023)
HPOJ Lab 3 Assignment (March 1st 2023)
HPOJ Lab 4 Assignment (March 8th 2023)
HPOJ Lab 5 Assignment (March 11th 2023)
Lab 6 (March 15th 2023) - Evaluation Lab 1
HPOJ Lab 7 Assignment (March 29th 2023)
HPOJ Lab 8 Assignment (April 5th 2023)
HPOJ Lab 9 Assignment (April 12th 2023)
HPOJ Lab 10 Assignment (April 19th 2023)
HPOJ Lab 11 Assignment (April 26st 2023)
Lab 12 (May 3rd 2023) - Evaluation Lab 2
HPOJ Lab 13 Assignment (May 17th 2023)
HPOJ Lab 14 Assignment (May 24th 2023)
HPOJ Lab 15 Assignment (May 31st 2023)
HPOJ Lab 16 Assignment (June 7th 2023)
Lab 17 Project Review (June 14th 2023)
Evaluation Pattern
Internal: 65 External: 35 (Theory :45, Lab: 55)
● Internal (65 Marks)
Mid Term Exam- 20 Marks (April 18th 2023)
Continuous Assessment Theory - 15 Marks
Tutorial 1 (T1) - 7 Marks (April 12th 2023)
Problem solving applying linear DS & Binary trees in real world applications; understanding design choices Complexity analysis of solutions
Tutorial 2 (T2) - 8 Marks (May 24th 2023)
Problem solving applying Height balanced trees & graphs (traversal, MST) in real world applications; understanding design choices Complexity analysis of solutions
Continuous Assessment Lab - 30 Marks
Linear DS, Sorting - 10 Marks (March 15th 2023)
BST, Priority Queues - 10 Marks (May 3rd 2023)
Innovative/ Hybrid data structures - Project/Implementation - 10 Marks (June 14th 2023)
● External (35 Marks)
End Semester Exam (20+15) - June 22nd 2023
Tentative Exam Schedule
Evaluation Lab 1 March 15th 2023
Tutorial 1 April 12th 2023
Evaluation Lab 2 May 3rd 2023
Mid Term Exam April 18th 2023
Tutorial 2 May 24th 2023
Project Review June 14th 2023
End Semester Exam Begins June 22nd 2023
Recommended Study Material
The following will be used as a reference/text book for this course:
1. Goodrich MT, Tamassia R, Goldwasser MH. Data structures and algorithms in Python. John Wiley & Sons Ltd; 2013.
2. Goodrich MT, Tamassia R, Goldwasser MH. Data structures and algorithms in Java. Fifth edition, John Wiley & Sons Ltd; 2010.
3. Tremblay JP, Sorenson PG. An introduction to data structures with applications. Second Edition, Tata McGraw-Hill; 2002.
4. Shaffer CA., Data Structures and Algorithm Analysis. Third Edition, Dover Publications; 2012.
5. Wirth, N., Algorithms and Data Structures. Prentice-Hall of India, 2017.
6. Cormen T, Leiserson C, Rivest R, and Stein C., Introduction to Algorithms. MIT Press, 2009.
Acknowledgements
Some of the materials used in class build on that from other tutors and researchers. In particular, we will use some materials from Nptel Lectures of Prof. Naveen Garg, Prof. Madhavan Mukund, Prof. David J. Eck, Prof. Timothy Fowler and other online sources. Use these slides/materials only for academic study purposes.