Assign4: Backtracking

Due Friday, May 08 at 11:59 pm

• The assignment deadline is by the end of the day, Anywhere on Earth.
• Submit by end of day Friday deadline for a small, “early-bird” bonus.
• All students have a pre-approved extension or "grace period" that extends until Sunday end of day AoE, with no penalty.
• The grace period expires end of day Sunday, after which we cannot accept further late submissions.
• Note that our Paperless submission system displays due dates and submission times in PDT frame of reference.

Recursion is a powerful problem-solving tool with tons of practical applications. This assignment centers on three real-world recursion problems, each of which we think is interesting in its own right. By the time you’re done with this assignment, we think you’ll have a much deeper appreciation both for recursive problem solving and for what sorts of areas you can apply your newfound skills to.

Learning goals

• Gain familiarity applying the choose/explore/unchoose framework of recursive backtracking
• Implement more advanced recursive algorithms to solve problems that cannot be easily solved using an iterative approach
• Practice using recursion to build and explore different data structures

Assignment parts

This assignment consists of a short warmup exercise and three recursive problems.

For this assignment, we are requiring that you complete the warmup and at least 2 of the 3 remaining problems. We strongly recommend completing all 3 if you have the time and capacity to do so, as it will make for good practice in solidifying the concepts we have seen in class. However, completion of only 2 of the 3 non-warmup parts is the baseline that we will be using as "full-credit" on this assignment. If you decide to complete all 3 parts, you will be eligible for extra-credit, similar in vein to completing extensions on other assignments.

After you have completed the warmup, you may select any combination of the 3 remaining problems to complete (hmmm, how many different possible ways could you choose to complete this assignment?). We recommend looking over all 3 parts before getting started.

• Warmup

  Practice with unit tests and debugging on recursive functions.

• Multi-merge

  An efficient recursive divide-and-conquer algorithm for merging a collection of sorted sequences.

• Boggle score

  Find all words on a given Boggle board and tally maximum possible score.

• Banzhaf power index

  Compute the voting power of the different blocks in a block-voting system.

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 source files you will edit are warmup.cpp, merge.cpp, boggle.cpp, voting.cpp

Additionally, you will answer questions in short_answer.txt.

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

Getting help

Here are some resources that you might find helpful while working on the assignment:

• You can find the slides from the Assignment 4 YEAH session here and the recording of the session has been posted on Canvas. We highly recommend starting with these resources as you get started on the assignment.
• Lecture Slides: Monday Procedural Recursion, Wednesday Backtracking, Friday More Backtracking
• Section: Recursive Backtracking
• Textbook Chapter 9 Recursive Backtracking.
• We’re here to help you get there! Contact us on Ed discussion, email your section leader, or come join non-stop coding party that is the LaiR.

Submit

Review our submission checklist before calling it done. Upload your completed files for grading to the Paperless website.

Please submit only the files you edited; for this assignment, these files will be

• warmup.cpp
• merge.cpp
• boggle.cpp
• voting.cpp
• short_answer.txt

🏁 Submit to Paperless

Note: When submitting to Paperless, due dates are expressed in PDT.