CSCI 255 Fall 2020
Introduction to Algorithms and Discrete Structures		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

  1. AIDMA Problem 2.1 (page 45)
  2. AIDMA Problem 2.4 (page 45)

Homework 2

  1. AIDMA Problem 2.6 (page 45)
  2. AIDMA Problem 2.11 (page 45)
  3. AIDMA Problem 2.19 (page 46)

Homework 3

  1. AIDMA Problem 3.1 (page 72)
  2. AIDMA Problem 3.10 (page 73)
  3. AIDMA Problem 3.14 part (c) (page 73)
    Your code should be in a Java Class as follows (Package is important!): 
    package stuffFor255;
public class RoundIt {
    public int roundDivision(int n, int m) {
        // Implement your algorithm here and have it
        // return the correct answer instead of -1.
        return -1;
    }
}

    Submit RoundIt.java using WebHandin 255-HW3

    NOTE: If your code is significantly broken (e.g. crashes or has an infinite loop) please rename the class/file to RoundItBroken.java before handing it in so that you do not break the autograder. (It will not run the tests properly, but I will still be able to run them by hand and look at your code.) (Actually, ignore that comment. I forgot to turn on the autograder.)
The rest of your answers should go in the HW Google Doc as usual.

Homework 4

  1. AIDMA Problem 4.12 (Page 123, 12 points).
    Make sure you only use the allowed operation on parts c and d. You can only use the NOR operator. You can't use AND, OR, NOT, or anything else. Hint: Experiment with some truth tables until you discover the correct way to do each of these.
  2. AIDMA Problem 4.23 a and b (Page 126, 6 points).
  3. Problem removed. AIDMA Problem 4.25 b (Page 127, 6 points).
    Make sure you use the procedure indicated in the exercise!

Homework 5

  1. AIDMA Problem 5.3 b (Page 177, 10 points)
    Make sure you use a set containment proof as required!
  2. AIDMA Problem 5.5 (Page 177, 6 points)
  3. AIDMA Problem 5.8 (Page 178, 6 points)
    Hint: You need to show two things.
  4. Problem removed. AIDMA Problem 5.19 (Page 179, 10 points)
    Hint: You need to prove 3 things. Once you understand what you need to prove, it should be pretty straightforward. Also, don't forget to answer the final question (Give the equivalence classes).

Homework 6

5 points each

  1. AIDMA Problem 6.5 (page 213)
  2. AIDMA Problem 6.6 h (page 213)
    Begin by doing some algebra.
  3. AIDMA Problem 6.6 i (page 213)
    Be very careful on this one—there are a lot of places to potentially make errors. But overall it is pretty straightforward.
  4. AIDMA Problem 6.18 (page 215)
  5. Problem removed. AIDMA Problem 6.14 (page 214)

Homework 7

10 points each

  1. AIDMA Problem 7.3 (Page 288)
  2. AIDMA Problem 7.4 (Page 288)
  3. AIDMA Problem 7.10 m (Page 290)
    Note: Work out the exact value of the summation(s) and then give a tight bound. You need to be careful on this one because it is a little tricky.
  4. AIDMA Problem 7.16 (page 293)
    Hint: What makes the algorithm different for an ArrayList verses a LinkedList? Also, justify your answers! (Not a full "proof" required, but explain your answers.)

Homework 8

Read the section and problem numbers carefully!

  1. IDAA 2.3 #6 (Page 68, 10 points)
    Do all of the parts (a-e). Work out the exact number for part c
  2. IDAA 2.3 #11 (Page 69, 6 points)
    For part a, find an exact formula for the number of basic operations and then give a bound. For part b, it is possible to improve the algorithm by decreasing the constant factors involved in the computation, but you won't be able to change the complexity class.

Homework 9

  1. AIDMA Problem 8.1 (Page 354, 10 points) (Submit on the due date)
  2. AIDMA Problem 8.9 (Page 354, 10 points) (Submit next class period)
    The hint is telling you that 1+(1±sqrt(5))/2=[(1±sqrt(5))/2]2. It's up to you to figure out why this is helpful.

Homework 10

  1. AIDMA Problem 8.11 a (Page 354, 10 points)
    Remember to solve it in two different ways.
  2. AIDMA Problem 8.11 e (Page 354, 10 points)
    Remember to solve it in two different ways.
  3. AIDMA Problem 8.17 (Page 356, 15 points)
    Note that you cannot use multiplication/addition anywhere in your code. And there is no method to compute powers or squares of numbers. You have to somehow compute that using only increments.
NOTE: The Master Method does not apply to at least one of the problems on this assignment. Remember to only use it if it is a recurrence of the proper form.

