Hmk #3 Solution

ECE 4122 students need to do Problems 1 & 2. Each problem is worth 50 points.




ECE 6122 students need to do Problems 1, 2, & 3. Problems 1&2 are worth 33 points, and problem 3 is worth 34 points.




Note:




You can write, debug and test your code locally on your personal computer. However, the code you submit must compile and run correctly on the PACE-ICE server.




Submitting the Assignment:




Follow the steps below to create the file to upload to canvas.




First, determine your buzzid (your gatech.edu email without the “@gatech.edu”). In the following, I refer to it as buzzid.



Assume that your current working directory is the source directory for Hmk#3 (it does not matter what you call that directory).



Create a subdirectory named buzzid in the current working directory by executing the following command in the shell:



$ mkdir buzzid




Create a text file named manifest with the following lines in it buzzid /<FirstName_LastName_Hmk3Prob1/*.cpp
buzzid /<FirstName_LastName_Hmk3Prob1/*.h buzzid /<FirstName_LastName_Hmk3Prob2/*.cpp buzzid /<FirstName_LastName_Hmk3Prob2/*.h buzzid /<FirstName_LastName_Hmk3Prob3/*.cpp buzzid /<FirstName_LastName_Hmk3Prob3/*.h




1







Now execute the following lines in the shell: $ cp -a <FirstName_LastName_* buzzid
$# the previous command makes copies of the files in buzzid $ tar -zcvf buzzid-hmk3.tgz $(cat manifest)

$ tar -ztvf buzzid-hmk3.tgz










The last command above should generate a listing that looks like the following (for example): $ tar -ztvf tlagrow3-hmk3.tgz






-rwxrwxrwx balius/balius 5 2019-09-23 11:54




tlagrow3/theodore_lagrow_Hmk3Prob1/theodore_lagrow_Hmk3Prob1.cpp




-rwxrwxrwx balius/balius 5 2019-09-23 11:54




tlagrow3/theodore_lagrow_Hmk3Prob1/theodore_lagrow_Hmk3Prob1.h




-rwxrwxrwx balius/balius 5 2019-09-23 11:54




tlagrow3/theodore_lagrow_Hmk3Prob2/theodore_lagrow_Hmk3Prob2.cpp




-rwxrwxrwx balius/balius 5 2019-09-23 11:54




tlagrow3/theodore_lagrow_Hmk3Prob2/theodore_lagrow_Hmk3Prob2.h




-rwxrwxrwx balius/balius 5 2019-09-23 11:54




tlagrow3/theodore_lagrow_Hmk3Prob3/theodore_lagrow_Hmk3Prob3.cpp




-rwxrwxrwx balius/balius 5 2019-09-23 11:54




tlagrow3/theodore_lagrow_Hmk3Prob3/theodore_lagrow_Hmk3Prob3.h










We will be compiling your code and testing against unseen commands. We will also be checking for collusion; better to turn in an incomplete solution that is your own than a copy of someone else’s work.














































Grading Rubric




Speed matters in this homework assignment. For each homework problem, the students with the fastest run times and correct answer will get full credit.










AUTOMATIC GRADING POINT DEDUCTIONS PER PROBLEM:






Element
Percentage Deduction
Details














Does Not Compile
40%




Code does not compile on PACE-ICE!












Does Not Match Output
10%-90%


The code compiles but does not produce










correct outputs.












Clear Self-Documenting
10%-25%


This can include incorrect indentation, using


Coding Styles






unclear variable names, unclear/missing










comments, or compiling with warnings. (See










Appendix A)


Execution Speed
0%
< 2x fastest








5% = 2x but < 10x fastest






10%
= 10x fastest














LATE POLICY










Element
Percentage
Details






Deduction


















Late Deduction Function
score -
H = number of hours (ceiling function) passed deadline




(20/24)*H
note : Sat/Sun count as one day; therefore H = 0.5*Hweekend





































































Problem 1: Lattice paths




(www.projecteuler.net) Write a console program that takes as a command line arguments the height and width of a lattice.




Example for a lattice 20 high and 10 wide.




Problem1.exe –h 20 –w 10




Using the logic described below use multithreading to determine the number of possible paths through the lattice as quickly as possible. You should output to the console the number of paths exactly like the following (remember to add a line feed at the end of the ouput)




Problem1.exe –h 2 –w 2



Number of Routes: 6








Path rules:




Starting in the top left corner of the lattice, and only being able to move to the right and down, determine the number of routes to the bottom right corner of the lattice.




Example:




There are exactly 6 routes to the bottom right corner of a 2 x 2 lattice.






























































































4







Problem 2: Largest Product in a Grid




(www.projecteuler.net) Write a multithreaded console program using OpenMP that takes as a command line argument the name of a data file. The data file will contain a M x N grid of numbers. Your program must read in the data file and determine the largest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally). Below is an example of 4 adjacent diagonal numbers in Red:












































































File format:




All values in the text data file are space delimited. You can assume that the input data file does not contain errors, such as missing numbers or nonnumeric numbers and all numbers are greater than or equal to 0. You are free to create as many files as you like and use whatever filenames in order to create a solution. All the files *.cpp and *.h files you create should reside in a single folder that can be compiled to create the executable.




The first line in the file will have the number of M rows and N columns. The next M lines in the data file will contain the rows of N numbers.




Use the file data_Problem2.txt included in the assignment as a test input file.




Output:




Your program should create a text file called output2.txt, in the same directory as the executable, with just the numerical answer on a single line.

Problem 3 (ECE 6122 students only): Maximum Path Sum




(www.projecteuler.net) By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.




























That is, 3 + 7 + 4 + 9 = 23.




Similar to Problem #2, write a multi-threaded console program using OpenMP that takes as a command line argument the name of a data file. Your program must read in a triangle of arbitrary size from a data file. The first line will contain the number of levels in the triangle. A sample data file is attached (data_triangle.txt) to the homework assignment. Your program must find the maximum sum path through the input triangle starting at the top of the triangle.




You can assume that the input data file does not contain errors, such as missing numbers or nonnumeric numbers and all numbers are greater than or equal to 0.







Output:




Your program should create a text file called output3.txt, in the same directory as the executable, with just the numerical answer on a single line.



































































Appendix A: Coding Standards




Indentation:




When using if/for/while statements, make sure you indent 4 spaces for the content inside those. Also make sure that you use spaces to make the code more readable.




For example:




for (int i; i < 10; i++)




{




j = j + i;




}




If you have nested statements, you should use multiple indentions. Each { should be on its own line (like the for loop) If you have else or else if statements after your if statement, they should be on their own line.




for (int i; i < 10; i++)




{




if (i < 5)




{




counter++;




k -= i;




}




else




{




k +=1;




}




j += i;




}




Camel Case:




This naming convention has the first letter of the variable be lower case, and the first letter in each new word be capitalized (e.g. firstSecondThird). This applies for functions and member functions as well! The main exception to this is class names, where the first letter should also be capitalized.




Variable and Function Names:




Your variable and function names should be clear about what that variable or function is. Do not use one letter variables, but use abbreviations when it is appropriate (for example: “imag" instead of “imaginary”) . The more descriptive your variable and function names are, the more readable your code will be. This is the idea behind self-documenting code.

























7

File Headers:




Every file should have the following header at the top /*




Author: <your name




Class: ECE4122 or ECE6122




Last Date Modified: <date




Description:




What is the purpose of this file?




*/




