Introduction to Programming (Fall 2011)

This class is taught by Jay McCarthy.

We meet in TMCB 1170 at 9:00 MWF.

Jay McCarthy’s office hours are 9am to 4pm, except during classes and lunch, in 3328 TMCB. Although, feel free to call him on the phone between 8am and 10pm (excluding 5pm to 7pm) on Monday through Saturday at: the phone number behind this link.

There is a mailing list hosted at Google Groups. Use it to ask non-revealing questions and receive answers, as well as general course announcements. If you are nervous about asking questions, you can use anonymous email. You are responsible for content appearing on the mailing list, whether you read it or not.

1 Introduction

This course is an introduction to programming. We assume no previous experience with programming.

2 Meetings

	Start	End	Topic	Code	Screen
1	8/29	8/31	Introduction to Programming and C++	1 2	1 2
2	9/2	9/7	Expressions and Functions	1 2	1 2
3	9/9	9/12	Function Composition and Conditionals	1 2	1 2
4	9/14	9/16	Conditionals and Strings	1 2	1 2
5	9/19*	9/21*	Objects	1 2	1 2
6	9/23	9/26	Objects and Nested Objects	1 2	1 2
7	9/28	9/30	Methods	1 2	1 2
8	10/3	10/5	Mixed Data	1 2	1 2
9	10/7	10/10	Introduction to Lists	1 2	1 2
10	10/12	10/14	More on Lists	1 2	1 2
11	10/17	10/19	Producing Lists; Sorting	1 2	1 2
12	10/21	10/24	Lists of Objects	1 2	1 2
13	10/26	10/28	More Lists of Objects	1 2	1 2
14	10/31	11/2	Trees	1 2	1 2
15	11/4	11/7	Trees and Hierarchy	1 2	1 2
16	11/9	11/11	More on Hierarchies	1 2	1 2
17	11/14	11/16	Introduction to Mutation	1 2	1 2
18	11/18	11/21	Program Design with Mutation	1 2	1 2
19	11/22	11/28	Changing Structure Contents	1 2	1 2
20	11/30	12/2	More on Mutation with Structures	1 2	1 2
21	12/5	12/7	Deep Dark Secrets of C++	1 2	1 2

This schedule may change.

Jay will be absent on days marked with a *. Instead, one of the TAs will teach.

3 Help

You can get help in various ways:

You must read the Google Group in this class. If you need help, please check the list for past answers and then ask your own question.
If you want a little bit faster turn-around, there is a chat room for the course. (Make sure you prefix your message with the name of a TA or me (jeapostrophe), because it makes a notification pop-up on their screen.)
If you want to talk in person, you can find TAs in 1058 TMCB (offices 19 and 20) on MWF and 1121 TMCB on TR. They have a schedule. There are TAs in other places for other sections of 142; please do not bother them, every section of 142 has its own TAs and they are each paid by a different professor and are instructed specfically for each section. In other words, if you talk to another section’s TAs, you’ll be overburdening that section’s staff and getting incorrect information.
My office is 3328 TMCB, so you can stop by and chat. I try to hang out in the 1121 lab on Tuesday and Thursday, so you may want to check there on Tuesday and Thursday. You can also call me (see the top of this page for the number.)

4 Course Software

In this course, we will learn programming with C++.

You can program C++ with Emacs on the CS department Linux machines.

The first step to getting started with C++ is to log on to the CS machines. You can do this from your personal computer or use a CS computer. If you use a CS department computer, please use the computers in TMCB 1121. This page describes the process, although I will abbreviate it here for you.

If you are on Windows, download PuTTY. If you are on Mac OS X, open Terminal found in the Utilities folder of the Applications folder. (You can also just type Terminal into Spotlight.) On Linux, open some terminal program.

Your username will be your NetID—in all lower case. The password will be your 9-digit student ID.

Connect to schizo.cs.byu.edu (or weapons.cs.byu.edu, simpsons.cs.byu.edu, sports.cs.byu.edu, or pizza.cs.byu.edu.) On OS X and Linux, type

ssh -l NetID schizo.cs.byu.edu

With PuTTY, there should be a menu to specify this same information.

Next, type in your password. You won’t see any letters, but you are really typing!

You are now in Linux. A little Linux tutorial is a short introduction to simple things like creating and navigating files. In general, you type stuff and then press Enter to send the commandline to Linux. You can also watch this short tutorial video.

You should create a directory for all your work in this course:

mkdir 142

You should initialize the course turn-in system:

~jay/courses/2011/fall/142/install

Then you should log out of the system and log back in. Only do this once.

email your-email@address.com

name Your Name

When you start an assignment, suppose we are doing assignment 0, create a new directory for it and enter it:

mkdir ~/142/0

cd ~/142/0

Now, to work on an exercise, suppose we are doing exercise 1, open it in Emacs:

emacs -nw 1.cc

Now you are in Emacs, here is a short tutorial on basic Emacs usage.

Most of your C++ exercise programs will start like this:

