THINK FIRST·CODE LATER

CPS 2232 · CPS 2233

Data Structures and Algorithms

Abstract data types, algorithm analysis and design

Chapters
16
Questions
499
Labs
126
Your progress
0 · 0% correct

About this course

How do we store data so that a program stays fast when the data grows from a hundred items to a hundred million? This course answers that question. Students first use the data structures of the Java Collections Framework, then learn to analyse algorithms and prove them correct, and finally build the core structures themselves — lists, stacks, queues, heaps, search trees, hash tables and graphs — understanding exactly why each operation costs what it costs.

Every chapter explains the big idea in plain words first, then follows it step by step in code, so that the hardest course of the programming sequence becomes a manageable one.

Focus

  • Recursion, generics and collections — backtracking and memoization, generic types, lambdas, comparators and streams, lists, stacks, queues, deques, sets and maps
  • Analysis and design of algorithms — Big-O, loop invariants and correctness, recurrence relations and divide-and-conquer, greedy algorithms and dynamic programming, sorting
  • Implementing data structures — array-based and linked lists, stacks and queues, heaps and priority queues, binary search trees, AVL trees, hashing
  • Graphs — representations, breadth-first and depth-first traversal, shortest paths and minimum spanning trees

Learning objectives

By the end of the course, students will be able to:

  1. Choose the right collection for a problem (List, Deque, Set, Map, PriorityQueue…) and justify the choice by the cost of its operations.
  2. Write generic classes and methods, and use comparators, lambdas and streams fluently.
  3. Analyse the running time of iterative and recursive algorithms with Big-O notation and recurrence relations, and argue that an algorithm is correct.
  4. Apply the main design strategies — divide-and-conquer, greedy, dynamic programming and backtracking — to new problems.
  5. Implement, trace and compare the classic sorting algorithms.
  6. Implement lists, stacks, queues, heaps, binary search trees, AVL trees and hash tables, and explain their invariants.
  7. Model problems as graphs and solve them with traversals, shortest-path and spanning-tree algorithms.

Teaching approach

Use it, analyse it, build it. Each structure is first used through Java's own library, then analysed, then implemented from scratch — so students always know what a structure promises before learning how it keeps that promise.

  • "The Big Idea" first: every hard concept opens with a plain-language explanation and an everyday analogy, before any formula or code.
  • Step-by-step traces: tables that follow an algorithm one step at a time (produced by real Java programs, so they are exact), plus "common confusion" boxes for the mistakes students make most often.
  • Analysis next to code: every implementation comes with its cost, and every cost is explained, not just stated.
  • Question banks with explanations for tracing, complexity and design questions.
  • Programming labs with tested model solutions, written for Java 8 so they run in any environment.

Course content

Open a chapter to read its review, then practise with its question bank.

Recursion, Generics and Collections

  1. Chapter 1 · Week 1

    Recursion II: Helper Methods, Backtracking and Memoization

    recursive helper methods, recursive binary search, recursion vs iteration, exponential recursion, memoization, backtracking (subsets, permutations, N-Queens), StackOverflowError

    0/30 answered
  2. Chapter 2 · Week 2

    Generics

    generic classes, interfaces and methods, diamond <>, bounded types <T extends Comparable<T>>, wildcards ? extends / ? super (PECS), raw types, type erasure

    0/30 answered
  3. Chapter 3 · Week 2–3

    Lambdas, Comparators and Streams

    functional interfaces, lambdas, method references, Comparable vs Comparator, Comparator.comparing, streams, collectors, Optional

    0/33 answered
  4. Chapter 4 · Week 3

    The Collections Framework: Lists, Stacks, Queues and Deques

    Collection hierarchy, ArrayList vs LinkedList, Iterator/ListIterator, fail-fast iterators, ArrayDeque as stack and queue, PriorityQueue, Arrays.asList, Collections utilities

    0/33 answered
  5. Chapter 5 · Week 4

    Sets and Maps

    HashSet, LinkedHashSet, TreeSet, equals/hashCode, Comparator, NavigableMap, HashMap, TreeMap, merge, computeIfAbsent

    0/31 answered

Analysis and Design of Algorithms

  1. Chapter 6 · Week 5

    Algorithm Analysis and Correctness

    RAM model, Big-O / Big-Ω / Big-Θ, growth rates, loop analysis, best/worst/average case, space complexity, amortized analysis, loop invariants

    0/31 answered
  2. Chapter 7 · Week 6

    Recurrence Relations and Divide-and-Conquer

    recurrences, iteration and substitution, recursion trees, Master theorem, divide-and-conquer, recursive binary search, merge step, counting inversions, maximum subarray, fast exponentiation

    0/31 answered
  3. Chapter 8 · Week 7

    Greedy Algorithms and Dynamic Programming

    greedy choice property, interval scheduling, fractional knapsack, Huffman coding, optimal substructure, memoization vs tabulation, coin change, 0/1 knapsack, LCS, LIS, solution reconstruction

    0/31 answered
  4. Chapter 9 · Week 8

    Sorting

    insertion sort, mergeSort, quick sort (Lomuto), heap sort, counting/radix/bucket sort, stability, Ω(n log n) lower bound, Arrays.sort

    0/32 answered

Implementing Data Structures

  1. Chapter 10 · Week 9

    Implementing Lists, Stacks and Queues

    List ADT, MyArrayList and ensureCapacity, amortized O(1) append, singly and doubly linked lists, Iterator inner classes, array and linked stacks, circular-array and linked queues

    0/32 answered
  2. Chapter 11 · Week 10

    Heaps and Priority Queues

    complete binary trees in an array, max-heap and min-heap, sift-up and sift-down, bottom-up buildHeap, heap sort, MyPriorityQueue<E> with a Comparator, top-k and k-way merge, java.util.PriorityQueue

    0/31 answered
  3. Chapter 12 · Week 11

    Binary Search Trees

    tree vocabulary, the BST property, search and insert, delete (three cases), pre-/in-/post-/level-order traversal, height and O(h) costs, recursive tree utilities, isBST, a BST iterator

    0/31 answered
  4. Chapter 13 · Week 12

    AVL Trees

    height and balance factor, the AVL invariant, LL/RR/LR/RL rotations, rebalancing after insertion and deletion, O(log n) height, red-black trees and TreeMap

    0/31 answered
  5. Chapter 14 · Week 12–13

    Hashing

    hash functions and compression, String.hashCode, separate chaining, linear/quadratic probing, double hashing, load factor, rehashing, tombstones, MyHashMap, equals/hashCode, HashMap internals

    0/31 answered

Graphs

  1. Chapter 15 · Week 13

    Graphs and Traversals

    graph vocabulary, edge list, adjacency matrix, adjacency lists, BFS, DFS, connected components, cycle detection, bipartite graphs, topological sort, O(V + E)

    0/30 answered
  2. Chapter 16 · Week 14

    Weighted Graphs: Shortest Paths and Spanning Trees

    weighted edges, relaxation, Dijkstra's algorithm, predecessor array, negative weights, Bellman–Ford, minimum spanning trees, cut property, Prim's algorithm, Kruskal's algorithm, union–find

    0/31 answered
Labs

126 labs with model solutions

Realistic programming problems. Work out your own answer first, then compare.