Introduction to CS123

Just some quick introduction to make sure we’re all on the same page:

• What class is this? CS 123, “Introduction to Programming in C++”

• What is “programming”? There are lots of definitions, but the one I like is

  Computer programming is the art of solving problems using computers.

• Note that I said “art”; programming is inherently creative, there’s an “aesthetic” quality to it. A lot of times you’ll hear programmers talk about “elegant” programs, programs that don’t just accomplish some task, but do it in a particularly nice way.

• Computer programming is about problem solving. You have some task or process, and you want the computer to carry it out. You have various components already at your disposal, and you need to put them together to form a solution.

• Finally, and least importantly, computer programming involves computers.

  “Computer science is as much about computers as astronomy is about telescopes.” Edsger Dijkstra

Problem Solving

A problem is anything that you don’t already know how to solve. An example of something that is not a problem:

• What’s the quadratic formula?

  $$x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$

• If I give you

  $$2x^2 - 3x + 4 = 0$$

  and ask you to solve using the quadratic formula, that is not a problem. Why not? Because you already know exactly what to do in order to get the solution! As long as you apply the formula correctly, you will get the correct answer every time. Getting to the solution is just a matter of being careful, there’s never any question as to what steps need to be taken.

A real problem is one in which you don’t know what steps to take to get from the data, the “givens”, to the solution. You may have tools (like the quadratic formula) available to you, but you don’t immediately know which tools to use, and in which order.

In computer programming, the computer is responsible for being careful, and it is always perfectly so. It never forgets to square b or accidentally drops a negative. Thus, any “problem” that comes down to just being careful usually becomes easy on a computer. The really interesting problems are those where we have to figure out the steps to take.

Problem solving example

Here’s a problem that I came up with:

Suppose we have a sequence 1, 2, 3, and another sequence a, b, c. We want to know how many different ways there are of “interleaving” these sequences, putting the elements into a single sequence while still keeping them in the same relative order. For example, one interleaving is a, 1, 2, b, 3, c. How many ways can we do this?

What are some ideas about how we can solve this?

• List out all the possibilities. How do we know when we’ve got them all? (There are a lot!)

• Instead of using 123 abc, use “x” for the first list and “y” for the second. So the example above would be yxxyxy. Note that because we want to keep the order from the original lists, there’s no contradiction.

• We could try doing it with smaller sequences: 1 and a, then 12 and ab.

  • With 1,a there are only 2 possibilities: 1a and a1.
  • With 1,2 and a,b there are 6 possibilities: 12ab, a12b, ab12, 1a2b, a1b2, 1ab2.

  Is there some kind of pattern?

• Can we break the problem down into smaller problems? Suppose we use the xy scheme above. For the first element, we have to choose either an x or a y. Suppose we choose x. Then, what do we have for the rest of the list? We have two x’s and three y’s to interleave. In other words, for the first symbol, we have two possibilities:

  • Choose x, and then interleave two x’s and three y’s.
  • Choose y, and then interleave three x’s and two y’s.

  The total number of possibilities is just the sum of the number of possibilities of both choices.

  Notice that if we keep breaking the problem down, we’ll eventually get to a point where there is only one choice: one x, or one y.

  This method of solving problems by breaking them down into smaller versions of the same kind of problems is hard for us to use if we’re working by hand, but it’s great for computers, which are good at keeping track of many different tasks all in-progress.

The C++ Programming Language

The main tool we’re going to be using is the programming language C++. C++ is an artificial language that we use to sort of bridge the gap between us humans and the computer. It tends to care about things that seem trivial.

Personal Introductions

My name is Andy Clifton. Mr. Clifton, Prof. Clifton, and Andy are all perfectly acceptable ways of getting my attention.

My email is aclifton@fullcoll.edu. It’s also on the handout.

My office is 611-02, right at the back.

Course details

4 units, meets twice a week.

Our learning objective is “You will be able to design and implement Abstract Data Types using C++ classes.”

The textbook is “Problem Solving with C++”, Walter J. Savitch. You can use an older edition if you want; the chapters are the same. I tend to skip around and do things a bit differently from the book, but its there for you as another source of information. I’ll be highlighting other sources as the semester goes on.

Grading

The grading system I use is a bit different from your other classes. You don’t have a single percentage towards which all your work accumulates. Instead, there are several different measurements:

• Assignments: there are 10-ish of these over the semester.

• Midterm topics: each midterm exam is broken into modules or topics, 12 in total, over the whole semester. The first six are “core” topics and the last six are “advanced”.

• Project: There’s a semester-long project, with four “stages”, roughly aligned to the four midterms.

