CSCI 385 Fall 2020
Advanced Data Structures and Algorithms		Archived Class
Charles Cusack
Computer Science
Hope College
Main
Schedule
Grading
Gradebook
Homework
Policies
Advice
College
    Policies
Notes
Programs
Tutorials
CSCI 125
CSCI 255
Others
Admin

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. 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

  1. 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 column i and row j). The solution should be placed in a vector x (e.g. x[1] will store the value of x1, 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.)

  2. 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

  1. IDAA 8.2.1 (page 296) (4+2+2)
  2. IDAA 8.2.6 (page 297) (4+1+1)
  3. Problem removed IDAA 8.3.4 (page 303)
  4. IDAA 8.4.7 (page 312) (6)
    Show all of the intermediate matrices!

Homework 4

  1. IDAA 9.1.7 (page 323).
    Prove that your algorithm is optimal.
  2. IDAA 9.3.3 (page 338).
    Explain why the counterexample "breaks" the algorithm.
  3. IDAA 9.3.6 (page 338)
    Hint: Use induction and it isn't that difficult.

Homework 5

  1. IDAA 10.2.2a (page 371).
    Show all of the intermediate steps! Do not forget to give the value of the maximum flow and specify the minimum cut (i.e. give the set X).
  2. IDAA 10.2.10 (page 372).
    Make sure you clearly explain your solution!
  3. IDAA 10.3.1 (page 378)
    Make sure to fully justify your answer.
  4. IDAA 10.3.10 (page 380)
    Looking at a picture of a chess board might help. Make sure to prove your answer.

Homework 6

  1. IDAA 11.1.3 (page 393)
    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.
  2. IDAA 11.1.7 (page 394)
    Make sure your argument is very clear and complete.
  3. 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 7

  1. IDAA 11.4.3 (page 419).
    Note that √(e)=e0.5, and the formula you want is 11.6 on page 412. If you don't know what is meant by "fifth-degree Taylor's polynomial about 0," please ask.
  2. IDAA 12.1.8 (page 431).
    Show the state-space tree and any other necessary work.
  3. IDAA 12.2.5 (page 440).
    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.

Homework 8

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 vertex 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-HW8. 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).

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).

Homework 9

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.

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.

Submit matmul_par.c using Webhandin 385-HW9.

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 10

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-HW10. 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. 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.
  3. Discuss how the running time scales with the number or processors. Is it what you would expect? Try to explain why or why not.
  4. 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.
  5. 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.
  6. 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 11

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. 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.
    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. 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-HW11
  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 12

You may work in teams of 2 on this project if you wish.

Implement either Mergesort or Quicksort 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.

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-HW12.

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 (although if you get partition correct, there is no reason that you shouldn't also get quicksort correct). 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 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)