Problem Set #1¶

Assigned: Mar 30, 2021

Due: Apr 6, 2021

Background¶

Watch Course Lectures 1, 2, and 3.

In the past it has been suggested that students might experiment with a playback speed for the lectures that best suit their own listening and learning styles. (Panopto provides the ability to speed up or slow down playback speed.)

Walkthrough

Preliminaries¶

Set Up Your Development Environment¶

For a number of reasons (some of which we discussed in lecture), the platform that supports most high-performance computing today is Linux with its associated terminal-based command-line tools. Although personal computers today have a different paradigm for interaction, a Linux environment can be fairly well approximated on Windows 10 and Mac OS X.

The particular development tools that will need to be in your development environment are the following (how to obtain and install them is described below).

Visual Studio Code (latest available version)

clang (v 6.0 or later)

lldb (v 6.0 or later)

python, python-pip, python-dev, matplotlib

cimg-dev, cimg-doc

man, wget, apt-utils, net-tools, ssh, nano

bash (default version for your environment)

There will be additional packages to add for future assignments, but these will be sufficient for the next few assignments.

Windows 10¶

Note: I have done my best to make sure these instructions are correct and complete by going through them a couple of times on my own laptops. However, those already had the tools installed and so there might have been some vestiges from previous installations when I went through the reinstallation process. As a result, some things might have worked for me that might not for you. If this is the case and if things don’t go according to plan, notify the instructional staff right away (via Piazza) so that we can issue a clarification / correction. If you figure out the right steps yourself, post that to Piazza.

The basic steps are:

Enable Windows Subsystem for Linux

Install Ubuntu 20.04 from the Microsoft Store and launch it once to set username and password

Go through some magic steps to configure your WSL environment

Install additional packages

Install and configure Visual Studo Code (vscode)

Enable Windows Subsystem for Linux

You can enable WSL through a control panel rather than on the command line: Open the control panel and select “turn windows features on or off”. Check the box next to “Turn Windows Subsystem for Linux.” You will need to reboot for this to take effect.

Install Ubuntu 20.04

Once you have rebooted, go to the Microsoft Store and search for “ubuntu”. You will have choice of 3 (or more) versions. Choose 20.04 and select install. For this course, we will be accessing WSL via vscode. However, there is a setup process to go through (just once) before we use it through vscode. You can launch a bash shell by typing bash into the start menu. NB: You can also use the command “ubuntu” in the start menu.

Additional info on installing ubuntu on WSL can be found here:

https://ubuntu.com/wsl

When the bash window launches for the first time it will ask you for a username and a password. This “account” is completely within the WSL universe and has nothing to do with your account on the host (Win10) computer. For a username you can enter anything you like, but I suggest using your UW network id or the username that you use on your machine. Choose whatever password you like. Once you have gone through that process you will be presented with a prompt; you can exit from bash with the “exit” command.

Cast Two Magic Spells The linux subsystem that has been installed ``thinks’’ it is in its own world. The filesystem and directory structure appear as they would for a natively installed linux distro – in the default post-install configuration, it will not be connected to the files and folders that you see through Windows Explorer. But, since vscode (and all other native Windows applications) work with files and folders in the Windows space – we need to connect the two. To do that, we are going to create a course folder in your Documents folder and set that to be your home directory under WSL.

In the first magic spell, we need to adjust the configuration of how WSL “sees” the windows NTFS file system. To do this we will n eed to install a text editor. From a WSL window, type the following:

$ sudo apt update

Do not type the dollar sign – that is just a placeholder for the terminal prompt. The apt update command will update your the ubuntu package manager so that it knows which packages it can install and where to download them from. The apt command requires elevated privileges—typing sudo before a command will allow that subsequent command to be executed under elevated privileges. Note that you may be asked for your WSL password.

Tip

You can copy the code (or commands) from most examples by clicking the copy icon ()in the upper right of the box.

Next we need to install the “nano” text editor using the apt-get command:

$ sudo apt-get install -y nano

Once nano is installed we are ready to configure the WSL filesystem.

To cast the first Magic Spell, from a WSL window, type the following

$ sudo nano /etc/wsl.conf

(This is a privileged file, hence we need to edit it with elevated privileges.) This will open the nano editor on a new file /etc/wsl.conf. In the nano window, type the following:

[automount]
options = "metadata"

Make sure to put a new line after the second line.

Type the key combination ^O (ctrl-O) to save the file and then ^X to exit.

Now we need to restart WSL. First, close all of your WSL windows. Then, from the start menu, type “command” to open a command window. In the command window type

C:\> wsl --shutdown

