2024-01-11

Wednesday, January 10th, 2024

Through pride we are ever deceiving ourselves. But deep down below the surface of the average conscience a still, small voice says to us, something is out of tune.

— Carl Jung

• PostgreSQL database object (e.g. unique constraint) naming convention: StackOverflow
• PortSwigger Web Security Academy
  • I should probably continue doing this (thanks Lance for reminding me in Discord announcement XD). Seems like the site got an overhaul.
  • I’m more interested in API testing, so that’s where I’ll start.

MUS106 Discussion 1: Intro & BeepBox Project

• song listening session
  • ”Ward Riders”
    • distorted, powerful
    • very active bass drum
    • energetic
  • ”Make it Right”
    • began with syncopated rhythm section (drums)
    • synthesized sounds
    • 6/8
    • chorus, harmonized vocals in bridge section
    • use of sampled vocals
  • similarities
    • percussion (drums)
    • groove-oriented
• contrast 2 songs
• BeepBox project
  • 2 phrases minimum per track, 4 vertical phrases total

ECS165A Lecture 2: Intro to DBMS

• typical DBMS functionalities
  • maintenance
  • access control
  • transaction
  • concurrent access
  • versioning
  • persistence & recovery
  • logging
  • indexing & query optimization
  • …
• Why DBMS?
  • DBMS helps provide an abstraction layer between application and data—modifying / improving the database software should not affect the application code, i.e. DBMS enables lower coupling.
  • Reduces application development time: no need to worry about data access.
  • Data integrity & security guarantees (e.g. via limiting privileges)
  • Universal interface for data adminstration across all databases & applications
  • Concurrent access with crash recovery: DBMS uses in-memory pages/cache to prevent having to write the disk every time. This protects the database file from being corrupted during concurrent access.
• There’s a need for specialized database software, e.g. videos, Human Genome project, etc.
• making a database
  • data model
  • schema
  • relational data model
  • conceptual schema
  • physical schema
  • external schema

ECS122A Lecture 2: Recurrence via Substitution

Basic Terminology

• Assume RAM has cells that store $w$-bit integer, where $w\ge {\log }_{2}n$ (i.e. $w$ bits can store $n$). An algorithm’s memory usage is described as the number of such cells used.
• primitive operation
  • arithmetic/logic
  • memory read/write
  • dereference pointer
  • branching
• running time
• desirable scaling property
• poly-time
• types of algorithm analysis
  • worst-case analysis
  • probabilistic analysis
  • amortized analysis
• algorithm growth terminology
• asymptotic analysis of log bases
• divide and conquer

Recurrences

• recurrence
• useful formulas to “solve” recurrence (i.e. transform a recurrence into a closed-form expression)
  • geometric series
  • sum of first n cubes
  • sum of first n squares
  • sum of first n natural numbers
• solving recurrence (find upper bound for a recurrence)
  • via substitution
  • via recursion tree
  • via master theorem

ECS122A quiz 1 study guide

Caution: Answers might be wildly wrong XD

Q1

$T(n)=5n^2\log n+4n^2+3$ $g(n)=2n^2\log n$

Prove that $T(n)=\Theta (g(n))$

Use the definition of big-Theta notation. Find $c_1$ that makes $T(n)\ge c_1\cdot g(n)$ and $c_2$ that makes $T(n)\le c_2\cdot g(n)$.

$$\begin{array}{rl}T(n)& \ge c_1\cdot g(n)\\ 5n^2\log n+4n^2+3& \ge 2c_1{n}^2\log n\end{array}$$

Guess a constant $c_1=1$, we need to find $N$ such that this relationship is true for $n\ge n_0$.

For $n_0=10$, left-hand side is $500+400+3=903$, whereas the right-hand side is $200$, so the inequality holds from now on. Technically induction is needed, but I’m too lazy for this.

For the other constant:

$$\begin{array}{rl}T(n)& \le c_2\cdot g(n)\\ 5n^2\log n+4n^2+3& \le 2c_2{n}^2\log n\end{array}$$

Guess a constant $c_2=100$, we need to find $n_0$ such that the relationship is true for $n\ge n_0$.