• Final exam: comprehensive, assigned its own grade (A, B, or C)

To earn a higher grade, you have to do more in each area:

• For the minimum passing grade of a C, you need 70% of the assignments, all six of the “core” midterm topics, the first two stages (stages 1 and 2) of the project and around a C on the final.

• To earn a B, you add a bit more: 80% of the assignments, all the core midterm topics and at least three of the advanced topics, stages 1, 2, and 3 on the project, and around a B on the final.

• For an A: 90% of the assignments, and basically all core and advanced midterm topics, all four project stages, and around an A on the final.

The higher the grade you want, the more you have to do. On the other hand, if you’re OK with a B or C, you can do less work!

Additional requirements to get a C or better

As this is now effectively an online course, there are a few additional tasks you must complete in order to get a C or better:

• Login to the server (this is “assignment 0”)

• Sign the syllabus assignment which I’ll post to Canvas later this week.

• Post to Piazza an average of once per week. It’s OK if you miss a week, but you’ll have to post twice the following week.

Assignments

Assignments are issued at the beginning of the week and are generally due the Friday of the following week. Assignments have two parts:

• Worked examples are short example programs for you to type in and get working. There’s no real problem here; all of the example programs are complete and correct, and should work so long as you type them in as written.

• One or two problems which are incomplete (or empty) programs which you have to write yourself.

Midterms

Midterms are cumulative, but in a non-horrible way: each midterm includes the topics from all the previous ones, and introduces three additional topics (whatever material we’ve covered since the last midterm), but you only need to work those topics that you haven’t already passed. So if you keep up, you’ll have to do three topics per midterm. If you don’t pass a topic, it doesn’t count against you: you can just try again on the next midterm. Only if you fail to pass a topic on all four midterms does it finally count against you.

Midterm topics generally have 5(ish) problems each, with each problem graded pass/fail. “Passing” a topic means getting at least three of the 5 problems.

Projects

There are four projects, each with a different emphasis. Each project has three “levels” which build on each other. The fundamental level generally involves building the most basic version of a project. The intermediate level involves incorporating some more interesting concepts into the project, while the advanced level adds that final polish.

If you’re doing the advanced project, the fundamental and intermediate levels are like the “drafts” of your project.

Projects are graded on a professional quality basis; we’ll talk more about what this means.

Stage 1 of the project is a group project, while stages 2 – 4 are individual. If you know who you want to work with, let me know, otherwise I will assign groups randomly.

Final exam

The final has a number of problems, usually around 15, each worth 1 point; the final is graded out of 10, so ≥9 points for an A, ≥8 for a B, etc. The final grade is averaged with your grade for the rest of the class and then rounded up.

However, the fact that the final is averaged/rounded gives you an opportunity to make up for anything you might have missed. For example, if you did pass five of the core topics (not quite enough for a C, so your grade would be a D) but then got a C on the final, a C averaged with a D rounded up is still a C. Thus, getting the grade you want on the final allows you to “make up” anything you might still be missing at the end of the semester. On the other hand, if you do much worse on the final, it can pull your grade down; you must be able to repeat your performance on the final to lock in your grade.

Other grades

A D will be given to students who complete some material, but not enough to earn a C. An F will be given to students who fail to complete even the most minimal amount of material.

Tokens

Each student begins the class with four tokens. At any time you can trade in a token for a two-week extension/resubmission on a practice set, or project, or make-up an exam that you missed, for whatever reason.

Cheating

If you cheat on an assignment (practice set, project, or midterm topic) you’ll fail it and you will not be allowed to resubmit it. That item will become impossible for you.

If you cheat on the final exam, then the highest grade you can possible achieve is reduced to a D.

Having said that, computer science is a fundamentally collaborative field: wanting to work together is natural. The only problem is that your grade for the class must be yours alone.

I’d ask you to adhere to the principle of the erased whiteboard. The idea is to imagine a group of students working together around a whiteboard. They write things on the board, explaining material to each other, and so forth. When they are finished, they erase the whiteboard, without copying it down verbatim or taking a photo of it. All they take away is the insight they’ve gained from their fellow students’ explanations.

Course website, Canvas, and the CSCI Server

Online, there are four main things we’ll be using

• The course website has all the details: projects, handouts, lecture notes, etc.

• I’ll be posting your grades to Canvas.

• I’ve enabled the discussion board on Canvas, and I’d encourage you to post and answer questions about the material.

The CSci server

