Quiz Prep 2 Solutions

v1 Patch Notes - Oct. 9, 5:49 am

hey losers :3 !!! its 5:49 am i didnt check any of my work pls ping me with any errors so i can revise a v2, , ,,, i should just host a website for these… im hungry.. . could go for a warm bowl of soondubu rn. god i have to wake up at 6:30 im cooked time to faint in bed. miku out!! 🛌🌙

v2 Patch Notes - Oct 11, 3:25 am

filled out q1 w/ explanation of prev problems, added to question 2.b, included some formulas, uhhhh i made the soondubu i talked abt in v1 notes lol oh yeah we got an actual website now yippeeeeeeeeeeeeeeeee!!!!!

1) Code analysis like quiz1 or hw1 or any class code analysis 

Note From Miku

uhh uhhhhnmmm ermmm she didnt really give problems here… so instead i will show you guys my thought process with the hw ones…

hw1 problem 5.e

what i usually do w these nested loops is find the number of iterations each loop/function has in $O(n)$ form. so at the top we have a for loop iterating i from 0 to n. obviously this makes i’s iterations $O(n)$.

then, the inner loop iterates j from 0 to i${}^2$. we just determined i to iterate $O(n)$ times, so we can square that to say j iterates O(n${}^2$) times.

then, we have k looping from 0 to j. since j to iterates $O(n^2)$ times, this means k also iterates $O(n^2)$ times.
finally, within the innermost loop is a $O(1)$ line, ++sum. multiply all those numbers together and we get $O(n)\cdot O(n^2)\cdot O(n^2)\cdot O(1)=O(n^5)$.

careful ‼️

watch out when doing these problems!!! this first example was much easier bc the iterators were only affected by the for loop and nothing else. additionally, the contents of the innermost for loop was O(1), keeping things simple. she will probably give more complex problems on exams and quizzes!! make sure you look thru the code line by line and deeply analyze how certain lines could affect other parts. below ill go over two examples of some things to pay attention for.

hw1 problem 10

questions like hw1 problem 10 modify the iterator values outside of the main for loop iteration. keep the behavior of these in mind and think about how they affect each loop. if we think about what j does here, it adds 1 to j every inner for loop iteration; this causes j to increment by 2 instead of 1, which is still $O(n)$. then, at the end of the inner for loop, i has increased by n/2 due to the line i++. This means the outer for loop only runs exactly twice, which is an O(1) operation.

other thing to watch out for the innermost for loop may not contain an O(1) operation! heres one a lot of ppl struggled with:

hw1 problem 5.f

lets start with loop analysis on this one. i iterates from 1 to n, so that’s $O(n)$. j iterates from 1 to i${}^2$ and is thus $O(n^2)$. the innermost loop iterates k from 0 to j, which is again $O(n^2)$. however, an if statement in the 2nd loop prevents this problem from being identical to problem e. the innermost loop is nested in an if statement which checks if j % i == 0. this means although j iterates $O(n^2)$ times, its contents only run every i times. using this information, we can divide j’s iterations by i’s iterations to determine the second loop’s content only runs $O(n)$ times, not $O(n^2)$. we can multiply these values and calculate the runtime as $O(n)\cdot \frac{O(n^2)}{O(n)}\cdot O(n^2)\cdot O(1)=O(n^4)$.

2) Solve via recurrence tree, and confirm via substitution.

Formulas!!

Here are some formulas that are super useful for solving geometric series!! ^^
The main formula u should know is

$$\sum _{k=0}^{n}a{r}^k=\frac{a(1-r^{n+1})}{1-r}$$

When $|r|<1$, then as $n$ approaches $\infty$ we know that

$$\sum _{k=0}^{\infty }a{r}^k=\frac{a}{1-r}$$

Then, when $r=1$ aka there’s no exponent, then

$$\sum _{k=0}^{n}a=a(n+1)$$

As a bonus heres Masters Theorem. Makes lots of problems so easy :D
For $T(n)=aT\left(\frac{n}{b}\right)+O(n^d)$,

if $a>b^d$ then the recurrence is $O(n^{{\log }_B(A)})$.

if $a=b^d$ then the recurrence is $O(n^d\log (n))$.

if $a<b^d$ then the recurrence is $O(n^d)$.

T(n)=27T(n/3)+5n^3