/* Jay McCarthy: Assignment 0: Exercise 1

Create a "HelLOL World" program.

#include <stdio.h>

#include <math.h>

#include <stdlib.h>

int main () {

printf("Ima in ur conpyuta, rn'ng ur progZ\n");

return 0;

}

When you are ready to save the file, press Control-x then Control-s. This is abbreviated C-x C-s. Next, you can quit Emacs with C-x C-c.

Now you are back at the command-line. You compile C++ programs by typing:

g++ 1.cc -o 1.bin

You can then run your program by typing:

./1.bin

You will often need to open your file back up in Emacs to change it to get the compilation working or to make the run work like you expect. Because you’ll do this so many times, you can compile and run from inside Emacs by typing C-t.

4.1 A little Linux tutorial

This tutorial was written by Nick Shelley. He titled the email "For stupid, by stupid". Cute, but I think more highly of both Nick and the reader. :)

After you log in, you will see what is called a prompt. It is usually some text followed by a $ symbol. This just means you can type in commands and press Enter to have them run.

Directory is what "folders" are called in Linux.

Here is a list of commands you can ype at the prompt:

ls : list the files and directories (folders) in the current directory (folder)
pwd : print working directory (or folder, see how they’re the same?)
mkdir <dir-name> : creates a directory in your current location named "dir-name" For example, mkdir 142 creates a directory named 142 and place it in the current directory.
cd <name> : change directory to that specified by "name". Predefined names include "..", which is your parent directory, and "~" which is your home directory. For example: cd ~ takes you to your home directory cd .. : takes you to your parent directory (the directory that contains your location) cd 142 : takes you to the 142 directory, assuming that directory exists in your current location (type ls to make sure)
mv <existing-thing> <new-location-or-name> : move something somewhere else. Also renames things if the location is the same but the name is different. For example mv cs143 cs142 : renames the directory cs143 to cs142; mv 1.cc .. : moves the file "1.cc" to the parent or enclosing directory
rm <file> : delete a file. For example: rm 1.cc : deletes the file named 1.cc
rm -r <directory> : delete a directory and all of its contents For example: rm -r cs142 : deletes the cs142 directory and everything in it (you probably won’t want to do this very often).
emacs -nw <filename> : run the emacs program on "filename", which will create or open that file.
emacs is a separate program that is now running. All the commands described above are no longer valid until you quit emacs. See the emacs tutorial for what to do when the emacs program is running and how to quit.

Example session: the text in quotes is what’s typed after the prompt, and then enter is pressed. The text in parentheses is explaining what should happen. After you log in, you will be in your home directory.

"pwd" (see what the path to your home directory is)

"ls" (see what stuff is in your home directory)

"mkdir cs142" (create the cs142 directory in the current directory, which is your home folder)

"ls" (see that cs142 now shows up and is the color of directories)

"cd cs142" (change the active directory to the cs142 directory)

"pwd" (verify that you are in the cs142 directory and your path changed)

"ls" (see what's in the directory...should be empty)

"mkdir 1" (make a directory called 1 for your first assignment)

"ls" (verify that your directory was created)

"cd 1" (move into the 1 directory)

"pwd" (see how your location changed)

"emacs -nw 1.cc" (run emacs on the 1.cc file, which will create it if it doesn't exist)

After creating your program and exiting...

"ls" (see that your program now exists in the current directory)

"cd .." (move to the parent directory, which is cs142)

"pwd" (see that you are now in the cs142 directory)

"ls" (see that directory 1 exists in the current directory)

"dry-turnin 1" (do the dry turnin, see the web site for the turn in procedure)

Note: all the extra pwd and ls commands are for your information and to get you familiar with what the other commands are doing.

4.2 A little Emacs Tutorial

Adapted from a tutorial written by Eric Hill.

When you are using Emacs, you can just type your text in. There are a bunch of commands that do things like saving, etc. These commands always use a modifier key, like the Control key, plus another key. A special notation is used for these commands:

C-x: Press x while Control is held down.
M-x: Press x while Alt/Option/Meta is held down.

Here are the most useful basic commands:

C-x C-s: Saves your work
C-x C-c: Exits Emacs
C-v: Scrolls the window down one page
M-v: Scrolls the window up one page
C-x o: Switches to the other part of Emacs, called a window, normally the program output
C-x 1: Closes all other windows
C-x 0: Closes the current window
C-x 2: Open a new window, splitting the screen vertically, with the file shown in both
C-x 3: Open a new window, splitting the screen horizontally, with the file shown in both
C-_: Undo

Copying and pasting is a little more involved.

First, press C-<space> and move the cursor (with the arrow keys) to highly the region you want to copy or cut.
Next, press C-w to cut it. If you want to copy it, press M-w.
Next, move to where you want to paste it, and press C-y.

4.3 Using tools other than Emacs

If you don’t want to exclusively use Emacs through SSH, here are some other options.

Refer to the first screencast of topic 4 for a demo of doing these things.

4.3.1 General

You need to do three things to do the work for the class:

Write programs in a text editor.
Compile and test programs.
Submit programs using the Linux system.

The final step must always be done on the Linux system. However, you can transfer the files that you create on your home computer to the Linux system. You either use an SFTP file transfer program or use Copy & Paste.

4.3.2 Mac

Cyberduck is a program to transfer files to the Linux system.

Every Mac has a program called TextEdit which is a basic text editor, although make sure you are using "plain text" mode when writing programs. This editor doesn’t know about C++.

TextWrangler is a good free text editor that knows about C++. It will perform highlighting and other pretty things. One of the cool things is that it can directly open and save files on the Linux system from your computer.

If you use either of these, you can use the online codepad compiler, rather than constantly compiling and running your program on the Linux system.

However, if you install Xcode, then you can compile and run them locally by running g++ in the Terminal.

Installing Xcode also gives you an editor like TextWrangler.

Additionally, Xcode can behave like Emacs where pressing Command-R runs the program, if you first create a "project". You should select the "Command Line Program" and "C++" language option when creating a project. You will have to find and rename the files created by the project before turning them in.

Samuel Bradshaw made a tutorial on using Xcode in this class.

4.3.3 Linux

Your Linux computer should come with sftp, Emacs, and g++. So you can act just like you’re on the CS department computers and then transfer the files use SFTP.

4.3.4 Windows

Cyberduck is a program to transfer files to the Linux system.

Every Windows computer has a program called Notepad which is a basic text editor, although make sure you are using "plain text" mode when writing programs. This editor doesn’t know about C++.

Notepad++ is a good free text editor that knows about C++. It will perform highlighting and other pretty things.

If you use either of these, you can use the online codepad compiler, rather than constantly compiling and running your program on the Linux system.

However, if you install Visual C++ 2010 Express, then you can compile and run programs on your computer. To do this, you must create a "Project". When you do so, choose an "Empty Project" and then select "Add New Item" and a "C++ file" which will include your program. There is a "play" button on the upper bar of the UI which will compile and run your program.

If you want to run your programs from inside Visual C++, you need to do one more thing. You will probably notice that when you run your programs, they will pop up for a moment and then immediately quit, so you won’t be able to see the answers. You can make it wait for you to press Enter before quiting by adding this line and the end of your main function:

getc(stdin);

Put this right above the final return 0; in your main function. It is okay to leave this in your programs that you submit, however, when you try to turn them in, you will have to press Enter when submitting. It is probable that you’ll forget that, so I recommend commenting out the line before submitting the homework.

Installing Visual C++ also gives you an editor like Notepad++ that can be used independently of creating "projects".

5 How to Solve Your Problems

When you are programming, whether you are a beginner or an expert, you will face difficulties. A programmer’s competence comes from how they deal with these problems. I’d like to help you be a good programmer, so I will push you very hard to solve these problems in a constructive way.

The first step is to understand what kind of problem you are having. For the purposes of this discussion, let’s say there are only four kinds of problems.

5.1 Low-level

The first kind are low-level challenges. For example, the compiler gives an error message you don’t understand; you don’t know the name of the function that computes the square root; etc. In many cases, as your technical programming skills increase you will avoid these problems because you won’t make such errors or you will have intuitively memorized the various functions you care about. Even so, even expert programmers are consistently faced with such challenges.

Some programming courses try to force you to deal with these problems by having explicit memorization assignments, tests, etc. I think this is a waste of time and insulting to you. Instead, I’d like to teach you how most real programmers deal with these problems and allow you to do that. (This is why, for example, there are no closed-resource tests in this class, because real programmers don’t face such constraints.)

When faced with such a problem, a real programmer uses Google to find the answer. They may specialize the search to a programming FAQ site like StackOverflow or the reference for the language they are using. If you want to be a productive programmer, your number two goal should be to be familiar with these resources.

Therefore, I have instructed the TAs to never directly answer such technical questions for you. Instead, I’ve asked them to help you search for the answer in the appropriate places, so you can learn this valuable skill.

Whenever you find such an answer, please send a email about it to the mailing list. This will help others.

5.2 Domain-specific

You cannot program in a vacuum. Programs are always about some domain. For example, a simulation of the solar system lives in the domain of physics; an animation lives in the domain of geometry and optics; etc.

Many "programming" problems are actually misunderstanding of the domain. If you don’t know what the area of a circle is, then obviously you can’t write a program to compute it. Many times it is challenging to realize that you are lacking domain knowledge.

In practice, many real programmers are not domain experts in the area they program in. Instead, they interface with their customer (the domain expert) for these problems. Most advice about designing software that people want (i.e. that solves their problems) amounts to "Ask them."

I have tried very hard to not use challenging or unfamiliar domains in this course. Whenever there is doubt, I’ve tried to link to an informative Wikipedia discussion. If I have read you wrong, please let me know so we can change the assignment. Even though you can’t do programming without domains, I believe it is wrong for this to be a class about domains, rather than one that uses domains.

In essence, you should never need to ask a TA about a domain question, because they are all already answered. If you find that you need to, then I should revise the assignment to remove the obscure domain knowledge requirement.

5.3 Ignoring the Design Process

The hardest question in life is "What do I do next?" Programming is no different. You start with an empty screen and you have to write down something. What should it be?

This course emphasizes a particular design process that works very well for modular software. It can feel tedious to work through this process and you spend less time than you’d expect typing out code. Yet, experience has shown that programmers who follow such a process solve their problems faster and with less help. Learning to do this will mean that you are self-sufficient programmer.

We’ll talk about this more in class but roughly the process is this:

5.3.1 Information

Look at the problem and identify what information the human beings are providing and what information constitutes a solution. Write this down. For example, the pertinent information for an area finding program is probably the cirle’s radius in meters and its numeric area in meters-squared.

5.3.2 Data

Computers do not process information. They deal only with well-defined kinds of data. You need to decide how to represent the pertinent information as data. For example, you may choose to represent the radius and area as doubles. Write these down as comments or part of the program.

5.3.3 Data Examples

Write down in the programming language syntax examples of data. In some cases, like with numbers, this is as simple as 7.5 or 64.5. In other cases, like with objects, it is more complicated.

5.3.4 Function Prototype and Contract

Write down in the programming language syntax the header for the function you are writing as a transformation from the input data to the answer data. Write a contract comment above it. For example,

// areaOfDisk : double -> double

double areaOfDisk( double r )

5.3.5 Function Purpose

Rephrase the problem description in terms of the input parameters and write it as a comment above your prototype. For example,

// areaOfDisk : double -> double

// Computes the area of a disk where the radius is 'r'

double areaOfDisk( double r )

5.3.6 Examples

Write down examples of correct behavior of the program. This can be comments or real code. For example,

// areaOfDisk( 4.0 ) = 50.24

// areaOfDisk( 7.0 ) = 153.86

You will not be able to complete this step unless you understand the domain. It is nice to know that before you’ve started programming.

5.3.7 Template

Take inventory inside the body of the function of what you know about the data independent of the function’s purpose. For example, you know that you can use the values of the parameters:

// areaOfDisk : double -> double

// Computes the area of a disk where the radius is 'r'

double areaOfDisk( double r ) {

// ... r ...

}

If a parameter’s type is compound, then you know you can access it’s pieces:

bool inUnitCircle ( Posn* p ) {

// ... p->x ... p->y ...

}

Or if the program you are writing is a method, then you know there is a hidden compound data parameter called this:

bool inUnitCircle ( ) {

// ... this->x ... this->y ...

}

If a parameter’s type is a flat union, then you know you can distinguish the cases:

int theAnswerToEverything ( bool shouldBe42Huh ) {

if ( shouldBe42Huh ) {

// ... shouldBe42Huh ...

} else {

// ... shouldBe42Huh ...

}

In general these rules also apply to the pieces of compound data. In that case, the following rule is very common too.

If a piece’s type is a complicated kind of data, such as mixed data or a different compound data structure, then you know you can only call a function to solve the problem for it:

class Parent {

public:

ListOfKids* kids;

...

int howManyKids ( ) {

// this->kids

// this->kids->length()

}

};

Write these down and leave them in your program, commented out, so you can refer back to them as you program.

5.3.8 Coding

The next step is to start filling in the template. Do this by taking one of your examples, copying it near the template, writing down what you expect the value of each thing identified by the template to be, then writing a return statement that returns the correct answer. Repeat this process with more examples. If you find that you cannot write the same thing after return you need to decide between one of two possibilities: (1) you must find a general formula that turns out the same for both examples. For example, suppose you should return 1 in one case and 2 in another; it may turn out that both numbers are actually this->x + 1. The other situation (2) is that there is no generalization of the two formulas, so you must distinguish one case from the other using an if statement—a conditional. The condition that distinguishes the two cases is probably based on something from the templates, but sometimes you have to invent a new function that will detect the property. As you continue with examples after introducing an if, you should evaluate the if’s condition on the new example to see which category it fit is and therefore which examples it must generalize or distinguish against. Eventually, you will be satisfied that no further examples will change the behavior of the function.

In summary, the coding step is: Copy your template and fill in the ...s. Use your examples and domain knowledge to decide what to write.

During this step, you will face your greatest number of low-level problems.

5.3.9 Testing

After writing the program, you need to check that your examples are implemented correctly by the program. Do this by writing automatic tests with printf. If it turns out that an examples isn’t right, the fault could be in a few places: (1) the example is just wrong, you don’t understand the domain or made a mistake; (2) you incorrectly generalized an example’s formula; (3) you mis-identified what was different between two examples with incompatible formulas; or, (4) this function is correct, but it relys on another function that is implemented incorrectly—you can detect this by taking the assumptions about the values in the template for an example and turning them into tests on the underlying function.

5.3.10 Summary

The majority of your problems will come from failure to follow this process through. Therefore, the TAs have been instructed to refuse to answer questions about any step until you’ve completed all the steps below it. Here’s a questionnaire they may ask you:

Have you performed information analysis of the problem?

Have you mapped the information into data?

Have you written your data definition?

Have you coded a class definition for complex data?

Have you written examples of your data?

Have you written a contract for the method you are implementing?

Have you written a purpose statement?

Have you written a method prototype?

Have you written examples of the method’s output?

Have you written a function template?

Have you tested your function?

5.4 High-level

The most serious kinds of problems come when the entire prior discussion is not meaningful to you. You don’t understand what the next step in the design process is or even what I’m talking about. In these situations, I’ve probably done a bad job in class. In these situations, the TAs can try to help you, but probably you should come talk to me and we can figure out if others in the class can benefit from the outcome of our conversation.

6 Assignments and Turn In Policy

Each topic has associated exercises. It is your responsibility to do these exercises and return them by the next topic’s first day. This deadline is noted on each topic’s page.

6.1 Turn-in Content

When you do the exercises for day n, you must create a directory called n that contains one file per exercise. The file for exercise m must be named "m.cc". This file must start with a comment that contains your name, the assignment number, the exercise number, and the text of the exercise copied from the Web site. For example,

/* Jay McCarthy: Assignment 0: Exercise 1

Create a "HelLOL World" program.

After that, you should solve the exercise. Most of the time this solution consists of a program. Sometimes, it will just be a question that you would answer with plain text. In that case, write the answer in a comment after the initial comment.

Assuming that the exercise requires a program to be written, there are a few more things you must do.

You must follow the design process demonstrated in class. All data must have a corresponding data definition that is communicated to C++. Every function you write must have a contract and purpose statement. Each function must have a template. The template must be accurate—this means that it should not look at too much or too little. (For example, a Shape method that contains a Posn must not look at the Posn’s x and y parts.) Each return statement must be justified by an example. You must clearly explain (in a comment) how a return statement generalizes earlier examples. You must clearly explain (in a comment) how an if statement distinguishes two examples. The main function must contain automated tests corresponding to the examples you used to drive the function development. These should look like:

// A brief explanation of what this example demonstrates

printf("The answer is %d but should be %d\n",

// A call to the function

f(1,2,3),

// A handworked solution

1+2*3 );

At least one test case must have a complete substitution or store-tracking analysis performed on it. You are not required to do this as runnable code, in case it is too inconvenient to get that working. In those cases, just use comments. If you choose an example that is too trivial (for example, the empty list on a list function), I will not consider this requirement fulfilled.

These procedures must be followed for every function in the program (except main)—not just the function(s) required by the exercise! For functions that aren’t required, your purpose statements should teach me how to evaluate the correctness of your tests.

In general, the purpose of exercises is not just skin deep. When an assignment asks for "The area of a cylinder", I have zero interest in whether you can find the area of a cylinder. Instead, I am interested in if you can grasp and put to use the design process and the topic of the exercise—designing functions, using compound data, etc. This as a few important implications. First, if you make a trivial mistake, like find the area of a tube rather than a cylinder, I am unlikely to count it against you. Second, if you find the area correctly, but do not follow the design process or do not make use of the topic, you will get no credit, because you followed the letter of the assignment, but not the spirit. If it is not obvious to you how the topic can be applied or if you tried to apply it and failed, you should ask for help and guidance.

Following this requirement will be hardest if you’ve had programming experience in the past. You’ll instantly see "simpler" or "better" ways to solve the problem. I don’t necessarily disagree with you on whether they are "simpler" or "better", but you must accept that if the point is not to get the area of a cylinder, but instead to practice using functions, it doesn’t matter if there’s a different way: this is the way we are practicing right now. In summary, do not use features of C++ that we have not discussed in class yet or you will not get credit.

This issue has another implication: often times you’ll be learning programming techniques that are not commonly used in industry in general or in C++ programming in particular. This is because our techniques emphasis ensuring correctness of the program and understanding on the part of the programmer. In contrast, most industrial software is okay if it is correct, even if no one understands it, or even worse, if it just appears to be correct so far as it as been tried so far. This is why there are so many erroneous programs in the world. The "real world" values expediency. In contrast, college is the one time in your life when you can slow down and focus on principles that will lay a good foundation for the future. In that sense, you should never think of this a "C++ programming class", you should think of it as "programming class, that uses C++". We will teach you things that no practicing C++ would do normally and ignore things that they do all the time. The upside is that you’ll learn skills that are more transferable than the provincial C++ skills would be.

6.1.1 Summary

For each assignment, you should have one file per exercise. For each exercise, you should have a header with your name, the assignment number, the exercise number, and the exercise text. Every exercise is made of data defintions and functions. For each data definition, you should write it in a comment and communicate it to C++. For each function, you should have a contract, purpose statement, template, test-driven development with justifications through examples, tests, and substitution (or store-tracking) analysis of one test case. These things constitute "showing your work".

I’ve put an example online: .

6.2 Turn-in Deadline

As mentioned above, exercises are due before the first day of the next topic’s class, 15 minutes before class. Optional exercises are due before the first day of the topic after that. The final assignments are treated as finals and due before the final time scheduled by the University. Its optional exercises are due when grades are due (modulo enough time for me to grade them.) All of these deadlines are clearly marked on the assignment pages.

These are real deadlines: there are no exceptions. However, make sure you read about Your Final Grade, before you get too upset. (If you have a serious problem that prevents you from turning in work on time, you may go through the University to get an Incomplete grade and we can sign a contract to organize the late-work submission process. The University has a page that describes this process.)

6.3 Turn-in Method

In the directory where the assignment directory is (such as ~/142), you should type

turnin n

to turn-in assignment n. This will compile and run all the exercises for my records. This may take a little while. Make sure you give yourself enough time before the deadline to turn it in.

When you turn in the optional exercises for topic n, you must have a directory named nopt and instead type

turnin nopt

You may only submit a single time.

In case you want to make sure that the compilation will be successful, without potentially using up your single chance, you can type

dry-turnin n

and

dry-turnin nopt

to see what will happen.

You can check what assignments have been turned in and graded by typing:

assignments

6.4 Grading

Each exercise will be graded as either 0 or 1. This is no partial credit on a per-exercise basis. Exercises that do not have the correct format or components—described above—will receive no credit. Once an exercise has passed that bar, I will check your test cases to (a) ensure that they pass, (b) ensure that they should pass, and (c) ensure that they capture all required functionality of the exercise. This means you can fail to receive full credit if your function is correct but do not have comprehensive tests. (Although if you follow the design process, you are unlikely to have it correct anyways without enough tests. And if you don’t follow the process, then you won’t get credit because of that.)

Your assignment grade is expressed as a fraction of the exercises you did correctly over the total number. This is a representation of a real number between 0 and 1, that is used for computing Your Final Grade.

After I grade your assignment, you should get an email with the grade. If you want to see this again, you can type

check-grade n

For an optional assignment, type

check-grade nopt

If you want to see what notes I wrote about your exercises, you can type:

get-graded n

For an optional assignment, type

get-graded nopt

which will print the name of a new directory containing annotated versions of your exercise files.

7 Exams

There are no exams in this course, although I consider the final assignment a take-home exam, which is why it is due when the University scheduled our final.

8 Your Final Grade

Your final numeric grade is calculated by (1) summing your assignment grades, (2) incorporating extra credit (see below), and then (3) dividing by one-less-than the total number of assignments (20).

This means that you can safely skip one assignment and still get 100% in the course. If you do, each assignment is worth about 5 percent of your grade. If you don’t, you can get more than 100%, because each assignment is included in the numerator, but not the denominator.

Extra credit is based on the philosophy that you should be able to "pay debts" but that you may not "take loans". Specifically, optional exercises have equal weight to other exercises for the assignments prior to the optional assignment. For example, if you get 1/2 on day 2, if you do one optional exercise from day 2 or after, it will count as if you got 1 on day 2. However, if you get 100% on day 1 and 2, doing optional work on day 1 or 2 will count for nothing.

I have ensured that there are always half as many optional as required exercises. This means that you could ignore every required assignment, but turn in every optional exercise, and get a 50% in the course. (Actually a little more, because there is 1 of each for the first day.) Alternatively, this means you could get 50% wrong every day, but get 100% of the optional, and get a 100% in the course. If you want, you can think of optional exercises as a "week late, half credit" late policy.

I will convert your numeric grade to a letter. As will start at 0.9, Bs will start at 0.8, Cs will start at 0.7, and Ds will start at 0.6. I will remove the "minus" at x + 0.03 and will add a "plus" at x + 0.06.

If you ever want to know your current final grade, you can type

check-grade

It will tell you minimal possible grade (assuming you do not turn in any more work) and your maximum possible grade (assuming you turn in everything remaining perfectly.)

9 Glossary

Here is a glossary of technical terms used on this site. If I have missed a word or missed cross-referencing a word usage, let me know and I’ll update the site.

9.1 Basics

C++ is the language we’re using to program in this class. My favourite web site about is this one, but sometimes it can be really deep, but it is still a useful resource.

A program is a computational solution to a human problem. A description of the human problem is called the problem statement. It is defined by its "automatic-ness". It automatically finds the solution and is typically easy to modify to find the solution to related problems. The first task in programming is understanding the human information that describes the problem and the solution. The solution is normally called a computation or calculation.

A program contains things that are not C++. These are called comments. They are written like:

// This comment goes until the end of the line.

So this line has to be C++ (but it actually isn't)

/* This comment lasts until there is an asterisk and another slash

So this is still a comment

And so is this

But after this: */

