Discussion 13 handout

Group members (names & NetIDs)

Objectives

• Translate between tree and array representations of heaps
• Restore heap invariants by bubbling up and down
• Explore optimizations for navigating graphs (relevant to A6)

Binary heaps

Push

Consider a min-heap of integers (where each element’s priority is its own value). The elements are stored in int[] b, where b.length is 13. Here are the current values in b (a ? indicates an element whose value is not logically contained in the heap; the heap currently has size 11):

{ 4, 5, 7, 6, 8, 8, 9, 7, 7, 8, 9, ?, ? }

Draw the complete binary tree representation of this heap. Label each node with its index in the array.

Add the value 3 to the end of the heap, then bubble it up to its appropriate location. Draw the resulting tree.

Write the sequence of values contained in b representing the above tree.

Pop

Consider a min-heap of integers (where each element’s priority is its own value). The elements are stored in int[] b, where b.length is 15. Here are the current values in b (a ? indicates an element whose value is not logically contained in the heap; the heap currently has size 12):

{ 2, 3, 4, 7, 6, 5, 6, 8, 9, 8, 9, 7, ?, ?, ? }

Draw the complete binary tree representation of this heap. Label each node with its index in the array.

Pop the next element from the heap, then perform the necessary operations to restore the heap invariants. Draw the resulting tree.

Write the sequence of values contained in b representing the above tree.

What value should be returned by pop() after completing the above operations?

Further practice

For homework, open the dis13 project in IDEA and study its implementation of a heap that separates values from priorities. There are three TODOs in the code; based on the specifications and invariants, uncomment the appropriate line for each TODO, then run the accompanying test suite to check your work. We recommend reading the JavaHyperText entry on heaps with priorities.

Challenge problem

Modify the Heap class to support an updatePriority(e, p) operation that changes the priority of e to p and restores the heap’s class invariants. Your implementation should have a time complexity in O(lg N), where N is the size of the priority queue (you may assume O(1) lookups from a standard library hash table in this analysis). Be sure to document any fields and class invariants you add to the class.

Optimizing graph navigation

Seek

Discuss and propose at least two ways one could optimize the “seek” logic in A6 to find the ring in fewer steps in most cases. For a baseline, assume a depth-first search with strict backtracking.

Some questions you might consider include:

• When encountering a fork in the road, should one path be searched before the other?
• Suppose one fork goes in a loop. Is strict backtracking the best way to get back so you can take the other fork?
• When backtracking to a previous fork, should it always be the most recent one?
• Should you always explore a fork all the way until the tunnel dead-ends?

Scram

Discuss and propose at least two ways one could optimize the “scram” logic in A6 to gather more coins on the way out.

Some questions you might consider include:

• When should McDiver head straight for the exit?
• How might you decide between heading towards a big coin far away vs. claiming several small coins close by?
• Do you expect a “greedy” approach (planning only which coin to take next) to be optimal? If not, what would be required to consider longer-term plans?

Submission

1. Open the assignment page for “Discussion activity 13” in CMSX
2. [Recorder] Find the “Group Management” section and invite each group member
3. [Others] Refresh the page and accept your invitation
4. [Recorder] Take a picture of your work and save as either a JPEG or a PDF file named “discussion_responses”. After all invitations have been accepted, upload your picture along with your code as your group’s submission.
   • Recommended scanning apps: Microsoft Office Lens, Adobe Scan, Genius Scan, Evernote Scannable

Ensure that your group is formed and your work submitted before the Friday evening deadline.

Tips and reminders

• Discussion is not a race. Focus on the current activity being facilitated by your TA and engage your whole group to propose and explain ideas.
• Elect a recorder to maintain the “master” copy of your work (others are still encouraged to jot down ideas on scratch paper). Rotate this position each week.
• It is a violation of academic integrity to credit someone for work if they were not present when the work was done, and the whole group is accountable. Your CMS group must only include classmates who attended section with you on that day. Remember that our participation policies accommodate occasional absences without penalty.
• It is your individual responsibility to ensure that you are grouped on CMS and that your group’s work is submitted before the deadline. Log into CMS the day after section to ensure that everything is in order, and contact your groupmates if not. It would be prudent for multiple members to photograph the group’s work.
• Only one group member (typically the recorder) needs to upload a submission. But their submission must not be uploaded until after all group members have confirmed their membership in CMS (contact your TA if you have trouble grouping in CMS).