CMPUT 201, Fall 2014

Contents 1

Course Contents
Part 1: Introduction, UNIX
Part 2: C/C++ Basics
Basic types, expressions, flow control, functions, passing parameters
Part 3: C/C++ Basics Continued
C-structures, arrays, pointers, references, input/output, C-strings, dynamic memory allocation
Part 4: Code Modularization and Abstract Data Types
Part 5: Bits and Bytes
manipulating data at the bit level
Part 6: UNIX File I/O
Part 7: Parallel Computation with POSIX Threads
Part 8: C++, the better C
Template functions, class templates, Standard Template Library

CMPUT 201, Fall 2014

Contents 2

Part 1: Introduction, UNIX

Contents
Motivation p.3

[DOCUMENT FINALIZED]

The UNIX Operating System, Shell, Editor p.12

Getting Started p.21
Command Shell p.22
UNIX File System p.23
Launching Programs p.25
Wildcards p.26
Hidden Files p.27
Filename Completion p.28
Input/Output Redirection p.29
Pipes p.30
Edit Textfiles p.31
First C Program p.33

CMPUT 201, Fall 2014

Motivation 3

Motivation
Typical Personal Computer (PC) Mainboard

Flexible design: slots for central processing unit (CPU),

memory (RAM), and expansion cards such as video or
high-end audio cards.

CMPUT 201, Fall 2014

Motivation 4

Schematic Design of a PC

631

CPU = Central Processing Unit (Brain of the computer, manages data flows from connected devices to and from memory)
ROM = Read-Only Memory (doesnt lose content when power
switched off, contains start-up code)
RAM = Random Access Memory (misnomer: better would be
read/write memory, loses content when switching power off, is
filled with code/data from harddrive when booting and launching
applications)

CMPUT 201, Fall 2014

Motivation 5

Central Processing Unit (CPU)

Modern CPUs contain multiple execution cores which

run programs in parallel at a speed of over a billion
machine instructions per second each.

CMPUT 201, Fall 2014

Motivation 6

von Neumann Computer Architecture

0
1
2

CPU
Register File
ALU

Data

R0
R1
...
Rn

Memory
(sequence of bytes)

Program Counter PC

93
1
0
239
92
1
0
42
235
3

LD 1, R1
R1 := R1 + 1
ST R1, 1

Machine Program
(Assembly Language)

JMP 1003

1003

Memory is a sequence of numbers between 0 and 255

(8-bit values called bytes)
Each byte in memory has a unique address
Machine code and data are indistinguishable both
are just sequences of bytes
CPUs contain registers (fast temporary memory) and
execute machine code that is pointed to by a so-called
program counter (PC), which advances after each step.

CMPUT 201, Fall 2014

Motivation 7

Each machine instruction by itself doesnt do much, but

execution is FAST (billions of instructions per second).
Typical machine instructions read values from memory into a register, manipulate register values using
an Arithmetic Logic Unit (ALU), store values back, or
change the Program Counter (jump instructions).

CMPUT 201, Fall 2014

Motivation 8

Problems:
How can we handle a large variety of machine architectures and machine codes?
We want to write programs at a more abstract level
than machine code, so that they are easier to read,
write, debug and reuse.
We want to write one program that can run on many
different machines without changes.

CMPUT 201, Fall 2014

Motivation 9

Solution:

Design operating systems that abstract hardware peculiarities by means of device drivers that interact with
hardware and provide a uniform programming interface.
Write programs in high-level programming languages
that get translated into particular machine code by a
program called compiler.
So, instead of having to produce N machine code versions of our program for N different machine architectures, we only write our program once and let the
N different compilers (that somebody else wrote ,)
translate our program.

CMPUT 201, Fall 2014

Motivation 10

Software/Hardware Layers
CMPUT201
CMPUT379

CMPUT229

Libraries

User Programs

Operating System
CPUs

Devices Memory

In this course we take a look at the operating system