This ain't a comment

Information is what humans being care about and understand. There are innumerable forms of information. Computers, however, only deal with data. There are relatively few different kinds of data that computers understand; basically just numbers and words.

Numbers on computers are divided into integers, which don’t have decimal points and are written int or long, and floating point, which have decimal points and are written float and double. We prefer int and double for these different numbers. There is a weird floating point number called NaN—Not a Number—that C++ will use when it can’t figure something out. For example, finding the square root of -1. Computations only dealing with numbers are arithmetic.

Words on computers are called strings. Each string is written like "Something in between quotation marks". The category of strings is const char*. Funny name, huh?

The main task of a programmer is to look at the human information, decide what is important, and decide how to represent it as data in the program. This process is called data definition. Most of the time a built-in kind of data isn’t right, so a new kind of data needs to be created. That’s called abstraction or encapsulation.

9.2 Data Definition

A data definition is a comment that describes the data in your program. Often after writing a data definition, you need to communicate it to the computer through some code—turning a data definition into a data type. Typically these are written next to one another. The following glossary entries are specific kinds of data definitions.

An atomic data definition gives a human name to a kind of computer data. It looks like:

// A happiness factor is a double between 0 and 1

You don’t need to communicate an atomic definition to the language. When you use it in a program, you should use the name of the computer data; in this example, that’s double. The template for this kind of data is just the name of the piece of the data.

