Assignment 2

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

Typesetting. For written questions, typeset your answers and produce a PDF named hw2.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, 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, 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.

Inside Zeros (4 pts)

Trailing zeros are zeros at the rightmost digits of a number. Inside zeros are all the other zeros — those that appear between non-zero digits. The number 102400 has 2 trailing zeros and 1 inside zero, for a total of 3 zeros.

Recall that \(n! = n \times (n-1)!\) for \(n > 0\), and \(0! = 1\).

Implement the function below in FacInnerZero.kt:

fun zeroInsideFac(n: Int): Int {
    // your code here
}

zeroInsideFac(n) takes \(n \ge 0\) and returns the number of zeros inside the value of \(n!\). Your solution only needs to handle \(0 \le n \le 1024\).

Examples:

zeroInsideFac(5)  == 0    // 5!  = 120              → no inside zeros
zeroInsideFac(16) == 1    // 16! = 20922789888000   → one inside zero
zeroInsideFac(37) == 4

Fibonacci Growth (12 pts)

In class, our ArrayList implementation uses the array-doubling trick, which doubles the capacity of the array every time it becomes full. Our analysis shows that starting with an array of capacity 1 with no data items initially, appending \(n\) data items needs at most \(2n\) copying steps.

This problem involves a fancier array-growing scheme. Recall the Fibonacci sequence from Discrete Math:

with \(F_1 = F_2 = 1\). In our new scheme, the capacity of the underlying array strictly follows the Fibonacci sequence. Initially the capacity is \(F_2 = 1\). When full, we grow the capacity to \(F_3 = 2\). When full again, we grow to \(F_4 = 3\), then to \(F_5 = 5\), then to \(F_6 = 8\), and so on.

Amazingly, this turns out to work quite well! You will prove a few facts about Fibonacci numbers and apply them to analyze the total copying steps.

(i) Using mathematical induction, prove that for \(n \geq 1\),

You are expected to write a solid, rigorous proof based on the definition of Fibonacci numbers above.

(ii) Prove, e.g., using a direct proof, that for \(n \geq 1\),

(iii) Suppose we start with no data items in our list. If we use the Fibonacci growth scheme and add \(n\) data items, give a detailed analysis of the total number of copy steps (like we did in class). State your argument carefully. To simplify matters, you may assume that \(n = F_r + 1\) for some integer \(r \geq 2\).

Deque (32 pts)

A double-ended queue (deque, pronounced “deck”) is a sequence container that can be efficiently expanded or contracted at either end.

The Deque Interface

Place the interface below at the top of Deque.kt, which both implementations in this problem must import and implement.

interface Deque<T> {
    // Adds an item to the front of the deque.
    fun addFirst(item: T)

    // Adds an item to the back of the deque.
    fun addLast(item: T)

    // Returns true if the deque is empty, false otherwise.
    fun isEmpty(): Boolean

    // Returns the number of items in the deque.
    fun size(): Int

    // Returns a string showing items from first to last, separated by a space.
    override fun toString(): String

    // Removes and returns the item at the front; returns null if empty.
    fun removeFirst(): T?

    // Removes and returns the item at the back; returns null if empty.
    fun removeLast(): T?

    // Returns the item at the given index (0 = front), without altering the deque.
    // Returns null if no such index exists.
    fun get(index: Int): T?
}

Your class should accept any generic type, not just integers.

Part I — LinkedListDeque (16 pts)

Save your work in LinkedListDeque.kt.

Implement a LinkedListDeque<T> class that implements Deque<T> using a doubly linked list. Your implementation must satisfy the following rules:

• addFirst, addLast, removeFirst, and removeLast must not involve any looping or recursion — each must run in constant time, independent of the deque’s size.
• get must use iteration, not recursion.
• size must run in constant time.
• You must not maintain dangling references to removed nodes. If you add 1,000 items and then remove 999, memory usage should reflect a deque of size 1, not 1,000.
• Use the circular sentinel design.

Implement all methods from the Deque<T> interface, together with the following constructors:

// Creates an empty linked list deque.
class LinkedListDeque<T>() : Deque<T> { ... }

// Creates a deep copy of other.
constructor(other: LinkedListDeque<T>)

A deep copy means a fully independent LinkedListDeque with the same items. Mutating other after copying must not affect the copy, and vice versa.

Part II — ArrayDeque (16 pts)

Save your work in ArrayDeque.kt.

Implement an ArrayDeque<T> class that implements Deque<T> using a fixed-size array as the core data structure. Your implementation must satisfy the following rules:

• addFirst, addLast, removeFirst, and removeLast must run in constant time, except during resize operations.
• get and size must run in constant time.
• The starting capacity of your array must be 8.
• Memory usage must be proportional to the number of items at all times. For example, adding 10,000 items and then removing 9,999 must not leave an array of length ~10,000 allocated.
• For arrays of length 16 or more, the utilization ratio (used cells / total capacity) must always be at least 25 %. For smaller arrays, the ratio may be arbitrarily low.

Implement all methods from the Deque<T> interface, together with the following constructors:

// Creates an empty array deque.
class ArrayDeque<T>() : Deque<T> { ... }

// Creates a deep copy of other.
constructor(other: ArrayDeque<T>)

A deep copy is fully independent: mutating other after copying must not affect the copy.