Algorithms Homework Assignments

Due Date Assignment
Wednesday, Jan. 13 Read Sections 1.1 - 1.3; Hand in problems #4, 5, 7, 8, 9 on page 8. For problems #4 and 9a write your algorithm in a pseudocode form similar to that used in the text; for #7, 8, and 9b explain your reasoning.
Friday, Jan. 15 Hand in problem #11 on page 9 (show your reasoning, not just your conclusion), #2 on page 17, #5b and #9 on page 18 (the "standard" algorithm referred to in #5 is where you repeatedly divide by 2), #1 on pages 23-24 (for part (a) show the steps in the trace by, at a minimum, showing the contents of the Count array after each iteration of the outer loop; for part (b) either give your reasons if you answer "stable" or an example to illustrate if you answer "not stable").
Monday, Jan. 18 Hand in re-writes for problems 4, 9a, and 9b if you did not get credit on your first attempt. For 9b, find a formula for the number of integers that can be written down. Show your reasoning in coming up with that forumla. Then use that formula to decide whether or not to go first.
Wednesday, Jan. 20
  1. Do C++ lab 1. Hand in written answers or programs for the questions with three asterisks. Tar your work directory and send it to me in an email.
  2. Re-do problems (if you did not get correct on first try). Page 18, #5b and page 24, #1b (see note above - you need reasons if you say stable and you need an explicit example that you trace the algorithm for if you say not stable).
  3. Page 25, #8 (for part (a), state what the vertices represent and draw the graph, and for part (b) give the coloring; pages 38-39, #4.
Friday, Jan. 22
  1. page 38 #5, 6, 10
  2. Read Section 2.1
  3. pages 50-51, #1, 2, 3, 5, 8, 9
Monday, Jan. 25 page 60 #2, #3 (no proofs need at this point!)
Wednesday, Jan. 27
  1. Page 60, Prove your assertions about big-theta for #3a,b,c,d. For at least two of those use the formal definition (definition 3, page 55) and for at least two use the limit approach. In both cases show your work.
  2. page 60 #5
  3. REDO #4 on page 38 (both parts a and b)
Monday, Feb. 1 REDO #3a, b, d on page 60 (at least one must be a proof using the definition of big-theta, at least one must use limits, the other is your choice - be sure to show work)
Wednesday, Feb. 3
  • Section 2.3 (pages 67 - 68), #1b,c,d,e,f, #2b, 6
  • Lab #2 Programs - send electronic copy in an email.
    • Friday, Feb. 5 Page 67 #3 and 4. Be sure to count all of the operations requested for #3. For #4 you should be able to find an order one algorithm.
    Friday, Feb. 12 Page 76 #1a,b,c
    Monday, Feb. 15 Pages 76 & 77 #1c,d (also a, b, c, if you didn't already do those), #5a, b
    Wednesday, Feb. 17 No homework due
    Friday, Feb. 19 Click here for the 4 recurrence relations to solve.
    Wednesday, Feb. 24
    • Redo #4 and #5a,b on pages 76-77
    • p. 106, # 4, 5, 6
    • p. 112, #2, #6
    • Write the brute force algorithm for finding the convex hull in algorithm form (in a similar format to the textbook).
    Friday, Feb. 26
    • Lab 3
    • Recurrence Relation Exercises (Handout)
    • page 128, #3 and 5 (for #5 use the Master Theorem)
    Wednesday, Mar. 10 Write the algorithms for the divide and conquer solutions to the closest pair problem and the convex hull problem. You should use functions in your solutions but also write the pseudocode for the functions (no need to write pseudocode for standard tasks such as using merge sort to sort points).
    Friday, Mar. 12 No class
    Monday, Mar. 15 Section 5.1 (page 164) #9, 10a,b; Section 5.2 (page 171) #1, 2, 3
    Wednesday, Mar. 24
    • Section 5.2 (page 171) #8
    • Section 5.3 (page 176) #1, 4, 5, 6
    • Write (by hand) code to make a copy of a list in C++ just using the nodes and pointers (no "insert" functions or other functions).
    Friday, Mar. 26 C++ Lab 4 - note that you are to write answers to several questions.
    Monday, Mar. 29 Test Extra Credit
    Wednesday, Mar. 31 Do #8 in Section 5.3. That is, implement the two sorting algorithms in C++ using the adjacency list representation of a graph. You must use appropriate classes (and separate the declarations (put in .h files) from the definitions (put in .cc files)). Details here.

    Section 5.4 #4ac, 5, 6, 7; Section 5.5 #3

    Monday, April 5
    • Rewrite the two algorithms for detecting a bipartite graph (problem #8 in Section 5.2). Be sure to write in algorithm form using the basic DFS and BFS as a basis. You should make it VERY clear when you "color" a node and when you detect that the graph is not bipartite.
    • Do the problems that were due Wednesday if you haven't done them. (see above).
    • Section 5.6 #1, 2, 3 (be sure to write these in algorithm form)
    • Section 7.2, #1 - 4
    Wednesday, April 7 Section 8.2 # 1 - 4
    Monday, April 12 Re-writes (15 points each) of divide and conquer algorithms for the closest pair problem and the convex hull. Details were on the handout from class.
    Wednesday, April 14
    • Rework as much of Test #3 as you wish.
    • Section 8.4, #1, 2, 5
    Friday, April 16 C++ implementation of quick hull (details on handout from class)