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 · 32 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...
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...
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...
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...
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 —...
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...
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...
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...
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...
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...
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...
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...
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:...
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...
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...
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...