THINK FIRST·CODE LATER

← Data Structures and Algorithms

Programming labs

Write the program yourself, then compare with the model solution. The problems follow the chapters, from the first programs to object-oriented design.

CPS 2232/2233 · 126 labs

Chapter 1 Recursion II: Helper Methods, Backtracking and Memoization 9 labs

D1.1 Medium

Subsets with a Target Sum

Write a program that reads n (0 ≤ n ≤ 20), then n positive integers, then a target t (t ≥ 0). Print every subset of the numbers whose sum is exactly t...

D1.2 Medium

Climbing Stairs with Broken Steps (Memoization)

You stand on step 0 of a staircase and want to reach step n exactly. In one move you may climb 1, 2, …, k steps. Some steps are broken: you may never...

D1.3 Hard

N-Queens by backtracking

Place n queens on an n × n board so that no two attack each other (same row, column or diagonal). Write NQueens. Place one queen per row with a recurs...

D1.4 Medium

Permutations, including repeated letters

Write Permutations. Read a word and a limit. Generate all distinct permutations of its letters in alphabetical order with a recursive method that fill...

D1.5 Medium

Grid paths: the same recursion with and without a memo

A robot starts in the top-left cell of a grid and may move only right or down. Some cells are blocked. How many different paths reach the bottom-right...

D1.6 Medium

Counting islands with a recursive flood fill

A satellite map is a grid of land () and water (.). An island is a group of land cells connected horizontally or vertically. Write Islands: read rows...

D1.7 Hard

The knight's tour by backtracking

A chess knight must visit every square of an n × n board exactly once. Write KnightTour: read n and the starting row col (numbered from 0), and search...

D1.8 Medium

Recursive helper methods on arrays

A recursive method on an array usually needs extra parameters (an index, or a range) that the caller should not have to supply. The solution is a pair...

D1.9 Hard

The 24 game: backtracking over expressions

In the 24 game you receive four cards (1 to 13) and must combine all four with +, −, ×, ÷ and parentheses to obtain exactly 24. Write TwentyFour, whic...

Chapter 2 Generics 9 labs

D2.1 Easy

Generic Minimum and Maximum with Pair<A, B>

Write a generic class Pair<A, B (two private final fields, a constructor, getFirst() and getSecond()) and a single generic method [code] that returns...

D2.2 Medium

A Generic Stack Driven by Commands

Write a generic class GenericStack<E backed by a private ArrayList<E, with: - void push(E item) - E pop() and E peek() — both throw IllegalStateExcept...

D2.3 Medium

Bounded type parameters

Write BoundedGenerics with four generic methods: - <T extends Comparable<T int countGreater(List<T items, T limit) - <T extends Comparable<T boolean i...

D2.4 Medium

DynArray<T>: your own generic growable array

Write a generic class DynArray<T backed by an array that starts with capacity 2 and doubles when full (print (capacity grows to 4) each time). Methods...

D2.5 Hard

Wildcards: producer extends, consumer super

Write Wildcards with: - double sum(List<? extends Number numbers) — reads from the list; - void addSquares(List<? super Integer target, int n) — write...

D2.6 Medium

Result<T>: a generic "value or error"

Write a generic class Result<T that holds either a value or an error message: - a private constructor and two static generic factory methods, Result.o...

D2.7 Medium

One search for every comparable type

Write GenericSearch with two generic methods that work on an array of any type whose elements can be compared: [code] Count the calls to compareTo in...

D2.8 Medium

Generic tools: which bound does each method need?

Write GenericTools with four generic methods, giving each the weakest condition on its type parameter that makes it compile: - max(E[][] grid) — the l...

D2.9 Hard

A generic matrix: one algorithm, two number types

Matrix addition and multiplication are the same algorithms whether the elements are integers or exact fractions; only "add two elements" and "multiply...

Chapter 3 Lambdas, Comparators and Streams 6 labs

Chapter 4 The Collections Framework: Lists, Stacks, Queues and Deques 9 labs

D4.1 Medium

Balanced brackets with a stack

Check whether the brackets (), [] and {} in each line of text are balanced. All other characters are ignored. Input. An integer n, then n lines of tex...

D4.2 Easy

Hot potato: a queue simulation

Players stand in a circle and pass a potato. In each round the potato is passed k times; whoever holds it then is out. The last player left wins. Mode...

D4.3 Medium

Evaluating postfix expressions with a stack

In postfix (reverse Polish) notation the operator follows its operands: 3 4 + 2 means (3 + 4) × 2. No parentheses are ever needed. Write Postfix with...

D4.4 Hard

Sliding-window maximum with a deque

Given n values and a window size k, print the maximum of every window of k consecutive values — in O(n) total, not O(n·k). Write WindowMax using an Ar...

