Course Outline 

Lecture notes shared here

Introduction to Data Structures and Algorithms

• • Basic Data Types

  • Overview of Data Structures

  • Abstract Data Type (ADT): separating what from how

  • How the machine stores and executes: memory addressing, the RAM model, cost of a step

  • Algorithm and Analysis

  • Run-time and Space Complexity; worst / best / average case

  • Comparing algorithms

    • Asymptotic Notations and Analysis (O, Ω, Θ, o, ω; the limit method)

    • Summations and bounding techniques

Basic Data Structures Array

• • The array as an ADT; contiguous allocation and the address formula

  • Searching (linear, binary); binary-search correctness and optimality

Linked List

• Singly linked list; pointers and non-contiguous storage

• Difference — Array vs. Linked List (the cost duality)

• Doubly linked list, Circular linked list

More on Array and Linked List, Sorting and Order Statistics

• • The two-pointer and sliding-window techniques (new — array traversal patterns; heavily interviewed)

  • Prefix sums and the precompute-to-query-cheaply pattern (new — 1-D ancestor of Fenwick/segment trees)

  • Simple sorts: Insertion, Selection, Bubble 

  • Comparison sorts: Quick, Merge, Heap, Shellsort

  • Linear-time sorting: Bucket, Radix, Count (idea-level: when and why they beat the Ω(n log n) comparison bound, not hand-coded)

  • Comparative Analysis

  • Order Statistics (selection in expected linear time)

Stacks

• • Introduction, Implementation and Applications

  • Use in expression evaluation and Recursion

Queues

• • Introduction, Implementation and Applications; difference with stack

  • Circular Queue

  • Double-ended Queue (Deque)

Priority Queue (PQ) and Heap

• • PQ introduction and implementation

  • Introduction to heap (max, min) and binary heap

  • Heapsort

Hashing

• • Introduction

  • Components of Hashing, Hash Table

  • Hash functions

  • Collision Resolution techniques

  • Comparison of Collision Resolution techniques

Tree

• • Introduction

  • Binary Tree, Binary Search Tree (BST)

  • Traversals in BST: Inorder, Preorder, Postorder

  • Height-Balanced Trees: AVL (full treatment); Red-Black (concept and guarantees only) (trimmed — properties and balancing guarantees, not the full insertion-case surgery)

  • B-Tree: Introduction

  • Segment Trees and Fenwick (Binary Indexed) Trees 

Special Data Structures

• • Disjoint Sets

  • Union–Find (with path compression; amortized analysis revisited here)

Graph Algorithms

• • Graph representation

  • Graph traversal — breadth-first search, depth-first search

  • Topological ordering (sorting)

  • Shortest Path algorithms

  • Minimum Spanning Tree (brief introduction)

  • Cut-vertices and biconnected components

A Dynamic Programming Primer

• • Memoization and the top-down / bottom-up view

  • The two classic patterns (1-D and 2-D)

  • (May be developed further as part of Lab / the CP track)

Textbooks:

1. Cormen book

2. Seymour Lipschutz. Data Structures with C. Schaum's Outlines.

3. Karumanchi, Narasimha. Data Structures and Algorithms Made Easy: 700 Data Structure and Algorithmic Puzzles. CreateSpace, 2011. 

Reference Materials:

1. Algorithms by Robert Sedgewick