Work: $5n^3$
Depth: Largest recursive constant is 1/3.
$k={\log }_3(n)$

$$\begin{array}{rl}\sum _{k=0}^{{\log }_3(n)}5n^3& =(1+{\log }_3(n))(5n^3)\\ & =5n^3{\log }_3(n)+5n^3\\ & =O(n^3\log (n))\end{array}$$

Substitution

Hypothesis: $T(n)=O(n^3\log (n))$
Assuming $T(n)\le c{n}^3\log (n)$ for $\forall n\le k-1$, for great enough $k$ we can use this assumption to determine that $T\left(\frac{k}{3}\right)\le c(\frac{k}{3}{)}^3\log \left(\frac{k}{3}\right)$. Thus, we know that

$$T(k)=27\cdot T\left(\frac{k}{3}\right)+5k^3\le c{k}^3\log \left(\frac{k}{3}\right)+5k^3$$

From this, we want to prove that

$$c{k}^3\log \left(\frac{k}{3}\right)+5k^3\le c{k}^3\log (k)$$

We can divide by $k^3$ to rewrite the inequality as

$$c\cdot \log \left(\frac{k}{3}\right)+5\le c\log (k)$$

Logarithm rules further simplify this inequality to

$$c\log (k)-c\log (3)+5\le c\log (k)$$

By cancelling out $c\log (k)$ and treating the log base as 3 we can solve for $c$ and get

$$c\ge 5$$

Thus, $T(n)=O(n^3\log (n))$ is proven by definition of big O as $T(n)\le c{n}^3\log (n)$ for $c=5$ and $n_0=1$

T(n)=27T(n/3)+5n^2

Work: $3^i(5n^2)$
Depth: Largest recursive constant is 1/3.
$k={\log }_3(n)$

$$\begin{array}{rl}\sum _{k=0}^{{\log }_3(n)}{3}^k(5n^2)& =5n^2\frac{(3^{{\log }_3(n)+1}-1)}{3-1}\\ & =5n^2\frac{(3n-1)}{2}\\ & =\frac{15}{2}{n}^3-\frac{5}{2}{n}^2\\ & =O(n^3)\end{array}$$

Substitution

disclaimer!!

The first hypothesis below does not successfully prove the recurrence through substitution. However, I’m still showing its process so you can understand why it fails, recognize the issue, and know how to deal with it.

Hypothesis: $T(n)=O(n^3)$
Assuming $T(n)\le c{n}^3$ for $\forall n\le k-1$, for great enough $k$ we can use this assumption to determine that $T\left(\frac{k}{3}\right)\le \frac{c}{27}{k}^3$. Thus, we know that

$$T(k)=27\cdot T\left(\frac{k}{3}\right)+5k^2\le c{k}^3+5k^2$$

From this, we want to prove that

$$c{k}^3+5k^2\le c{k}^3$$

We can cancel out $c{k}^3$ from both sides and end with

$$5k^2\le 0$$

ermmmm what the flip!!

This inequality can never hold true for any non-zero values of $k$! Despite this, a failed substitution proof does not indicate an incorrect hypothesis. Sometimes a new hypothesis must be formed where a lower degree term is subtracted from the original term. Below is an application of such, where $n^2$ is subtracted to deal with the $5k^2$.

Hypothesis: $T(n)=O(n^3-n^2)$
Assuming $T(n)\le c{n}^3-c{n}^2$ for $\forall n\le k-1$, for great enough $k$ we can use this assumption to determine that $T\left(\frac{k}{3}\right)\le \frac{c}{27}{k}^3-\frac{c}{9}{k}^2$. Thus, we know that

$$T(k)=27\cdot T\left(\frac{k}{3}\right)+5k^2\le c{k}^3-3c{k}^2+5k^2$$

From this, we want to prove that

$$c{k}^3-3c{k}^2+5k^2\le c{k}^3-c{k}^2$$

We can cancel out $c{k}^3$ from both sides and combine like terms to get

$$5k^2\le 2c{k}^2$$

This time, we can solve for $c$ and get the inequality

$$c\ge \frac{5}{2}$$

As $O(n^3-n^2)=O(n^3)$, we have proven $T(n)=O(n^3)$ through definition of big O as $T(n)\le c{n}^3$ for $c=\frac{5}{2}$ and $n_0=1$.

T(n)=27T(n/3)+5n^4