(don’t type the C:\> – that’s a placeholder for whatever your prompt is.) This will shutdown WSL on your system. When we start it again, it will have the new settings we just established.

Next, in the command window, type the following:

C:\> wsl -u root

You should get back something like

root@machine:/mnt/c/Users/<win10id>#

where win10id is your Windows short user id.

Now issue the Magic Spell

root@machine:/mnt/c/Users/<win10id>#  usermod -d /mnt/c/Users/<win10id>/Documents/amath583 -m <userid>

where userid is the user id that you created above when you first started WSL. This will make a new directory in your documents folder called “amath583” and designate that as your home directory under WSL.

Next, type

root@machine:/mnt/c/Users/<win10id>#  exit

and then close the command window.

OneDrive Users If you are using OneDrive on your Windows 10 laptop, your Documents folder may be in a different place, depending on how you have OneDrive configured. If you are syncing your Documents folder to OneDrive, you may want to use

root@machine:/mnt/c/Users/<win10id>#  usermod -d '/mnt/c/Users/<win10id>/OneDrive - UW/Documents/amath583' -m <userid>

rather than the path above. Make sure to include the single quotes in this case so that the spaces in the path are properly handled.

Now, start wsl again by typing either bash or ubuntu in the start menu. You will get a slightly different terminal window depending on which you invoke but there should not be any functional difference. You may want to pin whichever window you open to the task bar to make it easier to open in the future.

Now, let’s verify your home directory was properly set. First, navigate with Windows to your Documents and folder and verify that there is now a sub-folder there named amath583.

Second, from the prompt in a WSL window

$ pwd

This requests the shell you are in (the bash shell) to print the directory you are in. If you invoked ubuntu, it should print the directory we just created above. If you invoked bash, it may print some system directory. In that case, issue the commands

$ cd
$ pwd

The cd commmand will change the directory to your home directory and the pwd will print it. At that point, it should be the home directory created before.

Next, list the files in that directory

$ ls

You should get nothing back – the directory appears to be empty. If you instead type

$ ls -a

you will see a few “dot files”. Files starting with the dot character are typically used as configuration files and are normally hidden when you list a directory — unless you specify the “-a” flag. Dot files are not special in Windows. When you navigated to this folder under Windows you should also have seen the dot files.

Example On my Windows laptop my login id is “andre” (I have no idea why). If I look in the Users subdirectory on the C: drive, there is a folder called “andre” and that is where all of my files are. When I need to login to my Windows laptop it shows “andre” as the user. (Personal computers sometimes will try to be helpful and show you your actual name instead – you don’t want to use that, you want the actual short user id). Further, the linux id I created for linux is the same as my UW id – “al75”. So I changed /home/al75 to /mnt/c/Users/andre/Documents/amath583

Important Despite the utter coolness of being able to run actual Linux programs under Windows, the two systems don’t always play nicely together. Be careful of using Windows programs (other than vscode) on the files in your working directory. Bad things can happen.

Note

If the above steps do not make sense or if something seems to have gone wrong along the way, contact the instructional staff and someone will help you get this properly configured. We will be covering these steps in the first problem set walkthrough as well as during office hours (as needed).

Install Your Development Tools As mentioned above, you need to install a few tools in your linux environment. The package manager tools in Ubuntu Linux are called apt and apt-get. To use them to install the necessary tools for this course, issue the following sequence of commands:

$ sudo apt-get update
$ sudo apt-get install apt-utils
$ sudo apt-get install clang lldb man make net-tools ssh wget

This process may run for a while but after some minutes you will be back at the bash prompt. You may be prompted (on the command line) whether or not to continue with certain installations – it is safe to answer ‘y’. You can also use the -y option in the install steps:

$ sudo apt-get install -y apt-utils
$ sudo apt-get install -y clang lldb man make net-tools ssh wget

to automatically answer ‘yes’ to proceeding.

You may also be prompted to choose your geographical area and timezone. Choose as is appropriate for your local situation.

To check quickly that the installation worked, type

$ c++ --version

It should report to you that clang version 10 is installed.

Install Visual Studio Code You can search for Visual Studio Code with Google and download the installer from a site at Microsoft. Note that Visual Studio Code is not the same (at all) as Visual Studio, so be sure to search for Visual Studio Code and not just Visual Studio.

Customize Visual Studio Code Once vscode is installed, you need to adjust a couple of settings. Right click on the gear icon in the lower left corner of vscode and select ``Command Palette’’. At the command palette prompt, type ``Terminal: Select Default Shell’’. You will get a drop down menu with three choices. Select ``WSL Bash.’’

