## Daily Problem

The set cover problem: given a set of subsets $$S = \{S_1, \ldots, S_m\}$$ each in $$U = \{1, 2, \ldots, n \}$$ find the smallest subset of subsets $$T \subset S$$ such that the union is $$U$$.

Find a counter-example to the algorithm: Select the largest subset first, then delete those elements from $$U$$. Repeat by selecting the subset containing the next most uncovered elements until everything is covered.

## A Dumb Example:

for i in range(n):
print i*i + i
print n + n


### What if there is no specific implementation?

• gcd($$a,b$$):
• if $$a \leq b$$ return gcd($$b, a$$)
• $$r := a \mod b$$
• if $$r \neq 0$$ return gcd($$b, r$$)
• else return $$b$$

## Thinking in $$\mathcal{O}$$

### Big-Oh, is $$\mathcal{O}()$$ many things

#### Computer scientists are transcendent (future $$\geq$$ today)

$$\mathcal{O}(g(x)) = \{ f(x) \textrm{ s.t. } \exists c, n \textrm{ with } f(x) \leq c \cdot g(x) ~\forall ~x \geq n \}$$

## The comparison family

• For all large enough $$x$$
• $$f(x) = \omega(g(x))$$ when $$\lim_{x \to \infty} \frac{g(x)}{f(x)} = 0$$
• $$f(x) = \Omega(g(x))$$ when $$f(x) \geq C \cdot g(x)$$
• $$f(x) = \Theta(g(x))$$ when $$f(x) \geq C_1 \cdot g(x)$$ and $$f(x) \leq C_2 \cdot g(x)$$
• $$f(x) = \mathcal{O}(g(x))$$ when $$f(x) \leq C \cdot g(x)$$
• $$f(x) = o(g(x))$$ when $$\lim_{x \to \infty} \frac{f(x)}{g(x)} = 0$$

## Put it all together

### Insertion Sort:

for (i = 1; i < n; i++){
j = i;
while ((j > 0) && (s[j] < s[j-1])){
swap(s[j], s[j-1]);
j = j-1;
}
}

## Project Euler Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two n-digit numbers.

What is the worst-case complexity of the brute-force solution?