CSCI 255 Fall 2022
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)
    Remember that you should try to find the most efficient algorithm you can.
    Write your code in the following Java file (which also has tests): SecondSmallest.

    Submit SecondSmallest.java using WebHandin 255-HW3

  3. AIDMA Problem 3.14 part (c) (page 73)
    Go to the RoundIt code and download both files. Create a package stuffFor255 and put the files in that package in Eclipse. Implement the method roundDivision in the RoundIt class. The other class is for testing purposes (It is a JUnit test).

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

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

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.

Homework 6

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

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 and simplify 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, simplify it, 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, 10 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)
    • This algorithm is probably best specified using pseudocode.
    • Assume the input to your algorithm is an array int a[] of coefficients a0 through an and the value x0.
    • 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) (8 points)
    1. This algorithm is probably best specified using a short description and not pseudocode.
    2. In this problem there is a scale that gives the weight of a single pile of coins. It does not compare two piles.
    3. 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.
    4. 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) (4 points)
  4. IDAA 3.4 #10 a, b, c and additional question below (page 121) (20 points)
    • This problem uses several concepts from the first half of the course, especially from chapters 6 and 9.
    • 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. Also, this is probably done best with a short description rather than pseudocode.
    • 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. This algorithm should be given using pseudocode.
  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. Finally, don't overthink about the average number of comparisons for sequential search. Just assume the character is equally likely to be anywhere in the array, so on average it should be at/near the center of the array, right? If so, the average number of comparisons should be easy to determine.
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. You should definitely give a paragraph description of your algorithm for this one.
  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) (6 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 (paragraph form is probably better for this one). 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. This problem (based on 8.1): (5 points)
    Solve this instance of the coin row problem: 6, 2, 3, 9, 11, 8, 5
  2. IDAA 8.2 #1 (page 296) (8 points)
    As with the rest, show all of your work!
  3. 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.)
  4. IDAA 8.4 #7 (page 312) (5 points)
    Show all of the intermediate matrices.
  5. 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.