IB Computer Science 2
From WLCS
Contents
Wednesday (12/1/10)
Warmup:
- Insert the following numbers into a binary tree: 45, 23, 12, 87, 54, 52, 12, 0
- How many comparisons does it take to find the number 54? (Remember to start at the root)
- How many comparisons does it take to find the number 12? (Remember to start at the root)
- What is the most number of comparisons that it takes to find a number? (Remember to start at the root)
Agenda:
- AddressBook 2 Demo
- Remove
- Prompt the user for a name
- Find the Contact in the LinkedList
- Use the LinkedLists's remove method to remove it
- Sort
- Use the SelectionSort algorithm
- You will need to convert the loops to traverse a LinkedList
- When swapping a Contact with the front, do not swap nodes, but just the Contacts inside them
- Edit
- In the Address menu, you will need to ask the user which Contact they want to edit
- Search for the Contact, and then prompt the user which field they want to edit
- Prompt the user for the new information and use the Contact's setter method to change the particular field
- Create 3 new classes called ContactBinaryTreeNode, ContactBinaryTree, and ContactBTTestMain
- Media:BinaryTreeNode.java
- Media:BinaryTree.java
- Media:BinaryTreeTestMain.java
- Convert the 3 given binary tree classes to use Contacts instead of ints
- Create and demo a BinaryTreeAddressBook
Monday (11/29/10)
Warmup:
- Insert the following numbers into a binary tree: 3, 7, 21, 34, 9, 8
- Insert the following words into a binary tree: the, quick, brown, fox, jumps, over, the, lazy, dog
Agenda:
- AddressBook 1 Demo
- add, print, search
- AddressBook 2 Demo
- remove, sort, edit
- Binary Tree Review
- Create 3 new classes called ContactBinaryTreeNode, ContactBinaryTree, and ContactBTTestMain
- Convert the 3 given binary tree classes to use Contacts instead of ints
- Create and demo a BinaryTreeAddressBook
Monday (11/22/10)
Warmup:
- Demonstrate adding, searching, and printing to your AddressBook using LinkedLists
Agenda:
- Add removing and sorting to your AddressBook
- Removing: Prompt the user for a firstname and lastname, create a temporary Contact, search for the index of the matching Contact
- Sorting: Use either the selection-sort or bubble-sort algorithms. When you need to swap, swap Contacts, not Nodes
- Add editing?
- Binary Trees continued...
Thursday (11/18/10)
Warmup:
- Look at the board, identify the invalid node in each binary tree. Where should the invalid node go in order for the tree to be valid?
Agenda:
- Review setters/getters
- Review using methods of objects
- Complete and demo a working AddressBook that uses LinkedList
- How do we add sorting to our AddressBook?
Tuesday (11/16/10)
Warmup:
- Create a new class named ContactNode
- It should have two attributes:
- Contact c = null
- ContactNode next = null;
- It should have two constructors
- Default constructor: ContactNode()
- Specific constructor: ContactNode(Contact newC)
- You should make setters and getters for the attributes
Agenda:
- Create a new class called ContactLinkedList
- Convert your LinkedList to use ContactNode and call it ContactLinkedList
- Be sure to test your ContactLinkedList
- AddressBook class review
- Convert your AddressBook to use ContactLinkedList instead of Contact[] array
- Be sure to test your AddressBook with LOTS of contacts
- HINT: Use a loop to auto-create 100s of Contacts and auto-add them
- Introduction to Binary Trees
Friday (11/12/10)
Agenda:
- Demo your completed LinkedList
- Contact class review
- Create a new class from your Node class and called ContactNode
- Create a new class called ContactLinkedList
- Convert your LinkedList to use ContactNode and call it ContactLinkedList
- Be sure to test your ContactLinkedList
- AddressBook class review
- Convert your AddressBook to use ContactLinkedList instead of Contact[] array
- Be sure to test your AddressBook with LOTS of contacts
- HINT: Use a loop to auto-create 100s of Contacts and auto-add them
Friday - Tuesday (11/5/10 - 11/9/10)
Agenda:
- Demo Media:DynamicStack.java
- Demo Media:DynamicQueue.java
- Introduction to Linked Lists
- Media:LinkedList.java
- Attributes: head, tail, size
- Constructors: default
- Methods:
- boolean isEmpty() - returns true if the LinkedList is empty, and false otherwise
- void append(int num) - adds a new Node with num at the end of the LinkedList
- void add(int num, int index) - adds a new Node with num at the index specified
- There are FIVE different scenarios when you add a Node
- DRAW the before-and-after pictures for all FIVE secenarios
- int remove(int index) - removes the index-th Node and returns its data
- There are SIX different scenarios when you remove a Node
- int getNum(int index) - returns the num found at the index (HINT: you'll need to traverse the LinkedList)
- int search(int num) - returns the index of the Node with num (returns -1 if num not in list)
- void print() - traverses the LinkedList and prints out each Node's data
- Test your LinkedList using Media:LinkedListTestMain.java
Wednesday (11/3/10)
Warmup:
- Draw the memory diagram after the following code executes:
<source lang="Java"> Node head = new Node(14); Node tail = head; tail.next = new Node(15); tail = tail.next; head.next.next = new Node(926); tail = tail.next; tail.next = new Node(3); tail = tail.next; </source>
Agenda:
- Turn in your Prototype Solutions
- Return all papers
- Demo your Media:DynamicStack.java
- Review Dynamic Queue
- Memory diagrams for each method
- Begin/Starting scenarios for each method
- Draw the before-and-after pictures for adding a Node to an empty Queue (be sure to use head and tail!)
- Draw the before and after pictures for adding a Node to a non-empty Queue
- Draw the before-and-after pictures for removing a Node from an empty Queue
- Draw the before and after pictures for removing a Node from a non-empty Queue
- Complete and demo Media:DynamicQueue.java
Tuesday (11/2/10)
- Teacher Work Day
