Assign3: Recursive Problem Solving
Due Thursday, July 16 at 11:59 pm
 The assignment deadline is by the end of the day in Pacific Daylight Time. This means that you have until 11:59pm PDT on the day of the assignment deadline to submit the assignment.
 Submit by the end of the day Thursday deadline for a small, âearlybirdâ bonus.
 All students have a preapproved extension or "grace period" that extends until Friday end of the day PDT, with no penalty.
 The grace period expires at the end of the day Friday, after which we cannot accept further late submissions.
 Note that our Paperless submission system displays due dates and submission times in the PDT frame of reference.
Recursion is a powerful problemsolving tool with tons of practical applications. This assignment consists of a "sampler" of different recursion problems each of which is interesting in their own way. Learning to solve problems recursively can be challenging, especially at first. We think it's best to practice in isolation before adding the complexity of integrating recursion into a larger program â we'll get to incorporating recursion into a large program at the end of the quarter! By the time youâre done with this assignment, we think youâll have a much deeper appreciation both for the art of recursive problemsolving and the types of probelms that you can solve with your newfound skills.
For almost all students, recursive problemsolving can take a nontrivial amount of time to get used to. We recommend that you start on this assignment as early as possible, so as to allow yourself enough time to wrap your head around this new way of solving problems. In particular, we strongly recommend revisiting the lecture slides and examples, working through the Week 3 section probelms, and joining the discussion on Ed as you come across challenging questions. The recursive solutions you need to write to solve this collection of problems may be not require many raw lines of code, but this doesn't mean that you should put the assignment off until the last minute. While you may not have to write many lines of code, most of your time should be spent thinking through the recursive structure of the problem and really nailing down a detailed problemsolving approach in pseudocode before trying to code up the solution. By putting in the time to nail down the recursive fundamentals now, you'll be in prime shape to tackle recursive solutions for even more impressive problems later on in the course!
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 problemsolving and identify problems that are wellsuited to be solved recursively.
 Understand and trace how data is stored and altered across multiple recursive function calls.
 Identify and carry out techniques for testing and debugging recursive functions.
 Break down a problem into a collection of smaller, selfsimilar tasks.
 Develop a recursive algorithm by dividing a problem into one or more base cases and one or more recursive cases.
 Apply the general frameworks of recursive backtracking to solve problems that cannot easily be solved using an iterative approach.
 Implement more advanced recursive algorithms to solve problems that cannot be easily solved using an iterative approach
Assignment parts
This assignment consists of a collection of multiple different recursive exercises, grouped into two parts.

Part 1: Fundamental Recursion
The first collection of recursive problems walks you through some fundamental recursion problems that increase in difficulty and complexity over time. These problems will serve as the foundational practice for you to begin to grapple with the core tenants of recursive problemsolving. The material needed to solve these problems was covered in lecture on MondayWednesday (7/67/8).

Fundamental Recursion Warmup
Practice with unit tests and debugging on core recursive functions.

Balanced Operators
Determine whether a snippet of code has properly matched pairs of bracketing characters.

Sierpinksi Fractal
Draw a beautiful selfsimilar fractal triangle.

Merging Sorted Sequences
Implement an efficient divideandconquer algorithm for merging a collection of sorted sequences.


Part 2: Recursive Backtracking
The second collection of recursive problems pivots towards applying the powerful nature of recursive backtracking to solve some realworld problems. After you've built your solid base of recursive fundamentals in Part 1, you will be well set to apply your newfound skills to solve some practical realworld problems. The material needed to work through the debugging warmup for this part was covered on Thursday (7/9). However, the material to complete the two programming questions (Boggle and the optional Voting problem) will be covered on Monday (7/13).

Recursive Backtracking Warmup
Practice with unit tests and debugging on core recursive functions.

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

Optional Extra Credit Extension âÂ Examining Voting Systems
Put the finishing touch on your journey to being a recursive problemsolving master by completing this optional challenge problem, which involves investigating block voting systems (like the U.S. Electoral College).

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 fundamentalwarmup.cpp
, balanced.cpp
, sierpinksi.cpp
, merge.cpp
, backtrackingwarmup.cpp
, and boggle.cpp
.
Additionally, you will answer questions in short_answer.txt
.
Before getting started writing code, we highly recommend reading the CS106B Style Guide. All of your assignment submissions this quarter will be graded on their coding style, and this guide contains the coding standards that make up our style rubric.
Helpful Resources
Here are some resources that you might find helpful for this assignment:
 Trip's Assignment 3 YEAH Slides
 A Guide to Testing Code in CS106B
 Common Build/Run Errors Guide, put together by one of our wonderful section leaders, Jillian Tang.
 Stanford Libraries Documentation
 Lecture slides: Monday Intro to Recursion, Tuesday Recursive Fractals, Wednesday Using Recursion, Thursday Recursive Backtracking and Enumeration
 Section: Recursion
 Textbook Chapters 7, 8, and 9. These chapters are a great resource âÂ the explanations and examples for recursion are Eric Roberts at his very best. Eric is our longtime Stanford colleague and a truly gifted educator.
Getting help
Recursion can take some time to get used to, so donât be dismayed if you canât immediately sit down and solve these problems. Ask for advice and guidance if you need it. Once everything clicks, youâll have a much deeper understanding of just how cool a technique this is. You can contact us on Ed, email your section leader, or stop by the virtual LaIR (here is the schedule of help hours). You can find more information about how to get help at the LaIR here. As a reminder, try to visit the LaIR for coding debugging questions âÂ however, if you cannot make it to the LaIR due to timezone issues, you can post on Ed to get help. 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.
Submit
Before you call it done, run through our submission checklist to be sure all your ts are crossed and is dotted. Then upload your completed files for grading to the Paperless website.
Please submit only the files you edited; for this assignment, these files will be:
fundamentalwarmup.cpp
balanced.cpp
sierpinksi.cpp
merge.cpp
boggle.cpp
voting.cpp
(optional)short_answer.txt
đ Submit to Paperless
Note: When submitting to Paperless, due dates are expressed in PDT.