2024-01-19

Friday, January 19th, 2024

If opportunity doesn't knock, build a door.

— Milton Berle

• caching in repository pattern in TypeScript/JavaScript
  • Redis cache invalidation

MUS106 Lecture 5

• Elvis Presley’s popularity and live performance capability outgrew Sun Records’ financial capability six months after Blackboard Jungle’s debut (Sam Phillips couldn’t even pay Elvis’s royalties)—Sam Phillips sold Elvis’s contract to RCA for $35,000 in 1955. Elvis hired Colonel Tom Parker as agent.
• ”Elvis the Pelvis”: nickname given by the press (?) to condemn against his appeal to teenage girls.
  • June 1956, Milton Berle Show
• Elvis got drafted in 1957, and chose to enlist into the military to serve in Germany (and shaved his iconic hair) instead of the entertainment corps. This helped recasting him in a patriotic light.
• Elvis released some gospel records, which he wanted to do for a long time.
• Elvis: a song stylist (never writes his own music)
• Aloha from Hawaii was broadcasted through globally linked satellite broadcast; 1 billion people were estimated to have watched it (25% of global population)

ECS122A quiz 2 study guide problems

Q1

Code analysis, like quiz1 or hw1 or any class code analysis

See ECS122A problem set 1 and ECS122A quiz 1

Q2

Solve via recurrence tree, and confirm via substitution.

1)

$$T(n)=27\cdot T\left(\frac{n}{3}\right)+5n^3$$

layers

• $27$ subproblems, each with $5{\left(\frac{n}{3}\right)}^3$ operations → $5n^3$
• $27\cdot 27$ subproblems, each with $5{\left(\frac{n}{3^2}\right)}^3$ operations → $5n^3$
• …

The tree height is ${\log }_{3}n$, so we have $5n^3{\log }_{3}n=O(n^3\log n)$. To ease proving, we can add a lower order term

To confirm via substitution

$$\begin{array}{rl}T(n)& =27\cdot T\left(\frac{n}{3}\right)+5n^3\\ & \le 27c_1{\left(\frac{n}{3}\right)}^3\log \frac{n}{3}-27c_2{n}^3+5n^3\\ & \le 27c_1{\left(\frac{n}{3}\right)}^3\log \frac{n}{3}-26c_2{n}^3-(c_2-5)n^3\\ & \le c_1{n}^3\log n-28c_2{n}^3,c_2\ge 5\\ & \le c_1\cdot n^3\log n\\ & \\ T(n)& =O(n^3\log n)\end{array}$$

2)

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

layers

• $27$ subproblems, each with $5{\left(\frac{n}{3}\right)}^2$ operations → $3\cdot 5n^2$
• $27\cdot 27$ subproblems, each with $5{\left(\frac{n}{3^2}\right)}^2$ operations → $3^2\cdot 5n^2$
• …

$$\sum _{k=1}^{{\log }_{3}n}5\cdot 3^k{n}^2$$

Runtime increases drastically in the leaves, overpowering the work done to split & combine solutions ($5n^2$), so we have $O(n^{{\log }_{3}27})=O(n^3)$.

To make it easier to prove, we can add a lower order term. Confirm via substitution:

$$\begin{array}{rl}T(n)& =27\cdot T\left(\frac{n}{3}\right)+5n^2\\ & \le 27c_1{\left(\frac{n}{3}\right)}^3-27c_2{n}^2+5n^2\\ & \le c_1{n}^3-27c_2{n}^2+5n^2\\ & \le c_1{n}^3-26c_2{n}^2-(c_2-5)n^2\\ & \le c_1{n}^3-26c_2{n}^2,c_2\ge 5\\ & \le c_1{n}^3\\ T(n)& =O(n^3)\end{array}$$

3)

$$T(n)=27T\left(\frac{n}{3}\right)-5n^4$$

• $27$ subproblems each with $5{\left(\frac{n}{3}\right)}^4$ operations → $\frac{5n^4}{3}$
• $27\cdot 27$ subproblems each with $5{\left(\frac{n}{3^2}\right)}^4$ operations → $\frac{5n^4}{3^2}$
• …

The work in leaves / higher tree depths decreases drastically, so we can safely disregard them. The overall runtime is therefore $O(n^4)$, the work taken to split & merge solutions, which came from $5n^4$.

Confirm via substitution:

$$\begin{array}{rl}T(n)& =27T\left(\frac{n}{3}\right)-5n^4\\ & \le 27c\cdot {\left(\frac{n}{3}\right)}^4-5n^4\\ & \le \frac{c\cdot n^4}{3}-5n^4\\ & \le c\cdot n^4\end{array}$$

Solve for $c$:

$$\begin{array}{rl}\frac{c}{3}-5& \le c\\ \frac{c}{3}-c& \le 5\\ -\frac{2}{3}c& \le 5\\ c& \le -\frac{15}{2}\end{array}$$

Q3

Design & analyze the run-time of your algorithms

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

// Assuming all elements are unique
// Assuming duplicate subsets are OK
int[][] subsets_of(int[] arr) {
    int[] result = [[]];
    for (i from 1 to arr.length ^ 2) {
        int[] current = []
        for (j from 0 to arr.length) {
            if (if j-th bit of i is 1)
                current.add(arr[j])
        }
        result.add(current)
    }
    return result;
}

• Outer loop: It takes $O(2^n)$ to iterate through the number of possible subsets. The loop counter i also happen to encode which elements are in the current subset.
• Inner loop: It takes $\Theta (i)$ time / $O(n)$ time to add the elements encoded in i into the current subset.
• Combined, the algorithm takes $O(n{2}^n)$ time.

2): Write psuedocode that finds the smallest number of an array of ints.

skipped

3): Write psudedocode that lists all possible substring of a string S.

skipped

4): Given you have two sorted lists, write pseudocode that returns a new merged sorted list

int[] merge_sorted(int[] a, int[] b) {
    int i = 0, j = 0;
    int[] result = [];
    while (i < a.length or j < b.length) {
        if (i == a.length) {
            result.add(b[j]);
            j++;
            continue;
        } else if (j == b.length) {
            result.add(a[i]);
            i++;
            continue;
        } else if (a[i] < b[j]) {
            result.add(a[i]);
            i++;
            continue
        } else {
            result.add(b[j]);
            j++;
            continue
        }
    }
    return result;
}

$O(m+n)$ runtime. The loop iterates through both arrays exactly once, so the runtime is the sum of lengths of the two arrays.