All Homework

Comments for all assignments

Most problems are found in one of the following:
1. ADM: The Algorithm Design Manual
2. IDMA: An Introduction to Discrete Mathematics and Algorithms
For full credit, provide context for each problem, show all calculations, and justify all answers by providing enough comments to explain your reasoning.
You will lose a significant amount of credit if you do not provide context, calculations, and justifications for a problem.
Numbers and/or algebra by themselves are not enough. A correct answer with no justification will be worth no more than half credit, and sometimes much less than that.
Precision is very important. You cannot skip steps, make guesses, or use flawed logic. Any of these things can lead to incorrect answers.
Homework assignments must be very neatly written or typeset (e.g. using Word or OpenOffice).
NEW! If you want to learn LaTeX, see the LaTeX section of Writing Notes for a sample LaTeX document. The machines in the lab have TexWorks installed. You may have to ask around to figure out how to compile a file the first time.
You must indicate any assistance/collaboration you had on an assignment as specified on the Policies page.
NEW! If a problem asks for an algorithm, you should give the most efficient algorithm you can find to ensure full credit. You should also specify the complexity of the algorithm with justification, whether or not the problem asks for it.

Homework 1

For this assignment you will implement a simple algorithm and answer a few questions about it.

Write a Java method int choose(int n, int k) that computes the binomial coefficient: .
- You can assume that n and k are both non-negative.
- You may not use any Java libraries to assist you.
- Your implementation should be as efficient as possible.
- Make sure you test your method on several inputs. In particular, you should be able to quickly and correctly compute choose(8,4), choose(15,7), and choose(100,5). Each of these is a little harder to get correct than the previous one for reasons I will let you discover/think about.
- You can check your answers at WolframAlpha using a search like "8 choose 4".
- Print out your code and hand it in at the beginning of class. (You only need to print the method, not the surrounding class, etc. It is O.K. if you print the whole class as long as your entire choose method is all together on one page.)
No matter how good your method is, it will not be able to compute choose(100,7). Why not?
Your method will also very likely not be able to compute choose(100,6) correctly, but for a slightly different reason. What it is?

Homework 2

The following problems are from pages 27-30 of ADM.
Problem
1-2
1-6
1-14
1-25
1-29

Homework 3

The following problems are from pages 57-64 of ADM.
Problem Notes
2-5
2-16
2-18 Express your answer by placing them one per line, except for two or more functions with the same growth rate should be placed on the same line.
2-22 No proof necessary for this one.
2-28a Don't forget to show enough work to justify your answer!
2-36
2-46 Bonus

Homework 4

The following problems are from pages 98-102 of ADM.
Problem Notes
3-12
3-26 Treat the input as an array of characters, and do not use any special methods (e.g. split) to help your process the string since that would obscure how long the algorithm is taking. Give your answer in paragraph form, pseudocode, or code. If you use paragraph form, make sure your description is clear and contains all of the necessary details. If you use pseudocode or code, you also need to include a description of what your algorithm is doing.

Homework 5

The following problems are from pages 139-144 of ADM.
Problem Notes
4-12 Prove that your algorithm has the specified complexity.
4-18 You should be able to do this in place (i.e. with a constant amount of extra memory). Prove that your algorithm has the specified complexity.
4-28
4-32 In both cases, specify how many questions are necessary as a function of n. Give the exact number and not just a bound.

Homework 6

The following problems are from pages 162-163 of IDMA
Problem
422
424
Problem A (below)
Problem A:
Solve the following recurrence relations. If you can provide an exact formula, do so. Otherwise, give a tight bound (not just an upper bound). Make sure you show all of your work.

T(n) = 2 T(n/2) + n³, T(1)=1
T(n) = T(n - 1) + n, T(1)=1
T(n) = T(n/2) + T(n/4) + T(n/8) + n², T(1)=1

Homework 7

The following problems are from pages 184-189 of ADM
Problem Notes
5-1 Show your work. In particular, details about the BFS/DFS tree should be given (e.g. parent pointers or the tree drawn on the graph) along with any relevant numbers (e.g. distances and/or timestamps). Essentially, show enough to demonstrate that you actually followed the algorithms.
5-3 This problem is talking about acyclic graphs, not rooted trees.
5-21 Explain the idea behind your algorithm and justify its complexity. If you use BFS, specify what additional data you need to keep track of and what to do in one or more of the "process" methods of BFS. You will implement this algorithm for Homework 9. Feel free to do so now as a way of testing your algorithm.

Homework 8

The following problems are from pages 184-189 of ADM
Problem Notes
5-2 Use an algorithm (or a modification of one) from the book. Specify what algorithm you are using and show enough work to demonstrate that you actually followed the algorithm.
5-15 Don't forget to give the complexity of your algorithm. The last part of the question is asking you to identify another graph problem that is equivalent to this one.
5-26

Homework 9

Write the following programs

Write a program that tries to determine whether or not using the formula to compute the nth Fibonacci number works properly on a computer. Your goal is to identify the smallest number for which it does not work properly.

You can start by using the iterative algorithm from the Recursive Functions example. Then implement a method that computes the nth Fibonacci number using the closed form expression we developed in class. You can find the formula here: Fibonacci number (Wikipedia). Do not use an approximation in your algorithm. Instead, compute it using the appropriate Java functions (e.g. Math.sqrt).

The easiest way to proceed is probably to compute the first 15 or so with each method and compare them. Your program should output 3 values per line: n, and the two values of f(n) as computed by your two methods. If they differ at any point, you have succeeded. If they don't, try some larger values. You might want to replace the ints with longs in the original code so you can compute slightly larger values (I think you can compute up to the 16th or 17th with 32 bits).