Code Comments:




Every function must have a comment section describing the purpose of the function, the input and output parameters, the return value (if any).
Every class must have a comment section to describe the purpose of the class.



Comments need to be placed inside of functions/loops to assist in the understanding of the flow of the code.



Appendix B: Accessing PACE-ICE Instructions




ACCESSING LINUX PACE-ICE CLUSTER (SERVER)




To access the PACE-ICE cluster you need certain software on your laptop or desktop system, as described below.







Windows Users:




Option 0 (Using SecureCRT)- THIS IS THE EASIEST OPTION!




The Georgia Tech Office of Information Technology (OIT) maintains a web page of software that can be downloaded and installed by students and faculty. That web page is:




http://software.oit.gatech.edu




From that page you will need to install SecureCRT.




To access this software, you will first have to log in with your Georgia Tech user name and password, then answer a series of questions regarding export controls.




Connecting using SecureCRT should be easy.




Open SecureCRT, you'll be presented with the "Quick Connect" screen.



Choose protocol "ssh2".



Enter the name of the PACE machine you wish to connect to in the "HostName" box (i.e. coc-ice.pace.gatech.edu)



Type your username in the "Username" box.



Click "Connect".



A new window will open, and you'll be prompted for your password.



Option 1 (Using Ubuntu for Windows 10):




