My Harvard CS50 Notes - Lecture 1 - C

by Thibault Seynaeve 2 months ago 19 min read

I'm following the online Harvard CS50 course and I'm making my notes public!

Lecture

In this lesson, we'll learn how to solve problems, but we'll also learn how not to solve problems.

We'll take the basic building blocks of programming that we visualized in Scratch in Lecture 0 and transform them into "real code".

Specifically, we'll write "source code". However, the computer only understands machine code (which is binary). We'll need a compiler to transform the source code into machine code.

In this course, we'll use a cloud-based version of Visual Studio Code, available on cs50.dev

We'll use both the GUI (Graphical User Interface) and CLI (Command Line Interface).

Hello, world

In the CLI, we use code hello.c to create a new file.

In this file, we'll write this code to print "hello world" to the screen. We use \n to make sure that the output 'Hello World' has a new line after it, so that the dollar sign in the terminal doesn't display next to the output.

Back in the terminal, we use "make hello" (note that we do not include the extension here), and this will make a second file 'Hello'.

And finally, we'll use the command ./hello to run the code.

So what does the #include <stdio.h> actually mean?

#include tells the compiler that it has to find the file stdio.h so that we can use "printf" in our code. It's a library.

Libraries allows us to stand on eachother shoulders. We can implement a library to get access to code that someone else wrote.

CS50 has a simplified version of the C documentation, since the official documentation is a bit hard to understand for beginners: https://manual.cs50.io/

CS50 also has it's own header file that simplifies a few core concepts. It are training wheels that will be removed in a few lessons. It includes functions like get_char and get_string.

Get user input

We now want to collect user input to display a personal greeting for the user.

We will store the value in a variable. In C, you have to define the type of variable (which is a string in this case).

In our print_f, we use %s to add a placeholder, and we'll have to pass the value of the placeholder as an argument.

Using other types of variables and conditionals

Now let's try to use some other types of variables as well.

We can use format codes in printf, like %s for string and %i for integers.

Let's try to write some code that checks if X is less than Y, or if it's greater than Y, or if it's equal.

Note that we use a double equal sign to compare the values of X and Y. If we only used 1, the computer would think that we want to assign the value of Y to the variable X.

Performance tip: we actually don't need the last if-statement, because if X isn't greater than Y and it isn't lower than Y, it must be equal.

Agree.c

Now let's write a program that propmpts the user for a 'Y' or 'N' and processes that input.

We're going to use the char type here, which differs from a string in the sense that it is always a single character.

Notice that we're using single quotes here. Usually you use double quotes for a string, but if you're using a single character, single quotes are fine.

We're using the double pipeline signes (||) as an 'or'. So if the user replies 'y' or 'Y', they get the same result.

#include <stdio.h>
#include <cs50.h>

int main(void){
   char answer = get_char("Do you agree?");

   if (answer == 'y' || answer == 'Y'){
    printf("Agreed \n");
   } else if (answer == 'n' || answer == 'N'){
    printf("Not agreed.\n");
   }
}

We can also use the double and-signs (&&) to make an 'and' operator but that wouldn't make sense in this case.

Loops

Now we'll write a piece of software that repeats something multiple times. We'll use a while loop that checks the value of a counter (that we decrement with each execution of the loop).

When defining a variable for a counter, it's common to use the name 'i'.

Instead of counter = counter -1, we can simply do counter--

#include <stdio.h>
#include <cs50.h>

int main(void){
    int i = 3;
    while (i > 0){
        printf("meow\n");
        i--;
    }
}

Now we're from 3 to 0, but we could reverse it and count up to 3 (or ideally, from 0 to 2 so you don't waste any bits).

We used a while-loop for this program, but there are other loops as well, like the for-loop which takes three parameters:

assigning a variable to a value (of the counter)
check the value of the counter
change the value of the counter (usually +1 or -1)

#include <stdio.h>
#include <cs50.h>

int main(void){
    for (int i = 0; i < 3; i++){
        printf("meow\n");
    }
}

Functions

If you want to create a function in C, you use void. This means that this function has no return value. It just does something.

void meow(void){
  printf("meow");
}

In this case it's really important that you define the function before you use it, so in this case you could simply put the void 'meow' would before the 'main'.

