EECE7205 Homework 1 Solution

Steps on how to access to COE system from Windows
Step 1
First, you will need to get your COE account. Go to this website: https://www2.coe.neu.edu/account/register.cgi
Fill out the COE/ECE account application form and submit it. Usually in a day or two, your account will be created. Note that you will NOT receive an email when your account has been created. READ all screens carefully and take note of the information you are given.
Step 2
We will be using SSH to log into the COE system. There are several SSH clients like PuTTY or Bitvise SSH client to help you with the login process. I will introduce how to use Bitvise client here. First, download Bitvise SSH from the following, https://www.bitvise.com/download-area
The SSH server has been set up. We only need to download the Bitvise SSH client.
Step 3
The installation of Bitvise SSH client is very easy. After the installation, you will see the client like this

Set the host to gateway.coe.neu.edu and the port to 22 in Server. In authentication, fill out the user name and password of your COE account. That would be enough to log into COE system. Click the Login button and wait a few seconds.
Step 4
If your COE account has been created and you provide the right username and password, you will log into the COE Linux system. There will be two new windows. One is the command line bash shell and the other is the SFTP window for file transfers.
• Terminal console
The terminal console is like the following figure. You can execute your commands. This is a Linux bash shell. You can type ‘pwd’ to check the path of your current location. Use ‘cd’ command to go to other directories. Use ‘ls’ to list all the directories and files under the current directory. New directories and files can be created and modified by you under your home directory through command lines.



• SFTP window
The other window is a SFTP window like this:

The left column is a list of the files on your PC. The right column is a list of files on your COE system. You can copy or move files between the two system. The SFTP window would help you manage your files.
Remember to right click your mouse and choose refresh to get the newest list of files if you find something strange.
The original Bitvise SSH client would be like this,

If you happen to close one of the windows, don’t worry, you can get new terminal console or SFTP window by clicking the corresponding icon in the left column of the client.











Steps on how to access to COE system for MAC
For Mac users, you already have a command-line terminal, and you can do these all by commands.
Step 1
First, you will need to get your COE account. Go to this website: https://www2.coe.neu.edu/account/register.cgi
Fill out the COE/ECE account application form and submit it. Usually in a day or two, your account will be created. Note that you will NOT receive an email when your account has been created. READ all screens carefully and take note of the information you are given.

Step 2
Open a bash terminal and enter “ssh USERNAME@gateway.coe.neu.edu”, where USERNAME is your COE account name. You will be prompted for password. So, remember to apply for your COE account first as in step 1. After authentication you will get onto a Solaris server.
For example, I can log onto the COE system on my MAC like this:
ssh siyuew@gateway.coe.neu.edu
Use ‘pwd’ to check the current directory. Use ‘cd’ command to go to other directories. Use ‘ls’ to list all the directories and files under the current directory.

Step 3
For file transfer: You can do this with the scp command, which uses the ssh protocol to copy files across machines. It extends the syntax of cp to allow references to other systems:
scp username1@hostname1:/path/to/file username2@hostname2:/path/to/other/file
Copy something from this machine to some other machine:
scp /path/to/local/file username@hostname:/path/to/remote/file
Copy something from another machine to this machine:
scp username@hostname:/path/to/remote/file /path/to/local/file

