Reading Assignments, Discussion Questions, and Programming Projects will be listed here in chronological order, i.e., with the most recent ones at the bottom of the list.

All reading assignments are from the textbook, Java Software Structures by Lewis and Chase, unless specified otherwise.

Jump directly to Week 1 | Week 2 | Week 3 | Week 4 | Week 5 | Week 6 | Week 7 | Week 8 | Week 9 | Week 10

This document was last modified on November 17, 2008.

CS 210 Home Homework Labs Syllabus Bibliography

• Reading Assignment for Monday -- Binary Trees
  • Read Chapter 12 through Section 12.3 (pp. 361 - 371).
  • Read through the Binary Tree Lab.

• Reading Assignment for Wednesday -- Implementing Binary Trees, Expression Trees
  • Read the rest of Chapter 12 (pp. 371 - 391).

• Discussion questions for Wednesday:
  • Analysis questions ("Inside or Outside?") from the Binary Tree Lab.
  • Determine how your implementation of NQueens would be different if you used a stack to keep track of which queens had already been placed on the board.
  • Under what conditions is merge sort better than insertion sort? When is insertion sort a better choice?
  • Under what conditions is quicksort a good choice of algorithm? Under what conditions is it a poor choice?
  • A stable sort is defined as a sorting algorithm that preserves the original order of duplicate objects. Which of the sorting algorithms that we studied are stable sorts?

• Discussion questions for Friday:
  • See DQs from Wednesday!
  • Check if the quicksort algorithm is stable by tracing the code on pages 352 - 353 to sort the following list: 7 5 10 12 3 10 8 2 10.

• Binary Tree Programming Assignment (due Wednesday of Eighth Week)
  • Complete the Binary Tree Lab. Create a junit test class to test your BinaryTree methods. You may use the hints for creating a junit test if necessary. Hand in your modified version of the BinaryTree class, your two new visitor classes (the summing visitor and ExtremeValueCalculator, and your junit test class. 

• Reading Assignment for Monday -- Binary Search Trees (BST's)
  • Read Chapter 13 up to 13.3 (pp. 395 - 409).
  • Read the introduction to the BST Lab (everything before the beginning of the actual mini-lab).

• Reading Assignment for Wednesday -- Balanced Binary Search Trees (BST's)
  • Read Sections 13.4 - 13.6 (pp. 410 - 423). You will not be responsible for implementing rotations, but you should have a good sense of the issues involved.
  • If you want to experiment with AVL and Red-Black trees, there are several applets that allow you to insert, delete, and search these trees: www.site.uottawa.ca/~stan/csi2514/applets/avl/BT.html and webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm.

• Reading Assignment for Friday -- The Map Interface; TreeMap and TreeSet
  • Read Section 13.7 (pp. 423 - 426).

• BST Programming Project (due Wednesday of Ninth Week)
  Complete the BST Lab. Hand in your BST and BSTLab classes.

• Looking Ahead:
  Your Final Programming Project will be due on or before the Final Exam day.

• Reading Assignment for 9th Week -- Hashing
  • Read Chapter 17 (pp. 515 - 539).

  • Read through the Final Programming Project.

• Discussion Questions for Wednesday:
  • Test the following code segment to determine what gets printed:
    TreeMap m = new TreeMap();
    m.put(new Integer(12345),"John");
    m.put(new Integer(23456),"Sue");
    m.put(new Integer(12543),"Adam");
    m.put(new Integer(32145),"Nathan");
    m.put(new Integer(14352),"Kay");
    Set pairs = m.entrySet();
    Iterator itr = pairs.iterator();
    while (itr.hasNext())
    
    System.out.println(itr.next());

  • Change the code above to use a HashMap instead of a TreeMap. What output do you get?

  • Think about the Data Structures we have studied so far. Since the HashMap allows us to add, remove and search for objects in constant time, why would or wouldn't this be our "ultimate" data structure? Would there be other times/reasons we would want to use other structures? Some examples?

  • Answer the design questions from the Final Programming Project.

• Discussion questions for the rest of the week (to be discussed Monday, Week 10):

  • Exercises 17.1 and 17.5 on p. 541 of Lewis and Chase.
  • Consider implementing a class, HMUnboundedEnv, that uses a hash map for its internal representation. (See Exercise 6 on p. 104 of the MBS case study). What methods would change in UnboundedEnv and how?

Looking Ahead:

• Final Programming Project (due on or before the Final Exam day)
  Implement the BLAST Project. This contains a possible design and some files to get started with the implementation. You may choose to use your own design.

Week 10:

• Reading for this week:
  The assignment for this week is to review the material from this quarter and take the review exam.

• Discussion questions for the rest of this week:
  • Any questions you want answered concerning this course.

Jump directly to Week 1 | Week 2 | Week 3 | Week 4 | Week 5 | Week 6 | Week 7 | Week 8 | Week 9 | Week 10

This page is maintained by Alyce Brady (abrady{at}kzoo{dot}edu) and Pamela Cutter (pcutter{at}kzoo{dot}edu). It was last modified on November 17, 2008 .