JavaScript isn't enabled in your browser, so this file can't be opened. Enable and reload.
Randomized Algorithms exercise 5
Sign in to Google
to save your progress.
Learn more
* Indicates required question
Name
*
Your answer
In a graph on n vertices, how many ways are there to pick a subset of 4 vertices? Write your answer using the Theta notation, e.g. Theta(n).
*
Your answer
Consider the G_{n,p} model. What is the expected number of 4-cycles?
*
Theta(n^3 p^3)
Theta(n^2 p^3)
Theta(n^3 p^4)
Theta(n^4 p^4)
Other:
In the previous question, for what values of p is the expected number of 4-cycles o(1)?
*
o(1/n)
o(1/n^2)
\omega(1/n)
\omega(1/n^2)
o(1/n^{4/3})
Other:
Submit
Clear form
Never submit passwords through Google Forms.
Forms
This form was created inside of The George Washington University.
Report Abuse
Terms of Service
Privacy Policy
Help and feedback
Contact form owner
Help Forms improve
Report