TCSS 343 Assignment 2 Solutions PDF

Preview

Summary

Homework solutions for TCSS434 Analysis and Design of Algorithms...

Description

S C HOOL OF E NG INEERING

AND

T ECHNOLOG Y

TCSS 343 - Assignment 2 Solution

Version 1.0

April 1, 2021

1 G UIDELINES Homework should be electronically submitted to the instructor by midnight on the due date. A submission link is provided on the course Canvas Page. The submitted document should be typeset using any common software and submitted as a PDF. We strongly recommend using LATEX to prepare your solution. You could use any ALTEX tools such as Overleaf. Scans of handwritten/hand drawn solutions are acceptable, but your work may be considered incomplete if the handwriting is unclear or disorganized. You should attempt to present solutions that are correct (no errors or omissions), clear (stated in a precise and concise way), and have a well organized presentation. Show your work as partial credit will be awarded to rough solutions or solutions that make partial progress toward a correct solution. Remember to cite all sources you use other than the text, course material or your notes.

1

2 P ROBLEMS 1. In this problem you will show that n X

i=1

³ ´ i d ∈ Θ n d +1

by finding upper and lower bounds. You will do this using two different methods. The first method is to use binding the term and splitting the sum. The second method is to use integration. Complete the following steps and remember to show your work. a) Using the binding the term technique state an upper bound on the sum. Solution:

n X

i=1

id

≤

n X

nd

i=1

= nd ·

n X

1

i=1

= nd · n

= n d +1 ³ ´ ∈ O n d +1 b) Using the splitting the sum technique state a lower bound on the sum. Solution:

2

n X

id

n X

≥

⌋+1 ³j n k n X

i=⌊

i=1

id

n 2

≥

2

i=⌊ n2 ⌋+1

=

= = = = = ∈

³j n k 2

´d +1 ·

´d +1 n X

1

i=⌊ n2 ⌋+1

´ ´ ´d ³ ³j n k +1 +1 +1 · n − 2 2 ³j n k ´d l n m +1 · 2 2 ³ n ´d ³ n ´ · 2 2 ³ n ´d +1 2 µ ¶d +1 1 n d +1 2 ³ ´ Ω n d +1 ³j n k

c) Using the approximation by integration technique state a upper bound on the sum. n X

i

d

≤

Zn+1

xd d x

1

i=1

=

"

=

x d +1 d +1 1 ³

d +1

#n+1 1

(n + 1)d +1 − 1d +1

´

d) Using the approximation by integration technique state a lower bound on the sum. n X

id

≥

Zn

xd d x

0

i=1

= = =

"

x d +1

#n

d +1 1 ³

d +1 n d +1 d +1

0

n d +1 − 0d +1

´

3

3 EXTRA C REDIT P ROBLEM 2. In this problem you will find a tight bound on this sum n X

i i=2 log 2 i using any technique. a) State a simplified upper bound on the sum. Show your work. b) State a simplified lower bound on the sum. Show your work.

4...