An atomic union data definition gives a human name to a subset of a kind of computer data. It looks like:

// A life status is a string; either "Living", "Dead", or "Edward"

You don’t need to communicate an atomic union definition to the language. When you use it in a program, you should use the name of the computer data; in this example, that’s const char*, because that’s what strings are called in C++. The template for this kind of data is a conditional that distinguishes the different cases.

A bool is a built-in atomic union that C++ knows about. It would look like:

// A bool is a int; either 0 (called false) or 1 (called true)

bool is unique in that C++ knows about it, so you can write bool, false, or true in your program. C++ has a bunch of boolean functions built-in as well, with a cute arithmetic-like syntax, like &&, ||, and !. These are called boolean operators. There are some built-in C++ functions that take numbers and produce booleans, like ==, !=, <, >=, etc. These are called comparison operators.

A compound data definition gives a human name to a combination of other data. It looks like:

// A Posn is a

// new Posn ( x, y )

// where

// x is a double

// y is a double

You need to communicate an compound definition to the language. In the beginning of the class we write:

typedef struct Posn;

typedef struct Posn {

double x;

double y;

};

Posn* new_Posn (double x0, double y0) {

Posn* p = new Posn();

p->x = x0;

p->y = y0;

return p;

}

(We also write new_Posn( x , y )—the new function—rather than new Posn( x, y )—the new statement—in the beginning of the course.)