For $n_0=10$, left-hand side is $500+400+3=903$, and the right-hand side is $200\cdot 100\cdot \log (10)=200000$, so the inequality holds for $n\ge n_0$.

Q2

Prove $T(n)=O(g(n))$ via limit lemma

Assuming the $\log$ is the natural log for simplicity.

$$\begin{array}{rl}L& =\underset{n\to \infty }{\lim }\frac{T(n)}{g(n)}\\ & =\underset{n\to \infty }{\lim }\frac{5n^2\log n+4n^2+3}{2n^2\log n}\\ & =\underset{n\to \infty }{\lim }\frac{5n+10n\log n+8n}{2n+4n\log n}\\ & =\underset{n\to \infty }{\lim }\frac{5+10+10\log n+8}{2+4+4\log n}\\ & =\underset{n\to \infty }{\lim }\frac{10n^{-1}}{4n^{-1}}\\ & =\frac{5}{2}\end{array}$$

Since $L\ne 0$ and $L\ne \pm \infty$, $T(g)=\Theta (g(n))$.

Q3 i)

$f(n)=n\log n$ $g(n)=n^2+3n$

Prove via limit lemma that $f(n)=O(g(n))$

Assuming $\log$ is the natural log.

$$\begin{array}{rl}L& =\underset{n\to \infty }{\lim }\frac{n\log n}{n^2+3n}\\ & =\underset{n\to \infty }{\lim }\frac{1+\log n}{2n+3}\\ & =\underset{n\to \infty }{\lim }\frac{\frac{1}{n}}{2}\\ & =0\end{array}$$

Since $L=0$, $f(n)=O(g(n))$ via the limit lemma.

Q3 ii)

Can you prove $\log n=O(n^x)$ for some $x$? Explain why or why not.

Yes, this works for $x\ge 1$. For instance, given $x=1$, we have:

$$\begin{array}{rl}L& =\underset{n\to \infty }{\lim }\frac{\log n}{n}\\ & =\underset{n\to \infty }{\lim }\frac{\frac{1}{n}}{1}\\ & =\underset{n\to \infty }{\lim }\frac{1}{n}\\ & =0\end{array}$$

Since $L=0$, we know $\log n=O(n)$ via limit lemma.

$\log n$ is sublinear time, so we know that this works for all $x\ge 1$.

Q4 i-iii

Provide sample code for i-iii i) $T(n)=T\left(\frac{n}{5}\right)+T\left(\frac{3n}{5}\right)+n$ ii) $T(n)=T\left(\frac{2n}{5}\right)+T\left(\frac{3n}{5}\right)+n$ iii) $T(n)=4T\left(\frac{n}{2}\right)+n^3$

Skipped.

Q4 iv

Write a recurrence for the code below:

foo(int n)
    foo(n/2)
    for(i=1 to n^2)
        print hello

Each problem has one subproblem foo(n/2) and has some work with time complexity $O(n^2)$. We can write the recurrence as $T(n)=T\left(\frac{n}{2}\right)+n^2$.

Q5

i) Write pseudocode that lists the subsets of an array of ints. ii) Write psuedocode finds the smallest number of an array of ints. iii) Write psudedocode the list all possible substring of a string S. iv) Given you have two sort lists write pseudocode that returns a new merged sorted

Since we’re working on divide and conquer, I used recursion as much as possible. The code is quite literally crap.

i)

def subsets(arr):
    result = set()
    result.add(set())
    result.add(set(arr))
    for idx from 0 to arr.length:
        result.append(subset(arr.remove(idx)))
    return result

ii)

def min_elem(arr):
    known_min = int.max
    for idx from 0 to arr.length:
        if arr[idx] < known_min:
            known_min = arr[idx]
    return known_min

iii)

def substrs(str):
    result = set()
    result.append(str)
    if str.length > 1:
        result.extend(substrs(str.remove(0)))
        result.extend(substrs(str.remove(str.length-1)))
    return result

iv)

def merge(left, right):
    i = 0
    j = 0
    result = []
    while i < left.length and j < right.length:
        if i == left.length:
            result.append(right[i])
        else j == right.length:
            result.append(left[i])
        else if left[i] < right[i]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[i])
            i += 1
    return result