Course

Module I

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, Double-ended queue, Circular queue. Lab component to focus primarily on implementation of Dynamic arrays, inked lists, recursive operations, and queues.

Module 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. Lab component to focus primarily on implementation of trees, queues, and lists and corresponding topics covered in this unit.

Module 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. Lab component focuses primarily on implementation of algorithms covered in this unit. Final project lab exercise to build a real-life use-case using data structures and algorithms covered in this class.

Course Objectives

• To Develop a solid understanding of the theory and implementation of data structures, algorithms and associated implementation.
• To Cover the theory of data structures and algorithms and complement it with an implementation of each topic covered in the units below.

Course Outcomes

• CO1: Ability to implement linear and non-linear data structure operations using C
• CO2: Ability to solve problems using appropriate data structures
• CO3: Ability to analyze the algorithms and its complexity
• CO4: Ability to employ sorting and searching algorithms using relevant data structures

CO – PO Mapping

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.

Reference

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

Evaluation Pattern 50:50 (Internal: External)