Try   HackMD

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