Princeton Algorithms: Part 1, Week 2

Resources

• Lecture Slides

  • 1.3 — Bags, Queues, and Stacks
  • 2.1 — Elementary Sorts

• Book Notes

  • 1.3 — Bags, Queues, and Stacks
  • 2.1 — Elementary Sorts

• Assignment

  • Problem Description
  • Assignment Checklist
  • Files

Programming Assignment

Deque Implementation

I implemented a generic doubly linked-list to handle insertions at the end and beginning of the sequence. I created a Deque iterator to iterate through the data structure's sequence. The implementation passed all correctness, memory, and timing tests.

Randomized Queue Implementation

I used a generic array to allow for easier randomization, selection, and deletion of random elements, and the creation of new iterators. Resizing was done in amortized constant time. The implementation passed all correctness, memory, and timing tests.

Permutation

I created a class to read in N strings while randomly selecting K elements to output. It is supposed to use the Deque or Randomized Queue implementation with a maximum size of N. I used a Resevoir Sampling algorithm to pass the bonus challenge associated with this problem. At first, I tried a naive implementation by keeping all strings up to K and then randomly dequeuing items, but it did not meet the bonus requirements nor the basic correctness requirements for correctness. It passed all correctness and timing tests while exceeding memory tests by fulfilling the bonus requirements.

Results