---
tags: cs1101s
---

# CS1101S Studio S10 (T08C)

## Searching and Sorting II; Memoization

### Question 2
The following function, `bubblesort_array`, is an implementation of the ***Bubble Sort*** algorithm to sort an array of numbers into ascending order.

function bubblesort_array(A) {
    const len = array_length(A);
    
    for (let i = len - 1; i >= 1; i = i - 1) {
        for (let j = 0; j < i; j = j + 1) {
            if (A[j] > A[j + 1]) {
                const temp = A[j];
                A[j] = A[j + 1];
                A[j + 1] = temp;
            } else { }
        }
    }
}

What is the order of growth of its runtime for an input array of *n* elements?

theta(n^2)

Write the function, `bubblesort_list`, that takes as argument a list of numbers and uses the bubble sort algorithm to sort the list in ascending order. Your function **must not create any new pair or array**, and **must not use the function `set_tail`**. Its runtime must have the same order of growth as that of `bubblesort_array`.

function bubblesort_list(L) {
    const len = length(L);
    for (let i = len - 1; i >= 1; i = i - 1) {
        let k = L;
        for (let j = 0; j < i; j = j + 1) {
            const first = head(k);
            const sec = head(tail(k));
            if (first > sec) {
                set_head(tail(k), first);
                set_head(k, sec);
            } else {}
            k = tail(k);
        }
    }   
}

/**
if (head(lst) > head(tail(lst))){
        const temp = head(lst);
        set_head(lst, head(tail(lst)));
        set_head(tail(lst), temp);
}
else{}
good job 
**/

### Question 2
Consider the `cc` (coin change) function presented in Lecture L3:

function cc(amount, kinds_of_coins) {
    return amount === 0
        ? 1
        : amount < 0 || kinds_of_coins === 0
            ? 0
            : cc(amount, kinds_of_coins - 1)
                +
                cc(amount - first_denomination(kinds_of_coins),
                    kinds_of_coins);
}

function first_denomination(kinds_of_coins) {
    return kinds_of_coins === 1 ? 5 :
        kinds_of_coins === 2 ? 10 :
        kinds_of_coins === 3 ? 20 :
        kinds_of_coins === 4 ? 50 :
        kinds_of_coins === 5 ? 100 : 0;
}

Is function `cc` a good candidate for memoization? Support your answer with an example.

If memoization is suitable for function `cc` , provide the implementation.

const mem = [];

function read(n, k) {
    return (mem[n] === undefined) ?
        undefined : mem[n][k];
}

function write(n, k, value) {
    if (mem[n] === undefined) {
        mem[n] = [];
    } else {}
    mem[n][k] = value;
}

function mcc(n, k) {
    // Your solution here.
    if (n === 0){
        return 1;
    } else if (n < 0 || k === 0){
        return 0;
    } else if (read(n,k) !== undefined){
        return read(n,k);
    } else {
        const value = mcc(n, k - 1) + mcc(n - first_denomination(k),k);
        write(n,k,value);
        return value;
    }
}

What are the orders of growth in time and space of the memoized version?

## Bonus Round

### Question 1

Write a function `rotate_matrix` that takes as argument a 2D array that represents a *n×n* matrix, and rotates the matrix 90 degrees clockwise.

The **challenge** is that the matrix rotation must be performed **in-place**. This means that, besides the arrays that are used to store the original matrix, **no additional array or list** can be used for the rotation. The rotated result must be stored in the same space as the original matrix. (**Hint:** use only swaps to perform the rotation.)