Scribd
Upload
30 views2 pages

Homework 1

1) CS 161 Homework 1 is due October 7, 2016 at noon and contains 4 questions about algorithms analysis and graph theory. Students are asked to show full proofs and relevant calculations. 2) Question 1 asks to calculate the cardinality of subsets of a set, the expected value of a random subset, and the expected value and variance of rolling dice. 3) Question 2 asks to determine asymptotic bounds for various functions and prove summations are Θ(n log n) and Θ(log n). 4) Question 3 asks to prove an upper bound on the number of edges in a graph with no triangles. 5) Question 4 asks to solve recurrence relations for MergeSort using recursion trees and

Uploaded by

Craig Lizcht
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
30 views2 pages

Homework 1

1) CS 161 Homework 1 is due October 7, 2016 at noon and contains 4 questions about algorithms analysis and graph theory. Students are asked to show full proofs and relevant calculations. 2) Question 1 asks to calculate the cardinality of subsets of a set, the expected value of a random subset, and the expected value and variance of rolling dice. 3) Question 2 asks to determine asymptotic bounds for various functions and prove summations are Θ(n log n) and Θ(log n). 4) Question 3 asks to prove an upper bound on the number of edges in a graph with no triangles. 5) Question 4 asks to solve recurrence relations for MergeSort using recursion trees and

Uploaded by

Craig Lizcht
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/ 2

CS 161: Homework 1

Due by October 7, 2016 at noon


Instructions: Please answer the following questions to the best of your ability. Provide full and rigorous
proofs and include all relevant calculations. When writing proofs, please strive for clarity and brevity (in
that order). Please see the course website for submission instructions and collaboration policy. Cite any
sources that you use.

Question 1 (25 points)


1. What is the cardinality of the set of subsets of {1, 2, ..., }?
2. Let be a random variable denoting the cardinality of a randomly selected subset of {1, 2, ..., }
(where each subset has equal probability of being selected). What is the expected value of ?
3. Let rand(a,b) return an integer uniformly at random from the range [, ]. Each call to rand is
independent of other calls to rand. Consider the following function to simulate rolling a number of
dice:
roll(n,k):
sum = 0
for i = 1 to k:
sum = sum + rand(1,n)
return sum
Calculate the expected value and variance of roll(n,k).

Question 2 (25 points)


1. For each of the following functions, indicate whether = (), = (), or both ( = ()). Justify
your answers.
() = 62 + log + 6
( )
() = 7 log 7

(a)
(b)

() = 2 + 2
() = log

() = 32

(c)

() = 3

(d)

() = log

() = (log )2

(e)

() = 100

() = !

(f)

() = log log

() = (log )log

2. Show that

log = ( log ).

=1

3. Show that

=1

= (log ).

Question 3 (25 points)


Suppose that is a graph with 2 nodes and no triangles (cycles of length 3). is a proper graph, i.e. it
has no self-loops or multiple edges between the same pair of nodes. Prove that has at most 2 edges.

Question 4 (25 points)


In lecture, you saw how to solve the recurrence relation for MergeSort by drawing its recursion tree and
adding up the total running time. Use this method to solve the following recurrences that is, get a tight
bound of the form () = ( ()) for the appropriate function .
Show your work. If you wish, you may assume that initially has the form = , for an appropriate
constant .
1. () = 3 (/3) + 2
2. () = 4 (/2) + ()
3. () = ( 1) + , where > 0 is a positive constant.
Note: In this question, do not use the master theorem/method, which you will see in lecture soon.

You might also like