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

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

Homework 2

The following problems are from Chapter 1 of IDMA on pages 11-12.
Problem
50
51
54
55
57

Homework 3

Problems are from Chapter 2 of IDMA on pages 31-34.
Problem
98
102
108

Homework 4

Problems are from Chapter 3 of IDMA on pages 69-74.
Problem
221
237
245

Homework 5

Problems are from Chapter 3 of IDMA on pages 69-74.
Problem
223
227
249

Homework 6

Problems are from Chapter 3 of IDMA on pages 69-74.
Problem
233c
234c
240b

Homework 7

Problems are from Chapter 4 of IDMA on pages 93-95.
Problem
297
298.2
304
307

Homework 8

The following problems are from pages 57-64 of ADM.
Problem Notes
2-16 Use the definition of Big-O notation or the limit theorem.
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.

Homework 9

The following problems are from pages 57-64 of ADM.
Problem Notes
2-5
2-28a Don't forget to show enough work to justify your answer!
2-36
2-46 Bonus

Homework 10

The following problems are from pages 162-163 of IDMA
Problem Notes
418 The context for this problem is in section 6.4.
419 Can you say induction?

Homework 11

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

Homework 12

The following problems are from pages 195-197 of IDMA.
Problem Notes
516 Questions 1 and 4 are pretty straightforward. Question 3 includes the possibility of taking however many courses you want, as long as the requirement is met.
517.1-3 The setup for the problem is on page 195. See page 196 for questions 1-3. Question 1 can be done by generalizing the idea in the setup.
526 Don't use induction. It's actually easier than that. But be careful. If you think about it correctly, at some point in your proof you will consider multiple cases/possibilities.

Homework 13

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 14

The following problems are from pages 193-197 of IDMA.
Problem Notes
504.2 Don't do it the hard way!
509 You really don't want to do this one the hard way.
536 The technique you used in the previous 2 problems (assuming you did them the easiest way) can be used here. This one is actually really easy if you use the correct tool.

Homework 15

The following problems are from pages 98-102 of ADM.
Problem Notes Grading
3-3
3-20 Assume you do not know the length of the list. Your algorithm should be as efficient as possible. If a list has an even number of elements, return either of the middle two elements. Algorithm Rubric
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. Algorithm Rubric

Homework 16

The following problems are from pages 139-144 of ADM.
Problem Notes Grading
4-12 Prove that your algorithm has the specified complexity. Also, see the heading right above the problem. It may give you a hint about how you might want to approach the problem. Algorithm Rubric
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. Algorithm Rubric
4-28 This one is really not that hard if you use some of your math skills. Computational Problem Rubric
4-32 You are not limited to 20 questions. They just use that as a setup for the problem. For both parts, specify exactly how many questions are necessary as a function of n (not just a bound). Algorithm Rubric

Homework 17

The following problems are from pages 184-189 of ADM.
A few general comments: Part of learning a topic is learning to use the vocabulary. Here are a few examples.

Graphs have vertices/nodes and edges, not elements.

For BFS/DFS, the terms discovered and processed are technically defined, so use those instead of explored, found, visited, seen, etc. which do not have clearly defined meanings.

You can reach the end of a linked list, but you can't reach the end of a tree.

Problem	Notes	Grades
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. Most of you seem to have ignored these comments. Please include all of the details asked for. Although the book's BFS algorithm does not explicitly compute distances, the version in the lecture notes does, so follow that version if necessary.	Computational Problem Rubric
5-3	This problem is talking about acyclic graphs, not rooted trees. For the induction step, assume it is true for any tree with n nodes. Then consider a tree with n+1 nodes. How do you get a tree with n nodes from a tree with n+1 nodes so that you can apply the inductive hypothesis? Hint: consider a leaf. You cannot just start with a tree with n nodes and add a leaf to it. The induction step needs to show that it is true for any tree with n+1 nodes, so you need to start with an arbitrary tree with n+1 nodes. Also, when you apply the inductive step, you need to prove that there is exactly one path between every pair of nodes. You need to argue it is true of the (n+1)th node with any other node, but also that it is still true of any pair of nodes not including the (n+1)th.	Proof Rubric
5-9	Assume the only operators are +, -, /, and *. The easiest way to think about it is to implement it as `Eval(node root)`, where `root` is the root of the binary tree. It is actually pretty straightforward if you use recursion. You should give your solution as pseudo-code and deal explicitly with the 4 possible operators.	Algorithm Rubric
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. Your answer can be as simple as something like "For each node keep track of X. Initialize the values to Y. In processXYZ, do Q..."	Algorithm Rubric

Homework 18

The following problems are from pages 184-189 of ADM
Problem Notes Grading
5-2 Note: Your book may have a typo. There should be edge (H,F) and not edge (F,H). 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. Computational Problem Rubric
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. In other words, your answer should be something like "this is equivalent to the Travelling Salesman problem". Algorithm Rubric
5-26 Part (a) is not too hard. Part (b) may require some more thought. Algorithm Rubric

Homework 19

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

The following problems are from pages 227 of ADM
Problem Notes
6-5
6-6 See the new Algorithm Rubric
6-17

Homework 21

Problem
A
8.5
Pick one: 8-10, 8-16c, 8-17, 8-25

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. (Hint: The input consists of n integers, so let's use n as the size of the input. Now you just need to think about what M can be.)

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 22

Complete the Data Structures and Algorithms Catalog. That document tells you just about everything you need to know.
Submit a PDF or docx file using Webhandin using assignment 255-HW22 (Use your 1Hope username/password).
The purpose of this assignment is to help you review all of the data structures and algorithms you have learned about from this and previous classes (primarily CSCI 235). In addition, the "catalog" component of the assignment should help you organize the algorithms in a way that makes sense to you.
Grades will be based primarily on completeness and correctness (but see below).
Note: This will be graded by spot checking parts of it and looking at more detail at other parts. I am telling you this because if the final exam is open book/notes, I want to make sure that you know that you are responsible to know whether or not all of the details in your catalog are correct.
Note #2: Submit this by Thursday if you want comments for Friday. Otherwise the deadline is being extended to the final exam period (Tuesday at 12:30). I will not be assigning a grade if you submit it Thursday so make sure you resubmit it before the exam if you make changes.