- 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. :)
Java Dictionary ADT Interfaces:
Map. It uses a hash table with separate chaining to handle collisions.
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.
Set) when you want a fast access. Use
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.
||Review for Midterm 2
Quick Review of Tree Traversals: Preorder, Postorder, Breadth-first, Inorder (for binary trees)
Binary Heap [Lab 8]
- Heap operations:
- 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.
Lab 8 Implementation
- 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.
- Use this declaration for BinaryMinHeap:
public class BinaryMinHeap<E extends Comparable<? super E>> implements BinaryMinHeapI<E>
- How to keep track of the last node?
- Use this JUnit test file to preliminarily test your heap: TestHeap.java
- In case of
- 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
- 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 Symbol class to avoid warnings (in case you want to implement Huffman encoding): Symbol.java
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
Getting to know Eclipse: a powerful Java IDE [Lab 6]
Good for a big project, such as our upcoming project. :)
- 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)
||No Meeting: Fall Break
||Review for Midterm 1
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
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
Counting exact number of steps in code snippets.
- Need to count primitive operations right:
- Need to count the number of iterations in each loop right.
- arithmetic operation
- array indexing
- method invocation
- return from procedure
- object referencing
- Consider the worst case for if statements.
- Sometimes parts of the code never execute!
- Solution to Lab 2
- 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]