|
| All HomeworkComments for all assignments
- Most problems are found in one of the following:
- ADM: The Algorithm Design Manual
- 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 1The following problems are from pages 27-30 of ADM.
Homework 2The following problems are from Chapter 1 of IDMA on pages 11-12.
Homework 3Problems are from Chapter 2 of IDMA on pages 31-34.
Homework 4Problems are from Chapter 3 of IDMA on pages 69-74.
Homework 5Problems are from Chapter 3 of IDMA on pages 69-74.
Homework 6Problems are from Chapter 3 of IDMA on pages 69-74.
Homework 7Problems are from Chapter 4 of IDMA on pages 93-95.
| Problem
|
|---|
| 297
| | 298.2
| | 304
| | 307 |
Homework 8The 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 9The 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 10The 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 11The 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) + n3, T(1)=1
- T(n) = T(n - 1) + n, T(1)=1
Homework 12The 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 13For 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 14The 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 15The 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 16The 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 17The 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 18The 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 20The following problems are from pages 227 of ADM
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.
|