Assignment 2. Fun with Collections

Due Friday, July 14 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 24 hours after the due date. Late submissions are accepted during the grace period with no penalty.
  • The grace period expires Sat, Jul 15 at 11:59 pm Pacific, after which we will deduct 15% per late day.
  • You must submit the assignment by Thu, Jul 20 at 11:59 pm Pacific to receive any credit. We will not accept any submissions past this date.
  • 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.

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 you've got some powerful tools in your arsenal to tackle these challenges. Let's hear it for abstraction!

We'll end with a recursion problem that presents an alternative approach to the Check Balance problem you may have seen in Section 2. We'll cover recursion in Monday's lecture, so you'll want to save this problem for last.

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

Learning goals

  • Experience the joy of using pre-written classes. Most of the heavy-lifting is handled by the collection ADTs.
  • Use abstraction as a mechanism for managing data and providing functionality without worrying about the representational details.
  • Model and solve problems using classic data structures such as vectors, grids, stacks, queues, sets, and maps.
  • Leverage recursion to repeatedly break down a problem into more managable steps.

Assignment parts

This assignment consists of a short warmup exercise using the debugger and two coding tasks that use of variety of ADTs. You'll finish off with a recursion problem that operates on strings.

  • 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.

  • Balanced Operators

    Determine whether an expression has properly matched pairs of bracketing characters. Compare an iterative and recursive approach to this problem.

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.

📦 Starter code

The source files you will edit are maze.cpp, search.cpp, and balanced.cpp. Additionally, you will answer the questions in short_answer.txt.

Resources

Getting Help

Keep an eye on the Ed forum 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
  • balanced.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.