Assignment 1

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

This assignment refreshes your Kotlin programming skills and introduces mathematical running-time analysis. Use Kotlin 1.9 or later. Write helper functions as needed; prioritize code clarity.

Typesetting. For written questions, typeset your answers and produce a PDF named hw1.pdf; place it at the top level of your zip. We do not accept scanned or handwritten submissions. Proper typesetting means math symbols — summations, integrals, fractions, inequalities — 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 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.

Math Typesetting Practice (4 pts)

Throughout the term, you will neatly typeset mathematical solutions. Reproduce the proof excerpt below. This warm-up builds fluency with common notation: summations, integrals, fractions, and inequalities. Consult the course resources page for tool options and references.

Proposition. Let \(H_n = \displaystyle\sum_{k=1}^{n} \dfrac{1}{k}\). Then, for all \(n \ge 1\),

Proof. Since \(f(x) = 1/x\) is decreasing on \((0, \infty)\), for each integer \(k \ge 1\):

Summing over \(k = 1, \ldots, n\) and using

we have that

Big-O: The Basics (8 pts)

This problem has you working directly with the formal definition of Big-O.

(1) Show, using the formal definition of Big-O, that \(f(n) = n\) is \(O(n \log n)\).

(2) Prove the following claim carefully:

Claim. If \(d(n)\) is \(O(f(n))\) and \(e(n)\) is \(O(g(n))\), then the product \(d(n) \cdot e(n)\) is \(O(f(n) \cdot g(n))\).

(3) Suppose fnE(i: Int, num: Int) always runs in exactly \(1000 \cdot i\) steps regardless of num. What is the running time of fnA in Big-O as a function of \(n\) (the length of s)? Assume array length can be read in constant time.

fun fnA(s: IntArray) {
    val n = s.size
    for (i in 0 until n) {
        fnE(i, s[i])
    }
}

(4) Show that \(h(n) = 16n^2 + 11n^4 + 0.1n^5\) is not \(O(n^4)\).

Roman to Number (4 pts)

Roman numerals are built from seven symbols. When a smaller-valued symbol appears immediately before a larger one, it is subtracted rather than added (e.g., IV = 4, IX = 9, XL = 40, XC = 90, CD = 400, CM = 900); otherwise symbols are additive.

Implement the function below in Roman.kt:

fun romanToInt(s: String): Int {
    // your code here
}

Examples:

romanToInt("I")       == 1
romanToInt("VII")     == 7
romanToInt("MCMLIV")  == 1954
romanToInt("MCMXC")   == 1990

Subselection (4 pts)

Implement both functions below in Subsel.kt:

inline fun <reified T> takeEvery(a: Array<T>, stride: Int, beginWith: Int): Array<T> {
    // your code here
}

inline fun <reified T> takeEvery(a: Array<T>, stride: Int): Array<T> {
    // your code here
}

takeEvery(a, stride, beginWith) returns a new array containing a[beginWith], a[beginWith + stride], a[beginWith + 2*stride], … stopping as soon as the index falls outside a. takeEvery(a, stride) behaves identically to takeEvery(a, stride, 0). The output may be empty; stride may be positive or negative, but is never zero. Do not use any built-in collection types — work directly with arrays.

Examples:

takeEvery(arrayOf(1, 2, 3, 4), 2)                    == [1, 3]
takeEvery(arrayOf(2, 7, 1, 8, 4, 5), 3, 2)           == [1, 5]
takeEvery(arrayOf(3, 1, 4, 5, 9, 2, 6, 5), -1, 5)   == [2, 9, 5, 4, 1, 3]
takeEvery(arrayOf("a", "b", "c", "d"), 2)            == ["a", "c"]

How Long Does This Take? (4 pts)

For each function below, determine the running time in \(\Theta\) notation as a function of \(n\). Show your work — we care more about the reasoning than the final answer.

fun programA(n: Int) {
    var prod = 1L
    var c = n
    while (c > 0) {
        prod *= c
        c /= 2
    }
}

fun programB(n: Int) {
    var prod = 1L
    var c = 1
    while (c < n) {
        prod *= c
        c *= 3
    }
}

Best Case and Worst Case (6 pts)

