Assign2: Fun with Collections

Due Wednesday, July 07 at 11:59 pm

• The assignment deadline is by the end of the day in Pacific Daylight Time. This means that you have until 11:59pm PDT on the day of the assignment deadline to submit the assignment.
• Submit by the end of the day Wednesday deadline for a small, “early-bird” bonus.
• All students have a pre-approved extension or "grace period" that extends until Friday end of the day PDT, with no penalty.
• The grace period expires at the end of the day Friday, after which we cannot accept further late submissions.
• Note that our Paperless submission system displays due dates and submission times in the PDT frame of reference.

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 will walk you through the process of writing 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 then two coding components, 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. Note: This assignment asks you to develop considerably more complex code than in Assignment 1, so make sure you get started early!

• Warmup

  Practice with unit tests and debugging on different abstract data types.

• Maze

  A Grid of walls and corridors is used to represent a maze, and the Stack, Queue, and Set ADTs are used in the implementation of a famous algorithm that can efficiently find a solution for the maze.

• Search Engine

  A Map is used to associate words found on the internet with a Set of web pages containing that word. This allows us to efficiently search for pages matching both simple and compoud queries, which emulates the behavior of a search engine!

• Beyond Algorithmic Analysis

  In this section, you will explore beyond traditional Big-O analysis to study some of the potential human and societal impacts of designing and optimizing efficient software systems.

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.

Before getting started writing code, we highly recommend reading the CS106B Style Guide. All of your assignment submissions this quarter will be graded on their coding style, and this guide contains the coding standards that make up our style rubric.

Helpful Resources

Here are some resources that you might find helpful for this assignment:

• Jin-Hee and Grant's Assignment 2 YEAH slides
• A Guide to Testing Code in CS106B
• Common Build/Run Errors Guide, put together by one of our wonderful section leaders, Jillian Tang.
• Stanford Libraries Documentation
• Lecture slides: Console Programs and Vectors, Ordered Data Structures, Unordered Data Structures, and Using abstractions
• Section: ADTs

Getting Help

As always, feel free to reach out to us if you have questions. You can contact us on Ed, email your section leader, or stop by the virtual LaIR (here is the schedule of help hours). 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 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 submission checklist to be sure all your ts are crossed and is 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

And that's it, congratulations 🥳. We hope you had fun with collections!

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