Homework 11

10 points each

  1. AIDMA Problem 9.4 (Page 392)
  2. AIDMA Problem 9.14 (Page 392)
  3. AIDMA Problem 9.33 (Page 396)
    Give and prove the efficiency of your algorithm.

Homework 12

  1. AIDMA Problem 9.3 (Page 392, 6 points)
  2. AIDMA Problem 9.19 (Page 393, 6 points)
  3. AIDMA Problem 9.22 (Page 393, 6 points)
  4. AIDMA Problem 9.25 a, c, d, g (Page 394, 8 points)

Homework 13

10 points each

  1. AIDMA Problem 10.2 (Page 427)
  2. AIDMA Problem 10.3 (Page 427)
    Hint: Label the vertices as in Example 10.42 and think about how to choose which vertices should go in each partite set based on the label.
  3. AIDMA Problem 10.16 (Page 427)

Homework 14

  1. IDAA 3.1 #4 (page 102) (10 points)
    Hint: Read part (b) before you do part (a). Also, make sure to justify your answer to part (c))
  2. IDAA 3.1 #7 (page 103) (5 points)
    Hint: In this problem there is a scale that gives the weight of a single pile of coins. It does not compare two piles. For part a, read the problem carefully--it is asking for a brute force algorithm. Second, the complexity of your algorithm is the number of weighings you need to do.
    Let me clarify part (b). This is asking for a SECOND algorithm, not for an analysis of your first algorithm. It is really asking you to come up with the most efficient algorithm possible to solve the problem. When it says "minimum number of weighings", it is not implying that you might get lucky and get it with a small number of weighings. It is saying what is the minimum number so that no matter what you determine the proper pile. Getting this part correct requires a very careful reading of the problem!)
  3. IDAA 3.2 #4 (page 107) (5 points)
  4. IDAA 3.4 #10 a, b, c and additional question below (page 121) (20 points)
    Hint: Part (a) should be pretty straightforward. For part (b), remember that you are trying to find an exhaustive search algorithm, so do not try to be too clever. Do the obvious. For (c), make sure you give your source!
    Additional question: Instead of (d), give the complexity of the two algorithms from parts (b) and (c) and compare them.
  5. IDAA 3.5 #6 (page 129) (10 points)
    You don't have to give the full algorithm as long as you clearly say how to modify BFS/DFS to do the required task. For instance, you can say "whenever BFS does such-and-such, have it also do this-and-that." But make sure your description is clear and unambiguous.
Important Reminders:
  • Give a clear description of your algorithms. You may give code/pseudocode, but you must also include a short description of the algorithm since it is usually very difficult to determine what an algorithm is doing from code alone.
  • Don't forget to give and justify the complexity of your algorithms.
  • Remember to give the most efficient algorithm possible. If there is a more efficient algorithm, you will likely lose some points.
  • This book has hints in the back for many of the problems. Use them as needed.
  • Tip: Always make sure you test your algorithms on several reasonable inputs to convince yourself they are correct.

Homework 15

  1. IDAA 4.1 #5 (page 137) (5 points)
    Note: The line that reads "if(A[n-1,j])" should be interpreted like it was written in C/C++. In other words, it means "if(A[n-1,j]==1)". Read the algorithm very carefully and try it out on a few graphs. If the algorithm is not correct, show a sample graph for which it gets the wrong answer and explain why it is wrong.
  2. IDAA 4.2 #1 (page 142) (10 points)
    Assume adjacency lists are in alphabetical order and start from vertex a. Make sure you show all of the necessary work and don't forget to give the topological sort in each case.
  3. IDAA 4.4 #2 (page 156) (5 points)
    Hint: Think about the relationship between the number of bits in the binary representation of n and what you need to compute. Then consider how a decrease-and-conquer strategy might be useful. Also, there is no log function for you to call. You need to do it with just basic integer arithmetic.
  4. IDAA 4.4 #4 (page 156) (5 points)
    Make sure you clearly explain your calculation(s). Your final answer should be something like "binary search is X times faster than sequential search", NOT something like "it takes X more steps". If you don't understand the difference between these statements, please ask me for clarification.
Important Reminders:
  • Give a clear description of your algorithms. You may give code/pseudocode, but you must also include a short description of the algorithm since it is usually very difficult to determine what an algorithm is doing from code alone.
  • Don't forget to give and justify the complexity of your algorithms.
  • Remember to give the most efficient algorithm possible. If there is a more efficient algorithm, you will likely lose some points.
  • This book has hints in the back for many of the problems. Use them as needed.