But for the majority of the course, we write:

class Posn {

public:

double x;

double y;

Posn (double x0, double y0) {

x = x0;

y = y0;

}

};

This is called defining a class in C++.

When you use it in a program, you should use the name of the compound data with a * after it; in this example, that’s Posn*. The template for this kind of data is the name of the compound data instance, ->, and the name of all the pieces. Each of these is called a selector. For example:

int distance (Posn* p) {

// p->x .... p->y

}

A nested structure is just compound data where one of the pieces is also compound data. It is treated exactly like normal compound data, except you can’t look at the pieces of the compound piece. Instead, you should always call a function (or method) that returns what you want from the compound piece.

Instances of compound data are called objects. For example,

new Posn (3.0, 4.0)

is an object.

A mixed data definition gives a name to a few different kinds of compound data. The different kinds are called variants. It looks like:

// A Shape is either

// - a Circle

// - a Square

Each variant will have its own data definition.

You have to communicate it to the language in two ways. First, you need to tell C++ what a Shape is and what it can do:

class Shape {

public:

virtual double area () = 0;

};

In C++, this is called a pure virtual class.

Then, for each of the variants, you must annotate them as belonging to the mixed data:

class Circle : public Shape {

...

};

class Square : public Shape {

...

};

When you annotate a variant like this, it is called inheritance in C++. The analogy is that Circles are like the children of Shapes and "inherit" their "shapyness".