However, it's not really the best idea to keep pushing the main void lower to the bottom. So let's leave meow at the bottom, but put void meow(void); at the top. This tells the compiler that while this doesn't exist yet, it will soon.

Let's take it one step further and take a parameter as the value for the 'meow'. This makes the code more flexible, since you don't have to write another function if you now want to meow 4 times instead of 3. So in the for loop we don't use i < 3 anymore, but i < n, which takes the value of the parameter.

Calculator

This program will take two values and add them together.

We could do this like this:

#include <cs50.h>
#include <stdio.h>

int main(void){
    int x = get_int("X: ");
    int y = get_int("Y: ");

    printf("%i \n",x+y);
}

Let's now create a new function 'add' that takes 2 parameters, add them together and return the value.

This is a good time to teach us about scope, which is the context in which variables exist. For example, a variable declared in the void 'main' only exists between those two curly braces, and won't be accessible in another function we create. This means that we'll have the function 'add' to take two parameters.

#include <cs50.h>
#include <stdio.h>

int add(int a, int b);

int main(void){
    int x = get_int("X: ");
    int y = get_int("Y: ");
    int z = add(x,y);

    printf("%i \n",z);
}

int add(int a, int b){
    return a + b;
}

We could even remove the line with variable z, and use the 'add' function directly as the argument for the printf.

Linux

Let's talk about Linux! Most servers run Linux (with a command line interface).

When we run cs50.dev, we automatically connect to a cloud version of VS Code, with a small own server (docker container) that's only accessible to use. So whenever we run a command like "make calculator", we run a command on the server.

Some of the most important commands are:

cd
cp
ls
mkdir
rmdir

Rename a file

If we want to rename a file, we can simply use the 'mv' (move) command.

mv hello.c goodbye.c

Show a list of all the files in the directory

ls

The asterix after 'hello', and 'agree' means that it's executable.

Remove a file

rm goodbye.c

Mario.c

We'll now make a command line version of Super Mario Bros.

First we'll print four question blocks.

#include <stdio.h> 

int main(void){
  for (int i = 0; i<4; i++){
    printf("?");
  }
  printf("\n");
}

Now what if we want to display blocks like this

###
###
###

This is a great way to introduce us to introduce us to nested loops.

We're introduced to constants, putting 'const' before our variable declaration will "protect" it since we won't be able to change it to something else.

We'll also extend our code with a variable n that will be used in the for loops to create blocks. We'll request this value from the user. To provent that they enter a value lower than 1, we'll add a while loop that keeps asking for a value until it's 1 or higher.

#include <stdio.h>

int main() {
    
    int n = get_int("Size: ");
    
    while (n < 1){
        n = get_int("size: ");
    }
    
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            printf("#");
        }
        printf("\n");
    }
}

This check can be more compact with a do-loop. This way, we don't have to repeat the "get_int" step more than once. We'll also declare the n variable above this loop, so that we can use it in the for loops.

Integer overflow

Let's talk about memory or RAM, where data is stored in your computer. We only have a finite amount of memory in our devices.

If we're only using 3 digits, we can count to 7 in binary. To count to 8, we need a 4'th bit, but what if we don't have it? Then the result will actually be 0 (since 8 is 1000, but the computer only has access to the last 3 zero's).

The fact that we have a finite amount of memory is a problem, and negative numbers increase complexity since you can only count to -2 billion instead of 4 billion with 32 bits.

If integers are not enough, you can choose for the long data type that supports 64 bits.

If you want to print a long variable in printf, you should use %li.

Truncation

If you take an integer, and you divide it by an integer, even if you get a fractional value the fraction get's thrown away. Everything after the decimal point becomes 0.

To fix this, we can use type casting to treat integers as floats.

int main(void){
  int x = get_int("X: ");
  int y = get_int("Y: "); 

  float z = (float) x / (float) y;
  printf("%f\n",z);
}

In this case, Z will now be defined by dividing one float by another, which means that the truncation will not work.

If we want to show specifically 5 decimal places, we can use %.5f in printf.

print("%.5f\n");

Floating Point imprecision

Say that we ask our program to divide 1 by 3 and show 20 decimal points. The result is 0.333333334326744079590

Weird, right? Should it be 0.3333333333333333333333?

This is because the computer has finite memory so it can't represent every possible number in the universe. So what we're seeing is the closest it can actually get.

Even if we upgrade from floats do doubles, we get more 3's but still not only 3's.

