Description
1. [50%] Strassen’s matrix multiplication algorithm. Your program should take an input variable n > 0 in the Linux command line, generate two n*n random float matrices, A and B, and compute A * B using the Strassen’s matrix multiplication algorithm for the following two cases. To generate A and B, generate random float numbers that range between -5.0 and 5.0. For random float numbers consider two digits after decimal points (like 3.45) (a) [25%] n =2k where k is a positive integer. (b) [25%] n =/ 2 . k In addition, implement the standard matrix multiplication algorithm with O(n3 ) time complexity. Compute A*B using Strassen’s algorithm and compare the result to the result produced by the standard matrix multiplication algorithm. Print both results for comparisons. (If incorrect results are produced, no credit will be given. Your program should work for any matrices. If it works for specific matrices but doesn’t work for other matrices, no credit will be given.) Your c or cpp file for strassen’s algorithm should contain two basic functions. strassensMultiplication() and standardMultiplication(). You main() function should be able to read inputs and generate two matrices. If you need additional functions to process random matrices, you can create your own. Make sure both strassensMultiplication() and standardMultiplication() functions prints the result before the return statement. These two functions will be called from main() function. Make sure you put appropriate one or two line comments to each of your function definitions. Inappropriate function declaration and unnecessary function calls will cost your points. if your multiplication function is recursive then use strassensMultiplication() as a wrapper function and call your own custom recursive function from it. Do similar for standard function too. DO NOT print unnecessary result other that mentioned below sample output. Example: void strassensMultiplication(parameters) { customRecusriveStrassensMultFunction(); print result here; return; } For strassen’s matrix multiplication, the c or cpp file name should be strassen.c or strassen.cpp. Your makefile will generate .out file as strassen.out. Make sure your makefile will not run/execute the executable file. Your command to run the Strassen program should be: ./strassen.out The TA will run this program for both the above mentioned conditions and will test the output. For each case your program will generate matrices A and B, the output of Strassen’s algorithm and output of standard multiplication algorithm. Don’t print unnecessary texts or debug comments. Your output will look like below (don’t go with the exact multiplication value, this is just an example): Matrix A: Matrix B: Strassen’s Multiplication Output: Standard Multiplication Output: 2. [30%] Implement the tromino tiling algorithm. Your program should take an input positive integer k and the position of the hole as the Linux command line and generate a 2k * 2k board. For example if your input is 4 then your code should generate 16 x16 board. Visualize the final result, similar to the illustration in Slide 7 in Chapter 5. represent you result as the below image Here “digit” represents the regular tile cell and “X” represents a hole. Make sure your program correctly implements the tromino tiling algorithm with O(n2 ) time complexity (the divide and conquer algorithm described in class); that is, there must be only one hole on the board and each of all the remaining 2k * 2k -1 squares on the board must be covered by exactly one square of one tromino tile. No credit will be given if the algorithm is incorrectly implemented, the time complexity of your program is higher than O(n2 ), or your program only works for specific k values. There should be a function named trominoTile(), which will be called from your main() function. main() should be able to read the user input. To generate a board and print it, you can create additional function calls. Make sure you put appropriate one or two line comments to each of your function definitions. Inappropriate function declaration and unnecessary function calls will cost your points. For the tromino problem, the c or cpp file name should be tromino.c or tromino.cpp. Your makefile should generate a .out file as tromino.out. Make sure your makefile will not run/execute the file. To run tromino program your command should be: ./tromino.out example: ./tromino.out 4 5 6 3. [10%] Elegant, compact, and easy to read code with meaningful comments. 4. [10%] Exactly follow file naming, directory naming, packaging, and submission instructions given next. Submission Guidelines: Please submit a tar.gz file with the below naming convention. _project2.tar.gz Make sure you include all the source code files as mentioned below: Your makefile should be able to compile both the source code and generate .out files. make sure you makefile will not run the executable files. You should run and test your code in remote.cs.binghamton.edu and make sure it works there without any issues. You code will be evaluated in the same environment. If code does not run on remote server the TA will not run it on any other environments. Wrong directory structure and presence of unnecessary files will cost you points. Do not create unnecessary output files that are not asked to create. Please do not assume anything, email questions to the TA (psaha4@binghamton.edu), and see him during his office hours for any required clarifications. Important Policies: ● All work must represent each individual student’s own effort. If you show your code or any other part of your work to somebody else or copy or adapt somebody else’s work found online or offline, you will get zero and be penalized per the Watson School Academic Honesty Code (http://www.binghamton.edu/watson/about/honesty-policy.pdf). To detect software plagiarism, everybody’s code will be cross-checked using an automated tools. On the first violation, you will receive zero point for this project, and have to fill in and sign the official form that will be kept by the Binghamton University. On the second violation, it will be reported to the Watson School Committee for Academic Honesty for an official hearing. ● Your code will be compiled and executed. If your code does not compile or produce any runtime errors such assegmentation faults or bus errors, you will getzero. Before submitting your code, run it in a Linux machine (e.g., a remote machine) to remove any such errors. You can use “valgrind” (http://valgrind.org/) to debug memory errors, such as segmentation faults or bus errors. Note that robust programming is essential for developing high quality software. If you are curious about robust programming, check this out: http://nob.cs.ucdavis.edu/bishop/secprog/robust.html ● You are supposed to figure out how to implement this project. The instructor and TA will be more than happy to explain fundamental algorithms covered in class; however, they will not teach you how to implement them or help you to make any kind of decision. Neither will they read or debug your code. By the same token, the instructor and TA will not take a look at an emailed code. If you have questions about general C/C++ programming or Linux, use Google search, which will be much faster than asking the TA. (Don’t copy from the Internet though.)
