Due Friday, October 22 at 11:59 pm
- Submissions received by the 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 24 at 11:59 pm, after which we cannot accept further late submissions.
- All due dates and submission times are expressed in Pacific time.
Last week's assignment introduced you to the intriguing world of recursion and built your solid base of recursive fundamentals. This week we pivot towards applying the powerful nature of recursive backtracking to solve real-world problems. As is typical in recursive problem-solving, you'll likely spend the bulk of your time wrapping your head around the "thinking recursively" part, but once writing the actual code, you'll find that a rather concise algorithm is all that's needed to solve the task. That sparse elegance can sometimes seem incongruous with how hard you had to work for it. Start early to give yourself enough time to let these deep and powerful ideas percolate to full understanding. When you put the finishing touches on these problems, you will have earned your rightful place as a master in the way of recursive problem-solving.
This assignment is to be completed individually. Working in pairs/groups is not permitted.
Learning goals
After completing this assignment, you will be able to…
- Appreciate the elegance and power of recursive problem-solving and identify problems that are well-suited to be solved recursively
- Implement more advanced recursive algorithms to solve problems that cannot be easily solved using an iterative approach
Assignment parts
This assignment consists of a warmup exercise and three separate problems to solve using recursive backtracking.
-
Warmup
Practice with testing and debugging recursive functions.
-
Text Predict
Predict a user's intended word when typed on old-style phone keypad.
-
Scoring Boggle
Find all words on a given Boggle board and tally the maximum possible score.
-
Voting Power
Compute the voting power of the different blocks in a block-voting system such as the U.S. Electoral College.
Getting started
We provide a ZIP of the starter project. Download the zip, extract the files, and open the .pro file in Qt Creator.
The source files you will edit are, predict.cpp
, boggle.cpp
, and voting.cpp
. Additionally, you will answer questions in short_answer.txt
.
Resources
Here are some resources that you might find helpful for this assignment:
- The CS106B Style Guide
- A Guide to Testing Code in CS106B
- Common Build/Run Errors Guide, put together by one of our wonderful section leaders, Jillian Tang.
- Lectures: Monday Recursive Problem Solving, Wednesday Recursive Backtracking and Enumeration, Friday More Backtracking
- Section: Backtracking
- Textbook Chapter 9 Recursive Backtracking
Getting help
Look for an announcement on the Ed forum for the YEAH session for this assignment. If you have questions for us, the Ed forum is open 24/7 for general discussion. Always start by searching first 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 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:
predict.cpp
boggle.cpp
voting.cpp
short_answer.txt
Note: On Paperless, all due dates and submission times are expressed in Pacific time.