Due Thursday, July 25 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.
Last week's assignment introduced you to the intriguing world of recursion and built your base of recursive fundamentals. Now you move on to apply the power of recursive backtracking to solve real-world problems. As is typical in recursive problem-solving, the primary challenge is at the beginning as you work to develop the recursive insight, but once ready to write the code, a concise algorithm is all that's needed. That sparse elegance can sometimes seem incongruous with how hard you had to work for it. Start without delay 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
- Reflect thoughtfully on the ends to which you will apply these techniques
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.
-
Banzhaf power index
Compute the voting power of the different blocks in a block-voting system.
-
Computational Redistricting
Determine if there is a fair geometric division of a state's population into equal-size electoral districts.
Getting started
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
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.
- Textbook Chapter 9 Recursive Backtracking
Getting help
Look for an announcement on the Ed forum for the YEAH session for this assignment. We welcome your questions on the Ed forum. Always start by searching first to see if your question has already been 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
voting.cpp
redistrict.cpp
short_answer.txt
Note: On Paperless, all due dates and submission times are expressed in Pacific time.