Assignments by week:
Fall Term:
Winter Term:
Spring Term:
Monday, January 21
Description
Queues
Homework
- Download the queue-implementation lab kit. Complete the two classes called LinkedQueue and ArrayQueue that implement the AP Queue interface. The linked implementation should use a singly-linked list. The array-based implementation should implement a fixed-size buffer (the size should be a parameter passed to the constructor, with a default value provided by the no-args constructor). All operations must be O(1) (constant time) for both implementations.
- Note: you may decide if you'd like to throw an exception for a full array or overwrite old data (be sure to document which you've chosen in your class comments!). Note that my unit tests expect an exception (fixed-size, not circular); if you're going to overwrite then you may wish to disable the "full()" test in ArrayQueueTest.java.
- Both implementations are due at the start of class on Friday. Our next class will have time for questions and working on the lab.
Tuesday, January 22
Description
Queue Implementation
Homework
- Keep working on your Queue lab, due Friday at the start of class.
- By next class, read the Wikipedia entry on Priority Queues, up through the Implementation section, covering the Naive and Usual implementations (you don't need to read about the more specialized implementations). Optionally, you may re-read 12.16 - Array Implementation for Complete Binary Trees and 12.17 - Heaps and Priority Queues from DSA. You read these when we covered Heapsort, and the same principles will apply as we cover priority queues.
- On Friday you'll have a practice test covering the linear data structures we've covered (Lists, Stacks, Queues). You won't need to write an implementation from scratch, but you should be familiar with using the data structures, as well as their trade-offs and common applications.
Thursday, January 24
Description
Introduction to Priority Queues
Homework
- Complete your Array- and Linked-Queue implementations, due at the start of next class.
- If you've finished your queue lab, move on to the priority queue lab; see tomorrow's homework for details.
Friday, January 25
Description
Practice Test
Homework
- Download the priq-implementation lab kit. Complete the PriQ class that implements the PriorityQueue interface. Due Thursday at the start of class. Your solution should adhere to the following guidelines:
- Your implementation should use a native array or an ArrayList as its backing structure.
- All operations should have an amortized runtime of O(log n) or better. (Amortized basically means you don't need to count the occasional array resize, but runtime should be O(log n) in every other case.)
- You should use the natural comparison between objects to determine their priority (in other words,
compareTo). The AP interface specifies a min-priority strategy, so you should always return the smallest item when you dequeue.
- Like our sorting methods, this class should only accept items that are Comparable to each other (even though the interface just says "E"). Note that the class is declared with this additional constraint:
public class PriQ<E extends Comparable<? super E>> implements PriorityQueue<E> {
-
If you use a raw array (instead of an ArrayList) in your implementation you'll need to make a small change to your array declaration. You should say something like:
private E[] a = (E[])(new Comparable[somesize]);
Note the use of Comparable instead of Object. Otherwise, Java's type checker won't know that you want to hold only items that are Comparable in the array.
- You may want to review your HeapSort code in preparation for Priority Queues. A Priority Queue does not need to create an "initial" heap (as it is not given unordered data at the start). But it does need to "re-heap" whenever a new item is added or an item is removed.