The Assignments

The text has three types of problems: R problems (which stands for Reinforcement), C problems (Creativity) and P problems (Programming). I generally like the C problems since they require some thought. Some of these problems are easy, some take some thinking. The idea here is to spend a reasonable amount of time thinking about a problem. That is, don't spend four hours on a problem. If you've given it some good thought and a solution is not forthcoming, then come to me or one of your classmates for help. And yes, you can solve these together, though each of you must write up your solution on your own, and you are each responsible for knowing these on quizzes and exams.

• Chapter 1:
  
  • R: 1.2, 1.10--1.14, 1.18
  • C: 1.5 (there is a typo in the problem: the "1 if n=1" should read "3 if n=1"), 1.8, 1.9, 1.16,1.25, 1.29, 1.30.
  • Prove parts 3,5,6,7, and 8 of Theorem 1.7 on page 15 in the text. You must use the formal definition of Big-Oh for these proofs. Hint: for parts 6 and 8, it helps to use calculus.
  • Show that the sum from i = 1 to n of i^2 is exactly (n(n+1)(2n+1))/6
    
• Chapter 2:
  • R: 2.4, 2.6, 2.11, 2.15
  • C: 2.4, 2.10, 2.28, 2.30, 2.31, 2.32
    
• Chapter 3:
  • R: 3.2, 3.3,
  • C:
    
• Chapter 4:
  • R: 4.5, 4.14, 4.15
  • C: 4.4, 4.10, 4.11, 4.14, 4.16, 4.22
    
• Chapter 5, Section 1:
  • R: 5.1, 5.2
  • C: 5.1, 5.2, 5.5,
    
• Chapter 5, Section 2:
  • R: 5.4, 5.7, 5.8
  • C: 5.6, 5.7,
    
• Chapter 5, Section 3:
  • R:
  • C: 5.9, 5.12, 5.13
    
• Chapter 6 (pre DFS, BFS)
  • R: 6.2
  • C: 6.1, 6.5, 6.6, 6.9, 6.12, 6.18
    
• Chapter 6 (post DFS, BFS)
  • R:
  • C: 6.11, 6.13, 6.17,
    
• Chapter 7
  • R:
  • C: 7.1, 7.3, 7.5, 7.7, 7.8
    
• Chapter 13, Sections 1-3:
  • R: 13.1, 13.7, 13.9, 13.10, 13.12
  • C: 13.1, 13.8, 13.10
    
• Chapter 13, Sections 4-5:
  • R: 13.21, 13.22
  • C: 13.4,13.12-13.15, 13.19
    

     

• Programming Project 1: Convex Hull. I have provided the class files for a working convex hull application as an example of what your project should do in this jar file containing the classes for Convex Hull. It's got a bunch of other things it is as well, some of which are needed, some not. In the interest of time I just packed everything in together. So, unpack the jar file (jar works just like tar, so unpacking means using the command jar -xvf convex_hull.jar and then run the class ConvexHull. This assignment is due at 11:59:59pm on Wednesday, January 30.
  
  
• Here is the Swing code I promised: SwingShell.java, CanvasPanel.java. You can just modify these when writing your code (so the ``empty hands policy'' does not apply to these or any other files I give you.)
  

• Here is the form I use to grade your programs! test once more