Algorithms and OOD (CSC 207 2013F) : Labs
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] [FAQ] [IRC] [Teaching & Learning]
Current: [Assignment] [EBoard] [Lab] [Outline] [Partners] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Partners] [Readings]
Reference: [Java 7 API] [Java Code Conventions]
Related Courses: [CSC 152 2006S (Rebelsky)] [CSC 207 2013S (Walker)] [CSC 207 2011S (Weinman)]
Misc: [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] [Issue Tracker (Course)] [Issue Tracker (Textbook)]
Summary: In this laboratory, you will have an opportunity to ground your understanding of priority queues, particularly of the array-based implementation of queues.
Required Code Files:https://github.com/Grinnell-CSC207/linear
a. Add up the number of vowels in the first names of all of your group members. Remember if that number is even or odd.
b. Review the reading on linear structures.
c. Review the reading on priority queues.
d. If you haven't already done so, fork and clone the repo at https://github.com/Grinnell-CSC207/linear If you have forked and cloned that repository, pull changes from the upstream repository using commands something like the following.
$ git commit $ git remote add upstream https://github.com/Grinnell-CSC207/linear $ git pull upstream master
You may also have to fix any merge conflicts. After fixing the merge conflicts, try something like the following to note that you have resolved those conflicts.
$ git add merged-file-1.java $ git add merged-file-2.java $ git commit
a. Read through our interface for priority queues,
PriorityQueue.java
.
b. Read through the documentation on the standard Java implementation of priority queues, available at http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html.
c. Note how you would write a wrapper class (formally, an adapter class) to make the built in priority queues behave like our priority queues.
d. Look at BuiltinPriorityQueue.java
to see how our
implementation matches your design.
Look at PriorityQueueExpt
. Summarize what the queue
should look like at each step of the first series of procedure calls.
You may also want to revisit the ReportingLinearStructure
class.
Run PriorityBasedQueueExpt
and see if you get the output that
you expect.
a. Revise PriorityQueueExpt
so that the queue gives highest
priority to the longest strings. That is, get
should
return the longest remaining string.
b. Revise PriorityQueueExpt
so that the queue gives
highest priority to the alphabetically first string.
Read through ArrayBasedPriorityQueue.java
. You will note
that the iterator is not yet implemented and that prioritization is not
yet implemented.
Make some notes to yourself as to how you might finish implementing
the put
and get
methods.
As the reading noted, there are two basic strategies for implementing priority queues in arrays.
put
method must ensure that
the elements in the array are stored in order. (You can probably
use a variant of the insert
method from insertion sort to
achieve that goal.)
get
or
peek
. (You can probalby use a variant of the
indexOfSmallest
method from selection sort to
achieve that goal.)
If you came up with an even number in the preparation, use the first of the two approaches. If you came up with an odd number, use the second of the two approaches.
If you are fortunate enough to have extra time, do some of the following:
get
. The easy approach is to simply pick a random
position each time. However, that approach does not guarantee
that peek
returns the same value as the subsequent
get
. Start with the easy approach, and then see if you
can get peek
and get
to work in synchrony.
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] [FAQ] [IRC] [Teaching & Learning]
Current: [Assignment] [EBoard] [Lab] [Outline] [Partners] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Partners] [Readings]
Reference: [Java 7 API] [Java Code Conventions]
Related Courses: [CSC 152 2006S (Rebelsky)] [CSC 207 2013S (Walker)] [CSC 207 2011S (Weinman)]
Misc: [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] [Issue Tracker (Course)] [Issue Tracker (Textbook)]
Copyright (c) 2013 Samuel A. Rebelsky.
This work is licensed under a Creative Commons Attribution 3.0 Unported License. To view a copy of this
license, visit http://creativecommons.org/licenses/by/3.0/
or send a letter to Creative Commons, 543 Howard Street, 5th Floor,
San Francisco, California, 94105, USA.