Assignment 2

What to Do

  1. Open this Google Doc.
  2. Make a copy of the Google Doc in your own Google account by choosing File → Make a Copy.
  3. Answer each of the questions below in the Google Doc by filling in the blanks marked TODO. Your answers, if not code, should be no more than a few sentences in length each.

Questions

  1. What does it mean for some algorithm to be in O(n)? That is to say, in “big oh of n”?

  2. When sorting n integers, why, as Obama notes, is bubble sort probably not the way to go?

  3. In a few sentences (or in step-by-step pseudocode), propose an algorithm via which to find the tallest person in a room.

  4. Assuming there are n persons in the room, what’s the running time of your algorithm, in terms of big-oh notation? Why?

  5. Generally speaking, what’s an array?

  6. In the context of linked lists, what is a pointer (otherwise known as a reference)?

  7. What are (at least two) advantages that a linked list offers over an array? Why?

  8. What price(s) do you pay when using a linked list instead of an array?

  9. What are (at least two) advantages that a tree offers over an array? Why?

  10. What might be a downside of storing (clean) plates in a stack, just as Harkness Cafe does?

  11. Why is it a good thing that Harkness Cafe “stores” customers in queues, and not stacks, at checkout?

Debrief

  1. About how many MINUTES would you say you spent on this assignment? Just to set expectations for future students.

How to Submit

  1. Download your completed assignment as a PDF by choosing File → Download → PDF Document, and save it to your computer.
  2. Go to CS50 for JDs’s Gradescope page.
  3. Click Assignment 2.
  4. Click Submit PDF.
  5. Click Select PDF and choose your assignment file.
  6. Click Upload PDF.
  7. Click the first question in the Question Outline at left, then click the page (or pages) on which your response to that question is located. Repeat this process for the remaining questions.
  8. Click Submit.

You should see a message that says “Assignment 2 submitted successfully!”

If you run into any trouble with the above steps, email hls@cs50.harvard.edu!