Assignment 5

Starter pack: a5-starter.zip — download, open in IntelliJ, and fill in the TODO stubs.

Submission: Upload a single .zip file named u{Student ID}.zip (e.g., u6880517.zip) to MS Teams Classroom.

Typesetting. For written questions, typeset your answers and produce a PDF named hw5.pdf; place it at the top level of your zip. We do not accept scanned or handwritten submissions. Proper typesetting means math symbols — summations, fractions, exponents, fractions — are rendered with correct notation, bounds, and spacing, as you would see in a textbook.

Coding logistics. Your submission is graded by a script before any human reviews it. The script is unforgiving, so follow these instructions exactly:

  • Name each source file exactly as specified in the task and place it at the top level of your zip — no subdirectories.
  • Use the exact function, class, and interface names given.

AI Usage Policy. Before you begin, remind yourself of the AI usage policy and guideline on the course website. In brief: Don’t offload your learning and thinking to AI. Use AI to help you learn.

Missing Tile (20 pts)

Save your work in MissingTile.kt.

There are four ways an L-shaped triomino can be arranged. Labeled by the missing corner, the four arrangements are:

Four L-shaped triomino arrangements labeled by their missing corner: NE, SE, SW, NW

You have seen this theorem in Discrete Math:

Theorem. Any \(2^n\)-by-\(2^n\) grid with one painted cell can be tiled using L-shaped triominoes such that the entire grid is covered, no two triominoes overlap, and no triomino covers the painted cell.

Subtask I (6 pts) — written. Prove this theorem in your own words, by induction on \(n\).

Subtask II (14 pts) — implementation. Implement the function

fun tileGrid(board: Grid)

that tiles the given board using L-shaped triominoes. The Grid interface is provided in the starter pack:

interface Grid {
    // Width/height of the square grid; coordinates are 0..size()-1.
    fun size(): Int
    fun getPaintedCellX(): Int
    fun getPaintedCellY(): Int
    // Place a triomino whose missing corner is at (x, y).
    // Orientation: 0 = missing NE, 1 = missing SE, 2 = missing SW, 3 = missing NW.
    // Returns true on success; false if the placement conflicts with an existing tile
    // or the painted cell.
    fun setTile(x: Int, y: Int, orientation: Int): Boolean
    fun isFullyTiled(): Boolean
}

For example, a \(4 \times 4\) board with the painted cell at \((x=3, y=1)\) can be tiled by calling:

A 4-by-4 grid showing a complete L-triomino tiling with a painted cell at (3,1) 
board.setTile(1, 1, 1)   // missing SE corner at (1,1)
board.setTile(3, 1, 1)
board.setTile(2, 1, 0)
board.setTile(1, 2, 0)
board.setTile(2, 2, 3)

A test driver implementing Grid is provided in the starter pack; do not modify it.

Performance. Your function must return within 2 seconds for grids up to \(1024 \times 1024\).

(Hint: To tile a \(2^k \times 2^k\) grid, recursively tile four \(2^{k-1} \times 2^{k-1}\) subgrids, each with its own painted cell.)

Tail Sum of Squares (10 pts)

Written question — answer in your PDF.

Consider the following Kotlin code:

fun sumHelper(n: Int, a: Int): Int =
    if (n == 0) a else sumHelper(n - 1, a + n * n)

fun sumSqr(n: Int): Int = sumHelper(n, 0)

Prove that for \(n \geq 1\), sumSqr(n) returns \(1^2 + 2^2 + 3^2 + \cdots + n^2\). To prove this, use induction to show that sumHelper computes the right thing. (Hint: How did we prove factHelper in class?)

Mysterious Function (10 pts)

Written question — answer in your PDF.

Consider the following Kotlin function foo, which takes an integer \(n \geq 1\) and returns a Pair of integers:

fun foo(n: Int): Pair<Int, Int> {
    require(n >= 1)
    if (n == 1) return Pair(1, 2)
    val (p, q) = foo(n - 1)
    return Pair(q + p * n * (n + 1), q * n * (n + 1))
}

Prove that for \(n \geq 1\), foo(n) returns \((p, q)\) such that

\(\frac{p}{q} = 1 - \frac{1}{n+1}.\)

(Hint: induction on \(n\).)

Midway Tower of Hanoi (15 pts)

Save your work in Midway.kt.

In Tower of Hanoi, you are given \(N\) disks labeled \(0, 1, \dots, N-1\) by size. Three pegs — Peg 0, Peg 1, and Peg 2 — hold the disks. Initially all disks sit on Peg 0, smallest on top. The goal is to move all disks to Peg 1, moving one disk at a time, never placing a larger disk on a smaller one.

The following Kotlin code prints the optimal sequence of moves:

fun solveHanoi(n: Int, fromPeg: Int, toPeg: Int, auxPeg: Int) {
    if (n > 0) {
        solveHanoi(n - 1, fromPeg, auxPeg, toPeg)
        println("Move disk ${n - 1} from Peg $fromPeg to Peg $toPeg")
        solveHanoi(n - 1, auxPeg, toPeg, fromPeg)
    }
}
// entry point: solveHanoi(n, 0, 1, 2)

Following these instructions uses \(2^N - 1\) moves in total. Below is a trace of all configurations for \(N = 3\) disks (left to right, step 0 through step 7):

