Problem set 0: Warmup

The goal of this ungraded problem set is 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, but work through the problems yourself first.

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 are almost overwhelmingly detailed, but don’t despair! It often works to scroll through reference pages 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:

Part 1. Byte counting

Write a program wc61 that counts the number of bytes in its standard input and prints the result to standard output. Examples:

$ echo foo | ./wc61
       4
$ ./wc61 < /dev/null
       0
$ yes | head -c 1000 | ./wc61
    1000

Use the fgetc and fprintf library functions for C-style I/O.

Part 2. Word and line counting

Change wc61 to count 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

Use the isspace library function to detect whitespace.

Part 3. File concatenation

Write a program cat61 that behaves like simple Unix cat: it should read each file named on the command line in order, printing their contents to the standard output.

When run with no arguments, cat61 should read from standard input; and an argument that equals a single dash - means “read from standard input here.” Many cat implementations support a large variety of flag arguments, but yours doesn’t need to.

Use the fopen, fclose, fread, and fwrite library functions for C-style I/O. Read and write more than one character at a time.

It’s important when programming to handle errors, such as incorrect file names and errors when reading or writing. We don’t specify exactly what you must do, but we expect that your program will not crash on any input. Document the error handling you do so that others who read or use your code know about the decisions you made. (You may want to run experiments to see how the Unix cat utility handles errors; its choices are probably good to emulate.)

Part 4. Argument sorting

Write a program sortargs61 that prints out its command-line arguments, one per line, in sorted 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,

First, do it using a minimal subset of the C library: use strcmp and an \(O(n^2)\) algorithm.

Then, 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++.)

Part 5. strstr

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

This driver program may be useful for testing:

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

char* mystrstr(const char* s1, const char* s2) {
    // Your code here
    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:

$ ./strstr61 "hello, world" "world"
strstr("hello, world", "world") = 0x7ffee2c97bca
mystrstr("hello, world", "world") = 0x7ffee2c97bca
$ ./strstr61 "nfsnafndkanfkan" ""
strstr("nfsnafndkanfkan", "") = 0x7ffee579bbcb
mystrstr("nfsnafndkanfkan", "") = 0x7ffee579bbcb

(The hexadecimal numbers will differ from run to run; we’ll find out why in Unit 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.

Second, implement mystrstr exclusively using pointer operations: do not use brackets at any point. (The purpose of this exercise is to re-familiarize you with C/C++ pointer notation.)

Going further

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

Recommended reference: C for Java Programmers


This pset was created for CS61.