So far we have focused almost exclusively on worst-case running time. For each method below, determine both the best-case and worst-case running times in \(\Theta\) notation. Justify your answers.

(1)

fun method1(array: IntArray) {
    val n = array.size
    for (index in 0 until n - 1) {
        val marker = helperMethod1(array, index, n - 1)
        swap(array, marker, index)
    }
}

fun swap(array: IntArray, i: Int, j: Int) {
    val temp = array[i]; array[i] = array[j]; array[j] = temp
}

fun helperMethod1(array: IntArray, first: Int, last: Int): Int {
    var max = array[first]
    var indexOfMax = first
    for (i in last downTo first + 1) {
        if (array[i] > max) { max = array[i]; indexOfMax = i }
    }
    return indexOfMax
}

(2)

fun method2(array: IntArray, key: Int): Boolean {
    for (x in array) {
        if (x == key) return true
    }
    return false
}

(3)

fun method3(array: IntArray): Double {
    val n = array.size
    var sum = 0.0
    for (pass in 100 downTo 4) {
        for (index in 0 until 2 * n) {
            var count = 4 * n
            while (count > 0) {
                sum += array[index / 2].toDouble() / count
                count /= 2
            }
        }
    }
    return sum
}

Two Sum (4 pts)

Given an integer array nums and a target integer \(k\), return the indices \((i, j)\) with \(i < j\) such that

You may assume exactly one valid solution exists.

Examples:

Input:  nums = [2, 7, 11, 15],  k = 9
Output: Pair(0, 1)     // 2 + 7 = 9

Input:  nums = [3, 2, 4],  k = 6
Output: Pair(1, 2)     // 2 + 4 = 6

Part I (2 pts). Implement the function below in TwoSum.kt:

fun twoSum(nums: IntArray, k: Int): Pair<Int, Int> {
    // your code here
}

Part II (2 pts). What is the worst-case running time of your solution in \(\Theta\) notation, as a function of \(n = \texttt{nums.size}\)? Show your analysis.

Subarray Sum Equals K (4 pts)

Given nums and an integer \(k\), return the number of contiguous subarrays whose elements sum to exactly \(k\).

Example:

Input:  nums = [1, 1, 1],  k = 2
Output: 2     // subarrays [1,1] starting at index 0 and index 1

Part I (2 pts). Implement the function below in SubarraySum.kt:

fun subarraySum(nums: IntArray, k: Int): Int {
    // your code here
}

Part II (2 pts). What is the worst-case running time of your solution in \(\Theta\) notation, as a function of \(n = \texttt{nums.size}\)? Show your analysis.

Windowed Sum (6 pts)

Given an integer array a and a non-negative integer w, replace each element a[i] in place with the sum of a[i] through a[i + w], but only if a[i] is positive. If the window extends past the end of the array, sum only the available elements. Non-positive elements are left unchanged.

Examples:

Input:  a = [1, 2, -3, 4, 5, 4],  w = 3
Output: a = [4, 8, -3, 13, 9, 4]
//  a[0] =  1 > 0 → 1 + 2 + (−3) + 4     = 4
//  a[1] =  2 > 0 → 2 + (−3) + 4 + 5     = 8
//  a[2] = −3 ≤ 0 → unchanged
//  a[3] =  4 > 0 → 4 + 5 + 4             = 13  (window hits end)
//  a[4] =  5 > 0 → 5 + 4                 = 9   (window hits end)
//  a[5] =  4 > 0 → 4                     = 4   (no elements after)

Input:  a = [1, -1, -1, 10, 5, -1],  w = 2
Output: a = [-1, -1, -1, 14, 4, -1]
//  a[0] =  1 > 0 → 1 + (−1) + (−1)      = −1
//  a[1] = −1 ≤ 0 → unchanged
//  a[2] = −1 ≤ 0 → unchanged
//  a[3] = 10 > 0 → 10 + 5 + (−1)        = 14
//  a[4] =  5 > 0 → 5 + (−1)             = 4
//  a[5] = −1 ≤ 0 → unchanged

Constraints: \(1 \le w \le m\)

Part I (2 pts). Implement the function below in WindowedSum.kt:

fun windowPosSum(a: IntArray, w: Int) {
    // your code here
}