When you use it in a program, you should use the name of the mixed data with a * after it; in this example, that’s Shape*. Since you never write functions directly on mixed data (instead you write it on the variants individually), there is no template for mixed data.

Functions that work on mixed data without caring about what variant they receive, like

double megaarea ( Shape* s ) {

return s->area() * 99;

}

are called polymorphic or instances of polymorphism. polymorphism is a Greek-derived word meaning "many shaped", because functions like megaarea operate on many different shapes with a single definition, unlike all other functions we typically write that only work on one kind of shape. In C++ (and other languages) there are other ways of making polymorphic functions than mixed data, but they are typically only used by advanced programmers. (Google "templates" or "generics" for these options.)

A self-referential data structure is a nested structure where the compound sub-piece is the same kind of thing as the outer data structure. Sometimes this structure is called recursive, because functions that operate on them must use recursion, which means that the function contains a call to a function with the same name as itself, in the same way that a self-referential data structure contains an instance of the same kind as itself.

The simplest self-referential data structure is a list. A list represents a sequence of items of indeterminate length. It’s data definition always looks like:

// A ListOfX is either a

// - OneMoreX

// - NoMoreXs

// A OneMoreX is a

// new OneMoreX ( first, rest )

// where

// first is an X

// rest is a ListOfX

// A NoMoreXs is a