You’ll be doing all your programming work on the CSci server. This has the advantage that I can take a look at your work if you’re needing help (without having to email it around), and to “submit” your work, all you have to do is let me know. In addition, you don’t have to worry about losing your work because your laptop fell in the lake or whatever. On the other hand, the server is a bit unfamiliar, so we’ll spend some kind getting familiar with it.

To connect to the server you’ll need a piece of software called an SSH client, and the details about the server’s connection.

• On Windows, the best (free) SSH client is PuTTY.

• On a Mac, there’s a built-in SSH client, in the Terminal app.

The server connection requires you to know

• The hostname fccsci.fullcoll.edu

• The port 5150

• Your username, generally your first initial followed by your last name.

• Your password, at first this will be your student ID, without the @ at the beginning, but the system will ask you to pick a new password when you first login.

In PuTTY, you enter the hostname and port on the main screen and then click connect, and it will ask you for your username and password. (The first time you connect it will ask you if you are sure that the server is the one you want to connect to. You can also save the connection on your own machine so you don’t have to type it every time.)

If you’re using the Terminal, then you actually give the hostname, port, and your username, as part of a command. Type

ssh username@fccsci.fullcoll.edu -p 5150

(replace username with your actual username) and press Enter. It will ask for your password. (Just like in PuTTY, the first time you connect it will ask you to verify that you’re connecting to the right server.)

Note that in both PuTTY and the Terminal, when you type your password, nothing will appear on the screen. This is normal; it’s still recording whatever you type, so just type your password and press enter when you are done.

If you want to try it out but your username/password isn’t working yet, you can try using the “sample user”:

• Username: sampleuser

• Password: TOP-SECRET!

I’m going to login to my account on the server and show you the general flow of things.

Editing files

There are several editors available on the server (Nano, Emacs, VIM) but I’m going to recommend you use micro, as its probably the easiest. Most things in micro are as you expect: Press Ctrl-S to save, Ctrl-Q to quit, you can select with the mouse and use Ctrl-C to copy, Ctrl-V to paste. (Outside of micro, you have to use Shift-Ctrl-C to copy, and Shift-Ctrl-V to paste.)

The files read by C++ must be in plain text format. If you don’t know what that means, think of editing a file in Word or Google Docs: you can add formatting like bold, colors, centering, etc. These things are not part of the text, the letters, numbers, and punctuation that you type, but the have to be stored in the file somehow, so the program uses special codes. If you were to give such a file to C++ it would get completely confused by the formatting codes and give up (note that even a plain Word document includes some minimal formatting: the default font, margins, etc.). So we have to use an editor which is guaranteed to put nothing in our files except the things we type.

The development process

The process of writing a program is something of a cycle. You don’t just write it and it works, rather, you write some small part of it, try that out, then fix or add to it, and repeat, until you get the final product working. This is sometimes referred to as the

Edit-Compile-Run Cycle

1. First you edit your file, writing some small but complete program. (C++ can’t handle programs that are not complete; it has to do something, even if it’s not exactly what you want.)

2. You then compile your program. This takes the text of your program, and turns it into codes that the computer can understand.

3. Finally, you run the compiled program (the code) to see what happens.

I’ll illustrate each of these steps in turn.

Edit

To edit a file in micro, we type the command

micro filename.cpp

and press Enter at the end, replacing filename with the name of the file to edit. (The .cpp is part of the name of the file, but for now, all our program files will end with .cpp; this identifies them as being C++ files.) (If you start micro without a filename, it will give you a blank, unnamed file, and you will have to name it when you save.)

The part of the server where you type commands and press Enter is called the shell. Once we start micro, we are now “in” micro, and thus the things you can do are different. (It’s important to keep in mind which commands are used in micro when editing files, and which are used in the shell.) Just remember that all shell commands end by pressing Enter. Note that the shell is completely different from C++. You cannot use shell commands in your programs, and you cannot use C++ commands in the shell.

In micro, most of the normal things you type are entered into the file. There are special commands, using the Ctrl and Alt keys, for doing things like saving your work, opening another file, etc. The most common of these are summarized in the table below

Indent and unindent will become useful as you start to edit programs, where we use indentation to show the structure of the program. Ctrl-B (run a shell command) will allow you to compile and run your program, without leaving micro.

Micro can have more than one file open at a time; if you have more than one, it will list them all across the top of the screen, and you can click on the name of a file to switch to it. This will be useful when you are working on the practice problems: you can keep the practice set file open in one tab, and your program open in another, and copy/paste between them. Similarly, later on in the semester you’ll be working on larger programs where it will be useful to organize them into more than one .cpp file; you can open them all in micro and switch between them.

Here’s a simple example program to start:

