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
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...
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...
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...
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...
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...
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...
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...
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...
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
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...
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...
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...
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...
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...
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...
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...
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...
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
Leaderboard with a multi-key comparator
Read a class's exam results and print a leaderboard. Input. An integer n (n ≥ 0), then n lines each with a name (one word, no spaces) and an integer s...
Word statistics with streams
Read one line of text and summarise its words using streams and collectors. A word is a maximal run of letters A–Z/a–z; everything else separates word...
An order report as a stream pipeline
Write OrderPipeline. The first number is a threshold; then come orders customer product quantity unitPrice until the end of input. Using streams only...
Comparator chains
Write a class Staff (name, department, salary, getters, toString → Lina(IT,9000)) and StaffSort, which reads name department salary lines and prints t...
Grouping with collectors
Write a class City (name, country, population in millions) and CityGroups, which reads name country millions lines and uses Collectors to print: 1. co...
Building rules from functional interfaces
Write TextRules. The first input is a minimum length; the rest are words. Write a method static List<String transform(List<String words, Predicate<Str...
Chapter 4 The Collections Framework: Lists, Stacks, Queues and Deques 9 labs
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...
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...
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...
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...
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...
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...
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...
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...
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
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...
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 —...
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...
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...
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...
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...
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). -...
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...
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
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...
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...
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...
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...
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...
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...
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...
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...
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
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...
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...
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...
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...
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...
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...
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...
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...
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
Minimum number of coins
Given k coin denominations (unlimited supply of each) and an amount, find the minimum number of coins whose values add up exactly to the amount, or re...
Longest common subsequence with reconstruction
Read two strings and print the length of their longest common subsequence (LCS) and one LCS. Fill the table dp[i][j] = LCS length of the first i chara...
Booking one room: which greedy rule is right?
One meeting room, n meeting requests name start end. Accept as many meetings as possible; two meetings are compatible if one ends before or exactly wh...
0/1 knapsack with the list of items
A backpack holds at most W kg. Each of n items has a weight and a value and is either taken or left (no fractions). Maximise the total value. Write Kn...
Edit distance (spell-checker distance)
The edit distance between two words is the fewest single-character insertions, deletions and substitutions that turn one into the other — the measure...
Longest increasing subsequence
Given n numbers, find the longest strictly increasing subsequence (elements in their original order, not necessarily adjacent) — e.g. the longest run...
Chapter 9 Sorting 9 labs
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...
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...
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...
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...
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...
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...
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...
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...
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
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...
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...
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...
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...
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...
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) —...
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...
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...
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
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...
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...
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...
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...
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...
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...
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...
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...
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
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...
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...
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...
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...
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...
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...
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...
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,...
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
Build an AVL Tree
Read an integer n, then n integer keys. Insert them in order into an initially empty AVL tree (duplicates are ignored). Then print the pre-order trave...
AVL Rotation Log
Read an integer n, then n integer keys, and insert them one by one into an initially empty AVL tree. After each insertion print one line: - Insert K:...
Balance factors and the four rotation cases
Write BalanceFactors. Insert the input keys into a plain BST (no rebalancing). Then print, in increasing key order, each node's height (a leaf has hei...
BST versus AVL on the same keys
Write AvlVersusBst. Read n and n keys. Insert them, in order, into a plain BST and into an AVL tree (store each node's height; after inserting, rebala...
A live leaderboard on an AVL tree with subtree sizes
Write AvlRanking: an AVL tree whose nodes store their height and the size of their subtree, used as a game leaderboard of distinct scores. Commands un...
How tall can an AVL tree be?
The AVL condition limits the height. Write AvlLimits: - minNodes(h) — the fewest nodes an AVL tree of height h can have: N(h) = 1 + N(h − 1) + N(h − 2...
Chapter 14 Hashing 6 labs
Linear Probing Table
Read the table size m, the number of keys n, and then n integer keys. Insert the keys in order into an empty hash table of size m using h(k) = Math.fl...
Separate Chaining with Rehashing
Read the initial number of buckets m, the number of keys n, and then n integer keys. Insert them in order into a separate-chaining hash table with h(k...
Linear versus quadratic probing
Write ProbingCompare. Read the table size m, then non-negative keys. Insert each key into two open-addressing tables with h(k) = k mod m: one with lin...
The equals/hashCode contract
Write two seat classes with fields row (String) and number (int): - BrokenSeat overrides equals only; - Seat overrides equals and hashCode (from the s...
Rabin–Karp: string search with a rolling hash
Write RabinKarp. The first line is a modulus p; the second line is the text; each following line is a pattern. For each pattern of length m compute it...
Good and bad hash functions
Write HashQuality with two hash functions for strings: - sumHash(s) — the sum of the character codes; - polyHash(s) — the polynomial hash h = 31·h + c...
Chapter 15 Graphs and Traversals 6 labs
Fewest hops: BFS shortest path
Read an undirected, unweighted graph and two vertices s and t, and print a path from s to t with the fewest edges. Input [code] Rules - Build adjacenc...
Course plan: Kahn's topological sort
Courses are numbered 0 … n − 1. A line u v means "course u must be taken before course v" (a directed edge u → v). Print an order in which all courses...
Connected components
Write Components. Read an undirected graph: n m, then m edges u v (vertices 0 … n − 1), then pairs a b to test. Using BFS (or DFS) from every not-yet-...
Finding a cycle in a directed graph with DFS colours
Tasks depend on each other: an edge u v means "u must be done before v". Write CycleFinder. Read n m and m directed edges. Run DFS from vertices 0, 1,...
Two teams: is the graph bipartite?
Some pairs of players refuse to be in the same team. Can everybody be split into two teams? Write TwoTeams. Read n m and m pairs u v that must be sepa...
Shortest way out of a maze with BFS
Write MazeBfs. Read rows cols and a maze: wall, . free cell, S start, E exit. Moves go up, down, left or right. A grid is a graph whose vertices are t...
Chapter 16 Weighted Graphs: Shortest Paths and Spanning Trees 6 labs
Dijkstra: distances from a source
Read a directed graph with non-negative integer weights and a source s, and print the shortest distance from s to every vertex. Input [code] Parallel...
Kruskal with union–find
Read an undirected weighted graph and build a minimum spanning forest with Kruskal's algorithm and a union–find structure (union by size or rank, and...
Prim's minimum spanning tree
A campus wants to connect n buildings with cable as cheaply as possible. Write PrimMst. Read n m and m undirected edges u v weight. Starting from vert...
Bellman–Ford: shortest paths with negative edges
Dijkstra's algorithm fails when edges can be negative (a refund, a downhill energy gain, an exchange-rate advantage). Write BellmanFord. Read n m sour...
Floyd–Warshall: all pairs, with routes
Write FloydWarshall. Read n m and m directed edges u v weight, then pairs a b until the end of input. Compute the shortest distance between every pair...
Project schedule: the critical path
A project has n tasks with durations in days, and m dependencies u v meaning "task u must finish before task v starts" (a weighted DAG). Write Project...