Who this course is for
This course is for complete beginners. It is also for you if you learned some programming a while ago and are rusty enough that you barely remember the syntax. You don't need to know anything before you start.
It is modeled after CS 61A, the introductory computer science course at UC Berkeley, and follows that course's textbook, Composing Programs. CS 61A teaches Python the way a computer scientist looks at it: how a program actually gets worked out step by step, how functions build on each other, and, at the end, how to write an interpreter yourself.
By the end of the course, you will be able to:
- write programs with variables, functions,
ifand loops - work with lists, strings, dictionaries and sets
- use recursion, sorting and brute-force search
- define your own classes
- read a problem's input and print an answer an online judge accepts
- estimate whether a program is fast enough before you run it
- build a small interpreter for a calculator language
Python and C++
We will write almost everything in Python. Python is easy to read, so you can pay attention to the idea instead of the syntax.
Every code example also has a C++ tab. You don't have to learn C++ here, but it helps to see the same program in a second language: you start to notice which parts are the idea and which parts are only how one language writes it.
Here is a complete Python program. It prints 7:
print(2 + 5)Switch the tab to C++ and the same program takes six lines. C++ makes you say where the program starts and where printing comes from. Python asks for neither.
Interpreted and compiled languages
So why not write everything in C++? Mostly because Python is easier to start with. What you give up is speed, and the reason is how each language runs a program.
Python is an interpreted language: another program, called the interpreter, reads your code and carries it out one step at a time while it runs. C++ is a compiled language: a program called a compiler translates your whole program into the processor's own instructions before it runs.
That makes Python slower. When Python reaches a + b, it first has to check what a and b are, because + adds two numbers but joins two pieces of text. It does that check every time it gets there. A C++ compiler works it out once, before the program starts. To give you a sense of the gap, counting the numbers from 1 to 100,000,000 that are divisible by 3 or 5 took about 5 seconds in Python 3.14 and 0.05 seconds in C++ on the Mac we checked this lesson on.
For nearly everything in this course you won't notice, because the programs finish in a fraction of a second either way. It starts to matter on problems with a time limit. USACO, the USA Computing Olympiad, gives C++ programs 2 seconds per test and Python programs 4, and the USACO Guide still finds Python too slow for most problems in USACO's two hardest divisions. Part 3, Interpreters and compilers, goes deeper into how both work.
Practice problems and online judges
Each lesson ends with practice problems. They come from online judges: sites where you submit a program and the site checks it for you. The judge runs your program on tests you can't see, and accepts it only if every output is right and the program finishes within the time limit.
Most of our problems are from AtCoder, a Japanese site that holds a Beginner Contest about once a week, and the rest are from Codeforces. You may have heard of USACO and LeetCode too. USACO judges programs the same way. On LeetCode you write one function instead of a whole program, and the site checks what it returns.
These problems are a good test of whether you can use an idea on something you haven't seen before. They are practice, though: the lessons teach each idea directly, and you don't need to care about contests to take this course. Reading input and the judge, a later lesson in this chapter, shows you how to submit a program.
Expressions and their values
Let's take the program from Part 1 apart. It is one line, print(2 + 5), and it has two pieces: 2 + 5 works out a number, and print shows that number on the screen. We'll look at each piece in turn.
The 2 + 5 is an expression: a piece of code that has a value. Working out the value is called evaluating the expression, and 2 + 5 evaluates to 7. Subtraction is written - and multiplication *, since a keyboard has no × key. Spaces around them are up to you: 2+5 and 2 + 5 are the same expression.
| Expression | Value |
|---|---|
7 | 7 |
2 + 5 | 7 |
10 - 3 | 7 |
2 * 5 | 10 |
2 * 6 | 12 |
A number on its own, such as 7, is an expression too, and its value is the number itself. As the first three rows show, many different expressions have the same value.
Printing a value
Now the second piece. print shows the value of whatever is inside its parentheses, and a program can have as many print lines as you like. This one has two:
print(2 + 5)
print(2 * 5)It shows 7 and then 10. Python evaluates 2 * 5 first and hands print the result, which is why the second line shows 10 and not the characters 2 * 5. The lines run from top to bottom, and each print ends its line, so the next value starts on a new one.
You can check this with the Run button under the listing. It runs the program on WhiteBox's server and shows what it printed, so you can follow the lessons without installing anything. Running a listing needs a WhiteBox account; the editor in Part 5 runs Python in your browser without one.
Numbers and text in quotes
So far every value has been a number. To show words instead, put them in quotes. Here is the same expression with quotes and without:
print("2 + 5")
print(2 + 5)Quotes mark a piece of text, so the value of "2 + 5" is those five characters and no arithmetic happens. Text is how a program shows words, such as "Hello". Text in quotes is shown as written; an expression outside quotes is worked out first.
Interpreters and compilers
In Part 1 we said that Python runs your program with an interpreter, while C++ translates it with a compiler first. This part looks at what each of them does between the moment you press Run and the moment 7 appears. The difference affects more than speed: it also decides when you find out about a mistake.
Both start from the same fact: a processor can't read Python or C++. What it carries out is machine code, instructions stored as numbers, each of which does one small thing, such as adding two numbers or copying a value from one place in memory to another. A program in any language has to be turned into machine code, or be carried out by another program that already is machine code.
A compiler does the translation ahead of time. A C++ compiler such as g++ reads your whole file, checks that it follows the rules of C++, and writes a new file of machine code. Running your program means running that new file, and the compiler plays no further part. For a + b with two whole numbers, the compiler writes the processor's instruction for adding whole numbers, so the finished program never has to ask what kind of values it is adding.
An interpreter carries the program out itself. Python's interpreter, python3, is a program written in C and compiled to machine code. When you run a Python file, it reads the whole file and checks that every line is well formed, translates the file into simpler instructions called bytecode, and then carries out the bytecode one instruction at a time. a + b becomes a single bytecode instruction that works for numbers, text and anything else that can be added, so each time that instruction runs, the interpreter looks at a and b and decides which kind of addition to do. That repeated decision is where the speed difference from Part 1 comes from.
| Python | C++ | |
|---|---|---|
| Translated into | bytecode | machine code |
| When | every time you run the file | once, by compiling, before it runs |
| Carried out by | the interpreter, one instruction at a time | the processor, directly |
What + means is decided | each time the + runs | once, while compiling |
| A misspelled name is found | when its line runs | while compiling, before anything runs |
Error messages
A language applies its rules exactly. A person reading prnt(2 * 5) would see that you meant print and read on; Python stops the program. Here is one with that typo on its second line:
print(2 + 5)
prnt(2 * 5)Run it and you see 7, then an error message. Python carried out line 1 before it ever looked at what prnt means. When it reached line 2, it found that no such name exists and stopped there. Python calls this kind of message a traceback, and running typo.py on your own computer prints:
Traceback (most recent call last):
File ".../typo.py", line 2, in <module>
prnt(2 * 5)
^^^^
NameError: name 'prnt' is not defined. Did you mean: 'print'?Read a traceback from the bottom up. The last line says what went wrong: a NameError means Python met a name it doesn't know, and here it even suggests the one you probably meant. The lines above it say where: line 2 of typo.py, with the line itself and carets under the name that failed.
A mistake in the grammar of a line is caught sooner. Python checks the whole file before it runs any of it, so if line 2 were print(2 * (3 + 4), with a parenthesis never closed, Python would stop with SyntaxError: '(' was never closed and show nothing, not even the 7. prnt(2 * 5) got past that check because it is written correctly: it is a well-formed call to a name that happens not to exist, and Python finds that out only when it runs the line.
Debugging
An error message at least tells you where to look. A line that is correct but computes the wrong thing gives no message at all. Finding and fixing mistakes of either kind is called debugging.
Suppose you want the seconds in 2 hours, , and write 2 * 60 * 6. The program runs without complaint and shows 720. Rather than stare at the line, show the calculation one step at a time:
print(2)
print(2 * 60)
print(2 * 60 * 6)2 hours is 120 minutes, so the second line is right. The third should be 7,200 and is 720, so the 6 should have been 60. The mistake is in the first line whose output differs from what you expected.
Your turn: make it show 12
This program shows 10. Change one number so that it shows 12, and work out the new value in your head before you run it.
Python code
Output
Your result will appear here.
Writing programs on your own computer
Installing Python lets you keep your programs as files on your own computer and run them whenever you like, outside these lessons.
-
Install Python
Download it from python.org/downloads(opens in a new tab) and run the installer. On Windows the page offers the Python install manager.
-
Install VS Code
Download the editor from code.visualstudio.com(opens in a new tab).
-
Add the Python extension
In VS Code, open Extensions, search for Python and install the one published by Microsoft.
-
Run a file
Create a file named
first.py, typeprint(2 + 5)and click Run Python File, the play button at the top right of the editor. The terminal panel that opens shows7.
To skip installing, the WhiteBox IDE runs Python and C++ in your browser after you sign in.
Once Python is installed, you can also use it without a file. In VS Code's terminal panel, type python3 (python on Windows) and press Enter. That starts an interactive session: at the >>> prompt, Python evaluates each line you type and shows its value straight away, without print. Type 7 * 6 and it replies 42; type "7 * 6" and it replies '7 * 6', the quotes telling you the value is text. quit() ends the session. It is the quickest way to check a small calculation.
Only the session shows values by itself. In a file, a line holding only 7 * 6 is evaluated and its value thrown away, so it shows nothing; a program needs print.
Recall What does a program show for `"3 * 4"` in quotes, and what does it show for `3 * 4` without them?
The first shows the characters 3 * 4, because text in quotes is shown as written. The second evaluates 3 * 4 before it is shown, so it shows 12.
Recall Why does a loop that adds numbers millions of times run slower in Python than in C++?
Python's interpreter checks what kind of values it is adding each time it reaches the +, because + also joins text. A C++ compiler makes that check once, before the program runs, so the finished program only does the additions.
Recall A program's first line is correct and its second line misspells the instruction that shows a value. What appears when you run it?
The output of line 1, then an error message. A misspelled name is well formed, so Python starts the program and finds out that the name does not exist only when it reaches line 2.
Key terms
| Term | Meaning |
|---|---|
| interpreted language | A language whose programs are normally carried out by an interpreter as they run, such as Python. |
| compiled language | A language whose programs are normally translated into machine code before they run, such as C++. |
| online judge | A website that runs a submitted program on hidden tests and checks its output and running time. |
| expression | A piece of code that has a value: 2 + 5, 7, "Hello". |
| evaluate | Work out an expression's value: 2 * 5 evaluates to 10. |
| text | Characters in quotes, shown exactly as written: "2 + 5" shows 2 + 5. |
| machine code | The instructions, stored as numbers, that a processor carries out directly. |
| compiler | A program that translates a whole file into machine code before it runs, as g++ does. |
| interpreter | A program that reads another program and carries out its instructions, as python3 does. |
| bytecode | The simpler instructions Python translates a file into before its interpreter carries them out. |
| error message | The report a language gives when it cannot run a program: what went wrong and where. |
| traceback (Python) | Python's error message: where the error happened, then on its last line what went wrong. |
| debugging | Finding and fixing a mistake in a program, for example by showing each step of a calculation. |
| interactive session (Python) | Python run without a file: it evaluates each line you type and shows the value. |