Problem set 0: Warmup

The goal of this ungraded problem set is to introduce you to course infrastructure, and to warm up your skills in the programming language we use, C++, and the kinds of programs we’ll write. The programming is not intended to be difficult, but don’t settle for sloppy results. The course aims to teach you robust, secure, and understandable coding, as well as fast and correct coding.

Solutions are provided, and you should look at them. Try to work through the problems yourself first, but don’t worry if you get stuck and peek at the solution. Understanding the solution is already a great step. The problems get progressively harder. If you get through all of the problems you are definitely ready for the course; if you get through part 4, you are very likely ready for the course.

Overview

This course teaches you the fundamentals of computer systems and systems programming, using C++ as its primary implementation language. C++ is a popular language for low-level systems coding, and unlike C, its predecessor, it comes with an extensive data structure library and high-level abstraction facilities.

Though the course uses C++, it is about systems programming. We don’t dive deep into the language, we do not use its object-oriented features, and we attempt to avoid its most difficult byways.

Some familiarity with C++’s data structures and libraries will be useful. You can get this from free resources on the web, although a textbook and reference is better. Some web resources, such as reference pages, contain an almost overwhelming amount of information. Don’t despair! A good way to use reference pages is to scan down for example code, which can be more concise and clear than the English-language reference material.

It will also be useful to have some familiarity with Unix shell syntax. You should know what standard input and standard output mean, and how to perform simple redirections. Specifically:

• A simple shell command like prog1 runs prog1 in the current context: its standard input and standard output are inherited from the shell, which usually means that its input reads from the keyboard and its output is printed to the terminal.

• Typing prog1 < IN redirects prog1’s standard input to come from a file. In this instance, prog1 will observe the contents of the IN file when reading from its standard input.

• Similarly, prog1 > OUT redirects prog1’s standard output to go to a file. If the file OUT already exists, its contents are overwritten.

• prog1 < IN > OUT performs both redirections.

• prog1 | prog2 (pronounced “prog1 pipe to prog2”) redirects prog2’s standard input to read from prog1’s standard output. Thus, all the bytes written by prog1 are read by prog2 in order.

Part 0. Course setup and Git

Objective: Prepare a CS 61 environment and get familiar with the terminal.

1. Follow the GitHub setup instructions.

2. Follow the Docker setup instructions.

3. Create a file in your cs61-psets/pset0 directory called hello.txt that contains one line, the word “awesome”. You can use your favorite text editor, or use an editor included in the CS 61 Docker (Nano, Emacs, or vi).

Check your work by entering the Docker environment and running the command make test-hello. This should print something like this:

cs61-user@04feeb3aadd2:~/cs61-psets/pset0$make test-hello ✅ Cool! hello.txt exists and has the right contents.  4. The git status command will show you that hello.txt is not yet part of your official repository: cs61-user@9ba17834d87b:~/cs61-psets/pset0$ git status
On branch main
Your branch is up to date with 'origin/main'.

Untracked files:
(use "git add <file>..." to include in what will be committed)
hello.txt

no changes added to commit (use "git add" and/or "git commit -a")