Tip: Always make sure you test your algorithms on several reasonable inputs to convince yourself they are correct.

Note: These reminders and tips will not appear on future assignments but they will still apply.

Homework 16

  1. IDAA 5.1 #11 (page 175) (5 points)
    Give a very clear and concise description of your algorithm.
  2. IDAA 5.2 #11 (page 182) (5 points)
    Read the problem description carefully to make sure you understand what you can and cannot do! You may modify an existing algorithm. If so, you may just explain (very clearly!) how to modify that algorithm. Make sure your algorithm is clear and complete. Don't forget to justify why your algorithm is O(n log n)
  3. IDAA 5.3 #5 (page 185) (6 points)
    The tree is on the next page. The result of a traversal should be a list of the nodes in some order.
  4. IDAA 5.4 #7 (page 192) (5 points)
    Show all of your work! This problem is tedious, but it should be straightforward. You should compute the product in the "normal" way to check your answer.

Homework 17

  1. IDAA 6.1 #2 (page 205) (10 points)
    Note: Read carefully. The arrays have different sizes. Keep in mind that the goal for part b is to be as efficient as possible. Make sure your algorithm description is clear and unambiguous. Don't forget to analyze your algorithms!
  2. IDAA 6.3 #7a (not b) (page 226) (10 points)
    Show enough work so it is clear how the final tree was obtained. (In other words, show the intermediate trees.)
  3. IDAA 6.4 #6 (page 233) (15 points)
    Give your solution in a nicely formatted table. Also, in case it isn't clear, the three operations are insert, deleteMax, and getMax.
  4. This problem: (10 points)
    Compute
    111329 mod 100
    by hand (That is, you are not allowed to use a calculator, computer, abacus, or any other computational device besides your brain) using one of the binary exponentiation algorithms. Show all of your work. You are permitted to verify that your answer is correct with the use of a computer or calculator. In case it is not clear, you may do all of your intermediate computations modulo 100 and you will still get the same answer. For instance, 11*11=121=21 mod 100, so you can use 21 instead of 121 in the next calculation.

Homework 18

  1. IDAA 7.2 #2 (page 267) (6 points)
    Show all of your work! Be careful because it is easy to make a mistake on this one.
  2. This problem (based on 8.1): (5 points)
    Solve this instance of the coin row problem: 6, 2, 3, 9, 11, 8, 5
  3. IDAA 8.2 #1 (page 296) (6 points)
    As with the rest, show all of your work!
  4. IDAA 8.2 #6 (page 297) (5 points)
    Do I need to remind you to show your work? Also, do not forget to clearly mark the entries that were retrieved without recomputation. (The entries that were never computed will be blank so no need to indicate them other than leaving them blank.)
  5. IDAA 8.4 #7 (page 312) (5 points)
    Show all of the intermediate matrices.
  6. BONUS! This problem: (10 points: 6, 2, 2)
    You can compute C(n,k) (n choose k) using the recursive formula C(n,k)=C(n-1,k-1)+C(n-1,k) with base cases C(n,0)=1 and C(n,n)=1 for all values of n.
    1. For each of the following, specify how much time and space is required (in the worst case) to compute C(n,k) using this formula with the following types of algorithms.
      1. A straightforward recursive algorithm based on the formula.
      2. A recursive algorithm that uses a memory function (or what I call memoization).
      3. A bottom-up approach (i.e. Compute C(1,k) for all valid values of k, then do the same for C(2,k), C(3,k), until you get to C(n,k)).
    2. Which of the options above is the best and why?
    3. Is there a better algorithm than the one based on the formula given above? If so, give it and explain why it is better. (In other words, give the best algorithm you can think of to compute C(n,k)). Be specific and complete with your reasoning.
    Hint: It might help to think of Pascal's Triangle.

Homework 19

  1. IDAA 9.1 #9 (b) (page 324) (10 points)
    Assume the adjacency lists are stored in alphabetical order and start from vertex a. Give the value in the priority queue at every step of the algorithm. Draw the graph and darken the edges of the minimum spanning tree. (you may scan/photocopy that page from the book if you wish). Finally, give the weight of the minimum spanning tree.
  2. IDAA 9.2 #1 (b) (page 331-332) (10 points)
    Show the sets of vertices for every step of the algorithm. Draw the graph and darken the edges of the minimum spanning tree (you may scan/photocopy that page from the book if you wish). Finally, give the weight of the minimum spanning tree.
  3. IDAA 9.4 #1 (page 342) (10 points)
    Be careful to keep the nodes in your tree in the proper order. In other words, follow the algorithm in the book very carefully. Show every step of the algorithm, not just the final tree.