Assign2: Fun with Collections

Due Saturday, April 25 at 11:59 pm

• The assignment deadline is by the end of the day, Anywhere on Earth.
• Submit by end of day Saturday deadline for a small, “early-bird” bonus.
• All students have a pre-approved extension or "grace period" that extends until Monday end of day AoE, with no penalty.
• The grace period expires end of day Monday, after which we cannot accept further late submissions.
• Note that our Paperless submission system displays due dates and submission times in PDT frame of reference.

This week's lectures have introduced you to the CS106 ADTs and now it's time to put those handy collections to use! With the low-level details abstracted away, your attention is freed to solve more interesting problems. Your next assignment is to write some client code that heavily leverage the ADTs to do nifty things. The tasks may sound a little daunting at first, but given the power tools in your arsenal, each requires only a page or two of code. Let's hear it for abstraction!

Learning goals

• To more fully experience the joy of using pre-written classes. Most of the heavy-lifting is handled by the collection ADTs.
• To stress the notion of abstraction as a mechanism for managing data and providing functionality without revealing the representational details.
• To become familiar with using C++ class templates.
• To learn how to model and solve problems using classic data structures such as vectors, grids, stacks, queues, sets, and maps.

Assignment parts

This assignment consists of a short warmup exercise and then two coding parts, each featuring use of different ADTs. The coding parts are roughly comparable to each other in size and scope, so pace yourself to complete each in about three days.

• Warmup

  Practice with unit tests and debugging on ADT types.

• Maze

  A Grid of walls and corridors is used to represent a max and the Stack, Queue, and Set ADTs are used in algorithms that to process and solve a maze.

• Search Engine

  A Map is used to associate words with a Set of web pages containing that word and allow efficient search for pages matching a compound query.

Getting started

We provide a ZIP of the starter project. Download the zip, extract the files, and open the project in Qt creator.

📦 Starter code

The two source files you will edit are maze.cpp and search.cpp.

Additionally, you will answer some questions in short_answer.txt.

Helpful Resources

Here are some resources that you might find helpful while working on this assignment:

• Lecture slides: Monday Vector/Grid, Wednesday Stack/Queue, Friday Set/Map
• Section: ADTs

Getting Help

This assignment is to be completed individually. Working in pairs/groups is not permitted.

As always, feel free to reach out to us if you have questions. Feel free to contact us on Ed, to email your section leader, or to stop by the virtual LaIR (helper hours this quarter are Sunday-Thursday evenings, 5:00PM – 9:00PM PDT and Monday, Tuesday mornings, 9:00AM - 11:00AM PDT). You can find more information about how to get help at the LaIR here. As a reminder, try to visit the LaIR for coding debugging questions – however if you cannot make the LaIR due to time zone issues, you can post your code on Ed to get help. However, you must use a private post so that you are not posting your code for the whole class to see.

Submit

Before you call it done, run through our submission checklist to be sure all your t's are crossed and i's dotted. Then upload your completed files for grading to the Paperless website.

Please submit only the files you edited; for this assignment, these files will be

• maze.cpp
• search.cpp
• short_answer.txt

You don't need to submit any of the other files in the project folder.

🏁 Submit to Paperless

Note: When submitting to Paperless, all due dates and submission times will be displayed in PDT across the website.