CSCI 255 Fall 2017
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 385
MATH 160
Others
Admin

All Homework

Homework 1

5 points each

  1. IDAA 1.2 #3. For each part, explain why it is or is not an algorithm.
  2. IDAA 1.3 #5 (You may photocopy that page in the book if you wish)
  3. IDAA 1.4 #10 (It is probably easiest to give an informal, but clear and complete, description of an algorithm instead of using pseudocode.)
  4. AIDMA Problem 10.2.

Homework 2

5 points each

  1. AIDMA Problem 2.1
  2. AIDMA Problem 2.4

Homework 3

5 points each

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

Homework 4

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

Homework 5

  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 6

  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 7

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 8

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 9

Read the section and problem numbers carefully!

  1. IDAA 2.2 #12. Give a clear description of your algorithm and prove that it requires at most O(n) steps. (10 points)
  2. IDAA 2.3 #6 (10 points) (Work out the exact number for part b)
  3. IDAA 2.3 #11. 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. (6 points)

Homework 10

  1. AIDMA Problem 8.1 (10 points)
  2. AIDMA Problem 8.7 (10 points)

Homework 11

10 points each

  1. AIDMA Problem 8.8 a
  2. AIDMA Problem 8.8 e
  3. AIDMA Problem 8.12

Homework 12

10 points each

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

Homework 13

  1. AIDMA Problem 9.19 (6 points)
  2. AIDMA Problem 9.22 (6 points)
  3. AIDMA Problem 9.25 a, c, d, g (8 points)

Homework 14

Update me!

  1. IDAA 3.1 #4 (page 102) (10 points) (Hint: Read part b before you do part a)
  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 #3 (page 106) (5 points) (Hint: It can be done in O(√n) time) Bonus problem in the future? If so, no hint.
  4. IDAA 3.4 #7 (page 121) (5 points) As always, don't forget to analyze your algorithm.
  5. Just assign 3.5 #6 in the future. Choose either IDAA 3.5 #6 or #8 (page 129) (5 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). 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. (10 points)
  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). 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. (5 points)
  5. Bonus in future? IDAA 4.5 #13 (page 167). (5 points) This is not a yes-no question. It is asking you to design an algorithm. Be careful because it is easy to make false assumptions about what the data looks like.
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

  • IDAA 5.1 (Remove #9 in the future) #9 or #11 (page 175). (5 points) Give a very clear and concise description of your algorithm and don't forget to give an analysis of your algorithm.
  • 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. Don't forget to justify why your algorithm is O(n log n)
  • 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.
  • 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) 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.2 #2 (page 216) (5 points) Read carefully and notice which technique it is asking you to use. Also, the solutions are integers, so you if don't get integers you have made a mistake somewhere.
    3. IDAA 6.4 #6 (page 233) (15 points) In case it isn't clear, the three operations are insert, deleteMax, and getMax. Give your solution in a nicely formatted table.
    4. This problem: 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. (10 points)

    Homework 18

    1. IDAA 7.2 #2 (page 267) (6 points) Show all of your work!
    2. IDAA 8.1 #2 (page 290) (5 points) Use the algorithm given in the book and show your work.
    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?
    5. IDAA 8.4 #7 (page 312) (5 points) Show all of the intermediate matrices.
    6. This problem: 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. (6 points)
        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? (2 points)
      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. (2 points)

    Homework 19

    1. IDAA 9.1 #9(b) (page 324). 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 photocopy that page from the book if you wish). Finally, give the weight of the minimum spanning tree. (10 points)
    2. IDAA 9.2 #1(b) (page 331-332). 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 photocopy that page from the book if you wish). Finally, give the weight of the minimum spanning tree. (10 points)
    3. IDAA 9.4 #1 (page 342). 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. (10 points)