Now click on Terminal in the vscode menu bar and select ``New Terminal’’. A window will open in the bottom half of vscode. You should see a bash prompt there. Issue the command

$ cd

To go to your home directory. (The shell defaults to a different initial directory than your home.) You can also start a terminal with the ctrl+ \ key combination (control and back-tick together). The terminal should behave just like a bash shell that you start from the start menu.

Finally, in the left hand column there are some icons, the bottom of which are four square boxes (more or less). Click on that to bring up an extensions panel. The third (or so) entry should be C++ intellisense. Click to install that. There are a huge number of other extensions that you might want to browse and explore, but the most important one is C++ intellisense. If C++ intellisense is not the near the top of the list, you can search for it in the search bar at the top of that column.

(I suggest also installing live share and live share extensions to enable collaborative editing.)

Mac OS X¶

Mac OS X has a version of Unix at it’s heart (the Berkeley Standard Distribution, or BSD) that actually predates Linux. As such, many of the tools we need are already installed (or installable via the Mac OS X ecosystem), so creating the course standard configuration is much more straightforward.

The basic steps are:

Install command-line tools for Xcode

Install visual studio code

You can actually install the command-line tools without installing all of Xcode. Since we only need the command-line tools, this is what I recommend.

Open a terminal (launch Terminal.app) – this will bring up a window with a bash shell. From that window type

$ xcode-select --install

This will bring up a pop-up window. Just select “install”.

NB: If you just select install rather than installing all of xcode you may require an extra step on Mojave (and Catalina).

For Mojave and earlier, check if there are files contained in the path /usr/include. That is, in a terminal window, run the command

$ ls /usr/include

If there are no files (or no include directory), then run the following:

$ sudo installer -pkg /Library/Developer/CommandLineTools/Packages/macOS_SDK_headers_for_macOS_10.14.pkg -target /

For Catalina and later, check that there are files in the following directory:

$ ls /Library/Developer/CommandLineTools/SDKs/MacOSX10.15.sdk/usr/include/

Remember the path where you found the include files, you’ll need it for compiling the assignment below.

All of the tools needed for the course (for now) will now be installed.

Make a Work Directory Since Mac OS X is Unix, the command line tools are completely integrated and compatible with the GUI tools – and there is only one filesystem. I suggest creating a subdirectory under your Documents folder (or wherever you like) to hold all of your course materials in one place.

When you open Terminal.app the shell will start up at your home directory. Issuing

$ pwd

will print

/Users/<yourid>

If you issue

$ ls

it will print the contents of your home folder (home directory), which may have alot of things, including your Documents folder, Pictures folder, etc.

Install Visual Studio Code The Mac OS X installer, with corresponding instructions, for vscode can be found here

https://code.visualstudio.com/download

The key combination for starting a terminal shell within vscode on Mac OS is ctrl+~.

Linux¶

If you are running your own linux, review the list of tools above for WSL and make sure you have those installed. Most important will be a recent version of clang. Visual Studio Code is also available for Linux, so make sure to install that as well.

Warm Up¶

In the installation steps above we didn’t really explain what any of the cryptic commands that you typed in actually did. In this part of the assignment we will explain a bit more about what is going on and give you some ideas about what they are and how to explore the environment on your own.

The Shell¶

The program that runs when you start bash is the “bash” shell. A shell is a program that can execute other programs as well as its own scripts. When run in interactive mode, the shell prints a prompt to the screen and waits for user input. The user enters text and when the user hits return, the shell attempts to execute the command and then again prompts the user for input.

Our development environment has documentation available for most of the commands that you will be using. These are generally comprehensive – which is good – but sometimes it can be difficult to locate exactly what you are looking for. In those cases your favorite search engine (and/or Piazza) can be your friend.

Three commands that are essential for navigating a Linux filesystem are cd, pwd, and ls, which change directory, print the working directory, and list the contents of the current directory, respectively. The ls command has a number of options that you can use with it to control what is displayed and how. The linux filesystem is basically a tree of directories (folders), each of which can contain files and other directories (sub-directories). The top-level directory is called “/”. The directories with the operating system and the linux home directories are subdirectories under “/”. When you ran ls above, you listed the contents of your “home” directory (your working directory), which in the case of Windows were the “dot” files.

To change to a different directory, use the cd (change directory) command. If you issue cd without any arguments you will change to your home directory, which we established above. If you provide an argument to cd the shell will attempt to change your working directory to the indicated path (a path is a sequence of directories, possibly ending in a file). There are two types of paths that you can supply – absolute or relative. An absolute path begins at the root, i.e., / while a relative path begins with the name of a subdirectory in the current directory. Finally, you can determine which is the current working directory for the shell by issuing the command pwd (print working directory).

