Submitting:

  • All homeworks should be turned in electronically to myCourses.
  • Paper submissions may be scanned in if legible.
  • If you take a photo of your paper solution, please take the photo outside or close to a bright window, for legibility.

Due dates:

  • Homeworks are due by 10pm on the due date (Thu).
  • No late submissions are accepted.
  • If there are extenuating circumstances, contact the instructor as soon as possible to make arrangements.

References:

  • If you find a resource helpful (from internet search, blog post, Stack Overflow, online courses, our lecture notes, etc), be sure to cite it. Citation format doesn’t matter, but make it easy for the TA to find the source: e.g., a clickable link.
  • Code / pseudocode should be your own work. If you find code online, understand how it works, then go write up your solution on your own.
  • The basic machine model was discussed in Lecture 1. Don’t use library functions which obviate the bulk of a question. E.g., if you’re asked to implement a sort, don’t use Python’s sorted().

HW2 (20pts) (solutions)

  1. (4pts) Demonstrate merge sort on the following array of integers (same as in HW1). Show as much work as you can. [ 35, 50, 44, 61, 17, 75, 23, 9 ]

  2. Consider the recurrence: ` T(n) = T(n/2) + T(n/4) + O(n) `.
    • a. (3pts) Guess a solution to the recurrence, showing your work.
    • b. (3pts) Prove your guess to be correct.

  3. (3pts) Solve the recurrence: ` T(n) = 8T(n/2) + 3n^3 + n^2 log n `

  4. (3pts) Demonstrate maximum subarray on the following input:
    [ 6, -5, 4, -1, -2, 4, 0, -3, 2, 3 ]

  5. (4pts) Recall that the best-case running time of insertion sort was Θ(n), although the worst-case was `Theta(n^2)`. Design (e.g., pseudocode) a randomised version of insertion sort that shuffles the input prior to running the sort. Discuss (provide reasoning, but need not be a formal proof) the running time of your randomised insertion sort.