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