For example, if your current working directory is / then when you issue the command pwd it will print /. The following two commands are equivalent (one is relative, one is absolute):

$ cd /
$ cd tmp

is equivalent to

$ cd /tmp

Note that ls can also take arguments, again an absolute or a relative path:

$ ls tmp
$ ls /tmp

There are two special subdirectories in every directory: . (dot) and .. (dotdot). Dot is the name of the current directory. If you issue ls . you will get the contents of the current directory. Dotdot is the name of the parent directory (recall that the filesystem is a tree – each directory has a unique parent, up to “/”). Try out . and .. with the “ls” and “cd” commands.

The Shell from vscode¶

Regardless of whether you are using Windows, Mac OS, or Linux, it can be quite helpful to access a shell from vscode (per the instructions above). A typical workflow is edit-compile-run-debug. Using a shell from within vscode allows you to issue the commands to compile and run from the same environment as you are editing without having to switch windows. (Like many IDEs, vscode also allows you to compile, run, and debug from within the editor.)

Help and Documentation¶

Your installation contains documentation for the packages that were installed with it. The typical Linux way of viewing the documentation is the man (manual) command. To view documentation of a particular command, invoke man with the name of the command as an argument. For example

$ man ls

will display the documentation for the ls command. Many commands that you issue at the command prompt are executable programs stored in the filesystem (usually in /bin, /usr/bin, or /usr/local/bin). However, some commands are built-in shell commands – cd for example is a built-in command. To find out information about built-in shell commands, use “help” (which is also built-in). Note that there is a difference between “man” and “help”.

Explore¶

Now, take a few minutes to move around the directory structure in your environment. Some directories to look at might be /usr/bin or /usr/include. Two more commands that you might find handy are cat and more.

Creating and Editing Files¶

For the rest of this course you will be creating and editing source code files – each assignment should go in a separate folder (subdirectory). When using visual studio code you can work with a single folder at a time – it will only show you the contents of the currently open folder. Use the File->Open… menu option and select the specific folder you want to work with. You can open any folder you like and the editor will show you all of the folders and files underneath it. I recommend just opening the folder associated with the current problem set. When you close and reopen vscode it will keep a record of which folder you had open and bring you back to that. When you want to work on the next assignment, close the current folder and open the next.

Hello World!¶

In your working directory, create a sub-directory named ps1. Open that folder with vscode and create a file called hello.cpp with the following contents:

#include <iostream>

int main() {

  std::cout << "Hello World" << std::endl;

  return 0;
}

Save the file and use cat or more to verify its contents. (What does the less command do?)

Now, execute the following commands:

$ c++ hello.cpp
$ ./a.out

Exercises¶

The C++ standard library contains a number of basic data structures – lists, arrays, hash maps, etc. The data structure that will be our workhorse (though we will be wrapping it up in other data structures) is std::vector.

The std::vector is a generic container – meaning it can hold data of any type. However, as we mentioned in lecture, C++ is a compiled and strongly typed language. The generic container can hold any type – but we have to specify the type to the compiler. To create a vector of integers with ten elements, we would use the statement

std::vector<int> x(10);

The type that the vector is holding is specified in the angle brackets; the size of the vector we are creating has 10 elements.

Elements of a std::vector are accessed with square brackets:

int a = x[3];

assigns the value of the element at index 3 to the variable a.

Important

Note that I did not call ``x[3]`` the third element! That’s because it is actually the fourth element. This might seem strange at first. Many other programming languages, especially those intended for mathematical operations use “one-based” indexing, meaning the first element is at index location 1. C and its derivative languages, however, use “zero-based” indexing, meaning the first element is at index location 0. Again, this might seem strange and non-intuitive. However, what an index in C++ is specifying is not the ordinality of the element, but rather the distance the element is from the beginning of the vector (or array). Thus the first element, which is at the beginning, is distance zero from the beginning and so is indexed as x[0].

In C++, zero is the indexing base and the base of the indexing is zero.

We can loop through a vector from beginning to end using the square bracket notation:

for (int i = 0; i < 10; ++i) {
    x[i] = 2 * i;
}

This loop specifies to assign values 0 to 9 (nine) to i and assign 2*i to each x[i]. Another consequence of zero-based indexing is that the final element in an array is location size - 1.

Now, if you aren’t familiar with it, it might seem that zero-based indexing is going to require you to always be adding and subtracting 1 from index values. In fact, zero-based indexing is the natural indexing for computer programming and you will rarely, if ever, see code that is accessing arrays having to add and subtract 1s from index values. On the other hand, you have probably experienced having to do this when programming with Matlab (for instance).