UNIX and the high-level programming languages C and
C++.
Linux is a free software UNIX variant. Android is based
on Linux. Apples OS X and iOS are derived from
NetBSD, another UNIX variant.
UNIX and C were developed together at AT&Ts Bell
Labs. Dennis Ritchie wrote C, and Ken Thompson and
Ritchie (and others) wrote UNIX in C and assembly language. Thompson and Ritchie won the Turing Award
in 1983 for developing UNIX.

CMPUT 201, Fall 2014

Motivation 11

C is sometimes called the lingua franca of computing

science, because it is ubiquitous.
Many other high-level languages such as Perl, Python,
and Java have C interfaces, because C allows us to
create very efficient programs.
C++ is the better C. Among other things it supports
object oriented and generic programming.

CMPUT 201, Fall 2014

The UNIX Operating System, Shell, Editor 12

The UNIX Operating System, Shell, Editor

Why UNIX?
Open standards (e.g. POSIX threads)
Dominant server operating system
Free versions available (FreeBSD, OpenBSD, Linux)
Many free software development tools:
gcc, emacs, gprof, gdb, gawk, kdevelop, etc.
Multi-tasking
(multiple programs can run at the same time)
Multi-user
(multiple users can work on the same machine)
We will be using Linux in the labs. In the next few
pages, well discuss your options for working from home,
depending on what OS you are currently running.

CMPUT 201, Fall 2014

The UNIX Operating System, Shell, Editor 13

Linux
As a computing scientist, its a good experience to install and administer your own Linux system at home.
There are many freely downloadable distributions appropriate for new users, such as Ubuntu or Linux Mint.
Two options for running Linux at home:
Install to a hard drive partition, either as your only
OS, or alongside Windows or Mac OS X.
live CD or USB stick. Boot up to Linux without
having to install it on your hard drive.
If you run Linux at home, you can program in C using
the same tools that we will use in the lab.

CMPUT 201, Fall 2014

The UNIX Operating System, Shell, Editor 14

Mac OS X
Mac OS X is based on Darwin, which is Apples version
of NetBSD UNIX. OS X ships with all of the development tools we will use in the labs, such as:
the bash shell (a command line interface)
emacs and vi (text editors)
gdb and ddd (debuggers).
gcc / g++ or clang (C / C++ compilers, see below)
If you dont have these tools installed, you can use the
homebrew package manager to install them for you.
Homebrew is free, and makes it easy to install and maintain open-source programs on your Mac.
OS X has a small number of differences from Linux
when it comes to C / C++, that we probably will not
encounter in this course. Your programs should compile
and run on both without changes.

CMPUT 201, Fall 2014

The UNIX Operating System, Shell, Editor 15

If your OS X is older than Mavericks, then it will have

the same gcc / g++ compiler that we will use on
Linux. You might have to install it from the OS X
cd or install it with homebrew.
If youre on Mavericks or newer, it uses a new open
source C / C++ compiler called clang instead of gcc
/ g++. This should work for this course but will have
different error messages from gcc in the labs.
However, you can also just log into a Linux lab machine
from home - well explain how in a few pages.

CMPUT 201, Fall 2014

The UNIX Operating System, Shell, Editor 16

Windows
For Windows, tools like Visual Studio let you write,
compile, and debug C and C++ programs.
Most of the language is the same as it is on Linux,
although functions for interfacing with the OS are often
different.
The C and C++ languages are continuing to evolve
over time (such as the C89, C99, C++0x / C++11,
and upcoming C++14 standards). Microsoft / Visual
C++ hasnt kept up to date with these standards, while
the UNIX world largely has.
Although you could use something like Visual Studio
for programming exercises, UNIX is a central part of
this course and you should use it. Its easy to log into
a Linux lab machine from home - well explain how in
a few pages.

CMPUT 201, Fall 2014

The UNIX Operating System, Shell, Editor 17

Working on multiple machines

A correctly written C / C++ program should compile
and run identically on any of these systems (aside from
a few OS-specific functions for Windows).
However: a buggy program might appear to work on
one computer or OS, but crash or give different output
on another.
In C and C++, its not uncommon for bugs to cause
different output if you run a program twice in a row.
Including crashing the first time and not the second!
Just because a program looks like it works at home,
dont assume that it will also run correctly on the lab
machines. Well be using the lab machines for marking
your work.
Your programs have to compile and run correctly in the
lab. But this works at home isnt an excuse; that
probably means its actually buggy in a hard-to-detect
way.

