Due Friday, October 2 at 11:59 pm Pacific
- Submissions received by due date receive a small on-time bonus.
- All students are granted a pre-approved extension or "grace period" of 48 hours after the due date. Late submissions are accepted during the grace period with no penalty.
- The grace period expires Sun, Oct 4 at 11:59 pm Pacific, after which we cannot accept further late submissions.
- In this course, we express all date/times in Pacific time GMT -7. Our Paperless submission system also displays/records due dates and submission times in Pacific time.
This week's lectures have introduced you to the many different Abstract Data Types (ADTs) that exist in the world, and now it's time to put those handy collections to use! With the low-level details of how these data structures work abstracted away, your attention is free to solve more interesting problems. This assignment asks you to write client code that leverages many different ADTs to implement some nifty algorithms and systems. The tasks may sound a little daunting at first, but given the powerful tools in your arsenal, each requires a very manageable amount of code. Let's hear it for abstraction!
This assignment is to be completed individually. Working in pairs/groups is not permitted.
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 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/debugging exercise and two coding tasks, each featuring use of different ADTs. We strongly encourage that you complete the warmup first and only then go on to the coding tasks.
-
Warmup
Practice with testing and debugging on different abstract data types.
-
Maze
A
Grid
of walls and corridors is used to represent a maze, and theStack
,Queue
, andSet
ADTs are used in the implementation of a famous algorithm that can efficiently find a solution path to escape the maze. -
Search Engine
A
Map
is used to associate words with aSet
of documents containing that word. Using the map, you can find matching entries that contain terms from simple or compound queries, which emulates the behavior of a search engine.
The two coding tasks are roughly comparable to each other in size and scope, so pace yourself to complete each in about three days. Note: The code you will write for Assignment 2 is considerably more complex than Assignment 1, so be sure to get an early start!
Getting started
We provide a ZIP of the starter project. Download the zip, extract the files, and double-click the .pro
file to open the project in Qt Creator.
The two source files you will edit are maze.cpp
and search.cpp
. Additionally, you will answer the questions in short_answer.txt
.
Resources
- The Assignment 2 YEAH Session will be held on Sunday, September 27 at 2pm PDT. Zoom information can be found on the Zoom Information page. This session is a great opportunity to get an overview of the assignment before getting started working on it!
- Trip's Assignment 2 YEAH slides
- The CS106B Guide to Testing
- The CS106B Style Guide
- Resolving Common Build/Run Errors, compiled by section leader Jillian Tang.
- Stanford library documentation for Vector, Grid, Stack, Map, Set
- Lectures: Vector and Grid (Mon), Stack and Queue (Wed), Friday Set and Map (Fri)
- Section: ADTs
Getting Help
As always, feel free to reach out to us for support. You can contact us on Ed, email your section leader, or stop by the virtual LaIR, or come to office hours. As a reminder, try to visit the LaIR for coding debugging questions – however, if you cannot make it to the LaIR due to timezone issues, you can post on Ed to get help. However, you must use a private post if you are including code so that you are not posting your solutions for the whole class to see.
Submit
Before you call it done, run through our submit checklist to be sure all your t
's are crossed and i
's dotted. Then upload your completed files to Paperless for grading.
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.
Note: On Paperless, all due dates and submission times are expressed in Pacific time.