CSCI 255 Fall 2018
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

5 points each

  1. AIDMA Problem 2.1
  2. AIDMA Problem 2.4

Homework 2

5 points each

  1. AIDMA Problem 2.6
  2. AIDMA Problem 2.11ab
  3. AIDMA Problem 2.17
  4. AIDMA Problem 2.18

Homework 3

  1. AIDMA Problem 3.1(10 points)
  2. AIDMA Problem 3.7 c (10 points)
  3. AIDMA Problem 3.9 (5 points)

Homework 4

  1. AIDMA Problem 4.4b (4 points)
  2. AIDMA Problem 4.7 (8 points)
  3. AIDMA Problem 4.17 a and b (4 points)

Homework 5

  1. AIDMA Problem 5.3 b (10 points)
  2. AIDMA Problem 5.5 (6 points)
  3. AIDMA Problem 5.8 (6 points)
  4. AIDMA Problem 5.19 (10 points)

Homework 6

5 points each

  1. AIDMA Problem 6.4
  2. AIDMA Problem 6.5
  3. AIDMA Problem 6.6 h
  4. AIDMA Problem 6.6 i
  5. AIDMA Problem 6.9
  6. AIDMA Problem 6.15

Homework 7

10 points each

  1. AIDMA Problem 7.3
  2. AIDMA Problem 7.4
  3. AIDMA Problem 7.10 m (Work out the exact value of the summation(s) and then give a bound)
  4. AIDMA Problem 7.16

Homework 8

  1. AIDMA Problem 8.1 (10 points) (Submit on the due date)
  2. AIDMA Problem 8.7 (10 points) (Submit when the next assignment is due.)

Homework 9

  1. AIDMA Problem 8.8 a (10)
  2. AIDMA Problem 8.8 e (10)
  3. AIDMA Problem 8.14 (15)

Homework 10

10 points each

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

Homework 11

  1. AIDMA Problem 9.3 (5 points)
  2. AIDMA Problem 9.19 (6 points)
  3. AIDMA Problem 9.22 (6 points)
  4. AIDMA Problem 9.24 (8 points)

Homework 12

10 points each

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

Homework 13

10 points each

  1. Algorithms 1.9 (page 39). The "also the corresponding rule for multiplication" means to also show that xy=x'y' mod N given the same assumptions. Also, N divides x-y means (x-y)=kN for some integer k. Use this definition in your proofs
  2. Algorithms 1.18 (page 40). Show all of your work!
  3. Algorithms 1.25. They don't mean things like Wolfram Alpha. Do it using a standard calculator and some algorithm that does it with far fewer than 124 multiplications. In fact, use some version of a binary exponentiation algorithm (like we did in class). Show all of your work!
  4. Algorithms 1.27. Show/explain your work.

Homework 14

  1. Algorithms 2.1 (10 points). You should use the algorithm with Gauss's trick and you should do recursive calls until n<=3 at which point you can compute those products in the normal way. Show all of your work!
  2. Algorithms 2.4 (10 points). Give and solve recurrence relations for each algorithm. You may use the Master Method/Theorem. You may also assume that each algorithm takes constant time for inputs of size 1. Josiah thinks you might need a result from page 281 of AIDMA (the discrete math book) for one of them, but I just worked them all out and I didn't need it (two of them are straightforward, one required a little effort, but it was one we have seen before so it wasn't that bad).
  3. Algorithms 2.14 (10 points). Give a clear and complete description of your algorithm. For this algorithm, you should probably give a description of the steps rather than trying to write Java or pseudocode. You may use algorithms we have already seen in this course or previous courses without giving the details (e.g. you can say "Use binary search to find the value k" without giving the algorithm. Although you probably shouldn't say exactly that because binary search won't help on this problem.) Make sure you justify that it's complexity is O(n log n).

  4. (10 points) Implement the modulus binary exponentiation algorithm. You may not use any of the Java libraries (e.g. Math.pow) and there is no need for any data structures (e.g. array, ArrayList, HashMap, etc.). The best implementation should only require a few extra variables. You can use all of the standard operations, including the mod operator (%).

    Here are the relevant files:

    Submit just ModPower.java using WebHandin 255-HW14. You should receive an e-mail with your test results. You must write your own code for this! Do not find a solution online. Please please do this on your own. I will penalize you heavily if you obtain your code from elsewhere and you do not specify so. (Recall that if you get really stuck you can get help online, but for up to half credit and you MUST specify that you did so, including the source. And you must make it clear that you understand the solution.)

Homework 15

  1. (10 points) Algorithms 3.2 b
  2. (10 points) Algorithms 3.3
  3. (10 points) Algorithms 3.11. This one is not too difficult if you use one or more of the algorithms described in this chapter. Make sure you justify the fact that it has the desired complexity.
  4. (12+4 bonus) Algorithms 3.28.
    • Be very careful with part (c) since it is really easy to interpret it wrong and/or make a mistake while constructing the graph.
    • (d) and (e) are a bit more difficult and will require some thinking, so they are bonus problems.
    • (f) can be done if you assume the results of (d) and (e) are correct even if you can't complete those parts.
    • (f) is asking you to describe the algorithm and justify that the complexity is linear.

Homework 16

Each problem is worth 10 points.

  1. Algorithms 4.1. Show all of the relevant details!
  2. Algorithms 4.2. Start from S. Also, they mean to show the intermediate steps and draw the final shortest-path tree. As always, show all of the relevant work.
  3. Algorithms 4.4. Give a graph and an explanation of why the proposed algorithm will fail on the graph. (Hint: I think my counterexample has 5 or 6 nodes.)
  4. Algorithms 4.5. Explain how to supplement/modify and existing algorithm. Justify that your algorithm is linear time.
  5. Algorithms 4.10. Do not make this one harder than it is. You should be able to describe an easy change to an existing algorithm to accomplish this. Clearly explain why the algorithm works and why the complexity is θ(k|E|).

Homework 17

  1. (20) Algorithms 5.2. Read carefully and show everything out asks you to show!
  2. (10) Algorithms 5.14. As usual, show your work.
  3. (10) Algorithms 5.16. Pick either (a) or (b) and do your best to give a clear proof for whichever one you choose. (To be clear, the frequencies of the letters add up to 1 in this problem. Think of it meaning the proportion or percentage of total letters.)
  4. (5) Algorithms 5.17. Your example set of frequencies should be generalized so it has n frequencies (rather than an example with n=4, for instance).