CMPUT 201, Fall 2014

The UNIX Operating System, Shell, Editor 18

Connecting from home

With any home computer or laptop, you can log in to
the lab computers over the internet by using Secure
Shell (ssh).
Linux, Mac OS X: Use ssh in a terminal window.
Mac: Applications/Utilities/Terminal.app. Youll
use this a lot, put it in your dock.
Windows: Install an ssh client like PuTTY.
The lab computers have the addresses ugXX.cs.ualberta.ca,
where XX is 01 through 34. On Linux or Mac, open
a terminal and type this, replacing <CSID> with your
Comp Sci username:
ssh <CSID>@ug01.cs.ualberta.ca
It will try to connect, ask for your Comp Sci password,
and (if successful) give you a terminal.

CMPUT 201, Fall 2014

The UNIX Operating System, Shell, Editor 19

If you are on Windows and using PuTTY, youll see this

window:

Open an address such as ug01.cs.ualberta.ca in the

Host Name field and choose the SSH radio button.
Optionally, also enter a name (such as c201 lab machine) in the Saved Sessions field and click Save, so
you dont have to enter this again. Click Open to
try to connect; it will ask for your Comp Sci login and
password.

CMPUT 201, Fall 2014

The UNIX Operating System, Shell, Editor 20

This gets you a terminal window that you can work

from. Its often handy to open a few windows, to edit
different files or run your programs while viewing the
code.
On the lab computers youll have a GUI for your text
editors and tools, which can be convenient. Optionally,
you could try setting up X Forwarding, which allows
you to open a remote computers GUI windows on your
display. But this can be laggy and sometimes tricky
to set up. For now, we recommend just using the ssh
text interface, or going to the lab to use the computers
directly.

CMPUT 201, Fall 2014

Getting Started 21

Getting Started
Two ways of accessing a UNIX computer:
1. Sitting in front of it and typing in a command window
2. Connecting to it from a remote machine using ssh
(secure shell)
ssh ug01.cs.ualberta.ca
Both require you to provide a Comp Sci username and
password.
In what follows we will present a UNIX refresher.

CMPUT 201, Fall 2014

Command Shell 22

Command Shell
In interactive mode, shells are command line interfaces (text window with keyboard attached to it)
e.g. xterm
Issue operating system or internal shell commands
directly via keyboard input; e.g.
ls (list directory contents)
cd (change directory)
mv (move/rename)

ls -lrt
cd workdir

mv old-file new-file

mkdir (create directory)

mkdir AS1

cp (copy file or directory) cp -r dir backup

rm (remove file or directory)
cat (display file)
echo (display string)
exit (quit shell)
man (command info)
apropos (keyword search)

rm -rf dir
cat text
echo hello
exit
man man
apropos root

CMPUT 201, Fall 2014

UNIX File System 23

UNIX File System

Data is stored in file systems which are usually located
on hard disks
Persistent: data isnt lost when computer is switched
off (unlike RAM)
Hierarchical structure (tree)
/ represents the root directory
Directories (folders) can contain other directories
and files (internal nodes)
Files (leaves) are just sequences of bytes
Files/directories are uniquely located by a directory
path. E.g. /home/user/AS1/foo.c
/ is also used as directory separator
Unlike Windows (with C:, D:, etc), on UNIX all storage
(hard drives, CDs, etc) is mounted somewhere under /.

CMPUT 201, Fall 2014

UNIX File System 24

Shell continued
Special directories:
/ root directory, everything is stored beneath
. current directory
cp ./foo ./bar = cp foo bar
.. parent directory

cd ../.. : 2 levels up

~ home directory

cd ~/foo

cd = cd