Print out your code along with the output of running both versions on data from 1 to 15 or so (at least until you find if/when the two methods differ).
Implement an algorithm called CountShortestPaths that counts the number of shortests paths between two vertices in an unweighted graph.
Use the Algoraph Plugin (which should already be installed on the lab machines) and upload your algorithm so you can test it on some graphs. Your algorithm should extend BreadthFirstSearchSkeletonAlgorithm. Ignore the stuff this used to say about implementing countShortestPaths and runAlgorithm. You should not do either of these. Instead, everything you implement should be in the 4 process methods and in initializeMoreData. The getResult method should return just the number of paths from the first vertex in the graph to the last one. BFS will automatically run starting at the first vertex.

I will look at your algorithms in Algoraph so all you need to do is make sure your algorithm is uploaded.

Homework 10

The following problems are from pages 226 of ADM
Problem Notes
6-3 See the new Proof Rubric
6-5
6-6 See the new Algorithm Rubric

Homework 11

The following problems are from pages 227 of ADM
Problem Notes
6-14 See the new Algorithm Rubric
6-17 See the new Proof Rubric
Algoraph Problem See Below
Use the Algoraph plugin to implement one of the following:

Prim's Algorithm. Use MinimumSpanningTreeInstance. To output the result, create a MultiEdgeChosenEvent using the constructor that takes an EdgeChooseInstance (MinimumSpanningTreeInstance is a subclass of this) and an ArrayList of edges. Pass in puzzle and your ArrayList of tree edges. Return encodeEvent.
Kruskal's Algorithm. See the previous option for more details.
Dijkstra's Algorithm. Use SSShortestPath. Otherwise, follow the same details from Prim's Algorithm above.
Floyd's Algorithm. Use WeightedInstance. Output the matrix. I may give further details.

More details coming soon.

Homework 12

Problem Grading
A ?
8-10 or 8-25 Algorithms Rubric
8-16c or 8-17 Algorithms Rubric

Problem A: Problem 8-10 suggests giving an algorithm that runs in O(nM) time. Is that a polynomial-time algorithm with respect to the size of the input? Explain.

Note: When giving a dynamic programming algorithm, give a recursive formula and specify how the values will be computed to yield an efficient algorithm.

Homework 13

Spending Money

I recently inherited $100,000,000. Since I never thought saving was a good idea, I want to spend it all. There are 10,000 products, numbered 1 through 10,000, I have always wanted to have. I have a file which includes the cost, to the nearest dollar, of each item. I want you to tell me which items I should buy so I can spend as much of the money as possible. In fact, I want to have at most $800 left over, if possible. Your program should output the number of items in your solution, the index of the items, and the total amount of money left over. For example, if your algorithm outputs "4 3 12 24 36 123", it means I should buy the 4 items 12, 24, 36, and 3, and I will have $123 left over.

Here are some important things you will need.

The input data: Prob1.dat

A Verification Algorithm: P1Verify.cpp. Read the comments carefully. In particular, note that it assumes indexing starting at 1 instead of 0.

Hand in your source code and solution files (call it Prob1.out) using Webhandin under assignment 385-H13.

New addition!
Submit a write-up (printed) that includes the following.

State which classical computational problem this is an instance of or is related to.
Give an assessment of the difficulty of solving the problem, including your reasoning. Start by specify if it is known to be in P or NP-complete and based on this evaluate how difficult you expect it to be.
For each algorithm you tried, give a one paragraph discussion that includes:

A brief description of the algorithm.
Whether your algorithm is attempting to find an exact solution or an approximation.
Why you thought it would be a good approach.
A tight bound on its complexity.
An evaluation of how well it performed (i.e. how good of a solution did you get with it?), including specific numbers (i.e. "the best this algorithm could do was leave $1200").

If you tried more than one algorithm, include a paragraph that compares them, specifies which one seems to be the best approach (with justification).
Discuss other strategies/algorithms that might work better than what you tried.

Homework 14

The country of Ferzle recently signed a treaty with the country of Foobar. Among the various conditions of the treaty are provisions for Foobar to have buildings to use as embassies. Each embassy should be in one of the 5000 largest cities (numbered 0 through 4999) in Ferzle, and each of these cites should be no further than 100 miles from an embassy. Since space in these cities is expensive, Ferzle needs to minimize the number of cities they allow Foobar to have embassies in. You have been hired by Ferzle to solve this problem. The file Prob2.dat lists the coordinates of each city, given relative to the south-western corner of the country. The distance between two cities can be computed using the standard distance formula.

Start by downloading the files from here: Ferzle Embassies Files. The program takes care of reading the file, showing solutions, and summarizing the best solution (assuming you call the right methods in the right places). You are most interested in FerzleModel and MyAlgorithms. FerzleModel contains a whole lot of methods that you might find useful. They are not well documented, but the names should give you a clue as to what they are trying to do. Look closely at the code to make sure they do what you think they do, though.

Hand in your source code and a file named BestSolution.txt containing your best solution (cut-and-paste from the application) Webhandin under assignment 385-H14.

Homework 15

The following are from Some Homework Problems for the Material in "A Sophomoric Introduction to Shared-Memory Parallelism and Concurrency"

Write a program for Problem 1. You should have two versions--one that uses a sequential cutoff and one that does not. See the examples in the book or the ForkJoinExamples to help you figure out how to properly use the ForkJoin stuff. Hand in using Webhandin
Problem 3
Problem 4