Algorithms and OOD (CSC 207 2014F) : Labs
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] - [Learning Outcomes] [FAQ] [Teaching & Learning] [Grading] [Rubric] - [Calendar]
Current: [Assignment] [EBoard] [Lab] [Outline] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Readings]
Reference: [Student-Curated Resources] [Java 8 API] [Java 8 Tutorials] [Code Conventions]
Related Courses: [CSC 152 2006S (Rebelsky)] [CSC 207 2014S (Rebelsky)] [CSC 207 2014F (Walker)] [CSC 207 2011S (Weinman)]
Misc: [Submit Questions] - [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] - [Issue Tracker (Course)] [Issue Tracker (Textbook)]
Summary: In this laboratory, you will explore the wonder of heaps.
Fork and clone the repository at https://github.com/Grinnell-CSC207/heaps.
Import the repository into Eclipse.
Scan through the code so that you understand what methods are available and what approaches are used. Make notes on areas that are likely to be problematic.
The file HeapExpt.java
contains a few simple experiments
with heaps. Pick one or two of those experiments, run the experiments,
and check that the heaps created seem to be correct.
As you may recall, the in-place heap sort algorithm has two phases. First, it turns the array into a heap. Then, it repeatedly swaps the largest remaining element to the appropriate place in the array.
Sketch invariants for each phase of heap sort.
The file HeapSorter.java
contains a stub implementation
of heap sort. Finish that implementation. You can check whether it
works using HeapSorterTest.java
.
Although we initially described the “swap up” algorithm
recursively, Heap.java
has an iterative
implementation. Rewrite swapUp
to use
recursion.
We've both described and implemented the “swap down”
algorithm recursively. However, as you know, many people prefer
iteration to recursion. Rewrite swapDown
to use iteration. You may not use break
to escape from
your loop. However, you may use a sentinel.
If you find that you have extra time, try any of the following problems.
Write a predicate that checks if an array is in heap order. Your predicate should have a signature something like.
public static <T> boolean isHeap(T[] values, Comparator<T> order) { .... } // isHeap
Add an iterator to the Heap
class. You may iterate the
values in any order you find easy. (You are likely to find it
easiest to iterate the values from left to right in the array.)
You need only implement the next
and
hasNext
methods. (You will have the
opportunity to implement the remove
method
in the next exercise.)
Implement the remove
method for the iterator
from the previous problem.
Implement an iterator that returns the values in order from largest to smallest. (Note: I know of no easy way to approach this problem.)