Reference no: EM1343512

1. Implement the tronomino tiling algorithm. Your program should take an arbitrary input positive integer k in the Linux command line and generate a 2^k * 2^k board. Randomly create one rectangular hole on the board and solve the tronomino tiling problem for this board. If a square on the board is occupied by a square of a tronomino tile, print "O". If it is a hole instead, print "X". Thus, your output should look like as the following, if there is a hole is at the intersection of the first row and second column. (To print the output, assume 1 ≤ k ≤ 6.)

 

| O | X | O | ............| O |

| O | O | O | ............ | O |

...............................

...............................

...............................

| O | O | O | ............ | O |

 

Make sure your program correctly implements the tronomino tiling algorithm with O(n²) time complexity (the divide and conquer algorithm described in Chapter 5); that is, there must be only one hole on the board and each of all the remaining 2^k * 2^k -1 squares on the board must be covered by exactly one square of one tronomino tile. No credit will be given if the algorithm is incorrectly implemented, the time complexity of your program is higher than O(n²), or your program only works for specific k values.  Save your source code in a file and name the file as yourlastname_pa2_tro.cpp.

2.      Implement the longest common subsequence (LCS) algorithm using the dynamic programming method that was discussed in class.  (No credit will be given if you implement a brute force algorithm, which does exhaustive comparisons between two input strings, or any other algorithm unless you prove your algorithm is correct and more efficient than the LCS algorithm described in Chapter 7.) Save your source code in a file and name the file as yourlastname_pa2_lcs.cpp.

Make sure that your program can take any two input strings in the Linux command line and print the LCS found between the two input strings. (Assume that a string consists of at most 100 alphabetic characters.) For example, student Smith types "smith_pa1_lcs abc afgbhcd" in the command line to find the LCS between string "abc" and string "afgbhcd".  Again, your program should work for arbitrary two input strings. No credit will be given, if your program only works for some specific strings, but fails to find the LCS for other strings.

3.      Implement Strassen's matrix multiplication algorithm. Your program should take an input variable n (=2^k where k is a positive integer) in the Linux command line and generate two n*n random integer matrices, A and B. Compute A*B using Strassen's algorithm and compare the result to the result produced by the standard matrix multiplication algorithm with O(n³) time complexity. Print the results, if correct. (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.) Finally, save your source code in a file and name the file as yourlastname_pa2_strassen.cpp.

All programming must be done using C or C++ in Linux where your code will be tested.  Create a tar file that includes (1) three source code files and (2) a readme file that clearly describes how to compile and run your code.