A very common error in C++ programming is to exceed the bounds of an array when reading or writing date from or to it. Unlike interpreted languages, these bounds are not checked when the program is running. However, the above for loop is an extremely common pattern. We begin at the beginning of the vector and loop to the end. The index variable i starts at 0 and the loop continues as long as i is less than 10 (the number of elements we want to loop over). The ++i statement indicates that the value of i should be incremented by one at the end of each loop.

Now, with all of those preliminaries out of the way…

The program I want you to write for this assignment is to plot the value of $\sin(x)$ with 1024 points for x from 0 to $6\pi$, inclusive. Important: I want you to include $\sin(6\pi)$ as the final value, not “$\sin$ of almost $6\pi$”.

(Hint: be thoughtful about how you index.)

A basic skeleton of the program to do this plotting is

#include <iostream>
#include <vector>

#define cimg_display 0
#include "CImg.h"
using namespace cimg_library;

const double pi = 3.141592653589793238462643383279;

// Plotting function
void make_plot(const std::vector<double>& x) {
  CImg<unsigned char> graph(500, 400, 1, 3, 0);
  const unsigned char red[] = {255, 0, 0}, green[] = {0, 255, 0}, blue[] = {0, 0, 255};
  CImg<double>        values(1, x.size(), 1, 1, 0);
  for (int i1 = 0; i1 < x.size(); ++i1) {
    values(0, i1) = x[i1];
  }
  graph.fill(255).draw_graph(values, blue, 1, 2).save_bmp("plot.bmp");
}


int main() {
  const size_t N = 1024;

  std::vector<double> y(N);

  // Compute sin(6*x) on interval [0, 1] -- inclusive of 1
  for (size_t i = 0; i < N; ++i) {
    /* Write Me */
  }

  // Call make_plot( /* Write Me */ );

  if (y[0] == 0 && y[1022] != 0 && std::abs(y[1023]) < 2.e-15) {
    std::cout << "Pass " << y[1023] << std::endl;
    return 0;    // return success value
  } else {
    std::cout << "Fail " << y[1023] << std::endl;
    return 1;    // return other than success value
  }

  return 0;      // default return success value
}

Download and copy it to your ps1 work directory (with the filename sin6pi.cpp).

You will also need the file CImg.h which you can download here:

Download

This file is a C++ header file to do plotting and image manipulation (we will be using it several times in this course).

There are two places in the file sin6pi.cpp that say “WRITE ME”. The first is within a loop that increments a value of i (which value you can use within the loop) from 0 to its limit (what is the limit?). Replace the “Write Me” with a statement that fills in the vector y with the values of $\sin(x)$ such that the last value computed will be exactly $\sin(6\pi)$ (exactly, that is, within floating point precision). You will need to scale the value of i by some constant value to get the equally-spaced points and the correct final value.

In the second “Write Me” you should call the function make_plot with the data you want to plot (the vector y). make_plot is a function that will plot the values it is passed and save those values to an image file “plot.bmp”.

Each “WRITE ME” should only require a single line of C++ code.

To compile your program, use the following command. You can just cut and paste this into your shell window; we will be looking at how to automate this process during lectures 3 and 4.

$ c++ -std=c++11 sin6pi.cpp

You can then execute your program using this command

$ ./a.out

This will create a file plot.bmp in your work directory. You can view it with the image viewing program of your choice. It should look something like this:

Written Exercises¶

Create a text file called ex1.txt in your ps1 folder. In that file, copy the following questions. Start your answers on a new line after each question and leave a blank line between the end of your answer and the next question.

What is the host name of the computer as reported by your linux environment? (You will need to find the right Linux command to execute for this. I suggest searching the web.)
How would you specify the name of an output file when you use the compiler if you wanted the executable to have a name other than a.out?
What happens if you type

$ a.out

instead of

$ ./a.out

to run your program? What is the difference (operationally) between the two statements?

What does clang print when you run

$ c++ --version

(AL: note two dashes.)

In the example program, the i and N variables are said to be size_t. What is a size_t?

Turning in The Exercises¶

To turn in your assignment, you will create a compressed “tarball” to upload to Canvas. To create the tarball, use the command

$ tar -czf ps1.tgz sin6pi.cpp ex1.txt

This calls the “tar” command with flags to indicate what type of compression to use, specifying the creation of a compressed tar (tape archive) file “ps1.tgz” that contains your “sin6pi.cpp” and “ex1.txt” files. To turn in your assignment, upload “ps1.tgz” to Canvas.