HW1

CS 350
Due 1/23 before class starts

• Collaboration: You may work in groups of up to 3 students per group. Remember to clearly indicate the group members on your HW submission.
• Submission: You should email your submission (preferably typed up in LaTeX but will also accept neatly handwritten) to cs350pdx@gmail.com
• IMPORTANT: Provide an email subject line with the following pattern: HWx Section xxx - Full Name, Full Name, Full Name

Problem 1

List the functions below from lowest order of growth to highest. If any two or more are the same, indicate which.

$\sqrt{n}$	$m$	$2^n$
$n \log n$	$n - n^3 + 7n^5$	$k^2 + \log k$
$m^2$	$n^3$	$\log n$
$n^{\frac{1}{3}} + \log n$	$(\log n)^2$	$n!$
$\ln m$	$\frac{n}{\log n}$	$\log \log k$
$(\frac{1}{3})^n$	$(\frac{3}{2})^n$	6

---

Problem 2

Prove that for any positive integer constants $a$ and $b$ where $b>0$
$(n+a)^b \in \Theta(n^b)$

(Hint: show that $(n+a)^b \in \Omega(n^b)$ and that $(n+a)^b \in \mathcal{O}(n^b)$ providing values for $c_1$, $c_2$, and $n_0$.)

---

Problem 3

(From textbook 2.2 ex. 2) Use the informal definitions of $\mathcal{O}$, $\Theta$, and $\Omega$ to determine whether the following assertions are true or false.

1. $n(n+1)/2 \in \mathcal{O}(n^3)$
2. $n(n+1)/2 \in \mathcal{O}(n^2)$
3. $n(n+1)/2 \in \Theta(n^3)$
4. $n(n+1)/2 \in \Omega(n)$

---

Problem 4

(From textbook 2.3 ex. 4) Consider the following algorithm:

Mystery Algorithm
Input: A non-negative integer $n$
Output: ?

  S <- 0
  for i <- 1 to n do
    S <- S + i * i
  return S

1. What does this algorithm compute?
2. What is its basic operation?
3. How many times is the basic operation executed?
4. What is the efficiency class of this algorithm?
5. Suggest an improvement, or a better algorithm altogether, and indicate its efficiency class. If you cannot do it, try to prove that, in fact, it cannot be done.

---

Problem 5

(From textbook 2.3 ex. 1) Compute the following sums.

1. $1+3+5+7+ ... + 999$
2. $2+4+8+16+ ... +1024$
3. $\sum_{i=3}^{n+1}1$
4. $\sum_{i=3}^{n+1}i$
5. $\sum_{i=0}^{n-1}i(i+1)$
6. $\sum_{j=1}^{n}3^{j+1}$
7. $\sum_{i=1}^{n}\sum_{j=1}^{n}ij$
8. $\sum_{i=1}^{n}\frac{1}{i(i+1)}$

---

Problem 6

(From textbook 2.4 ex. 1) Solve the following recurrence relations.

1. $x(n) = x(n-1) + 5$ for $n >1$, $x(1)=0$
2. $x(n) = 3x(n-1)$ for $n>1$, $x(1) = 4$
3. $x(n) = x(n-1) + n$ for $n>0$, $x(0) =0$
4. $x(n) = x(n/2) + n$ for $n>1$, $x(1) =1$ (solve for $n = 2^k$)
5. $x(n) = x(n/3) + 1$ for $n >1$, $x(1)=1$ (solve for $n = 3^k$)