Name: Solved--Homework 1 --Solution
SKU: 16439
Price: 30.00 USD
Availability: InStock

Description

5/5 – (2 votes)

All problems are out of 10 points. 30 points total plus extra credit.

Note for this HW and all future HW: Unless otherwise speci ed, you may use any algorithm covered in class as a \black box” { for example you can simply write \sort the array in (n log(n)) time” without having to describe how to do this.

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) = n²		7n and g(n) = n³	10n²
2.	f(n) = (^p		)³ and g(n) = n²	₍p		)³
		n			n

f(n) = n^log3⁽⁴⁾ and g(n) = n log³(n)

_{f(n) = 2}^log2⁽ⁿ⁾ _and _{g(n) =} _n

f(n) = log⁵(n) and g(n) = n= log(n)

f(n) = 4ⁿ and g(n) = 5ⁿ

f(n) = log₄(n) and g(n) = log₅(n)

f(n) = n³ and g(n) = 2ⁿ

f(n) = ^pn and g(n) = log³(n).

f(n) = n log(n) and g(n) = n²

2 Problem 2

induction that

^P5

k+1

Part 1

(3 points): Prove by

n i⁴

i=0

= (

1)2

Part 2

(4 points): Prove that

^Pi=1

= (n )

Part 3 (3 points): What is ^P^log2⁽ⁿ⁾ 4ⁱ equal to in -notation?

i=1

formal proof necessary, just a brief explanation.)

(No

HINT: use the formula for geometric sum:	k	r^k	r^k	=	r
This is generally a very useful formula.	^Pi=1		= (	1) (		1).

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 signi cantly better than n².

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 jx yj, where jx yj 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.

Problem 4 { EXTRA CREDIT

Given an array A, for any pair of indices j > i, de ne the interval A[i:::j] to be the subarray consisting of element A[i]; A[i + 1]; :::; A[j 1]; A[j]. Now,

de ne 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:

For each index i

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 (n³). You need to argue that the number of steps is at most a constant times n³, and at least a constant times n³.

HINT: to prove that the running time is Cn³, since it is hard to cal-

culate the sum		_i;j>i(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 su ciently small,
		P

and j is su ciently big.

Solved–Homework 1 –Solution

Description

Related products

Lab 3: “Thanks for All the Fish!!!” SOlution

Mario Level Generation Solution

[solved]Homework 6: Hero Agents-Solution

Project 4: GPU Programming Solution

Project 1A: Transformation Matrices Solution