Work: $\frac{5n^4}{3^i}$
Depth: Largest recursive constant is 1/3.
$k={\log }_3(n)$

$$\begin{array}{rl}\sum _{k=0}^{{\log }_3(n)}\frac{5n^4}{3^k}& \le \sum _{k=0}^{\infty }\frac{5n^4}{3^k}\\ & =\frac{5n^4}{1-\frac{1}{3}}\\ & =\frac{15}{2}{n}^4\\ & =O(n^4)\end{array}$$

Substitution
Hypothesis: $T(n)=O(n^4)$

Assuming $T(n)\le c{n}^4$ for $\forall n\le k-1$, for great enough $k$ we can use this assumption to determine that $T\left(\frac{k}{3}\right)\le \frac{c}{81}{k}^4$. Thus, we know that

$$T(k)=27\cdot T\left(\frac{k}{3}\right)+5k^4\le \frac{c}{3}{k}^4+5k^4$$

From this, we want to prove that

$$\frac{c}{3}{k}^4+5k^4\le c{k}^4$$

We can divide by $k^4$ to rewrite the inequality as

$$\frac{c}{3}+5\le c$$

Then by solving for $c$, we get

$$c\ge \frac{15}{2}$$

Thus, $T(n)=O(n^4)$ is proven by definition of big O as $T(n)\le c{n}^4$ for $c=\frac{15}{2}$ and $n_0=1$.

3) Create a linear algorithm that adds an array of numbers, and analyze it. 

Note From Miku

uhhhh we already did this for hw but i think its to set up for problem 4. ill just copy my prev code lol

arraySum(arr):
  total = 0
  for (i=0 to arr.length-1):
    total += arr[i]
  return arrTotal

4) Create a divide & conquer algorithm that adds up an array of numbers and analyzes it using the recurrence tree method.

divAndConqSum(arr, start, end):
  if start == end: # base case
    return arr[start]
 
  middle = floor((start + end) / 2) # MAKE SURE TO ROUND DOWN
  a = divAndConqSum(arr, start, middle)
  b = divAndConqSum(arr, middle+1, end)
  return a + b

Recurrence equation: $T(n)=2T\left(\frac{n}{2}\right)+O(1)$

Work: $2^k$
Depth: Largest recursive constant is 1/2.
$k={\log }_2(n)$

$$\begin{array}{rl}\sum _{k=0}^{{\log }_2(n)}{2}^k& =\frac{2^{{\log }_2(n)+1}-1}{2-1}\\ & =2n-1\\ & =O(n)\end{array}$$

5) Pseudocode

Note From Miku

we already did all of these for quiz1/hw1. my guess is that it’ll be on the quiz this time?? dont quote me on that im yapping but ima copy my prev hw/quiz answers onto here

Write pseudocode that lists the subsets of an array of ints.

listSubsets(arr):
  n = arr.length
  subsets = []
  
  for (i=0 to 2^n-1):
    subset = []
    for (j=0 to n-1):
      if i & (1 << j):
        subset.push(arr[j])
    subsets.push(subset)
  return subsets

Write pseudocode finds the smallest number of an array of ints.

findMinimum(arr):
  n = arr.length
  if !n:
    return "Empty Array"
 
  smallest = arr[0]
  for (i=1 to n-1):
    if arr[i] < smallest:
      smallest = arr[i]
  return smallest

Write pseudocode to list all possible substrings of a string S.

possibleSubstrings(S):
  n = S.length
  substrings = []
  
  for (i=0 to n-1):
    for (j=i to n-1):
      substrings.push(S.substring(i, j))
  return substrings

Given you have two sort lists write pseudocode that returns a new merged sorted

mergeSortedLists(list1, list2):
    mergedList = []
    # initializing iterators
    i = j = 0  
 
    # we run thru the lists until one of them runs out of elements
    while (i < list1.length && j < list2.length):
        # compare the smallest elements of both lists, then add 
        # it to mergedList. increment that list's iterator 
        if list1[i] < list2[j]:
            mergedList.push(list1[i])
            i++
        else:
            mergedList.push(list2[j])
            j++
 
    # once one of the lists runs out of elements, add the rest
    # of the elements from the other list
    while (i < list1.length):
        mergedList.push(list1[i])
        i++
    while (j < list2.length):
        mergedList.push(list2[j])
        j++
    return mergedList