Hanoi step 0Hanoi step 1Hanoi step 2Hanoi step 3Hanoi step 4Hanoi step 5Hanoi step 6Hanoi step 7

Subtask I (5 pts) — written. Prove by mathematical induction that solveHanoi(n, ...) generates exactly \(2^n - 1\) lines of output.

Subtask II (10 pts) — implementation. The monks have been following the computer-generated instructions exactly. Given the current disk configuration, implement a function

fun stepsRemaining(diskPos: IntArray): Long

that returns the number of steps left before completing the task. diskPos[i] \(\in \{0,1,2\}\) gives the peg where disk \(i\) currently sits. You are guaranteed \(0 \leq\) diskPos.size \(\leq 63\).

For example:

  • stepsRemaining(intArrayOf(0)) \(= 1\)
  • stepsRemaining(intArrayOf(2, 2, 1)) \(= 3\)
  • stepsRemaining(intArrayOf(2, 2, 1, 1, 2, 2, 1)) \(= 51\)

Performance. Your function must return within 1 second without generating the full instruction sequence.

(Hint: Solve intArrayOf(2, 2, 0) and intArrayOf(1, 2, 0) by hand. How many moves are made before the largest disk moves?)

Higher-Order Merge (10 pts)

Save your work in MultiwayMerge.kt.

You have \(k\) ArrayDeque<Int> instances, each sorted from small to large (duplicates allowed). Implement a function

fun mergeAll(lists: Array<ArrayDeque<Int>>): ArrayDeque<Int>

that returns a single ArrayDeque<Int> containing all elements in sorted order.

Your algorithm must run in \(O(N \log k)\) time, where \(N\) is the total number of elements and \(k =\) lists.size. Note: accessing an ArrayDeque at the front or back is \(O(1)\); accessing anywhere else costs \(O(\text{distance from end})\).

(Hint: Keep a PriorityQueue whose size never exceeds \(k\), storing the lists themselves ranked by their current front element.)

A Binary Tree Representation

The following three problems use a binary tree node class provided in BinaryTreeNode.kt from the starter pack:

class BinaryTreeNode(val key: Int, var left: BinaryTreeNode? = null, var right: BinaryTreeNode? = null)

An empty tree is represented by null. A single leaf: BinaryTreeNode(10001). A node with children: BinaryTreeNode(512, ll, rr) where ll and rr are the left and right subtrees. You may also assign T.left and T.right directly.

Let’s Grow a Tree (10 pts)

Save your work in MakeTree.kt.

Subtask I (7 pts). Implement a function

fun buildBST(keys: IntArray): BinaryTreeNode?

that takes an array of integer keys and returns a balanced binary search tree. If \(n =\) keys.size, your algorithm must run in \(O(n \log n)\) time and produce a BST no deeper than \(1 + \lfloor \log_2 n \rfloor\) levels.

Subtask II (3 pts) — written. Analyze the running time of your algorithm and argue why the resulting tree meets the depth requirement.

Uprooting (15 pts)

Save your work in Uproot.kt.

The parent-mapping representation of a tree stores, for each node, the key of its parent. Concretely it is a Map<Int, Int> where looking up a key yields the key of its parent. The root is the one key that appears as a value but never as a lookup key. Below is an example tree and its corresponding map:

A binary tree with root 1, children 20 and 9; 20 has child 14; 9 has children 2 and 18 
val p = hashMapOf(
    20 to 1,
    9  to 1,
    14 to 20,
    2  to 9,
    18 to 9
)

Subtask I (7 pts). Implement:

fun treeToParentMap(t: BinaryTreeNode): HashMap<Int, Int>

that takes a binary tree (not necessarily a BST) and returns its parent-mapping representation.

Subtask II (8 pts). Implement:

fun parentMapToTree(map: Map<Int, Int>): BinaryTreeNode?

that takes a parent-mapping map and returns the corresponding BinaryTreeNode tree. The parent-mapping has no notion of left vs. right; you may freely assign children to either side. The input is guaranteed to encode a valid binary tree (but not necessarily a BST).

Performance. On inputs with around 2,000 nodes, both functions must return within 2 seconds.

Decorative Tree (10 pts)

Save your work in Decor.kt.

Given the post-order and in-order traversal sequences of a binary tree, reconstruct the tree. The traversal sequences are produced by:

fun postList(t: BinaryTreeNode?): List<Int> =
    if (t == null) emptyList()
    else postList(t.left) + postList(t.right) + listOf(t.key)

fun inList(t: BinaryTreeNode?): List<Int> =
    if (t == null) emptyList()
    else inList(t.left) + listOf(t.key) + inList(t.right)

For example, the tree below yields:

A binary tree with root a; left child x (which has left child w and right child t); right child z
TraversalSequence
post-order\([w,\, t,\, x,\, z,\, a]\)
in-order\([w,\, x,\, t,\, a,\, z]\)

All keys are unique. Implement:

fun mkTree(postOrder: List<Int>, inOrder: List<Int>): BinaryTreeNode?

For full credit, your algorithm must run in \(O(n)\) time, where \(n\) is the length of the traversal sequences.

(Hint: A Map can speed up locating the root within the in-order sequence. Once the root position is known in both sequences, can you determine the sizes of the left and right subtrees in \(O(1)\)?)