This is an issue called floating point imprecision. You can't possibly represent an infinite amount of numbers with a finite amount of memory.

Real World examples

A lot of old software broke in Y2K, because they only used two digits to represent years (memory was very expensive and this was a way to save memory). So in 2000, the computer assumed the year was 1900.

Nowadays, we use 32-bit integers to keep track of time. Specifically the number of seconds from epoch (1 january 1970). You can only count to 4 billion with 32 bits, so that we're going to run into the same problem on 19 january 2038. That value is going to return a 0 value.

If we use 64 bits, we're going to fundamentally solve this problem but it's still finite.

Games like Pac-Man and the original Donkey Kong also break when you get to a too high level.

Boeing was also keeping an integer that was keeping track of time in 100s of seconds, so the plane's power would stop when the value got too high. However, a simple fix is turning the plane off and back on again!

Shorts

Data Types

Integer

Always take up 4 bytes of memory (32 bits). Half is negative, half is positive. So that's about 2 billion negative, 2 billion positive.

An unsigned int is when you double the positive range of variables, at the cost of disallowing any negative values.

Chars

Store single characters
Take up 1 byte of memory (8 bit)

Float

"real numbers"
They have a decimal point
Take up 4 bytes of memory (32 bits)
We are limited in how precise we can be

Double

Similar to float
Double precision, they can fit 8 byte (64 bits)
If you have numbers with a lot of decimal points that need precision, a double is a good choice

Void

Not a data type, but a type
Functions can have a void return type. This means that it doesn't return a value.
The parameter list of a function can also be a void, this means that it takes no parameters

Bool

Used for variables that will store a boolean value (true or false).
This isn't included in the C programming language, but we get access to this with the cs50.h library.

String

Also not included in C, but available through the CS50 library.
Used for variables that will store a series of characters (store words, sentences, paragraphs, etc)

Later we'll also see structures (structs) and defined types (typedefs) to create own data types.

Creating variables

Give it a type
Give it a name

int number; 
char letter;

You can also create multiple variables of the same type on the same line:

int height, width; 
float sqrt2, sqrt3, pi;

Best practice: only declare variables when you need them.

Using variables

After a variable has been declared, you don't need to declare the variable's type again.

Declaration

int number

Assignment

number = 17

You can also declare a variable and assign it at the same time. This is sometimes caleld initializing.

int number = 17;

Operator

Arithmetic Operators

Add (+), subtract (-), multiply (*), divide (/)

Modulo (%) gives you the remainder when you divide to numbers. 13 % 4 = 1.

You can also use a shorthand way

x = x * 5;
// This is the same as 
x *= 5;

If you want to increment or decrement a variable:

x++; // Increment by 1 
x--; // Decrement by 1

Boolean Expressions

These are used for comparing values
They evaluate to true or false
Every nonzero value is the same as saying true. So we don't always have to use bool variable types
There are two main types of Boolean expressions: logical operators and relational operators.

Logical operators

Logical AND (&&) is only trwo when both operands are true
Logical OR (||) is true if and only if at least one operand is true
Logical NOT (!) inverts the value of its operand

Relational operators

Less than ( x < y)
Less than or equal to (x <= y)
Greater than (x > y)
Greater than or equal toe (x >= y)
Test for equality (x == y)
Test for inequality (x != y)

Conditional Statements

Allow your programs to make decisions and take different forks in the road depending on the values of variables or user input

If-statements

if (boolean-expression){
  // Do something
}

If-else

if (boolean-expression){
  // Do something
} else {
  // Do something else
}

You can chain multiple else if's.

Switch

Conditional statement that permits enumeration of discrete cases instead of relying on Boolean expressions
Important to break; between each case otherwise you will run all the following cases as well (unless that is by design, because it can also be useful).

int x = GetInt();

switch(x){
  case 1: 
    printf("One!");
    break;
  case 2:
    printf("One!");
    break;
  default: 
    printf("Sorry!");
    break;
    
}

Shorthand (ternary operator)

int x = getInt();

if (expr){
  x = 5;
} else {
  x = 6;
}

Is exactly the same as

int x = (expr) ? 5 : 6;

Great choice if you're just making a quick simple choice

Loops

While

Use this you want to keep doing the same thing for an unknown amount of time

while (boolean expression){
  // Do something 
}

Do-while

