Due Friday, May 7 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 48 hours after the due date. Late submissions are accepted during the grace period with no penalty.
- The grace period expires Sun, May 9 at 11:59 pm Pacific, after which we cannot accept further late submissions.
- 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.
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 can be completed in pairs. You will still have individual IGs (one per student), and you must work on all parts of the assignment together, at the same time.
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
This assignment consists of a warmup exercise and three separate problems to solve using recursive backtracking.
Practice with testing and debugging recursive functions.
Solve a 3 x 3 tile matching game.
An embedded ethics and coding exercise that investigates the practice of Gerrymandering through the lens of data analysis and recursive backtracking algorithms.
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.
The source files you will edit are,
voting.cpp. Additionally, you will answer questions in
Here are some resources that you might find helpful for this assignment:
- The Assignment 4 YEAH Session is scheduled for 7:30pm PDT, Sunday April 25th. Zoom information can be found on the Zoom Information page. Come join the party!
- Assignment 4 YEAH slides (TBA)
- 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 Procedural Recursion, Wednesday Intro to Backtracking, Friday More Backtracking, Monday C++ Classes
- Section: Backtracking
- Textbook Chapter 9 Recursive Backtracking
We have several channels where you can reach out to the course staff: post on Ed, email your section leader, join in at office hours, or sign up for one-one-one help at the LaIR. For questions specific to your code, coming to Lair is your best bet. If you cannot attend LaIR due to timezone issues, you may post your question on Ed. 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.
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:
Note: On Paperless, all due dates and submission times are expressed in Pacific time.