Part II (2 pts). What are the worst-case and best-case running times of your solution in \(\Theta\) notation, as a function of \(m = \texttt{a.size}\)? Show your analysis.

Part III (2pts). Describe what inputs trigger the worst-case and best-case running times.

Happy Numbers (8 pts)

A number is happy if repeatedly replacing it with the sum of the squares of its digits eventually reaches 1; it is sad if the process reaches 4 instead. Every positive integer is one or the other.

For example, 19 is happy: \(1^2 + 9^2 = 82\), then \(8^2 + 2^2 = 68\), then \(6^2 + 8^2 = 100\), then \(1^2 + 0^2 + 0^2 = 1\). On the other hand, 145 is sad: \(1^2 + 4^2 + 5^2 = 42\), then \(4^2 + 2^2 = 20\), then \(2^2 + 0^2 = 4\).

All three functions below belong in Happy.kt.

(1) Implement sumOfDigitsSquared, which returns the sum of the squares of the digits of n.

fun sumOfDigitsSquared(n: Long): Long {
    // your code here
}

sumOfDigitsSquared(7)   == 49
sumOfDigitsSquared(145) == 42     // 1² + 4² + 5²
sumOfDigitsSquared(199) == 163    // 1² + 9² + 9²

(2) Using your answer to (1), implement isHappy.

fun isHappy(n: Long): Boolean {
    // your code here
}

isHappy(100)  == true
isHappy(111)  == false
isHappy(1234) == false
isHappy(989)  == true

We will test isHappy with \(n\) up to \(10^6\). Avoid recursion — it will not fare well for large inputs.

(3) Implement firstK, which returns an array of exactly k longs containing the first k happy numbers in ascending order.

fun firstK(k: Int): LongArray {
    // your code here
}

firstK(11) == [1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49]

We will test this function with \(k \le 20{,}000{,}000\).

Hidden String (4 pts)

We say that string t hides inside string s if every character of t appears in s in order, with arbitrary other characters possibly interleaved. For example, "cat" hides inside "afciurfdasctxz" (the matching positions are c … a … t …), but does not hide inside "xaytpc" because the characters appear out of order. Matching is case-sensitive.

Implement the function below in A1_<StudentID>.kt:

fun isHidden(s: String, t: String): Boolean {
    // your code here
}

Examples:

isHidden("welcometothehotelcalifornia", "melon") == true
isHidden("welcometothehotelcalifornia", "space") == false
isHidden("TQ89MnQU3IC7t6", "MUIC")              == true
isHidden("VhHTdipc07", "htc")                   == false
isHidden("VhHTdipc07", "hTc")                   == true

Halving Sum (4 pts)

Consider the following algorithm for summing \(n\) numbers, where \(n = 2^k\) for some non-negative integer \(k\):

def hsum(X):   # assume len(X) is a power of two
    while len(X) > 1:
        (1) allocate Y as an array of length len(X) / 2
        (2) fill Y so that Y[i] = X[2i] + X[2i+1]  for i = 0, 1, ..., len(X)/2 − 1
        (3) X = Y
    return X[0]

Part I (2 pts). Let \(z = \texttt{len(X)}\) at the start of one iteration. Express the work done in steps (1)–(3) of that iteration as a function of \(z\), using the cost model below. Do not use Big-O; give an exact answer in terms of \(k_1\) and \(k_2\).

• Allocating an array of length \(z\) costs \(k_1 \cdot z\).
• Each arithmetic operation, array read, or array write costs \(k_2\).

Your answer should have the form \(\bigl(\;\cdot\;\bigr) z + \bigl(\;\cdot\;\bigr)\).

Part II (2 pts). Using Part I, derive the total running time of hsum on an input of length \(n\). Show your work. You may benefit from the geometric sum formula.

Recursive Code (6 pts)

For each of the following functions:

(1) Describe how you will measure the problem size in terms of the input parameters. For example, “the input size is measured by the variable \(n\)”, or “the input size is measured by the length of array xs”.

(2) Write a recurrence relation representing its running time. Show how you obtain the recurrence.

(3) Indicate what your recurrence solves to (by looking up the recurrence in our table).

