csc346 test 1 review

1. Given the flowing piece of code, in the worst case it is big-O of what (where the input

is of size n)?

Foo(A)

1 k = 0

2 for i = 1 to A.length

3 A[i] = A[i] + 1

4 for j = 1 to A. length - i

5 A[j] = A[j] * A[i]

6 if A[j] > 20

7 k = k + 1

8 A[i] = k

9 for i = 1 to A.length / 2

10 exchange A[i] with A[A.length + 1 - i]

O(n²)

2. List a series of at least 6 different rates of growth on different standard functions (i.e.

lg n grows slower than n, n5 grows slower that 2n, etc.)

logn - n - nlogn - n² - 2^n - n!

The Master Method has the following 3 cases:

1. if f(n) = O(n(logba)), but not (nlogba), then T(n) = (nlogba)

2. if f(n) = (nlogba), then T(n) = (nlogba lg n)

3. if f(n) = (n(logba)+e), but not (nlogba), and if af(n/b) ≤ cf(n) for some constant

c > 1 and all sufficiently large n, then T(n) = (f(n)).

What is the asymptotic bounds of T(n) = 8T(n/2) + n?

T(n) = Θ(n³)

5. Write the code for a sort routine that is O(n2). You may use pseudocode so long as the

control flow is understandable

Bubblesort O(n)² routine:

foo(A):

for i = 1 to n - 1

for j = 1 to n - i

if A[j] > A[j+1]

exchange A[j] with A[j+1]

Name a sort, other than Heapsort, that also has (n lg n) complexity and briefly

describe how it works

O(n log n) - Merge Sort:

Splits array in halves and then sorts through each half. Merges the sorted halves together after compute.

Name a sort, other than radix sort, that sorts in linear time, give the conditions on use

of the sort, and briefly describe how it works

Bucket Sort - O(n):

puts a range of elements into “buckets” then sorts each bucket and concatenates the created buckets in order.

Use Radix sort (showing the list of numbers as they appear after each iteration) to sort

the numbers initially given in the following order:

314, 192, 763, 291, 111, 100, 345, 126, 722, 807

1st iteration (sorting by least significant digit): 100, 291, 111, 192, 722, 763, 314, 345, 126, 807

2nd iteration (sorting by next digit): 100, 807, 111, 314, 722, 126, 345, 763, 291, 192

3rd iteration (sorting by most significant digit): 100, 111, 126, 192, 291, 314, 345, 722, 763, 807

Briefly describe what is meant by Best-Case, Average-Case, and Worst-Case complexity of an algorithm.

Best-case: algorithm performs the least number of operations on an input.

average-case: expected performance across all possible inputs of that size.

Worst-case: maximum number of operations required by the algorithm in the most unfavorable situation.

10. Name two (n2) sorts. As these sorts are (n2), why do we still teach/learn them

when there are sorts like Quicksort.

Bubble Sort & Insertion Sort: important to learn because it aides in understanding the different kinds of algorithms & how they work.

11. What are the main properties of a red-black tree?

Root is always black

Red nodes cannot be next to another red node

Every path has equal number of black nodes

O(log n)

12. Briefly describe what the rotate routine, used in both red-black and AVL trees, does.

The rotate routine in tree data structures, such as red-black and AVL trees, is used to change the structure of the tree to maintain balance. It involves moving a subtree up or down to redistribute nodes and preserve the properties of the tree.

13. What properties should a good hash function have?

Rare Collisions

Minimum time to compute functions.

Distributes Uniformally

In a Hash table, is it always bad to have collisions? Why or why not?

It’s not bad to have collisions, but in an efficient hash table, they are rare. collisions are only bad when they start degrading performance.