Algorithms (CS 513)

Homework 0

Due: Feb 4, 2014

Send an email to swastik.kopparty@gmail.com and ameyrbh@gmail.com with subject "S14 513 Homework 0" with the following information, and solutions to the following problems.

Name

Department

Undergrad/MS/PhD, Year

Registered?

Email address

Courses related to algorithms/combinatorics/algebra taken

1. For the following f(n), g(n) state which of the statements f(n) = O(g(n)) , f(n) = o(g(n)), f(n) f(n) = , f(n) = are true:
f(n) g(n)

(log n)¹⁰⁰ n^0.1

n² (n+1)²

exp(n²) exp((n+1)²)

2ⁿ 3ⁿ

2n 3n

log(2n) log(3n)

5n³ (log n)^{log n}

n! nⁿ

nⁿ (n+1)ⁿ

2. Show (by induction on n) that if T(1) = 1, and , then

3. There are n+1 squares labelled 0,1,2 … n. You are given as input nonnegative integers a₁, … a_n. A frog starts at square 0, and you have to make it end up at square n via a sequence of hops. When the frog is at square k, it can hop to either square k + 4 or to square k + 7. When it lands on a square t, the frog collects a_t points. Design a poly(n) time algorithm to find the sequence of hops which takes the frog from square 0 to square n while collecting the maximum possible number of points.

4. You are given as input m, which is an n bit nonnegative integer. Design an algorithm that runs in time poly(n) and determines whether m is of the form a^b, where a, b are integers and b is at least 2.
You are only allowed to use addition, multiplication and comparison operations on integers (no powering, roots, logs etc).

5. What is the coolest algorithm that you know? Are there any particular kinds of algorithms that you would like to learn about?