// assume xs.size is a power of 2
fun halvingSum(xs: IntArray): Int {
    if (xs.size == 1) return xs[0]
    else {
        val ys = IntArray(xs.size / 2)
        for (i in ys.indices)
            ys[i] = xs[2 * i] + xs[2 * i + 1]
        return halvingSum(ys)
    }
}

fun anotherSum(xs: IntArray): Int {
    if (xs.size == 1) return xs[0]
    else {
        val ys = xs.copyOfRange(1, xs.size)
        return xs[0] + anotherSum(ys)
    }
}

fun prefixSum(xs: IntArray): IntArray {
    if (xs.size == 1) return xs
    else {
        val n = xs.size
        var left = xs.copyOfRange(0, n / 2)
        left = prefixSum(left)
        var right = xs.copyOfRange(n / 2, n)
        right = prefixSum(right)
        val ps = IntArray(xs.size)
        val halfSum = left[left.size - 1]
        for (i in 0 until n / 2) { ps[i] = left[i] }
        for (i in n / 2 until n) { ps[i] = right[i - n / 2] + halfSum }
        return ps
    }
}

Counting Dashes (4 pts)

Consider the following program:

fun printRuler(n: Int) {
    if (n > 0) {
        printRuler(n - 1)
        // print n dashes
        for (i in 0 until n) print('-')
        println()
        // --------------
        printRuler(n - 1)
    }
}

We would like to know the total number of dashes printed for a given \(n\). If we write a recurrence for that, we get

where the additive \(n\) term stems from the fact that we print exactly \(n\) dashes in that function call.

It may seem hopeless to try to solve this recurrence directly, but recall that the number of instructions taken to solve Tower of Hanoi on \(n\) discs is given by the recurrence

As you showed in a previous assignment, \(f(n)\) has a closed form of \(f(n) = 2^n - 1\).

The two recurrences are strikingly similar. In this problem, we’ll analyze \(g(n)\) using our knowledge of \(f(n)\). Since \(f(n)\) and \(g(n)\) have similar recurrences, differing only in an \(n\) term, we’re going to guess that

The following steps will guide you through determining the values of \(a\), \(b\), and \(c\) — and verifying that our guess indeed works out. Clearly show your work.

(i) We’ll first figure out the value of \(c\). What do you get when plugging in \(n = 0\) into equation (1)? It helps to remember that \(f(0) = g(0) = 0\). (Hint: \(c\) should be \(0\).)

(ii) To figure out the values of \(a\) and \(b\), plug \(g(n)\) from equation (1) into the recurrence \(g(n) = 2g(n-1) + n\). You should be able to write it as

and solve for \(a\) and \(b\) such that \(P = 0\) and \(Q = 0\).

Keep in mind: Because \(f(n) = 2f(n-1) + 1\), we know that \(f(n) - 2f(n-1) = 1\).

(iii) Derive a closed form for \(g(n)\).

(iv) Use induction to verify that your closed form for \(g(n)\) actually works.

Loop Detection (6 pts)

Recall the IntNode class from lecture:

class IntNode(var head: Int, var next: IntNode? = null)

A linked list normally terminates at a node whose next is null. But if some node’s next pointer points back to an earlier node in the chain, the list contains a loop — following next forever would cycle through the same nodes repeatedly.

Your task is to detect whether a given list has a loop and, if so, report the loop’s length (the number of nodes in the cycle).

What to return? Use the following sealed class, which you will place at the top of LoopDetect.kt:

sealed class LoopResult
object NoLoop : LoopResult()
data class Loop(val length: Int) : LoopResult()

(i) Implement the function below in LoopDetect.kt:

fun detectLoop(list: IntNode?): LoopResult {
    // your code here
}

Examples. Given the setup:

val a = IntNode(1)
val b = IntNode(2)
val c = IntNode(3)
val d = IntNode(4)
a.next = b; b.next = c; c.next = d

• With d.next = null: detectLoop(a) → NoLoop
• With d.next = b (loop through b → c → d → b): detectLoop(a) → Loop(3)
• With d.next = a (loop through all four nodes): detectLoop(a) → Loop(4)

(ii) What’s the running time of your code as a function of the number of nodes present in the input list? Show your work in your PDF write-up.