---
tags: cs1101s
---

# CS1101S Studio S10 (T05J)

## 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;
            }
        }
    }
}

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

Theta(n * n)? 

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`.

-- RH :) --
function bubblesort_list(L) {

    const len = length(L);
    for (let i = len - 1; i >= 1; i = i - 1) {
        let result = L;
        for (let j = 0; j < i; j = j + 1) {
            if (head(result) > head(tail(result))) {
                const temp = head(result);
                set_head(result, head(tail(result)));
                set_head(tail(result), temp);
            }
            result = tail(result);
        }
        
    }
    return L;
}
---------

### 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 cc(amount, kinds_of_coins) {

    if (amount === 0 ) {
       return 1;
    } else if (amount < 0 || kinds_of_coins === 0) {
        return 0;
    } else if (mem[amount] !== undefined && mem[amount][kinds_of_coins] !== undefined) {
        return mem[amount][kinds_of_coins];
    } else {
        const temp = cc(amount, kinds_of_coins - 1) + cc(amount - first_denomination(kinds_of_coins), kinds_of_coins);
        if (mem[amount] === undefined) {
            mem[amount] = [];
        }
        mem[amount][kinds_of_coins] = temp;
        return temp;
    }
}
---
function mcc(n, k) {
    if(n >= 0 && read(n, k) !== undefined) {
        return read(n, k);
    } else {
        const result = n === 0
                       ? 1
                       : n < 0 || k === 0
                       ? 0
                       : mcc(n, k - 1)
                         + mcc(n - first_denomination(k), k);
        
        if (n >= 0) {
            write(n, k, result);
        }
        
        return result;
    }
}

//AI LIN
function mcc(amount, kinds_of_coins) {
    
    const mem = [];
    
    for (let i = 0; i <= amount; i = i + 1) {
        mem[i] = [];
    }
        
    function cc(amount, kinds_of_coins) {
        
        if (amount >= 0 && mem[amount][kinds_of_coins] !== undefined) {
            return mem[amount][kinds_of_coins];
        } else if (amount >= 0) {
            const result =
                amount === 0
                    ? 1
                    : kinds_of_coins === 0
                    ? 0
                    : cc(amount, kinds_of_coins - 1)
                    +
                    cc(amount - first_denomination(kinds_of_coins),
                    kinds_of_coins);
            mem[amount][kinds_of_coins] = result;
            return result;
        } else {
            return 0;
        }
    }
    
    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;
    }
    
    return cc(amount, kinds_of_coins);
    
}

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

//Runqiao 
ø(amount * kind_of_coins)

## 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.)