Option 1 uses the Ubuntu on Windows program. This can only be downloaded if you are running Windows 10 or above. If using Windows 8 or below, use Options 2 or 3. It also requires the use of simple bash commands.




Install Ubuntu for Windows 10 by following the guide from the following link: https://msdn.microsoft.com/en-us/commandline/wsl/install-win10



Once Ubuntu for Windows 10 is installed, open it and type the following into the command line:






ssh **YourGTUsername**@coc-ice.pace.gatech.edu where **YourGTUsername** is replaced with your alphanumeric GT login. Ex: bkim334




When it asks if you’re sure you want to connect, type in: yes
and type in your password when prompted (Note: When typing in your password, it will not show any characters typing)




4. You’re now connected to PACE-ICE. You can edit files using vim by typing in:







vi filename.cc OR nano vilename.cpp




For a list of vim commands, use the following link:




https://coderwall.com/p/adv71w/basic-vim-commands-for-getting-started




5. You’re able to edit, compile, run, and submit your code from this command line.







Option 2 (Using PuTTY):




Option 2 uses a program called PuTTY to ssh into the PACE-ICE cluster. It is easier to set up, but doesn’t allow you to access any local files from the command line. It also requires the use of simple bash commands.




Download and install PuTTY from the following link: www.putty.org



Once installed, open PuTTY and for the Host Name, type in: coc-ice.pace.gatech.edu and



for the port, leave it as 22.




Click Open and a window will pop up asking if you trust the host. Click Yes and it will then ask you for your username and password. (Note: When typing in your password, it will not show any characters typing)






You’re now connected to PACE-ICE. You can edit files using vim by typing in: vim filename.cc



OR nano vilename.cpp










For a list of vim commands, use the following link:




https://coderwall.com/p/adv71w/basic-vim-commands-for-getting-started




5. You’re able to edit, compile, run, and submit your code from this command line.













MacOS Users:.




Option 0 (Using the Terminal to SSH into PACE-ICE):




This option uses the built-in terminal in MacOS to ssh into PACE-ICE and use a command line text editor to edit your code.




Open Terminal from the Launchpad or Spotlight Search.






Once you’re in the terminal, ssh into PACE-ICE by typing:






ssh **YourGTUsername**@ coc-ice.pace.gatech.edu where **YourGTUsername** is replaced with your alphanumeric GT login. Ex: bkim334

When it asks if you’re sure you want to connect, type in: yes



and type in your password when prompted (Note: When typing in your password, it will not show any characters typing)




You’re now connected to PACE-ICE. You can edit files using vim by typing in:






vi filename.cc OR nano filename.cpp




For a list of vim commands, use the following link: https://coderwall.com/p/adv71w/basic-vim-commands-for-getting-started

5. You’re able to edit, compile, run, and submit your code from this command line.







Linux Users:




If you’re using Linux, follow Option 0 for MacOS users.



































































11