Starting from:
$29.99
CS 344 Homework 1
CS 344 - Sections 1,2,3 - Covers lectures on Sep 5, 10, 12 Due September 19.
All problems are out of 10 points. 30 points total plus extra credit.
Note for this HW and all future HW: Unless otherwise specified, you may use any algorithm covered in class as a “black box” – for example you can simply write “sort the array in Θ(nlog(n)) time” without having to describe how to do this.
1 Problem 1 (1 point per part)
For each of the following functions, state whether f(n) = O(g(n)) or f = Ω(g(n)), or if both are true, then write f = Θ(g(n)). No proofs required for this problem. 1. f(n) = n2 −7n and g(n) = n3 −10n2 2. f(n) = (√n)3 and g(n) = n2 −(√n)3 3. f(n) = nlog3(4) and g(n) = nlog3(n)
4. f(n) = 2log2(n) and g(n) = n
5. f(n) = log5(n) and g(n) = n/log(n)
6. f(n) = 4n and g(n) = 5n
7. f(n) = log4(n) and g(n) = log5(n) 8. f(n) = n3 and g(n) = 2n 9. f(n) = √n and g(n) = log3(n).
10. f(n) = nlog(n) and g(n) = n2
1
2 Problem 2 • Part 1 (3 points): Prove by induction thatPk i=0 i2i = (k−1)2k+1 + 2 • Part 2 (4 points): Prove thatPn i=1 i4 10 = Θ(n5) • Part 3 (3 points): What isPlog2(n) i=1 4i equal to in Θ-notation? (No formal proof necessary, just a brief explanation.) HINT: use the formula for geometric sum:Pk i=1 rk = (rk −1)/(r−1).This is generally a very useful formula.
3 Problem 3:
Write an algorithm in pseudocode for each of following two problems below. The algorithm should be simple in both cases! Both algorithms should have running time significantly better than n2.
Part 1: Closest Pair (5 points) • Input: An array A with n distinct (non-equal) elements • Output: numbers x and y in A that minimize |x−y|, where |x−y| denotes absolute-value(x-y)
Part 2: Remove Duplicates (5 points) • Input: An array A of size n, with some elements possibly repeated many times. • Output: a list L that contains the elements of A (in any order), but without duplicates.
For example, if A = 1,3,7,5,3,5,3,1,4 then the output set L can contain the numbers 1,4,7,5,3 in any order.
4 Problem 4 – EXTRA CREDIT
Given an array A, for any pair of indices j i, define the interval A[i...j] to be the subarray consisting of element A[i],A[i + 1],...,A[j −1],A[j]. Now,
2
define sum(i,j) to be the sum of all the values in A[i...j]; that is, sum(i,j) = Pj k=i A[k]. Note that it is easy to compute sum(i,j) in time Θ(j−i) by doing a single pass over A[i...j]. Now, consider the following problem:
Maximum Interval Value • Input: an array A of length n with positive and negative numbers. • Output: the maximum possible value sum(i,j) For example, if A = 3,-5,4,-2,-1,4,-3,2, then the maximum interval value is 5, obtained via the interval [4,-2,-1,4]
Now, consider the following naive algorithm for this problem: Algorithm:
1. For each index i
2. For each index j i 3. Compute and store sum(i,j) in time Θ(j −i). 4. Return the maximum value sum(i,j) computed in step 3.
Question: Argue that the total running time of the algorithm is Θ(n3). You need to argue that the number of steps is at most a constant times n3, and at least a constant times n3. HINT: to prove that the running time is ≥ Cn3, since it is hard to calculate the sumPi,ji(j−i) for all pairs (i,j), you will want to lower bound the sum by consider only the part of the sum where i is sufficiently small, and j is sufficiently big.
3
All problems are out of 10 points. 30 points total plus extra credit.
Note for this HW and all future HW: Unless otherwise specified, you may use any algorithm covered in class as a “black box” – for example you can simply write “sort the array in Θ(nlog(n)) time” without having to describe how to do this.
1 Problem 1 (1 point per part)
For each of the following functions, state whether f(n) = O(g(n)) or f = Ω(g(n)), or if both are true, then write f = Θ(g(n)). No proofs required for this problem. 1. f(n) = n2 −7n and g(n) = n3 −10n2 2. f(n) = (√n)3 and g(n) = n2 −(√n)3 3. f(n) = nlog3(4) and g(n) = nlog3(n)
4. f(n) = 2log2(n) and g(n) = n
5. f(n) = log5(n) and g(n) = n/log(n)
6. f(n) = 4n and g(n) = 5n
7. f(n) = log4(n) and g(n) = log5(n) 8. f(n) = n3 and g(n) = 2n 9. f(n) = √n and g(n) = log3(n).
10. f(n) = nlog(n) and g(n) = n2
1
2 Problem 2 • Part 1 (3 points): Prove by induction thatPk i=0 i2i = (k−1)2k+1 + 2 • Part 2 (4 points): Prove thatPn i=1 i4 10 = Θ(n5) • Part 3 (3 points): What isPlog2(n) i=1 4i equal to in Θ-notation? (No formal proof necessary, just a brief explanation.) HINT: use the formula for geometric sum:Pk i=1 rk = (rk −1)/(r−1).This is generally a very useful formula.
3 Problem 3:
Write an algorithm in pseudocode for each of following two problems below. The algorithm should be simple in both cases! Both algorithms should have running time significantly better than n2.
Part 1: Closest Pair (5 points) • Input: An array A with n distinct (non-equal) elements • Output: numbers x and y in A that minimize |x−y|, where |x−y| denotes absolute-value(x-y)
Part 2: Remove Duplicates (5 points) • Input: An array A of size n, with some elements possibly repeated many times. • Output: a list L that contains the elements of A (in any order), but without duplicates.
For example, if A = 1,3,7,5,3,5,3,1,4 then the output set L can contain the numbers 1,4,7,5,3 in any order.
4 Problem 4 – EXTRA CREDIT
Given an array A, for any pair of indices j i, define the interval A[i...j] to be the subarray consisting of element A[i],A[i + 1],...,A[j −1],A[j]. Now,
2
define sum(i,j) to be the sum of all the values in A[i...j]; that is, sum(i,j) = Pj k=i A[k]. Note that it is easy to compute sum(i,j) in time Θ(j−i) by doing a single pass over A[i...j]. Now, consider the following problem:
Maximum Interval Value • Input: an array A of length n with positive and negative numbers. • Output: the maximum possible value sum(i,j) For example, if A = 3,-5,4,-2,-1,4,-3,2, then the maximum interval value is 5, obtained via the interval [4,-2,-1,4]
Now, consider the following naive algorithm for this problem: Algorithm:
1. For each index i
2. For each index j i 3. Compute and store sum(i,j) in time Θ(j −i). 4. Return the maximum value sum(i,j) computed in step 3.
Question: Argue that the total running time of the algorithm is Θ(n3). You need to argue that the number of steps is at most a constant times n3, and at least a constant times n3. HINT: to prove that the running time is ≥ Cn3, since it is hard to calculate the sumPi,ji(j−i) for all pairs (i,j), you will want to lower bound the sum by consider only the part of the sum where i is sufficiently small, and j is sufficiently big.
3
1 file (224.2KB)
