Problem Set #1¶

Assigned: Apr 2, 2020

Due: Apr 9, 2020

Background¶

Watch Course Lectures 1 and 2.

As mentioned in answer to a question on Piazza, you might experiment with a playback speed for the lectures that best suits your own listening and learning style.

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

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 18.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)

A general overview of how to get started with Visual Studio Code and the Windows Subsystem for Linux (WSL) can be found here:

https://daverupert.com/2018/04/developing-on-windows-with-wsl-and-visual-studio-code/

(You should not follow the specific steps found there however.)

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 18.04

Once you have rebooted, go to the Microsoft Store and search for “ubuntu”. You will have choice of 3 (or more) versions. Choose 18.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.

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 a Magic Spell 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 make this connection, first open a bash window (from the start menu or vscode) and type

$ pwd

(don’t type the $ – that’s a placeholder for whatever your prompt is.) You should get back something like

/mnt/c/<userid>

where userid is the user you created when you ran bash or ubuntu for the first time. Next, list the files in that directory

$ ls

You should get nothing back – the directory is empty. This is a consequence of linux having its own filesystem and directory structure. Now, we could just work within that, but the location of that directory within Windows is in a very convoluted place that would be hard to find from vscode.

What we are going to do instead is set up your home directory in linux to be a specific folder in your existing Documents folder.

Create Your Course Working Directory

Open up your Documents folder in Windows and create a new folder. I suggest using the name “amath583” but you can call it whatever you like (just remember that I will be referring to it as “amath583”).

Here is the Spell Open a bash window from the start menu (bash or ubuntu). Issue the following command:

$ sudo login -f root

You will be prompted for your password. (The sudo command elevates your privileges in linux to that of the “superuser”, which you need in this case to force a login to root, which is the account name of the superuser.)

After a few seconds, you will see a prompt, but this time the final character will be the hash mark # – which is the special prompt for the superuser.

The Deep Magic Spell At the superuser prompt, enter the following:

$ ( sleep 5 ; usermod -dm /mnt/c/Users/<your-windows-id>/Documents/amath583 <your-linux-id> )

Then, quickly (in less than 5 seconds), exit from the super user prompt, which will take you back to the first bash shell. Exit immediately from that shell. The bash shell window will close. If you don’t think you can exit the two environments in 5 seconds, change the 5 to 10 in the sleep command above. Substitute your Windows login and your linux user id the in the appropriate places above. NB: Beware of line wrap when viewing this command in a browser – the command all goes on a single line.

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 used this command

$ ( sleep 5 ; usermod -dm /mnt/c/Users/andre/Documents/amath583 al75 )

Finally, count to 5 and then open up a bash window again. Issue the command

$ cd

This will take you to your home directory. Next issue the command

$ pwd

This will print out you current working directory. In my case it would print:

/mnt/c/Users/al75/Documents/amath583

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

Finally finally, try the command

$ ls -lat

It should show you a few files with names like .bashrc and .profile.

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
$ sudo apt-get install python python-dev python-matplotlib
$ sudo apt-get install python3 python3-dev python3-matplotlib

This process will 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

to automatically answer ‘yes’ to proceeding.

To check quickly that the installation worked, type

$ c++ --version

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

Install Visual Studio Code You can search for Visual Studio Code in the Microsoft Store. It will return a link that will take you to the site at Microsoft where you can download the installer. Note that Visual Studio Code is not the same (at all) as Visual Studio, so be sure to choose Visual Studio Code and not just Visual Studio.

Customize Visual Studio Code Once vscode is installed, you need to adjust a couple of settings. To open the settings panel to edit the settings, there is the usual gear icon in the lower left of the vscode window that will pop up a window from which you can select “settings”. In the settings pane, enter

terminal.integrated.shell.windows

in the search bar. It will bring up a form with an entry area to set the value for this variable. You should set it to

C:\\WINDOWS\\System32\\bash.exe

Restart vscode so the changes can take effect. Once restarted, you can start a terminal by selecting from the menubar or 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.

When vscode opens again, it will bring up a startup page. In the left hand column there are some icons, the bottom of which is two nested squares (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.

(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, 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+~.

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

Tip

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

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 $\cos(x)$ for x from 0 to $4\pi$, inclusive. Important: I want you to include $4\pi$ as the final value, not “almost $4\pi$”.

(Hint: be thoughtful about how you index.)

A basic skeleton of the program to do this plotting is

#include <cmath>
#include <iostream>
#define WITHOUT_NUMPY
#include "matplotlibcpp.h"

namespace plt = matplotlibcpp;

int main () {
  double pi = std::acos(-1.0);  // C++ does not mandate a value for pi

  plt::figure_size(1280, 960);  // Initialize a 1280 X 960 figure

  std::vector<double> x(1024);  // Create two vectors
  std::vector<double> y(1024);

  // Fill in x with values from 0 to 4*pi (equally spaced)
  for (int i = 0; i < 1024; ++i) {
    // WRITE ME
  }

  // Fill in y with cos of x
  for (int i = 0; i < 1024; ++i) {
    // WRITE ME
  }

  // Check that the last value of x has the right value
  if (std::abs(x[1023] - 4.0*pi) < 1.0e-12) {
    std::cout << "Pass" << std::endl;
  } else {
    std::cout << "Fail" << " " << std::abs(x[1023] - 4.0*pi) << std::endl;
  }

  // Make the plot and save it to a file
  plt::plot(x,y);
  plt::save("cosx.png");

  return 0;
}

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

There are two places in the file that say “WRITE ME”. Replace those lines each with statements that compute an equally spaced set of x values from 0 to (and including) $4 \pi$ and a corresponding set of y values that are the cos of the x values.

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

You will also need this file:

which is a C++ wrapper around the Python matplotlib library.

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.

For WSL, Mojave and earlier, run:

$ c++ -std=c++11 -I/usr/include/python2.7 cos4pi.cpp -lpython2.7

For macOS Catalina, run:

$ c++ -std=c++11 -I/Library/Developer/CommandLineTools/SDKs/MacOSX10.15.sdk/usr/include/python2.7/ cos4pi.cpp -lpython2.7

You can execute your program using this command

$ ./a.out

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

Troubleshooting¶

macOS: If you are getting a runtime error Error loading module matplotlib or No module named _multiarray_umath, check that your system Python 2.7 has NumPy and Matplotlib installed:

$ /usr/local/bin/pip install -U numpy matplotlib

macOS: If you are getting a runtime error Error loading module matplotlib.pyplot, create a file ~/.matplotlib/matplotlibrc with just one line: “backend: TkAgg”. The following command does this for you:

$ echo "backend: TkAgg" >> ~/.matplotlib/matplotlibrc

Windows WSL: if you’re getting a runtime error regadring the DISPLAY variable, you need to install Xming for Windows 10. After the installation, log in to the WSL and add the following line to the beginning of your ~/.bashrc file:

export DISPLAY=:0;

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.)

(AMATH 583 only). What do the -I and -l flags do in the command we used to build a.out?

(AL: In case the fonts make the two flags look the same, one is lower-case “L” (ell) and one is upper-case “I” (eye).)

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 cos4pi.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 “cos4pi.cpp” and “ex1.txt” files. To turn in your assignment, upload “ps1.tgz” to Canvas.