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().

Pseudocode vs real code

  • For this HW, only pseudocode is required, it does not need to compile.
  • However, starting with HW6 there may be some coding projects in the HWs, so if you want to get prepared, you may optionally submit complete code for this HW.
  • If submitting code, you can ZIP/tar your files together for upload, or just upload them separately. Ensure your code is clear and easy for the TA to read.
  • You may also try using Git to track revisions to your code; tutorials are linked from our course homepage.

HW5 (20pts) (solutions)

  1. Consider a doubly-linked list.
    • (a) (1pt) Write (pseudocode) class definitions for a single node in the list and for the list as a whole.
    • (b) (4pts) Write (pseudocode) a function that deletes duplicate items from such a list.
      E.g., input [ 7, 1, 4, 7, 3, 4, 7 ] → output [ 7, 1, 4, 3 ]
      You may assume the items are integers between 0 and 99.
    • (c) (1pt) What is the running time of your algorithm, in terms of the length n of the list?

  2. (4pts) Augment the Stack pseudocode in the lecture slides to track the size of the stack and implement length() and isempty(). Handle stack underflow properly.

  3. (3pts) Illustrate the binary search tree after each operation in the following sequence (starting from an empty tree):
    • insert( 'D' )
    • insert( 'M' )
    • insert( 'B' )
    • insert( 'G' )
    • insert( 'K' )
    • insert( 'H' )
    • delete( 'D' )
    • insert( 'L' )
    • delete( 'G' )
  4. Preorder traversal of a binary search tree of characters yields the following sequence: M F D H G L K V P N S Q T
    • (a) (2pts) Draw the tree.
    • (b) (2pts) Print a postorder traversal.
  5. (3pts) Write pseudocode for a function which takes a sorted array of keys (length known) and returns a balanced BST (i.e., of minimal height).