For example, if you want to copy something from your MAC to the COE system, open another bash terminal on you MAC and go to the local directory under which you have put your files. On my MAC, I type “cd Users/wangsiyue/Desktop/SimplePro” (the directories have been made before by mkdir).
Now I transfer the file there by a command “scp” (means secure copy) like this:
$ scp Proj_simpleScalar.tar.gz siyuew@gateway.coe.neu.edu:~/.
You will be asked to enter your COE password. The file Proj_simpleScalar.tar.gz will be shown in the directory “/Users/Grad/siyuew”. The format for this command line is “scp file1 user@host:file2”, where file1 is on your local computer, and you are going to copy it to the server under your account (user@host) as file2, the file2 should contain all the directory information. The “.” in the sample command means using the same name as your source file name (Proj_simpleScalar.tar.gz). “~” means the default directory. On your computer, “~” means your “/Users/YOUR_USER_NAME” (“/Users/wangsiyue” for me), on the COE system, “~” means “/Users/Grad/siyuew” for me.
If you want to copy something from the COE system to your MAC, you can follow this command:
$ scp siyuew@gateway.coe.neu.edu:~/hw1/homework1.pdf /Users/wangsiyue/Desktop/.
It will copy the file homework1.pdf in the directory “/Users/Grad/siyuew/hw1” on the COE system to the location “/Users/wangsiyue/Desktop” with the same file name. Then you will find homework1.pdf file on your desktop.
My default directory might be different with yours, remember to check your path with ‘pwd’ command.



















2. Get Familiar with C++ Environment
For this course, we will assume a basic understanding of the following UNIX command-line tools:

• ls – List the content of the current directory.
• mkdir – Create a directory.
• pwd – Return the current path.
• cd – Change current working directory.
• nano – Basic word editor for plain-text files.
• vi – Alternative word editor, more powerful than nano, but harder to use for the first time.
• cp, mv, rm – Copy, move, or remove files/directories.

If you are not familiar with these commands, you can find a simple UNIX tutorial here:
https://people.ischool.berkeley.edu/~kevin/unix-tutorial/toc.html














3. Get Started with your first C++ Program
Let us start writing a simple hello world program in C++. The source code will be created in file hello.cc in directory ~/fce/hw1 (character “~” in directories is used to refer to the home folder).
Type the following commands:

Type the following code:



The header file <iostream> provides a standard name space std with a pre-defined object cout. This object can be used with operator “<<” followed by a string in order to dump text into the standard output. We will present all details in class needed to thoroughly understand this code. For now, we just need to know that this is the pattern used to write text into the screen. The following command can be used to compile the code:



This command takes file hello.cc as an input and produces an executable file named hello. The program can be executed with the following command:



4. A Sorting Example
Once our first program is running correctly, let us implement the insertion sort algorithm presented in class. This program is composed of a function running the algorithm itself, a function to print the unsorted and sorted versions of the vector, and a main program calling these functions.


Homework 1 (5pt.)
Submission instruction:
Submit one single pdf file for this homework including both coding problems and analysis problems.
For coding problems, copy and paste your codes. Report your results.
For analysis problems, either type or hand-write and scan.
Question 1 (2 pt.) Coding: write programs of insertion sort, and mergesort. Find the input size n, that mergesort starts to beat insertion sort in terms of the worst-case running time. You can use clock_t function (or other time function for higher precision) to obtain running time. You need to set your input such that it results in the worst-case running time. Report running time of each algorithm for each input size n.

Question 2 (1pt.) You are given with an array {10, 5, 7, 9, 8, 3}. Show the arrangement of the array for each iteration during insertion sort. You are given with the same array. Show the arrangement of the array for each iteration of the Partition subroutine of quicksort and the result of Partition subroutine.

Question 3 (1pt.) True or False
𝑛+3∈Ω(𝑛)
𝑛+3∈O(𝑛!)
𝑛+3∈Θ(𝑛!)
2"#$ ∈O(𝑛+1)
2"#$ ∈Θ(2")

Question 4 (1pt.) Using the master method, determine T(n) for the following recurrances.
𝑛
𝑇(𝑛)=8𝑇/ 0+𝑛 2
𝑛 !
𝑇(𝑛)=8𝑇/ 0+𝑛 2
𝑛 %
𝑇(𝑛)=8𝑇/ 0+𝑛 2
𝑛 &
𝑇(𝑛)=8𝑇/ 0+𝑛 2

Question 5 (extra 1pt.) Draw recursion tree for 𝑇(𝑛)=8𝑇/"0+𝑛. And prove the obtained T(n) by
! substitution method.