Add the hello.txt file to your repository and push it to GitHub (that is, upload it to the shared GitHub repository). Verify that it has arrived on GitHub by looking at the web page for your repository (its link will resemble “https://github.com/cs61/cs61-f21-psets-YOURUSERNAME”).

Part 1. Invoke the compiler

Objective: Use the C++ compiler and make to build a program.

Create a C++ source file exiter.cc containing the following code.

#include <cstdlib>

int main() {
exit(0);
}


QUESTION. What would this program do?

Then compile the program and run it. Do this two ways.

1. First, call the compiler directly and run the program on the terminal. Here’s how:

$c++ -std=gnu++2a -Wall -g -O3 exiter.cc -o exiter$ ./exiter


The first command invokes the compiler, asking it to compile your source file (exiter.cc) into an executable (a program that can be run, here called exiter). The flags supplied to the compiler are:

• -std=gnu++2a selects a recent version of the C++ standard.
• -Wall asks the compiler to warn you about possible mistakes in your code. You should always make sure that your code compiles without warnings.
• -g adds debugging information to the compiler’s output.
• -O3 asks the compiler to optimize its code. This makes the code run faster, but can make the result harder to debug and can slow down compilation.

The compiler exits silently if can complete its work without encountering an error or warning, so be excited if there’s no output! If there is an error, you’ll need to fix that error and invoke the compiler again.

The second command (./exiter) invokes the compiled executable, which, as advertised, does nothing.

2. Second, use our provided makefile to build the program. Here’s how:

$rm -f exiter$ make exiter
COMPILE exiter.cc
$make V=1 exiter g++ -std=gnu++2a -Wall -Wextra -Wshadow -g -fsanitize=undefined -MD -MF .deps/exiter.d -MP -O3 -o exiter.o -c exiter.cc g++ -std=gnu++2a -Wall -Wextra -Wshadow -g -fsanitize=undefined -O3 exiter.o -o exiter  As you can see, the makefile supplies more arguments than the simple compiler invocation! For fun, why not try to figure out what those arguments do? (-Wextra and -Wshadow especially.) Unlike the direct invocation in step 1, our makefile runs the compiler twice to produce an executable. The first invocation, COMPILE exiter.cc, produces an intermediate file called an object file, exiter.o; the second invocation, LINK exiter, uses the object file to produce an executable. This is unnecessary for a single-file program like exiter.cc, but useful for programs generated from multiple source files. Part 2. Say hello Objective: Recall C++’s output facility. Create a program hello that prints hello, kitty to the terminal (the standard output) and then exits. That is, write a C++ source file hello.cc, then compile it into a hello executable that behaves like this: $ make hello
$./hello hello, kitty$


It’s important that the “hello” message appears on its own line—this output is wrong:

cs61-user@caddb9e3ab14:~/cs61-psets/pset0$./hello hello, kittycs61-user@caddb9e3ab14:~/cs61-psets/pset0$


Hints:

Part 3. Count bytes

Objective: Recall more of C++’s input/output facilities.

Now let’s start really programming. Write a program bc61 that counts the number of bytes in its standard input and prints the result to standard output. Examples:

$make bc61$ echo foo | ./bc61
4
$./bc61 < /dev/null 0$ yes | head -c 1000 | ./bc61
1000
$./hello | ./bc61 13  Use the fgetc and fprintf library functions for C-style I/O. Make sure you test your bc61 program with different inputs. Because your bc61 program waits for input, running bc61 on its own will appear to hang the terminal. This can be confusing! $ ./bc61
[...... nothing happens here forever!!! .......]


When this happens, press Control-C to kill bc61 without waiting for it to complete its work. Alternately, type stuff, press Return to start a new line, and then press Control-D to pass bc61 some input. (Pressing Control-D at the beginning of a line informs the terminal that bc61’s input has ended; if bc61 attempts to read more characters, it will receive an end-of-file indication. Pressing Control-D anywhere but at the beginning of a blank line will simply release whatever you've typed on the current line so that bc61 can read it.)

Part 4. Count words and lines (harder)

Objective: Reason through a nontrivial specification for an input/output program.

Write a program wc61 that counts words and lines as well as bytes. A word is a sequence of one or more non-whitespace characters, and a line is zero or more bytes terminated by the newline character \n. The printout should give lines, words, and bytes in that order. Examples:

$echo foo | ./wc61 1 1 4$ ./wc61 < /dev/null
0       0       0
$yes | head -c 1000 | ./wc61 500 500 1000$ yes Hello | head -c 1000 | ./wc61
166     167    1000
$./hello | ./wc61 1 2 13$ echo "  hi  " | ./wc61
1       1       7


Use the isspace library function, which is declared in the <cctype> header, to detect whitespace.

Though this seems like a simple specification, getting simple things right on all input cases is always hard, and it may take you a while to get the answer right! Make sure you create your own test cases; the echo " WORDS " | ./wc61 pattern is quite useful.

Part 5. Implement a library function (hard)

Objective: Understand a library function’s specification, reason about special cases, and practice pointer notation.

Implement a function mystrstr that has exactly the same behavior as strstr.

This driver program strstr61.cc may be useful for testing:

#include <cstring>
#include <cassert>
#include <cstdio>

char* mystrstr(const char* s1, const char* s2) {
return nullptr;
}

int main(int argc, char* argv[]) {
assert(argc == 3);
printf("strstr(\"%s\", \"%s\") = %p\n",
argv[1], argv[2], strstr(argv[1], argv[2]));
printf("mystrstr(\"%s\", \"%s\") = %p\n",
argv[1], argv[2], mystrstr(argv[1], argv[2]));
assert(strstr(argv[1], argv[2]) == mystrstr(argv[1], argv[2]));
}


Examples:

$make strstr61$ ./strstr61 "hello, world" "world"
strstr("hello, world", "world") = 0x7ffee2c97bca
mystrstr("hello, world", "world") = 0x7ffee2c97bca
$./strstr61 "nfsnafndkanfkan" "" strstr("nfsnafndkanfkan", "") = 0x7ffee579bbcb mystrstr("nfsnafndkanfkan", "") = 0x7ffee579bbcb  No matter what arguments you supply, the strstr and mystrstr lines should print the same result. 1. First, implement mystrstr using array notation (brackets []). Make sure you read the specification for strstr carefully so you catch all special cases; do not call any library functions. 2. Second, implement mystrstr exclusively using pointer operations: do not use brackets at any point. Part 6. Sort arguments (hard) Objective: Handle C strings, program arguments, and more complex library functions. Implement algorithms described in pseudocode (such as insertion sort). Write a program sortargs61 that prints out its command-line arguments, one per line, in dictionary order (also called lexicographic order). Examples: $ ./sortargs61 a b c
a
b
c
$./sortargs61 e d c b a a b c d e$ ./sortargs61 A a A a A a
A
A
A
a
a
a
$./sortargs61$ ./sortargs61 hello, world, this is a program
a
hello,
is
program
this
world,


A C or C++ program’s command-line arguments are passed in an array called argv that is passed to main. Up til now, your main functions have taken no arguments; sortargs61’s main function should take two arguments, as follows:

int main(int argc, char* argv[])


argc is the number of arguments, and argv[I] is the Ith argument represented as a C string. Note that the argv[0] argument is always the name of the program and should generally not be considered a true argument. (Tutorial)

1. First, use a minimal subset of the C library: use strcmp and an O(n^2) algorithm such as insertion sort or selection sort. (Recall that strcmp(x, y) returns an integer that is less than zero when x < y in lexicographic order, equal to zero when x and y have the same characters in the same order, and greater than zero when x > y in lexicographic order.)

2. (More advanced) Now do it using C++ library features: use std::string (the C++ library type for automatically-managed strings), std::vector (the C++ library type for automatically-managed, dynamically-sized arrays), std::sort (the C++ library’s sort algorithm), and C++-style basic input/output. (Those links are to portions of a C++ tutorial, so do follow them if you’re new to C++.)

Going further

Here are some other things you should be able to do in C++:

• Dynamically allocate and free an object with new and delete.
• Dynamically allocate and free an array of objects with new[] and delete[].
• Define a structure type.
• Use the C library’s string functions correctly, including memory management.
• Write a function that takes three arguments, a size and two void* pointers to objects, and exchanges the values of the two objects (each of which have the given size).

Recommended reference: C for Java Programmers

This pset was created for CS61.