Edit the RMarkdown source file for this assignment in RStudio. Enter your responses after each question. When you finish, Knit the file to HTML and upload the .html output to Canvas.
Our textbook is Algorithms by Jeff Erickson, which we will henceforth refer to as [E]. Read about the running time of songs on pages 15-16 of [E], and then answer the following questions.
- Describe a song that requires \(\Theta(n^3)\) time to sing the first \(n\) verses. (This is problem 1(a) of [E].)
This is where your answer goes. Erase these sentences and replace them with your answer. Notice that you have to skip a line after the question so that the answer gets formatted differently from the question. If you want to make a pseudocode block, you can put it between two sets of three backticks, as follows.
pseudocode goes in blocks like this
They are rendered like <pre></pre> blocks in html.
You can indent, use special characters, etc.You can include mathematical expressions using LaTeX. Just delimit them with dollar signs: \(f(n) \in \Theta(g(n))\).
- Do problem 2 on pp. 17-18 of [E]. Justify your answers.
Describing algorithms in pseudocode is different from writing the code for an algorithm in a programming language. Read Section 0.4 of [E]. In particular, notice that it is OK to include things “that you’ve already learned how to do (like sorting, binary search, tree traversal, or singing ‘\(n\) Bottles of Beer on the Wall’)” as commands in your pseudocode. You don’t need to write the pseudocode for these subroutines; just invoke them.
- Describe an algorithm that inputs an array of \(n\) integers and another integer \(x\), and determines whether or not there are elements \(a\) and \(b\) in the array such that \(a+b=x\). Give the running time of your algorithm. (You should be able to find an algorithm with running time \(\Theta(n \log_2 n)\).)