------------------------------------------------------------------------------- CS99, Fall 2002: Homework 2 Due Monday 9/23 at BEGINNING of LECTURE ------------------------------------------------------------------------------- 0. Objectives Completing all tasks in this assignment will help you learn about the process of programming before you do actual writing of code. In this assignment, we expect you to do the following: * Follow all instructions for doing this assignment. * Demonstrate that you understand the process involved with solving a problem before writing a computer program. - Name a project - Brainstorm - Research - Outline * Create an appropriate and clear text file that contains the work that this assignment requires you to do. We've broken the assignment into these parts: * Section 1 introduces the problem. * Section 2 explains the tasks that you need to perform. * Section 3 provides specifications on your submission. First skim, and then, carefully read the ENTIRE assignment before starting any tasks! You may also wish to review last semester's equivalent homework assignment that demonstrates these tasks. Note that we have made some adjustments in this year's version. ------------------------------------------------------------------------------- 1. Algorithms and The Problem-Solving Process Problem: Suppose that a device randomly generates a random amount (between 1 and 3, inclusive) of bytes worth of bits that you need to analyze. Each bit has equal probability of being generated. You have been given the task of writing a program that performs one. At the end of the simulation, the program outputs the largest number of successively generated 1s. For instance, if the simulation generated 0011110010101110, the program would report the following output: Maximum sequence of 1s: 4. Ultimately, you will be required to write a program that performs this task. For now, you will do the initial development in solving that problem, but not actually *writing* the code! 2.1 Naming Pick a project name, which will be the name of your future program. You must first arrange a time to meet with your "development group," which, of course, is just yourself for this assignment. Every program must have a cool-sounding name! To show that you have this step, use this project name as part of the labeling for the remaining steps in this assignment. 2.2 Brainstorming Programming resembles writing a paper. What is the first step in writing? Brainstorming. For programming, brainstorming means writing down explicit and implicit specifications. Examples of explicit specifications include the following: * The devices generates a random number of bytes between 1 and 3, inclusive. * What does the simulation do if only 0s or 1s just happen to be generated? To help you develop this program, write down as many specifications as you can think of for this simulation, including the ones supplied to you, above. You might have to make some of your own decisions or request further clarification from your CLIENT (the person, company, or source asking you to develop your code). Include this write-up in your project as the first part of this solution. Do not forget to include the name of your program at the top. 2.3 Research After brainstorming, review your specifications and thoughts and look for *things* and *behaviors*. Sometimes I like to refer to this search as a game called "Spot the nouns and verbs!" (And thus, I deem this procedure as "research.") These nouns/things and verbs/behaviors will become important parts of your program. Unless you do something called object-oriented programming, you will likely represent each thing with a variable and behavior with an operation or function call. You may even wish to do actual research where you look up information related to your program. Often programmers need to work with other experts to develop software in the field for which the software is being written! For example, what is a bit? a byte? You might have to look up that information! Sometimes research means looking up prepackaged functions (MATLAB has collections of these functions in TOOLBOXES) for generating random numbers and any other part of the language that might help you. So, in your document, write out the results of all your "research." 2.4 Outlining The next stage of writing involves organizing your thoughts from brainstorming and research into an outline. For programming, these outlines are essentially ALGORITHMS (sequence of steps that explain how to solve a problem). So, take the specifications, and try to figure out how you, the human being, would model this simulation. Before you can automate the process, you must figure out how the simulation works, preferably on paper. You may even wish to simplify the problem first. To write an algorithm, organize your solution procedure and write each step as an instruction. If you have trouble writing the instruction, try to imagine that you are writing a recipe or manual for another person to follow. Each instruction should start with a verb (START, STOP, CHOOSE, REPEAT, PICK, OUTPUT, RETURN, FIND, INCREMENT, etc.) or condition (IF, ELSE, OTHERWISE, UNLESS, UNTIL, WHILE, etc.). When you pick these words, you are writing in PSEUDOCODE, which is a language that resembles a programming language. You may even wish to indent the pseudocode in blocks as if you were writing in actual code. Ideally, given well-written pseudocode, you could quickly convert any algorithm to actual code in almost any language. If writing on paper is too difficult, you could try a trick that DIS uses to appease the desire to program immediately: * Create a new text file with the editor that you use to create programs. * Pretend that you are writing a program, but write everything as comments. * Type the brainstorming notes, specifications, research, and algorithm as large blocks of comments. As you refine your approach, flesh out more and more of the algorithm until you feel ready to program. Eventually, you could feasibly (and quickly) write the necessary code a bit at a time, test that code, and move to the next portion. In the end, you will not only have produced working code, but the comments that go along with it as well! For this portion of this assignment, do *not* actually write the *code*! Instead, clearly write out your algorithm. In a future assignment, you will use the work in this project as we complete our demonstration of the entire development process. You will be drafting, writing, polishing, testing, and submitting your code. ------------------------------------------------------------------------------- 3. Submitting Your Work Type all your work for Section 2 (and its subsections) in a single text file, which is clearly labeled by problem. A text file is a file stored in ASCII format. Be sure to use a writing package, like Notepad. You can even create a MATLAB M-File, since MATLAB's editor produces ASCII text! Remember to follow the submission guidelines as specified in the syllabus. Print both the file and the grading guide. Staple the grading guide on top of your work. Do not e-mail your work this time! -------------------------------------------------------------------------------