Execute all lines of code once, and then only if the boolean-expr evaluates to true
Code will run at least once

do{
  // Do something
} while (boolean-expr)

For-loop

Use when you want a loop to repeat a discrete number of times, though you may not know the number at the moment the program is compiled

for (int i = 0; i < 10; i++){
  // Do something
}

Set the counter variable
Check the boolean expression
1. If true, execute the body of the loop
Counter variable is incremented

Linux Commands

These commands can be used on any UNIX-based system (like Linux or Mac). Some commands are different on Windows.

Short for 'list'. This gives you a readout of all your files and folders in the current directory.

Short for 'change directory'. Used to navigate between directories.

Curent directory is always dot (.)
Parent directory is (..)
If you enter 'cd' without anything else, you go the the highest level

mkdir

Short for 'make directory', used to create a folder.

Short for 'copy', used to create a duplicate of a file or directory

Copy a file:

cp hello.txt thisisacopy.txt

Copy a directory and everything inside of it (recursively):

cp -r pset0 pset3

Short for 'remove'. This will delete a file or directory.

Remove a file

rm hi.txt

If you add the 'force' flag (-f), the system won't ask you for any confirmation.

rm -f hi.txt

If you want to delete a directory:

rm -r pset2

This will remove the directory called 'pset2' and everything inside of it

You can combine flags like this:

rm -rf pset2

Remove the folder pset2 and everything inside it, and don't ask for any form of confirmation

Short for 'move'. Also used to rename folders or directory.

Rename a file:

mv hellow.txt hello.txt

Rename the file called 'hellow.txt' to 'hello.txt'

Magic Numbers

Directly writing constants into our code is sometimes referred to as using magic numbers. It's considered a bad practice.

card deal_cards(deck name){
  for (int i = 0; i < 52; i++) {
    // do something 
  }
}

In the example above (pseudocode), the number 52 is considered a magic number, because the number 52 has no context. If someone reads your code, they wouldn't immediately understand why there is a number 52.

C provides a preprocessor directive (also called a macro) for creating symbolic constants.

#define NAME REPLACEMENT

When the compiler goes through your code, it will replace everthing with the name 'name' with the name 'replacement'.

For example:

#define PI 3.14159265

Now you can use 'PI' in your code and the compiler will replace it with the value.

Another example:

#define COURSE "CS50"

The convention is to put the name of your symbolic constant in uppercase so you don't confuse it with a variable.

The code becomes much clearer this way:

#define DECKSIZE 52 

card deal_cards(deck name){
  for (int i = 0; i < DECKSIZE; i++) {
    // do something 
  }
}

Now if you need to change the decksize, you can just do it at this one place so you don't have to replace a lot of your code.

Section

Sections help us bridge the gap between lecture and problem sets.

Variables and types

A variable is basically a name for a container that holds a value so that you can easily reference it.

A variable has three parts:

The type (what kind of value does this container store)
The name
The variable

There is actually another part, and that's the assignment operator (equal sign).

int calls = 3;

Create an integer named calls that gets the value 3

Truncation