D4.5 Easy

Browser back and forward with two stacks

Write BrowserHistory. The browser starts on home. Commands until the end of input: - visit PAGE — the current page goes on the back stack, and the for...

D4.6 Medium

Removing while iterating: Iterator and ListIterator

Write IteratorLab. Read a limit, then integers into an ArrayList<Integer. 1. On a copy, try the wrong way: remove the values greater than the limit in...

D4.7 Hard

From infix to postfix with a stack

People write 3 + 4 2; a stack machine prefers the postfix form 3 4 2 +, which needs no parentheses and no priority rules. Write InfixToPostfix, which...

D4.8 Medium

Towers of Hanoi without recursion

The recursive solution of the Towers of Hanoi is famous; here you solve the puzzle with three stacks and a loop. Disks 1 (smallest) to n start on peg...

D4.9 Medium

Folder sizes with a queue and with a stack

Computing the size of a folder is naturally recursive; here you do it without recursion, first with a queue, then with a stack. The input describes a...

Chapter 5 Sets and Maps 9 labs

D5.1 Easy

Word-frequency report

Read a text from standard input (any number of lines, possibly none) and produce a word-frequency report. - A word is a maximal run of letters a–z, af...

D5.2 Medium

Group anagrams

Two words are anagrams if one is a rearrangement of the letters of the other (listen / silent). Their signature — the letters sorted alphabetically —...

D5.3 Medium

First unique letter with a LinkedHashMap

Write FirstUnique. For every non-empty input line, count its letters (ignore case, digits, spaces and punctuation) in a LinkedHashMap<Character, Integ...

D5.4 Medium

Next bus: navigating a TreeMap

Write BusTimetable. Read n departures HH:MM line into a TreeMap<Integer, String keyed by minutes after midnight. Print the first and last bus (firstKe...

D5.5 Easy

Club members: set algebra

Write ClubSets. Read the members of the chess club (n, then n names) and of the robotics club (m, then m names) into two TreeSet<String. Without modif...

D5.6 Hard

A tiny search engine: the inverted index

Write InvertedIndex. The first line is n; the next n lines are the text. Build a TreeMap<String, TreeSet<Integer mapping each word (lower case, letter...

D5.7 Medium

Counting the keywords of a Java program

Write KeywordCounter, which reads Java source code from the input and counts its keywords (class, int, if, while, …; include true, false and null). -...

D5.8 Medium

A tiny web crawler: the visited set

A crawler starts from one page, follows its links, then the links of those pages, and so on — and must never visit a page twice, even though pages lin...

D5.9 Medium

Name rankings: maps inside maps

A registry publishes, for each year, the ranking of the most popular first names for boys and for girls. Write NameRanks. Data — lines year rank boyNa...

Chapter 6 Algorithm Analysis and Correctness 9 labs

D6.1 Medium

Pairs with a given sum: Θ(n²) versus Θ(n)

Given an array of n integers and a target, count the pairs of positions i < j with a[i] + a[j] == target. Solve the problem twice and count the work e...

D6.2 Easy

Range sums with prefix sums

You are given an array of n integers and q queries. Each query l r (0-based, 0 ≤ l ≤ r < n) asks for a[l] + a[l+1] + … + a[r]. Answer every query, and...

D6.3 Medium

Counting operations and the doubling test

Write GrowthTable with four methods that count how many times their innermost statement runs: - halving(n): for (i = n; i = 1; i /= 2); - linearithmic...

D6.4 Easy

Linear versus binary search, in comparisons

Write SearchCompare. Read n and build the sorted array 1, 4, 7, … (a[i] = 3i + 1). For each key until the end of input, run a linear search and a bina...

D6.5 Medium

Maximum subarray: Θ(n²) versus Kadane's Θ(n)

Given n integers (some negative), find the largest sum of a contiguous, non-empty block — e.g. the best run of days in a list of daily profits and los...

D6.6 Medium

Three ways to find a duplicate

Does an array contain a repeated value? Write DuplicateCheck with three methods that answer the question and count their basic steps: - byPairs — comp...

D6.7 Medium

The longest increasing run: Θ(n²) or Θ(n)?

In a string, an increasing run is a block of consecutive characters in which each character is greater than the one before ("abcd" in "xabcdab"). Writ...

D6.8 Hard

Finding a pattern: naive search versus KMP

Write PatternSearch, which reads pairs of lines — a text, then a pattern — and finds all the positions where the pattern occurs (overlapping occurrenc...

D6.9 Medium

Counting primes three ways

How many primes are there up to n? Write PrimeCounting, which answers with three algorithms and counts the basic operations of each: 1. for every numb...

Chapter 7 Recurrence Relations and Divide-and-Conquer 9 labs

D7.1 Medium

Fast modular exponentiation

Write a program that computes aⁿ mod m for several queries using fast (square-and-multiply) exponentiation, so that exponents up to 10¹⁸ are handled i...

D7.2 Hard

Counting inversions with merge sort

An inversion in an array is a pair of positions i < j with a[i] a[j] (equal values are not an inversion). Write a program that counts the inversions o...

D7.3 Hard

Maximum subarray by divide and conquer

Solve the maximum-subarray problem again, now by divide and conquer. The best block of a[low..high] is either entirely in the left half, entirely in t...

D7.4 Medium

Recurrences: measure, then apply the Master theorem

Write Recurrences. For each triple a b d in the input, consider T(n) = a·T(n/b) + n^d with T(1) = 1. 1. Print the Master-theorem verdict by comparing...

D7.5 Hard

Quickselect: the k-th smallest without sorting

Write QuickSelect. Read n and n integers, then values of k (1 = smallest). For each k, find the k-th smallest element with quickselect: partition with...

D7.6 Medium

How many times does it occur? Two binary searches

In a sorted array with repeated values, count the occurrences of a key in O(log n) — without scanning the run of equal values. Write CountOccurrences...

D7.7 Hard

The closest pair of points

Given n points in the plane, find the smallest distance between two of them. Brute force compares all n(n − 1)/2 pairs. Write ClosestPair, which also...

D7.8 Medium

The Sierpinski triangle and T(n) = 3T(n − 1) + 1

The Sierpinski triangle of order 0 is a single star. A triangle of order n is made of three triangles of order n − 1: one on top, one at the bottom le...

D7.9 Medium

Euclid's algorithm: how many steps?

Write EuclidSteps, which reads pairs of positive integers until the end of the input and computes their greatest common divisor twice: 1. counting dow...

Chapter 8 Greedy Algorithms and Dynamic Programming 6 labs

Chapter 9 Sorting 9 labs

D9.1 Medium

Merge sort with a comparison counter

Implement top-down merge sort on an int array and count its work. Input: an integer n (n ≥ 0), followed by n integers. Algorithm (follow it exactly, s...

D9.2 Medium

Tracing quick sort with the Lomuto partition

Implement quick sort with the Lomuto partition (pivot = last element of the range, elements <= pivot go left) and print the whole array after every pa...

D9.3 Easy

Insertion sort: trace, shifts and inversions

Write InsertionTrace. Read n and n integers. First count the inversions of the input (pairs i < j with a[i] a[j]). Then run insertion sort, printing t...

D9.4 Medium

Counting sort and stability

Write CountingSortDemo. Read n k, then n records name key with keys in 0 … k. Sort the records by key with counting sort: 1. count each key (print the...

D9.5 Medium

LSD radix sort, pass by pass

Write RadixSort for non-negative integers. Sort by the least significant digit first: one stable counting-sort pass per decimal digit (units, tens, hu...

D9.6 Hard

Quick sort for many duplicates: three-way partitioning

With many equal keys, ordinary quick sort wastes time re-sorting them. Write ThreeWayQuick using Dijkstra's three-way partition with pivot a[low] and...

D9.7 Medium

A generic bubble sort, with and without a Comparator

Write BubbleGeneric with two versions of the same sort: [code] The first must simply call the second with Comparator.naturalOrder(). The sort stops as...

D9.8 Medium

Quick sort: does the choice of pivot matter?

Write PivotChoice, which sorts the same data twice with quick sort (Lomuto-style partition around the element at low) and counts the comparisons of el...

D9.9 Medium

Stable or not? Merge sort versus selection sort

A sort is stable if elements that compare as equal keep their original relative order. This matters as soon as records are sorted by one field: sortin...

Chapter 10 Implementing Lists, Stacks and Queues 9 labs

D10.1 Medium

A doubly linked list driven by commands

Implement your own doubly linked list of int values (fields head, tail, size; nodes with prev and next) — do not use java.util collections — and drive...

D10.2 Medium

A fixed-capacity circular queue

Implement a queue of int on a circular array of fixed capacity, with fields data, front (index of the oldest element, initially 0) and size. The array...

D10.3 Medium

Linked-list surgery: middle, duplicates, reverse

Write LinkedOps with your own singly linked list (a Node class with value and next, plus head and tail references — no java.util lists). Read integers...

D10.4 Medium

A stack on a resizing array

Write a class ResizingStack of ints on an array of initial capacity 2: push doubles the array when it is full; pop halves it when, after the pop, the...

D10.5 Medium

A queue made of two stacks

Write a generic class TwoStackQueue<T with two stacks: enqueue pushes on the inbox; dequeue pops from the outbox, and only when the outbox is empty po...

D10.6 Medium

Merging two sorted linked lists in place

Write LinkedMerge with your own Node class (no java.util lists). Read two sorted lists (n then n values, twice) and a number k. Then: 1. merge(a, b) —...

D10.7 Medium

A singly linked list with index operations

Write SinglyList containing a generic class MyLinkedList<E: a singly linked list with head, tail and size, and the methods addFirst, addLast, add(inde...

D10.8 Medium

addAll, removeAll, retainAll in your own array list

Java's collections offer three "bulk" operations; write them yourself. In ListSetOps, write a generic class MyArrayList<E on a growing array (add, get...

D10.9 Hard

Make your list work in a for-each loop

for (E e : list) works on any class that implements Iterable<E. In IterableList, write a singly linked list Chain<E implements Iterable<E with add, si...

Chapter 11 Heaps and Priority Queues 9 labs

D11.1 Medium

A command-driven min-heap

Implement your own array-based min-heap of int values (use an ArrayList<Integer as the array; do not use java.util.PriorityQueue) and drive it with co...

D11.2 Easy

Top-k and the k-th largest value

Read n integers and report the k largest of them and the k-th largest, using a min-heap that never holds more than k elements (java.util.PriorityQueue...

D11.3 Medium

Building a heap: bottom-up versus one by one

Write BuildHeap for a min-heap stored in an array (children of i at 2i + 1 and 2i + 2). Read n and n integers and: 1. say whether the input already is...

D11.4 Medium

Merging k sorted lists with a priority queue

Write MergeKLists. Read k, then k sorted lists (size followed by the values). Merge them into one sorted sequence using a PriorityQueue that holds at...

D11.5 Hard

Running median with two heaps

Write RunningMedian: after each number read, print the median of all numbers so far (for an even count, the average of the two middle values). Keep tw...

D11.6 Medium

Emergency room triage with a priority queue

Write Triage. Patients arrive with a severity from 1 (most urgent) to 5. Commands until the end of input: - arrive NAME SEVERITY; - next — treat the m...

D11.7 Medium

Heap sort, in place

Write HeapSortSteps, which sorts an array inside the array itself, in two phases: 1. Build a max-heap: call siftDown on every parent, from the last on...

D11.8 Medium

One heap class for every order

In ComparatorHeap, write a generic class Heap<E (on an ArrayList<E) whose order is given by a Comparator passed to the constructor: the element that t...

D11.9 Easy

Union, difference and intersection of two priority queues

Write QueueSets: read two lines of words and put each line in a PriorityQueue<String. Print: 1. the first queue as it is stored (toString) and then in...

Chapter 12 Binary Search Trees 9 labs

D12.1 Easy

Build a BST and print its traversals

Read integer keys, insert them one by one (in input order) into an initially empty binary search tree, and print the tree's size, its four traversals...

D12.2 Medium

Deleting keys from a BST

Build a BST from a list of keys, then delete a second list of keys one at a time and show the resulting tree. Rules. - Keys are inserted in input orde...

D12.3 Medium

BST queries: floor, ceiling and rank

Write BstQueries with your own BST whose nodes also store the size of their subtree. Read n and n distinct keys (inserted in that order), then query v...

D12.4 Medium

Lowest common ancestor in a BST

Write BstAncestor. Read n and n keys into a BST, then pairs a b until the end of input. For each pair print the lowest common ancestor (the deepest no...

D12.5 Hard

Range queries, k-th smallest and BST validation

Write BstRange. Read n and n keys into a BST, then low high k. Print: 1. the keys in [low, high] in increasing order, using an in-order traversal that...

D12.6 Medium

The best-shaped BST from sorted keys

Inserting sorted keys one by one gives the worst BST: a chain. Write BalancedBst: read n and n keys in increasing order, and 1. insert them one by one...

D12.7 Medium

The shape of a BST: height, leaves and levels

Write BstShape: insert the integers of the input in a binary search tree (duplicates are ignored), then print - the number of nodes and the height (th...

D12.8 Medium

Full, complete, perfect or degenerate?

Four words describe the shape of a binary tree: - full — every node has 0 or 2 children; - complete — every level is filled, except possibly the last,...

D12.9 Hard

Tree traversals without recursion

Recursion makes tree traversals three lines long, but each can also be written with an explicit stack — which is what the recursion does behind the sc...

Chapter 13 AVL Trees 6 labs

Chapter 14 Hashing 6 labs

Chapter 15 Graphs and Traversals 6 labs

Chapter 16 Weighted Graphs: Shortest Paths and Spanning Trees 6 labs