Assignment by Chris Gregg, based on an assignment by Chris Piech, Marty Stepp and Victoria Kirst. Originally based on a problem by Julie Zelenski and Jerry Cain.
Screenshots from the Mandelbrot and Grammar Solver parts of the assignment.
This assignment focuses on some cool problems that can be solved with recursion, both graphical (fractals) and textual (grammar solver). In the first portion of the assignment, you'll write several recursive functions to draw graphical patterns, also known as fractals. In the second portion of the assignment, you'll write a function to generate random sentences from provided "grammars", or word structures. This lets you generate random text, but from only the syntax rules, and not any previously-written text. We hope you enjoy these problems!
This assignment consists of two parts:
Note: ignore 20 Questions and Fractals flood fill. Also, the JAR does not demonstrate Mandelbrot.
It is fine to write "helper" functions to assist you in implementing the recursive algorithms for any part of the assignment. Some parts of the assignment essentially require a helper to implement them properly. However, it is up to you to decide which parts should have a helper, what parameter(s) (if any) the helpers should accept, and so on. You can declare function prototypes for any such helper functions near the top of your
.cpp file. (Don't modify the provided
.h files to add your prototypes; put them in your own
.cpp file.) We provide a GUI (graphical user interface) for you that will help you run and test your code.
Turn in only the following files via the Paperless submitter:
fractals.cpp, the C++ code for the Part A Fractals program
grammersolver.cpp, the C++ code for the Part B Grammar Solver program
mygrammar.txt, your own unique Part B input file representing a grammar to read in as your program's input
You may optionally work on this assignment as a pair programming assignment.
If you would like to work in a pair on this assignment, you may, under the following
As in other assignments, you should follow our Style Guide for information about expected coding style. You are also expected to follow all of the general style constraints emphasized in the Homework 1 and 2 specs, such as those detailing good problem decomposition, parameters, using proper C++ idioms, and commenting. The following are additional points of emphasis and style constraints specific to this problem.
Recursion: Recursion: Part of your grade will come from appropriately using recursion to implement your algorithm, as we have described. We will also grade on the elegance of your recursive algorithm; don't create special cases in your recursive code if they are not necessary. Avoid "arm's length" recursion, which is where the true base case is not found and unnecessary code or logic is inserted into the recursive case. Redundancy in recursive code is another major grading focus; avoid repeated logic as much as possible. As we mentioned above, it is fine (and sometimes necessary) to use "helper" functions to assist you in implementing the recursive algorithms for any part of the assignment.
While not new to this assignment, we want to stress that you should not make any global or static variables (unless they are constants declared with the
const keyword). Do not use global variables as a way of getting around proper recursion and parameter-passing on this assignment.
Collections: Do not use any collections on any graphical algorithms in this part of the assignment.