#include <iostream>
using namespace std;

int main() {
    cout << "Hello, world!" << endl;

    return 0;
}

If you want, you can save this into a file hello.cpp for the next sections. (Note: if you don’t type in the program exactly, you may see some >> marks in the left margin when you save. More on those in the next section.)

Compiling

Compiling is the process of translated C++ program text into the numeric machine code that the computer actually understands. There are two general ways of “running” a program that is not already written in these machine code:

• Interpretation

• Compilation

Interpretation is akin to a language interpreter translating a speech: it translates the program “on the fly” into machine code, in little pieces. This has advantages (you get immediate results) and disadvantages (it’s slow, and it never gets faster).

Compilation is like a person working to translate a book: they have the entire work available to them, and can work at any pace. The advantage is that you get a better (higher quality) translation, because you have all the time in which to do it. The disadvantage is that the first translation is slower, because it has to process the entire program, but subsequent runs are faster.

To compile your programs, I’ve written a simple tool called compile for you. To use it on our hello program, we would execute the shell command (either quitting micro and entering it into the shell, or using Ctrl-B to run it from within micro)

compile hello.cpp

This will process the contents of the C++ file hello.cpp and produce the compiled program hello (the .cpp part of the name is removed). We started with one file, but now we have two: our original file, and the compiled program.

If everything is OK with your program, then it will (confusingly) appear that nothing happens. If nothing happens, then that’s good! It means your program was free of errors and was successfully compiled. Otherwise, compile will print some messages telling you what is wrong with your program.

The messages printed by compile have two forms: errors and warnings. Errors are things that are definitely wrong with your program; your program will not compile until there are no errors. Warnings are things that are probably wrong with your program, but not wrong enough for compile to stop what it’s doing. If you get warnings, but no errors, then your program was compiled, but you should take a look at those warnings anyway.

Both errors and warnings look something like this:

hello.cpp:5:6: warning: unused variable ‘x’ [-Wunused-variable]

hello.cpp tells you the name of the file where the error occured, and 5 is the line number of the line where the problem is. This can really help you narrow down the problem! (Sometimes the problem is actually on the line before the one given by the message, it’s just that C++ didn’t notice the problem until you starting doing something different, on the next line.)

In fact, you don’t actually have to compile your program to see errors and warnings. Micro will check your program every time you save it, and if there are any problems, it will put a little >> next to the lines that have errors or warnings. If you move the cursor to one of those lines, you’ll see the error/warning message at the bottom of the screen.

Running

Running our (compiled) program actually makes the computer do whatever the program says to do. To run our program, we type ./ followed by the name of the program (which, if you used compile, is the name of your .cpp file, minus the .cpp). Again, you can do this either from the shell — by quitting micro — or in micro itself, by pressing Ctrl-B.

If all went well, you should be greeted with

Hello, world!

The result of running our program is to print this text to the screen. (Looking at the program above, can you make a guess as to which part actually does the printing? What would you have to change to make it print Goodbye, for now?)

Working on assignments

To work on an assignment, enter the command

do-assignment num

replacing num with the number of the assignment you want to work on (e.g., do-assignment 1). This will download the assignment files from the course website and then open them in Micro for you to edit. One .cpp file will be opened for each worked example and problem in the assignment. (Multiple files opened in Micro show up as tabs across the top; you can click on a tab to switch to that file.)

A general strategy for working on these is

1. Type in the first worked example into its corresponding file (all of the worked examples and problems have their filename in a comment at the top).

2. Save periodically. If there are any errors in your program, they will show up as red arrows in the margin. You can move the cursor to that line to get a short description of the problem, or

3. Press Ctrl-B, type compile filename.cpp (replacing filename.cpp with the filename of the file you are editing) and press Enter. This will print the full, multi-line error messages, if there are any errors. (Sometimes the short messages displayed by Micro aren’t much help.) Fix any problems and go to step (2).

4. If the compile command prints “OK”, then your program compiled without errors; time to run it and see if it does what it’s supposed to. Press Ctrl-B, enter ./filename (i.e., the name of the file you are editing, minus the .cpp at the end), and press Enter. This will run your program so you can try it out. If it does what it’s supposed to, you are done with this program! Move on to the next. Otherwise, try to fix the problem and go back to step (2).

Note that if you change your program at all, you must compile and run it (via ./filename) to see the results of your changes. A common mistake is to save, forget to compile, and then run. In this case, the program you run will still be the old version, without any changes you made.

Next time

In our next session, we’ll talk more about how you can organize your files in the shell (including how the do-assignment command organizes files for you).