The following function, bubblesort_array
, is an implementation of the Bubble Sort algorithm to sort an array of numbers into ascending order.
What is the order of growth of its runtime for an input array of n elements?
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
.
Consider the cc
(coin change) function presented in Lecture L3:
Is function cc
a good candidate for memoization? Support your answer with an example.
If memoization is suitable for function cc
, provide the implementation.
What are the orders of growth in time and space of the memoized version?
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.)