CIS121-204 Fall 2007
Recitations: Tuesdays, 3-4PM, Moore 100A

Staff Information

Recitation Leader: Chinawat Isradisaikul (Chin)
E-mail: chinawat@seas.upenn.edu

Announcements

Office Hours

- Sundays 7-9PM, Moore 100A
- By appointment

Schedule/What We Have Done

Date What's Up?
12/04/2007 Last Meeting
- Course Evaluation
- Quick review of graph terminology
- Finding single-source shortest path on an unweighted directed graph [Lab 12]
- Lab 12 PowerPoint
- Thanks for the good time we had this semester. :)
11/27/2007 Java Dictionary ADT Interfaces: Map, SortedMap, Set, SortedSet [Lab 11]
  • HashMap implements Map. It uses a hash table with separate chaining to handle collisions.
  • TreeMap implements SortedMap. It uses a Red-Black tree, which is a balanced binary search tree.
Set is a special case of Map where keys are identical to values.
SortedSet is a special case of SortedMap where keys are identical to values.
  • HashSet implements Set.
  • TreeSet implements SortedSet.
Use Map (Set) when you want a fast access. Use SortedMap (SortedSet) if the ordering of the keys is crucial. For example, use a TreeSet to store grades when you want to list the grades in order from highest to lowest; use a HashSet when you just want to look up whether a grade exists in the collection.
11/20/2007 Project Discussion
11/13/2007 Review for Midterm 2
11/06/2007 Quick Review of Tree Traversals: Preorder, Postorder, Breadth-first, Inorder (for binary trees)
Binary Heap [Lab 8]
- Heap operations: add, removeRoot
- add
  • Add the new node as the last node in the heap (so the tree remains complete, but it might not be a heap anymore).
  • Bubble the new element up until the tree is a heap, i.e., the heap-order property is satisfied.
- removeRoot
  • Instead of physically remove the root, we replace the value of the root by the value of the last node.
  • Delete the last node.
  • Bubble the value at the root down until the tree is a heap.
Lab 8 Implementation
- Use this declaration for BinaryMinHeap: public class BinaryMinHeap<E extends Comparable<? super E>> implements BinaryMinHeapI<E>
- How to keep track of the last node?
  • In case of add,
    • If lastNode is the left child of its parent, then lastNode's parent is the parent of new lastNode, and new lastNode is the right child of its parent.
    • If lastNode is the right child of its parent, then
      • Go up the tree until we find the node at which we branch left.
      • Go to the right child of this node.
      • The leftmost node of this subtree is the parent of new lastNode, and new lastNode is the left child of its parent
      • If we cannot find the node at which we branch left, then the leftmost node of the tree is the parent of new lastNode, and new lastNode is the left child of its parent
  • In case of removeRoot, the algorithm is the reflection of one for add:
    • If lastNode is the right child of its parent, then new lastNode is the left child of lastNode's parent.
    • If lastNode is the left child of its parent, then
      • Go up the tree until we find the node at which we branch right.
      • Go to the left child of this node.
      • New lastNode is the rightmost node of this subtree.
      • If we cannot find the node at which we branch right, then new lastNode is the rightmost node of the tree.
- Use this JUnit test file to preliminarily test your heap: TestHeap.java
- Use this Symbol class to avoid warnings (in case you want to implement Huffman encoding): Symbol.java
10/30/2007 Linked Structures [Lab 7]
- Time complexity of each list operation
- Stack and Queue: Time complexity of each operation
- Appending two lists: analyzing running time
- Solution to Lab 7
10/23/2007 Getting to know Eclipse: a powerful Java IDE [Lab 6]
  • Some definitions:
    • Workspace: folder for the projects to be saved; can switch workspace in the File menu.
    • Project: collection of files related to each other somehow--simple sense of the word
    • Perspective: look and feel (and of course functionality): Java for implementation, Debug for debugging (for sure)
  • Easy tasks:
    • Create a new project/class/interface/etc.
    • Import existing classes.
  • Moderate tasks:
    • Run a class with a main method
    • Debugging: breakpoints, conditional breakpoints, stepping, variable watches
  • Incredible tasks: refactoring
    • Change variable names without pressing Ctrl+H or call Replace.
    • Change method signatures such that you don't need to do it for every invocation of that method.
  • Features: autocomplete, autocompile, autoformat, autoindent, autodebug (last one just kidding)
Good for a big project, such as our upcoming project. :)
10/16/2007 No Meeting: Fall Break
10/09/2007 Review for Midterm 1
10/02/2007 Mathematical Induction and Big-O Notation (continued)
- Proving equalities is usually easier than proving inequalities.
How to determine Big-O in a given algorithm?
- Take the advantage of Big-O: insignificant terms don't matter; constants don't matter.
- Use summation to calculate the running time of the loop.
- Supplementary Document
09/25/2007 Mathematical Induction and Big-O Notation
- Induction is quite similar to trying to fall a sequence of dominos.
- Big-O is mostly used in analyzing complexity of algorithms.
- To prove that f(n) is O(g(n)), we just need to find a constant c and a natural number N such that the condition in the definition holds, whether they be an explicit number or in terms of some other variables.
- To prove that f(n) is not O(g(n)), we usually prove by contradiction.
- Solution to Lab 3
09/18/2007 Counting exact number of steps in code snippets.
- Need to count primitive operations right:
  • assignment
  • arithmetic operation
  • comparison
  • array indexing
  • method invocation
  • return from procedure
  • object referencing
- Need to count the number of iterations in each loop right.
- Consider the worst case for if statements.
- Sometimes parts of the code never execute!
- Solution to Lab 2
09/11/2007 First Meeting
- Icebreaker and Introductions
- Basic Unix Tutorial: 
ls, pwd, cd, mkdir, rmdir, mv, cp, rm, man, whoami, hostname, less, more
- Java and Code Repetition [Lab 1]

Valid HTML 4.01 Transitional
Updated: 12/04/2007