Scribd
Upload
203 views

CMSC-5343 Algorithm Analysis Homework 1

This homework assignment contains 5 problems related to algorithm analysis: 1) Analyze selection sort, including pseudocode, loop invariants, and runtime. 2) Use mathematical induction to prove two equations. 3) Prove that (n + a)b = Θ(nb) for any real constants a and b. 4) Determine if two equations are O(f(n)) using big-O notation. 5) Find big-Θ bounds for 5 recurrences.

Uploaded by

Robin Awal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
203 views

CMSC-5343 Algorithm Analysis Homework 1

This homework assignment contains 5 problems related to algorithm analysis: 1) Analyze selection sort, including pseudocode, loop invariants, and runtime. 2) Use mathematical induction to prove two equations. 3) Prove that (n + a)b = Θ(nb) for any real constants a and b. 4) Determine if two equations are O(f(n)) using big-O notation. 5) Find big-Θ bounds for 5 recurrences.

Uploaded by

Robin Awal
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

CMSC-5343 Algorithm Analysis

Homework 1 - 200 pt

Below, you will find the problems assigned for this assignment. Please elec-
tronically submit your assignment to blackboard.

1. Consider sorting n numbers in an array A by finding the smallest element of


A and swapping it with the first element of the array, then sorting the remaining
n 1 elements using the same process. This algorithm is known as selection
sort. Write pseudocode for this algorithm. What loop invariant or invariants
does this algorithm maintain? Give the worst-case runtime in notation.

2. Use mathematical induction to prove the following:


n
k 2 = n(n+1)(2n+1)
P
a) 6
k=1
b) The solution of the following recurrence:
T (n) = 2 for n = 2 T (n) = 2T (n/2) + n for n = 2k , k > 1
is T (n) = n lg n.

3. Show that for any real constants a and b, (n + a)b = (nb ).

4. Prove or disprove that:


a) 2n+1 = O(2n )
b) 22n = O(2n )

5. Find big- bounds for the following recurrences (assume that adequate base
cases exist for each):
a) T (n) = T (n 1) + n
b) T (n) = T (n/2) + 1
c) T (n) = 4T (n/2) + n2
d) T (n) = T (n 1) + T (n 2)

You might also like