Command history/editing
use arrow keys to navigate, <delete> or
<backspace> keys to remove characters
The shell is also a simple programming language
variables, functions, command aliases
The file ~/.bashrc (if using the bash shell) contains shell code that is run when the shell starts
You can customize this!
function ll() { ls -l "$@"; }
(files starting with . are hidden but can still be
edited, or seen with ls -a)

CMPUT 201, Fall 2014

Launching Programs 25

Launching Programs
Type program name (+ parameters) and hit the return key <ret>
ls<ret>
emacs foo.c<ret>
Shell interprets the first word as command name and
tries to locate a function definition with this name
(see ~/.bashrc). If this fails it searches in the directories listed in variable $PATH (try echo $PATH)
To run programs in your current directory, you need
to add ./ to specify that you want this program.
MyProgram<ret> (command not found)
./MyProgram<ret> (works!)
To detach a program from the terminal to run it in
the background, type:
./program &<ret>
Or, if a program is already running, type:
<ctrl-z>bg<ret> (bg: background)
To regain control of a background-ed program, type:
fg

CMPUT 201, Fall 2014

Wildcards 26

Wildcards
* matches all strings
? matches one character
Examples:
wc *.c
count the words in all files with names that end with
.c
ls foo?bar
list all filenames that start with foo, followed by an
arbitrary character and bar

CMPUT 201, Fall 2014

Hidden Files 27

Hidden Files
Files with names starting with . are hidden, they are
not listed nor matched by wildcards
This is why ls does not show . nor ..
Useful for avoiding clutter
(e.g. many resource files .*rc in ~)
ls -a reveals them

CMPUT 201, Fall 2014

Filename Completion 28

Filename Completion
Many shells have a filename completion feature: when
hitting the <tab> key the shell tries to complete the
filename. Saves typing!
cat super<tab>
will complete the command to
cat supercalifragilisticexpialidocious
if this is the only filename starting with super

CMPUT 201, Fall 2014

Input/Output Redirection 29

Input/Output Redirection
Output of programs can be stored in a file using >:
cat file1 file2 > file3
[writes content of files file1 and file2 to file3]
Generates error message if file3 already exists
Use >! to override
cat > foo
[copy keyboard input ended by <ctrl-d> to file foo]
Input can also be redirected:
grep foo < text
[display all lines in file text that contain foo]
Or both: sort < file > file.sorted

CMPUT 201, Fall 2014

Pipes 30

Pipes
Powerful UNIX feature: output of commands can become input for subsequent commands
grep aaa file | wc -l
[count the number of lines in file that contain aaa]
sort file | uniq | wc -l
[count the number of unique lines in file]

CMPUT 201, Fall 2014

Edit Textfiles 31

Edit Textfiles
Several good editors exist: emacs, vim, ...
We recommend emacs, its powerful!
Type emacs x <ret> to edit file x in a separate
window.
To edit within the terminal window, launch emacs
with emacs -nw x <ret>
Large number of commands bound to keys. E.g.
<ctrl-x> <ctrl-s> : save buffer
<ctrl-x> <ctrl-f> : load file
<ctrl-x> <ctrl-c> : exit
<ctrl-s> : search
<alt-%> : search and replace
<ctrl-x> 2 : split window; <ctrl-x> o : switch buffer
<alt-x> command : launch external commands such as gdb

man emacs, emacs reference cards, emacs tutorial

(in help menu or on the web, see Course Resources)
Highly customizable: emacs ~/.emacs

CMPUT 201, Fall 2014

More Details
Lab 0:
UNIX commands
emacs and bash customization
editing and compiling C++ programs

Edit Textfiles 32

CMPUT 201, Fall 2014

First C Program 33

First C Program
Create file hello.c using emacs and save it
#include <stdio.h>
int main()
{
printf("hello world\n");
return 0;
}

g++ -o hello hello.c generates executable

hello which prints hello world in the terminal
window and positions the cursor in the following line
after being invoked with ./hello
Without the -o hello option, g++ creates executable file a.out. Issue man g++ explains g++
options.
g++ is the GNU C++ compiler, which expects C++
programs. It also usually works with C programs, because normally C programs are also C++ programs.
gcc only compiles C programs.