Fun with Collections

Friday, April 19

Due Friday, April 19 at 11:59 PM

  • Submit to Paperless. Deadline is 11:59 PM.
  • The late day policy gives you the ability to self-grant an extension (as long as you have not used all your late days); we trust you will make reasonable and sparing use of this power. Be sure to reserve late days for emergencies.
  • Reminder: You have a limited pool of late days. You have a total of 4 late days to use throughout the quarter, but you cannot use more than 2 late days per assignment. Late days are expended in 24-hour blocks. See the Assignments page for more details.

The recent lectures have introduced you to some of the classic Abstract Data Types (ADTs), and now it's time to put that knowledge to use. In this assignment, you will write code that leverages those ADTs to implement some nifty algorithms. 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 exercise using the debugger. two coding tasks that use of variety of ADTs, and short ethical reflection on efficiency.

  • Warmup

    Practice with testing and debugging on different abstract data types. Do the warmup first!

  • Maze

    A Grid of walls and corridors is used to represent a maze, and the Vector, Stack, Queue, and Set ADTs are used in a clever algorithm to find a solution path that escapes the maze.

  • Search Engine

    A Map is used to associate words with a Set of documents containing that word. Using the map, you can find matching entries that contain terms from simple or compound queries, and construct a mini search engine.

  • Beyond Algorithmic Analysis

    In this section, you will consider some of the human and societal impacts of designing and optimizing efficient software systems.

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 start without delay!

Getting started

📦 Starter project

The starter project is provided as a zip archive. Download the zip, extract the files, and move the project folder to your CS106B folder. Open the .pro file in Qt Creator to get started.

Resources

Getting Help

Keep an eye on Ed for an announcement of the YEAH (YEAH = Your Early Assignment Help) group session where our veteran section leaders will answer your questions and share pro tips. We know it can be daunting to sit down and break the barrier of starting on a substantial programming assignment – come to YEAH for advice and confidence to get you on your way!

The Ed forum is open 24/7 for questions about the assignment, lecture topics, the C++ language, using Qt, and more. Please first search Ed to see if your question has already been asked and answered before making a new post. To troubleshoot a problem with your specific code, your best bet is to bring it to the LaIR helper hours or office hours.

Submit

Before you call it done, run through our submit checklist to be sure all your ts are crossed and is 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.

🏁 Submit to Paperless

Note: On Paperless, all due dates and submission times are expressed in Pacific time.