ICS4U computer science help, from recursion to the team project

# Rank a playlist with a recursive merge sort on objects (ours)

class Track:
    def __init__(self, title, plays):
        self.title = title
        self.plays = plays

    def comes_before(self, other):
        """More plays first; equal plays fall back to title order."""
        if self.plays != other.plays:
            return self.plays > other.plays
        return self.title < other.title


def merge_sort(tracks, counter):
    """Return a new sorted list. counter[0] counts comparisons."""
    if len(tracks) <= 1:                  # base case: already sorted
        return tracks[:]
    mid = len(tracks) // 2
    left = merge_sort(tracks[:mid], counter)    # recursive case
    right = merge_sort(tracks[mid:], counter)
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        counter[0] += 1
        if right[j].comes_before(left[i]):
            merged.append(right[j])
            j += 1
        else:                             # ties keep the left one: stable
            merged.append(left[i])
            i += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged


playlist = [Track("Northern Lights", 41), Track("Portage", 17),
            Track("Lake Effect", 41), Track("Snowbank", 8),
            Track("Ferry Line", 23), Track("Big Smoke", 17),
            Track("Muskoka", 30), Track("Algonquin", 23)]
count = [0]
for t in merge_sort(playlist, count):
    print(t.plays, t.title)
print("Comparisons:", count[0])

Output: eight lines from 41 Lake Effect down to 8 Snowbank, then Comparisons: 15. Lake Effect comes before Northern Lights because their play counts tie at 41 and L comes before N.

// Rank a playlist with a recursive merge sort on objects (ours)
import java.util.Arrays;

class Track implements Comparable<Track> {
    private final String title;
    private final int plays;

    public Track(String title, int plays) {
        this.title = title;
        this.plays = plays;
    }

    // Negative means this track comes first: more plays, then title order.
    @Override
    public int compareTo(Track other) {
        if (plays != other.plays) {
            return Integer.compare(other.plays, plays);
        }
        return title.compareTo(other.title);
    }

    @Override
    public String toString() {
        return plays + " " + title;
    }
}

public class Ranking {
    static int comparisons = 0;

    static Track[] mergeSort(Track[] tracks) {
        if (tracks.length <= 1) {                 // base case
            return tracks;
        }
        int mid = tracks.length / 2;
        Track[] left = mergeSort(Arrays.copyOfRange(tracks, 0, mid));
        Track[] right = mergeSort(Arrays.copyOfRange(tracks, mid, tracks.length));
        Track[] merged = new Track[tracks.length];
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            comparisons++;
            if (right[j].compareTo(left[i]) < 0) {
                merged[k++] = right[j++];
            } else {                              // ties keep the left one
                merged[k++] = left[i++];
            }
        }
        while (i < left.length) merged[k++] = left[i++];
        while (j < right.length) merged[k++] = right[j++];
        return merged;
    }

    public static void main(String[] args) {
        Track[] playlist = {
            new Track("Northern Lights", 41), new Track("Portage", 17),
            new Track("Lake Effect", 41), new Track("Snowbank", 8),
            new Track("Ferry Line", 23), new Track("Big Smoke", 17),
            new Track("Muskoka", 30), new Track("Algonquin", 23)
        };
        for (Track t : mergeSort(playlist)) {
            System.out.println(t);
        }
        System.out.println("Comparisons: " + comparisons);
    }
}

Same nine lines. Java keeps the fields private and exposes only compareTo and toString, which is encapsulation in practice; Python leaves the fields open and relies on convention.

def mystery(n):
    if n == 0:
        return 0
    return n % 10 + mystery(n // 10)

print(mystery(4096))

What is printed? Write out each call and what it returns.

static int countDown(int n) {
    if (n == 0) return 0;
    return 1 + countDown(n - 2);
}
// called as countDown(6), then countDown(7)

What does countDown(6) return? What happens with countDown(7), and why? Change one line so that both calls finish.

int big = 2147483647;
big = big + 1;
System.out.println(big);

What is printed? Name the limit involved and one way to avoid it.

print(0.1 + 0.2 == 0.3)

True or False? Explain, and write a comparison that gives the answer a person would expect.

class Shape { String name() { return "shape"; } }
class Circle extends Shape {
    @Override String name() { return "circle"; }
}
Shape s = new Circle();
System.out.println(s.name());

What is printed? Which ICS4U term describes what happened? Then: what would change if Circle had a method name(String prefix) instead?

grid = [[3, 1, 4], [1, 5, 9], [2, 6, 5]]
total = 0
for r in range(3):
    total += grid[r][2 - r]
print(total)

What is printed? Which cells of the grid are added?

def binary_search(values, target):
    lo, hi = 0, len(values) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if values[mid] == target:
            return mid
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

print(binary_search([9, 2, 7, 4, 5], 9))

What is printed, and why is it wrong? State the precondition this function depends on.

count = 0
for i in range(n):
    for j in range(i):
        count += 1

For n = 10, what is count at the end? Give a formula in n, and say how count changes when n doubles.