// new NoMoreXs ()

// where

A list is a unary data-structure, meaning that it only goes in one direction: from the left to the right. In contrast, ancestor family tree is an example of a binary data-structure, meaning it goes in two directions: from top to bottom choosing left or right along the way. This idea can be generalized into any fixed-width tree, where the branching factor is fixed: a list is fixed at 1, a binary tree is fixed at 2, etc. (A very common data structure used in graphical programming is fixed-width tree of width 4 (for 2D) and 8 (for 3D).) Despite this generality, trees are just simple self-referential data structures.

In contrast, a descendant family tree, where the number of "next steps" is different at each point in the tree (just like each generation in a family may have different numbers of children), requires more than simple self-referential structure. This is because each level of the tree contains an entire list where each element of the list is itself another tree. This structure, where two data definitions refer to each other, is called mutually recursive. The technical name for descendant family tree is a variable width tree, in contrast to a fixed-width tree.

9.3 Functions

After defining your data, you typically define a function to solve the problem. A function that doesn’t solve the main problem, but solves a related problem, or a small piece of the big problem is called an auxiliary function or helper. The relationship between the big problem and sub-problems is called a dependency as is reflected in the shape of the program: if the big problem depends on a sub-problem, then the big problem’s function will call the sub-problem’s function.

A function definition has a few pieces.

First, the contract gives the name of the function and specifies what kind of data it receives and what it produces. This is a comment. Here are some examples:

// areaOfDisk : double double -> double

// area : Disk -> double

The things to the left of the -> are the things that the function receives. Sometimes we use the verb consumes to describe these things. Sometimes we call them inputs, arguments, or parameters.

The thing to the right of the -> is the thing that the function produces. Sometimes we call it the output or the return.

Second, the purpose statement (or just purpose) describes the problem the function solves. Here are some examples:

// finds the area of a disk specified by the arguments

// finds the area of a disk specified by this object

Third, the function header communicates the contract to C++. In this step, the order of things in the contract changes. The output comes first, before the name. Each input is given a name. Each input’s kind is replaced with the C++ name of it. (For example, Posn* rather than Posn.) Here are some examples:

double areaOfDisk ( double inner, double outer ) {

...

}

A method is a special function inside of a class where the first input in the contract is automatically put in by C++ without you having to write anything. Because C++ writes it for you, it chooses the name and kind. It always chooses the name this and gives it the kind class* where class is the class it appears inside. Here’s an example:

class Disk {

...

double area ( ) {

// this is a Disk*

...

}

};