When you divide 9 by 2 and you store it in an integer, the result will be 4 (instead of 4.5. Since you use an integer, there will be truncation, and the decimal number will simply be removed.

Input and printing

In CS50, you have access to functions like get_int to prompt the user for an integer. It returns the value so you can store it in a variable.

To print things in C, we use the function printf.

int calls = 4;
printf("Calls if %i\n",calls);

We use a placeholder %i for an integer, and we pass the value as an argument

The 'f' in 'printf' means 'formatted'.

int (%i)
float (%f)
char (%c)
String (%s)

Functions

If you use a function, you have to make sure that the function has been defined before you use it. Otherwise, you can include a prototype at the top of your code.

It's generally a good idea to have the main function on top of all your other functions, because the main function is always the first one to run.

#include <cs50.h>
#include <stdio.h>

void print_row(int length); // Prototype

int main(void){
    int height = get_int("Height: ");
    print_row(height);
}

void print_row(int length){
    for (int i = 0; i < length; i++){
        printf("#");
    }
}

Problem Sets

Hello World

The first pset asks us to write a simple piece of software that shows 'hello world' when you run it.

Easy enough!

#include <cs50.h>
#include <stdio.h>

int main(void){
    // Print "hello, world"
    printf("hello, world\n");
}

But I have a feeling that this was just the warm-up.

Hello, it's Me

Problem set:

In a file called hello.c in a folder called me, implement a program in C that prompts the user for their name en then says hello to that user. For instance, if the user's name is Adele, your program should print "hello, Adele".

Not too hard either. We can extend our code from the "hello world" problem set with a variable 'name' and assign it to a function that prompts the user for their name.

#include <cs50.h>
#include <stdio.h>

int main(void){
    // Print "hello, name"
    string name = get_string("My name is: ");
    printf("hello, %s\n",name);
}

Mario (less challenging version)

Problem set:

In a file called mario.c in a folder called mario-less, implement a program in C that recreates a pyramid using hashes (#) for bricks. Prompt the user for an integer for the pyramid's actual height. The pyramid looks like this:

  #
 ##
###

Definitely a bit more challenging because we need to calculate how many spaces we need to print, so this one requires a bit of thinking first:

Let's translate this into code:

And now verify the result...

Mario (more challenging version)

Problem set:

In a file called mario.c in a folder called mario-more, implement a program in C that recreates the following pyramid:

   #  #
  ##  ##
 ###  ###
####  ####

Let the user decide just how tall the pyramids should be by first prompting them for a positive int between 1 and 8, inclusive.

Back to the drawing board. Now the line we have to print becomes significantly more complex. First we have to print a part of the right ride pyramid, then there are two spaces, and then there is the left side pyramid.

We can re-use our code of the first version, but we'll have to extend it with 2 spaces for the "buffer" between the two pyramids, and run the print_row function again, but this time it won't need any spaces.

Let's add it and check the output:

Seems good! Now we run the checker to verify our solution.

Yay! I'm available for hire, Nintendo.

Time to submit the code and get a grade.

Cash

Now we need to write a piece of software that will tell us how many coins (25 cents, 10 cents, 5 cents, 1 cent) we need to pay change to a customer. For example, when we need to pay 70 cents, in change, the program should tell us that we're going to need 4 coins (2 times 25 cents, 2 times 10 cents). If we need to pay 25 cents, we only need 1 coin.

I have a feeling we'll be able to use the modulo operator here!

So let's think about it:

Let's say we have to give the customer 70 cents. We do 70 module 25, which is 20. Since the remainder is different from the starting value (which is 70), we know that we can give a coin of 25 cents at least 1 time. So we subtract 25 cents, increment the coin counter and run the whole loop again.

So we get 45. 45 module 25 is 20 so it's still possible. Subtract the value with 25 and add 1 more to the coin counter.

The value is now 20. 20 module 25 is 20. Aha! That's the same as the starting value, so we know that we won't be able to give out any more coins of 25 cents. Now we need to move to a lower coin (10 cents) and repeat this process until we're left with a variable of 0.

Translated to code, it looks like this:

Testing is looking promising:

Let's run the checker:

Credit

Only 1 more pset to go.

For this problem set, we need to create a piece of software that will check if a given credit card number is valid. We'll do this by using a checksum. We use the algorithm invented by Hans Peter Luhn of IBM:

Multiply every other digit by 2, starting with the number's second-to-last digit, and then add those products' digits together
Add the sum to the sum of the digits that weren't multiplied by 2
If the total's last digit is 0 (or, put more formally, is the total modulo 10 is congruent to 0), the number is valid

Let's think about it, since this is certainly a sticky wicket.

So the first challenge will be to get every single digit in a number. A good way to handle this would be through arrays, but since there is a whole lecture dedicated to that, I refrained from using them here.

If divide a number by 10 and take the remainder, you get the last digit.

int lastDigit = (x / 10) % 10

How do we get the second to last digit?

Well, that's

int secondToLastDigit = (x / 100) % 10

Third to last?

int thirdToLastDigit = (x / 1000) % 10

I guess you start to see a pattern. We can use the value of the counter (that starts at 0 and get's incremented by 1 every time the loop runs) and use it as a power of 10. This is how we can loop through all the digits (from right to left). I'll use the function "pow" for this. This means that we'll have to include the library math.h. We can probably solve this problem in a way where we don't need this library.

We'll also need to find a way to count the amount of digits. We can do this by dividing the creditcard number by 10 until we get 0. If we count how many times we have to do this, we get the amount of digits. We'll put this in a function.

You can take a look at my code here: