Course

Professional Electives

Other Branches

Unit I

Introduction: Overview of Data Structures – 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, Double-ended queue, Circular queue.

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 List – Complexity.

Unit III

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.

Course Objectives

• To provide understanding of structure and implementation of the common data structures used in computer science and the concept of analyzing algorithms in terms of asymptotic notation.

Course Outcomes

CO1: Understanding of basic data structures.

CO2: Ability to illustrate various operations on data structures.

CO3: Ability to analyze algorithms and check for correctness.

CO4: Ability to analyze application problems and formulate solutions using data structure.

CO-PO Mapping

Evaluation Pattern: 70:30

*CAT – Can be Quizzes, Assignments, and Reports

*CAL – Can be Lab Assessments, Project, and Report

**End Semester can be theory examination/ lab-based examination/ project presentation

Textbook(s)

Goodrich M T and Tamassia R, “Data Structures and Algorithms in Java”, Fifth edition, Wiley publication, 2010.

Goodrich M T, Tamassia R and Michael H. Goldwasser, “Data Structures and Algorithms in Python++”, Wiley publication, 2013.

Reference(s)

Clifford A. Shaffer, “Data Structures and Algorithm Analysis”, Third Edition, Dover Publications, 2012.

Tremblay J P and Sorenson P G, “An Introduction to Data Structures with Applications”, Second Edition, Tata McGraw-Hill, 2002.