Fourth, the examples capture the programmer’s domain knowledge in comments:

// areaOfDisk ( 10, 5 ) = 100π - 25π

The examples should be written a function calls. A function call is a use of the function. (Also called a function application). It looks like:

function(input_one, input_two)

areaOfDisx(10, 5)

Fifth, the template layouts the available data to the function body.

Sixth, the function body contains the actual problem solution.

Seventh, the tests in the main function automatically check the examples.

Refer to Ignoring the Design Process for more information about these last three steps.

9.4 Analysis

In mathematics, when you write something like

x = 12

You are defining an eternal truth that "x is 12". Later in your math, when you see x, you can (do, and should) mentally replace x with 12. When I ask you, what is x + 1, you instantly know it is 13, because x is 12 and 12 plus 1 is 13.

In C++, you do the same thing. You can name a value, like 12, x. You must also say what kind of data it is. For example:

int x = 12;

double close_enough_to_pi = 3;

This is called defining a constant.

In the C++ program, when you write x+1, C++ substitutes x for 12 and finds 13.

A similar thing happens in C++ and math when you define and apply functions. When you write in math,

f(x) = x + 1

and the teacher asks, "What is f(12)?" You replace f(12) with the definition of f (which is x + 1) and inside of that you replace x with 12... getting 12 + 1, then you find the answer to that.

C++ does the same thing when you define functions:

int f (int x) {

return x + 1;

}

and use them f(12). It replaces the function application with its body and its inputs with the actual input expressions.

An important tool in understanding your programs is to do this manually. This is called substitution.

Here’s an example using f:

f(f(12))

f(12+1)

(12+1)+1

13+1

It is important to be able to do this so that you can internalize what the computer is doing when your program runs.

9.5 Accumulators

Normally when you write a function that uses auxiliary functions, the "big" function depends on the "small" function’s answer and the "small" function does not depend in any way on the "big" function, except to specify the problem. Occasionally you will write functions where this dependence relationship is bi-directional: the "big" function’s answer depends on the answer from the "small" function, but the "small" function depends on information from the "big" function that doesn’t just specify the problem. This is called accumulator style because the "big" function accumulates knowledge for the benefit of the "small" function.

Accumulator style is a pre-cursor to mutation.

9.6 Mutation

In mathematics,

x = 12

x = 13

doesn’t make any sense. Is x 12 or 13? Since = gives definitions in math, it doesn’t make sense to define things twice in different ways.

Unfortunately, in C++ this does make sense. Whereas in math, things are defined one way for all time, in C++ they can have different definitions at different points in time. Changing from one definition to another is called mutation. For example:

int x = 12;

printf("x is %d\n", x);

x = 13;

printf("x is %d\n", x);

prints 12 then 13.

This can be particularly confusing when the earlier value is used to compute the later value:

x = x + 1;

This means that substitution is actually incorrect for C++ programs, because substitution would tell use the program should print 12 twice. Substitution is very convenient and nice, because it corresponds to math, but it can only be applied when mutation is not present or is not visible. Good programming avoids mutation as much as possible so that more code can be analyzed with substitution.

A natural question is how mutation can be "invisible". The core idea is that a function uses invisible, or internal mutation, when applications of the function can be reasoned about using substitution, but the body cannot. For example, given

int g ( int x ) {

int y = 2 * x;

y = y + 1;

return y;

}

g(12) is always 25 at all times, and so it can be substituted when you see g(12). However, if we were to use substitution to analyze inside g, we would fail.

Mutation inside a function that is visible outside is called external mutation. It can never be reasoned about using substitution.

The ability to use mutation in C++ is why the names we give to values are typically called variables—because they vary. When we mutate the pieces of compound data, it is a special case of mutation called object variable mutation. Methods that do this are almost always exhibit external mutation. Unfortunately, C++ is designed in such a way that other programs can impose mutation on your program. You can protect against this a little with private designation—replacing the public: in your class with private:, but this is an advanced topic.

If substitution doesn’t work for mutation-based programs, how can you understand what they do?

The basic idea is to combine substitution with explicit tracking of the "current" definition of every variable. This is called store tracking, because the place the values of the variables are stored is called the store. Here is an example:

// Store:

int x = 0;

// Store: x = 0

x = 12

// Store: x = 12

int y = x * 2;

// y = 12 * 2

// y = 24

// Store: x = 12, y = 24

x = 9

// Store: x = 9, y = 24

x = x + y

// x = 9 + 24

// x = 33

// Store: x = 33, y = 24

y = x / 3

// y = 33 / 3

// y = 11

// Store: x = 33, y = 11

Each time the store changes, we note it in a comment. Each time we reach an expression, we perform substitution on it using values from the store.

The store is an accumulator (in the sense of accumulator style) that C++ automatically provides and threads throughout your program. When you do store tracking, all you are doing is substitution after making the accumulator explicit, rather than invisible.

There is a special kind of data in C++ called an array that can only be interacted with using mutation.

10 Miscellany

All other policies of BYU apply; in particular, the Honor Code and its relationship to cheating, etc.

I am not ashamed of past student feedback, so I publish it on my homepage. You may wish to read it.

1	Introduction
2	Meetings
3	Help
4	Course Software
5	How to Solve Your Problems
6	Assignments and Turn In Policy
7	Exams
8	Your Final Grade
9	Glossary
10	Miscellany