All Homework

Homework 1

Implement an efficient algorithm to generate all permutations of the elements of an array. You may use one of the algorithms from the textbook or find another algorithm elsewhere (if so, say where you got the ideas/algorithm from). (Future note: change to MUST use one from the book) However, you may not use any code from any source. An important skill to develop is implementing an abstract algorithm in an actual programming language.
Your program should be written in Java. Name your class CombinatoricsUtilities. It should have a method
public static ArrayList⟨String[]⟩ generatePermutations(String[] input)
that returns an ArrayList of all permutations of the original array.
To help you debug your code, include a method public static void printList(ArrayList⟨String[]⟩) that prints each array in the ArrayList, one per line. Each array should be printed by printing each element with commas in between. E.g. For array ["blah","foo","bar"], the output should be
blah,foo,bar
Note: The easiest mistake to make with this algorithm is to not copy an array when you need to.
Submit your Java file(s) (NOT your .class files) using Webhandin 385-HW1.
Submit a brief write-up that includes a description of your algorithm and gives the computational complexity of it, with justification. (Convince me that you fully understand how the algorithm works and that you understand the analysis of it.)

Homework 2

Do problem 6.2.5 on page 216. Assume A' is upper-triangular and has been augmented with b' as its final column, and that it is indexed in the expected way (e.g. A'[i,j] is the entry in row i and column j). The solution should be placed in a vector x (e.g. x[1] will store the value of x₁, etc.)

Hint: Pay careful attention to how you solved systems with 3 or 4 variables. Which variable did you solve for first? How did you find each of the remaining variables? You should realize that the process you followed can be captured by a simple formula.

Do not forget to analyze your algorithm. (Hint: You will need to express it using one or more sums which you will then need to simplify.)
Solve problem 6.6.11b on page 249 by reducing to a graph problem. Please do this problem on your own! I know that it is easy to find solutions for this one online, but you won't learn much by using one of those and you risk failing the assignment (unless you give credit, in which case the 1/2-credit policy applies).

Homework 3

(10) Solve the instance of the optimal binary search tree problem that contains items A, B, C, D, E, F with probabilities .15, .1, .23, .12, .33, .07 by using the algorithm from the textbook. Give the final tables and draw the tree. Show all of your work.
(10)
1. Ask chatGPT to solve Problem 1 for you. Include in your solution the question you asked and the entire response.
2. Evaluate chatGPT's solution. Did it get the correct solution? Did it explain it in a coherent way?
(10) Find a solution to the optimal binary search tree using items A-J with frequencies 1/2, 1/4, 1/8, 1/16, 1/32, 1/64, 1/128, 1/256, 1/512, 1/512 (assigned in that order). You may do it by hand, find help online, or use your intuition. In any of these cases, justify your solution. If you use chapGPT, you might want to double check to make sure it got it correct!
(20) Ask chatGPT for a Java implementation of an algorithm to solve the optimal binary search tree problem.
1. Look at it and see if you can figure out how the algorithm works (which might be easier if it gives you an algorithm similar to the one from our book). Evaluate whether or not you think it computes the correct solution.
2. Test the algorithm by running it on the textbook example, the example from Problems 1 and 3 above. Show the output of the algorithm! How did it do on these instances? Was it correct, close, or way off?
3. What is the efficiency of the algorithm? Is it more or less efficient than the algorithm given in the textbook?
4. Are there more efficient algorithms possible to solve this problem? Justify your answer. (Hint: Look at the exercises for section 8.3.)

Homework 4

(4+2+2) Consider this instance of the knapsack problem.
Capacity W = 11 Item weight value 1 3 27 2 2 13 3 4 40 4 3 32 5 5 48 6 7 82 7 1 12
1. Solve this instance of the knapsack problem using the bottom-up dynamic programming algorithm. Give the optimal cost and a list of the items to take.
2. How many different optimal solutions does this instance have? Explain how you know.
3. In general, how can you determine whether or not there is a unique solution to the knapsack problem using the table constructed by the algorithm?
(4+2+2)
1. Solve the instance of the knapsack problem from #1 using the memory function method.
2. Indicate which entries in the table are never computed by placing a '-' instead of a number.
3. Clearly indicate (using a circle or square or highlighter) which cells of the table are looked up rather than being recomputed. (That is, the entries that WOULD be computed a second time if the standard recursive algorithm was used.)
IDAA 8.4.7 (page 312) (6)
Show all of the intermediate matrices!

Homework 5

(8 pts) IDAA 9.1.7 (page 323).
Prove that your algorithm is optimal.
Correct (4), complexity (2), optimal proof (2)
(6 pts) IDAA 9.3.3 (page 338).
Explain why the counterexample "breaks" the algorithm. Be specific. (2)
(6 pts) IDAA 9.3.6 (page 338)
Hint: See the book's hint!

Homework 6

(6+4+2 pts) Apply the Ford-Fulkerson algorithm to find the maximum flow of the following network.
Do not forget to:
1. Show all of the intermediate steps (copy this graph into your file and/or print it multiple times to make it easier!)
2. Draw the maximum flow and give the value of the maximum flow.
3. Specify the minimum cut (i.e. give the set X).
(6 pts) IDAA 10.2.10 (page 372).
Explain how to construct the appropriate graph and explain what a maximum flow tells us about the answer to the question.
Make sure you clearly explain your solution!
(6 pts) IDAA 10.3.1 (page 378)
Make sure to fully justify your answer.
(6 pts) IDAA 10.3.10 (page 380)
To clarify, it is looking for a tiling in which the lower left and upper right squares are empty, but the rest of the board is covered. Looking at a picture of a chess board might help. Make sure to prove your answer.

Homework 7

(12, 3 pts per part) IDAA 11.1.3 (page 393)
Part (b) is determining whether or not a graph is the complete graph (the wording is a little strange). Breifly justify your answers. Also, to show that the bound is tight, you need to give an algorithm that solves the problem in that much time.
(6 points) IDAA 11.1.7 (page 394)
Make sure your argument is very clear and complete.
(8 points) IDAA 11.3.7 (page 410)
Don't forget to (1) clearly state the decision version, (2) clearly outline the verification algorithm, and (3), justify that the verification algorithm is polynomial-time.

Homework 8

(5+2+2+3+2 pts) The Taylor Polynomial of degree n for computing eⁿ is given on page 412 (formula 11.6).
1. Use it to approximate the value of e^0.25≈1.28402541669... using a fifth-degree Taylor Polynomial (i.e. e^x≈1+x+...+x⁵/5! )
2. What is the absolute error of this approximation, to at least 10 decimal places?
3. What is the relative error of this approximation?
4. According to formula 11.8 on page 413, what is the maximum value of the expected absolute error?
5. Is the actual error greater than or less than the expected error? Explain why your answer makes sense.
(10 pts) Apply backtracking to solve the following instance of the subset sum problem: A={2,3,4,7}, d=13
Clearly show the state-space tree labelled appropriately along with any other relevant work.
(10 pts) Solve the following instance of the knapsack problem using the branch-and-bound algorithm. Make sure to show the state-space tree, including all of the appropriate details in each node, and any other necessary work. You can use either the bound from the book or the one we discussed in class, but clearly state what bound you are using. Clearly state the solution and its value.

W=15
Homework 9
Implement an algorithm in Algoraph to solve the Traveling Salesperson problem. Your goal is to get the exact answer if possible, but otherwise get the best answer you can in a reasonable amount of time. So you might have multiple algorithms: an exact one and an approximation one.
Start as follows:
1. In Eclipse, create a new Algoraph Algorithm. Use WeightedInstance as the data type.
2. To be sure you have the latest plugin, right after you create the new algorithm, right-click on the project and select "Update Algoraph.jar from Algoraph".
3. On the first line of the runAlgorithm method, put the following line of code:
```
int[][] A = puzzle.getAdjacencyMatrix();
```
  (If this gives a compiler error, the jarfile is not up to date.) This will allow you to use the weighted adjacency matrix A in your algorithm and ignore the rest of the method calls and awkward ways of accessing the edge weights.
The algorithm should return a string that gives the cost of the optimal cycle followed by a ":" and then followed by the order the vertices should be visited with spaces between the vertices.
For instance, a valid output for a graph with 6 vertices might be: 34:0 1 4 3 5 2.
Note: A valid solution on a graph with n vertices will be a permutation of the numbers 0 through n-1.
Grades will be based on how many of the following graphs your algorithm can correctly solve and how close you can come to the optimal solution on the rest (the puzzleID for each is given in parentheses):
1. K05 TSP (1325)
2. K09 TSP (1319)
3. K10 TSP (1320)
4. K12 TSP (1321)
5. K15 TSP (1322)
6. K20 TSP (1323)
7. K25 TSP (1324)
8. K30 TSP (1326)
9. K35 TSP (1327)
10. K40 TSP (1328)
11. K45 TSP (1329)
12. K50 TSP (1330)
Algoraph has a few classes that you might find helpful in the package cusack.hcg.graph.algorithm.util. Unfortunately, they are not well documented. But here they are, listed in the order of the most likely you might want to the least likely:
- PermutationGenerator allows you to iterate over all of the permutations of the set {0,1,2,...,n-1}. It has methods next() and hashNext() like a typical iterator does.
- KSubsetGenerator allows you to iterate over all k-subsets of the set {01,1,2,...,n-1}.
- KPermutationGenerator allows you to iterate over all k-permutations of length k from the set {01,1,2,...,n-1}. So if n=5 and k=3, it would generate 012, 013, 014, 023, 024, 034, 123, 124, etc.
Get the test program TSPTests.java from the AlgorithmTests page. You can cut-and-paste the code from there into a new class in Eclipse. It is a JUnit test so you can run it easily. You will need to rename the type of variable from TSP to whatever the name of your algorithm class is in 2 places on line 88. If you don't want it to run them all (because some of them are large and might take years to run) you can comment out the line that says @Test before any test you do not wish it to run. This program will run your code and give you an indication of whether or not it worked properly, but it cannot always tell you if your answer is correct (since I don't know the optimal solution for some of them). If you look at the test cases, for the small ones the answer is known (the tests that call a 2-argument verifyStuff method). For the rest, I have indicated in a comment a bound on the optimal solution based on previous students' solutions (and just the ones I happened upon. It is possible another student did better but I can't find a record of it right now.)
Submit your algorithm and a file called results.txt that gives the solution to each graph using Webhandin 385-HW9. Each line of results.txt should contain the name of the graph followed by a colon followed by the output of your algorithm (which should be in the format described above). For instance, the first few lines might look like:
```
1325: 23:0 1 3 4 2
1319: 16:0 8 2 1 3 6 7 4 5
```
Finally, bring a write-up to class that describes the algorithm(s) you tried. Explain why you choose the algorithm(s) you did and describe how they performed--both in terms of speed and in terms of optimality of the solutions obtained. Then discuss ideas for improving your algorithm(s).
Hints:
- Exhaustive search will probably only get you to an exact solution for 15 vertices at best.
- Branch-and-bound will work better than exhaustive search, but probably will only get you to 20 vertices.
- Randomness is your friend. But not just pure randomness. Clever use of randomness is what you need.
- It might be possible to do some sort of randomization with branch-and-bound to make it work with larger graphs, but I haven't tried it so I can't be certain.
- The graphs we are dealing with are not Euclidean, so many algorithms you will find will NOT work properly on our graphs.
- A randomized nearest neighbor algorithm or a genetic algorithm are pretty good choices for larger graphs.
Homework 10
The goal of this assignment is to play around with Open MP to learn what you can about private versus shared variables, atomics and critical sections, and the various scheduling options.
Note: You may discuss strategies and ideas with each other on this assignment, but please don't just blindly follow any of your classmates. Your goal is to gain a better understanding of Open MP.
The file matmul_par.c is a parallel implementation of the matrix multiplication algorithm. Download it, place it in the directory with the files from the Open MP videos and modify the makefile so it will compile it (You will need to copy two lines and change the details and make 2 other additions to the file).
This file is a start of a parallel implementation but it is buggy and inefficient. Your job is to make it as efficient as possible. In other words, make the speedup ([time for 1 thread]/[time for 24 threads]) as high as possible. Note: It is broken right now so you will need to do some changes before it will even work with multiple threads.
The code looks a bit strange because the arrays are declared as 1-dimensional instead of 2-dimensional arrays, but they are treated as 2-dimensional arrays the way they are indexed. You shouldn't have to worry about this, though, since you probably won't be making any changes related to those details.
You should play around with shared versus private variables, using critical/atomic regions, changing the scheduling, etc.
Create a document in which you list every change you tried with as much detail as necessary to make it clear exactly what you changed (but as brief as possible). For instance, write something like added schedule(auto) to the parallel for loop. Then give the results for that change (the output of the program). document everything you try!. Your document should be quite large by the time you are done.
Attempt to get your speedup to 18-20, and even higher if possible.
When you are done optimizing your code, change the line that reads
```
#define ORDER 1000
```
to
```
#define ORDER 2000
```
and run your algorithm again and base your final analysis on this. (This should make your algorithm take about 1 minute on 1 core, and 2-3 seconds on 24 cores.)
Submit matmul_par.c using Webhandin 385-HW10.
Also submit your document with all of the details of your experiments. At the beginning of your document add a summary that includes what the best speedup you could attain was and how you did it. Explain why (to the best of your knowledge) the things you did gave you the improvements. Be as detailed as possible. Then include a table that summarizes all of your attempted improvements that shows the speedup with 24 threads for each change and the time it takes for 24 threads. (In other words, it should have 3 columns: A brief description of the change, the speedup attained with 24 threads, and the time for 24 threads.) Since this is likely to be a long document, print out just the summary page or two, but submit the entire document using Webhandin.
Homework 11
Work alone or in pairs on this assignment.
Complete your parallel implementation of Quicksort. Your goal is to make it as fast as possible. Use the test files largeTests.txt and reallyLargeTests.txt as you are optimizing your code. When you are satisfied with your implementation, run runSorts on the file hugeTests.txt and put the results in a file called hugeTestResults.txt.
You should already have the base code, but if not it is here: QuickSortProject.zip
Note: There is an OpenMP version of some notes we will be studying later in the semester linked below (we will go through the Java version). They may or may not help you with this assignment, but just in case, you can find them here: SPAC_CPP.pdf.
Zip up the directory with all of your files and use Webhandin 385-HW11. to submit it.
Submit a hard-copy of a write-up that includes the following. (Please take the write-up seriously and don't just throw it together at the last minute.)
1. A brief description of your algorithm. Focus on how you parallelized it.
2. Your output from running hugeTests.txt. Add a final column that gives the speedup versus the first trial (pQuickP1).
3. A chart showing its performance against the serial version on the hugeTests.txt file with 2, 4, 8, 12, 16, 24, and 32 threads. Plot the numbers from the average column using Excel or a similar program so you can see the trend.
4. Discuss how the running time scales with the number or processors. Is it what you would expect? Try to explain why or why not.
5. Give a tight bound on the expected running time of your parallel algorithm assuming you had k cores. Make sure you justify your analysis. Hint: It may not be exactly what you expect it to be.
6. Discuss any limitations of your parallel algorithm. What is the limiting factor of how much you can parallelize it? Could it be made faster? If so, explain.
7. Grade yourself out of 20 points, providing a clear justification.
For purposes of comparison, here is my output for hugeTests.txt:
```
             In Order  Reversed Random         Repeated  Clumped  Average
pQuickP1     No Data   No Data  19743513 (7)   No Data   No Data  19743513 (7)
pQuickP2     No Data   No Data  14265134 (7)   No Data   No Data  14265134 (7)
pQuickP4     No Data   No Data  10995513 (7)   No Data   No Data  10995513 (7)
pQuickP8     No Data   No Data   5709799 (7)   No Data   No Data   5709799 (7)
pQuickP16    No Data   No Data   4191602 (7)   No Data   No Data   4191602 (7)
pQuickP24    No Data   No Data   3482685 (7)   No Data   No Data   3482685 (7)
pQuickP32    No Data   No Data   3175726 (7)   No Data   No Data   3175726 (7)
```
Homework 12
You may work in pairs on this assignment.
The following are from Grossman Homework. They will be equally weighted (10 points each).
1. Write a program for Problem 1 but with some modifications-- Keep reading!.
  
  Have a parameter (to the constructor) that allows you to set the threshold for the sequential cutoff (where a value of 1 essentially means there is no cutoff) and run tests with various thresholds and array sizes. The constructor should be:
```
public LongestSequence(int [] array, int lo, int hi, int val, int thresh)
```
  The code on page 27 of the Grossman notes is a good starting point.
  Have your main program run tests on arrays of various sizes. Run it on some "known" small arrays so you can test the correctness of the algorithm, and then it should run it on larger arrays. Make sure you output the array size, cutoff, and time taken for each test. If you can figure out how, run it on Loki so you can test it with 24 cores.
  Submit your results as a textfile or on paper.
  For a lot of helpful tips on implementing your algorithm using ForkJoin, see Beginner's Introduction to Java's ForkJoin Framework and/or examples from the book.
  Hand in your code using Webhandin 385-HW12
2. Do Problem 3. Use Excel or a similar program to create the tabels of values and charts. Submit your Excel file using webhandin. If you use another program make sure you submit a printed copy of your tables and charts.
3. Do Problem 4. Hand this one in on paper.
Homework 13
You may work in teams of 2 on this project if you wish. In fact you really should work with a partner on this one! It contains several challenges.
Implement either Mergesort or Quicksort (recommended) using the algorithm given in the SIPC notes. Run tests to compare it with an optimized serial version and your naive parallel version from HW 8 (which you are welcome to improve a bit if you wish). Zip up the directory with all of your files and submit it using Web handin as usual.
Start by implementing packP and testing it (Change which test it runs by commenting/uncommenting at the end of the file, and compile using make parCode) and running it (./parCode). Then implement and test partitionP, making sure to change which test method gets called.
Here are some resources you might find helpful
1. SPAC_CPP.pdf A version of the Parallelism and Concurrency written for OpenMP instead of Java.
2. QuickSortProject The starting files which you should already have from a previous assignment. It has my version of parallel sum, parallel-prefix sum, and a start of the pack and partition algorithms. It also has methods that will test parallel sum, parallel-prefix sum, and pack.
Submit a hard-copy of a write-up that includes the following. (Please take the write-up seriously and don't just throw it together at the last minute.)
1. A chart that compares the performance of the various algorithms. At a minimum, both parallel algorithms should be run on 1, 2, 4, 8, 16, 24, and 32 threads.
2. Discuss how the algorithms compare with each other. Is the new-and-improved algorithm better than your naive one? If not, explain why you think it is the case. Discuss what would happen if you had a lot more processors and/or larger arrays.
3. Grade yourself out of 20 points, providing a clear justification.
Hand in your code using Webhandin 385-HW13.
If you are unable to complete the implementation of quicksort, you may receive up to 13/20 points for a proper implementation of pack and up to 16/20 points for a proper implementation of partition (If you only implement partition so it works on a full array, it will need to be modified to work in Quicksork so it can work on just part of an array). My code (given above) already has a test program for pack. If you get partition correct but not quicksort, include a program that tests your partition algorithm.
Here are my results from HugeTests.txt (in 2023):
```
           In Order    Reversed   Random      Repeated  Clumped    Average
Quick2       No Data   No Data  20030716 (7)   No Data   No Data  20030716 (7)
pQuickP1     No Data   No Data  20217046 (7)   No Data   No Data  20217046 (7)
pQuickP2     No Data   No Data  12910157 (7)   No Data   No Data  12910157 (7)
pQuickP4     No Data   No Data   8132749 (7)   No Data   No Data   8132749 (7)
pQuickP8     No Data   No Data   5249098 (7)   No Data   No Data   5249098 (7)
pQuickP16    No Data   No Data   3657280 (7)   No Data   No Data   3657280 (7)
pQuickP24    No Data   No Data   3037894 (7)   No Data   No Data   3037894 (7)
pQuickP32    No Data   No Data   2726988 (7)   No Data   No Data   2726988 (7)
fQuickP1     No Data   No Data  28325679 (7)   No Data   No Data  28325679 (7)
fQuickP2     No Data   No Data  26838886 (7)   No Data   No Data  26838886 (7)
fQuickP4     No Data   No Data  23836322 (7)   No Data   No Data  23836322 (7)
fQuickP8     No Data   No Data  15874206 (7)   No Data   No Data  15874206 (7)
fQuickP16    No Data   No Data   5462368 (7)   No Data   No Data   5462368 (7)
fQuickP24    No Data   No Data   3619784 (7)   No Data   No Data   3619784 (7)
fQuickP32    No Data   No Data   2948947 (7)   No Data   No Data   2948947 (7)
```
Here are my results from previous years with a slightly worse algorithm:
```
           In Order    Reversed   Random      Repeated  Clumped   Average
pQuickP1     No Data   No Data  20110140 (7)   No Data   No Data  20110140 (7)
pQuickP2     No Data   No Data  11751138 (7)   No Data   No Data  11751138 (7)
pQuickP4     No Data   No Data  10558189 (7)   No Data   No Data  10558189 (7)
pQuickP8     No Data   No Data   6403963 (7)   No Data   No Data   6403963 (7)
pQuickP16    No Data   No Data   4241028 (7)   No Data   No Data   4241028 (7)
pQuickP24    No Data   No Data   3525688 (7)   No Data   No Data   3525688 (7)
pQuickP32    No Data   No Data   3061767 (7)   No Data   No Data   3061767 (7)
fQuickP1     No Data   No Data  39916515 (7)   No Data   No Data  39916515 (7)
fQuickP2     No Data   No Data  39280604 (7)   No Data   No Data  39280604 (7)
fQuickP4     No Data   No Data  33353175 (7)   No Data   No Data  33353175 (7)
fQuickP8     No Data   No Data  18289919 (7)   No Data   No Data  18289919 (7)
fQuickP16    No Data   No Data   7671305 (7)   No Data   No Data   7671305 (7)
fQuickP24    No Data   No Data   9214110 (7)   No Data   No Data   9214110 (7)
fQuickP32    No Data   No Data   7341779 (7)   No Data   No Data   7341779 (7)
```
Item Weight Value

1 7 53

2 6 49

3 3 19

4 8 60

5 2 14

All Homework

Homework 1

Homework 2

Homework 3

Homework 4

Homework 5

Homework 6

Homework 7

Homework 8

Homework 9

Homework 10

Homework 11

Homework 12

Homework 13