Difference between revisions of "IB Computer Science II"

From WLCS
(Redirected page to IB Computer Science 2)
 
(84 intermediate revisions by the same user not shown)
Line 1: Line 1:
== Tuesday (12/15/09) ==
+
#REDIRECT [[IB Computer Science 2]]
'''Agenda:'''
 
* LLAddressBook? BTAddressBook?
 
* Makeup Software Development Quiz
 
* Algorithm Evaluation - Big O! - [[Media:AlgorithmEvaluation.ppt]]
 
* Introduction to Binary - [[Media:Binary.ppt]]
 
* Introduction to Binary #2 - Media:Binary2.ppt
 
* Binary Games
 
** [http://britton.disted.camosun.bc.ca/binary.swf Binary Game #1]
 
** [http://forums.cisco.com/CertCom/game/binary_game_page.htm Binary Game #2]
 
* Binary Quiz on Thursday (12/17/09)
 
* Dossier Progress Check on Thursday (12/17/09)
 
** You will demo / present completion of the following components in your dossier:
 
*** Basic container class (e.g. Contact)
 
*** Node class (e.g. ContactLLNode or ContactBTNode)
 
*** Partial completion of your major data structure (e.g. ContactLL or ContactBT)
 
 
 
== Friday (12/11/09) ==
 
'''Warmup:'''
 
* Finish cramming for software development quiz
 
 
 
'''Agenda:'''
 
* Software Development Quiz!  Yay!
 
 
 
== Wednesday (12/9/09) ==
 
'''Warmup:'''
 
* List the stages of the software development life cycle
 
* List 3 different methods of data collection for the Analysis stage
 
 
 
'''Agenda:'''
 
* Proper coding style
 
** Program header at the very top
 
*** the program name
 
*** author, date, school
 
*** computer used, IDE used, purpose
 
** Proper indentation
 
** Proper line-wrapping (how to deal with LONG lines of code)
 
* Demo missing work
 
* Recursion Review
 
** [[Media:Recursion.ppt]]
 
* Software systems life cycle & software development
 
** [[Media:SoftwareDevelopment.ppt]]
 
* Work on the programming for your dossier
 
 
 
'''Homework:'''
 
* Software development quiz on Friday (12/11/09)
 
 
 
== Monday (12/7/09) ==
 
'''Warmup:'''
 
* Illustrate the binary tree that is created when you insert the following values:
 
** 24, 75, 4, 12, 98, 33, 0
 
* Illustrate the binary tree that is created when you insert the following values:
 
** Newman, Braden, Hines, Rawoot, Whelan, Luoma-Overstreet, Anderson, Apseloff
 
 
 
'''Agenda:'''
 
* Demo missing work
 
* Software systems life cycle & software development
 
** [[Media:SoftwareDevelopment.ppt]]
 
* Work on the programming for your dossier
 
 
 
'''Homework:'''
 
* Software development quiz on Friday (12/11/09)
 
 
 
== Tuesday - Thursday (12/1/09 - 12/3/09) ==
 
'''Warmup:'''
 
* Prepare to demo your BTAddressBook
 
 
 
'''Agenda:'''
 
* BTAddressBook demos
 
* Recursion Review
 
** [[Media:Recursion.ppt]]
 
* Dossier Review - Data Structures section
 
* Dossier Programming - use this time in class to begin programming the classes you will use in your dossier
 
** Create your basic container classes (e.g. Person, Schedule, Book, Order, Ticket, etc.).  They should contain the following:
 
*** private attributes
 
*** default constructor
 
*** specific constructor
 
*** setters
 
*** getters
 
** Create any classes that may contain these other classes (e.g. Library, AddressBook, etc.)
 
** Using your prototype solution as a guide, you should begin creating the main menu system for your dossier.
 
 
 
'''Homework:'''
 
* Dossier - Data Structures rough draft - due (Thursday 12/3/09)
 
 
 
== Tuesday (11/24/09) ==
 
'''Agenda:'''
 
* Dossier - Data Structures
 
* [[Media:CriterionB1_dataStructures.doc]]
 
* Demo your LinkedList AddressBook
 
* 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
 
 
 
'''Homework:'''
 
* Demo BinaryTreeAddressBook - due (Tuesday 12/1/09)
 
* Dossier - Data Structures rough draft - due (Thursday 12/3/09)
 
 
 
== Friday (11/20/09) ==
 
'''Agenda:'''
 
* Demo your LinkedList AddressBook.  It should be able to do the following:
 
** add a Contact
 
** print list of Contacts
 
** find a Contact
 
** sort list of Contacts
 
* Re-Introduction to Binary Tree
 
** [[Media:BinaryTreeNode.java]]
 
** [[Media:BinaryTree.java]]
 
** [[Media:BinaryTreeTestMain.java]]
 
* Create 3 new classes called ContactBTNode, ContactBinaryTree, and ContactBTTestMain
 
* Convert the 3 given binary tree classes to use Contacts instead of ints
 
 
 
== Wednesday (11/18/09) ==
 
'''Warmup:'''
 
* What is the algorithm for a linear search?
 
* What is the algorithm for a selection sort?
 
* What is the algorithm for a bubble sort?
 
 
 
'''Agenda:'''
 
* int find(String fn, String ln) in the ContactLinkedList
 
** Add the find() option to your AddressBookMain and AddressBook
 
** find() in the AddressBook should use the ContactLinkedList's find() and then ContactLinkedList's getContact()
 
* void selectionSort() in the ContactLinkedList
 
* You should move the bubbleSort() into the ContactLinkedList and complete the method yourself
 
* Removing a Contact
 
** Add a remove option to your AddressBookMain
 
** Create a remove(String fn, String ln) method in your AddressBook
 
** In the method, use the ContactLinkedList's find() method to get the index of the Contact
 
** Check if the index is valid (not the error code), and if so, then use the ContactLinkedList's remove() method using that index
 
* Demo a completely working AddressBook
 
 
 
== Monday (11/16/09) ==
 
'''Warmup:'''
 
* Open your Contact class and review the code
 
 
 
'''Agenda:'''
 
* Contact class review as a class
 
* Create a new class from your Node class and called ContactNode
 
** Do this as a class...quickly
 
* Create a new class called ContactLinkedList
 
** Do this as a class...quickly
 
* Convert your LinkedList to use ContactNode and call it ContactLinkedList
 
** Go through one or two examples as a class
 
* Be sure to test your ContactLinkedList
 
* AddressBook class review as a class
 
* Convert your AddressBook to use ContactLinkedList instead of an array
 
** Comment out the parts for find(), selectionSort(), and bubbleSort().  We will convert these later
 
** Be sure to test your AddressBook with LOTS of contacts
 
 
 
'''Homework:'''
 
* Complete the AddressBook conversion over to ContactLinkedList by Wednesday (11/18/09)
 
* Be ready to demo your AddressBookMain
 
 
 
== Thursday (11/12/09) ==
 
'''Agenda:'''
 
* Abstract data types review
 
* Introduction to Binary Tree
 
** [[Media:BinaryTreeNode.java]]
 
** [[Media:BinaryTree.java]]
 
** [[Media:BinaryTreeTestMain.java]]
 
* Demo your 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 array
 
** Comment out the methods for find(), selectionSort(), and bubbleSort().  We will convert these later
 
** Be sure to test your AddressBook with LOTS of contacts
 
 
 
== Monday (11/9/09) ==
 
'''Agenda:'''
 
* Turn in homework
 
* Demo DynamicQueue
 
* Introduction to Linked Lists
 
** [[Media:LinkedList.java]]
 
** Attributes: head, tail, size
 
** Constructors: default
 
** Methods:
 
*** isEmpty() - returns true if the LinkedList is empty, and false otherwise
 
*** void add(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
 
*** print() - traverses the LinkedList and prints out each Node's data
 
** Create a main method to test out all the methods and scenarios of LinedList
 
 
 
'''Homework:'''
 
* Complete the LinkedList class and all its methods by the beginning of class on Thursday (11/12/09)
 
* Mr. Bui will give you his LinkedListMain on Thursday to test
 
 
 
== Thursday (11/5/09) ==
 
'''Warmup:'''
 
* 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
 
 
 
'''Agenda:'''
 
* Return 1st Quarter Exams
 
* Dynamically-sized Queues
 
** Create a new class called DynamicQueue
 
*** [[Media:DynamicQueue.java]]
 
** Test out your DynamicQueue using the original QueueMain file
 
* Introduction to Linked Lists
 
** [[Media:LinkedList.java]]
 
** Attributes: head, tail, size
 
** Constructors: default
 
** Methods:
 
*** isEmpty() - returns true if the LinkedList is empty, and false otherwise
 
*** void add(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
 
*** print() - traverses the LinkedList and prints out each Node's data
 
 
 
'''Homework:'''
 
* Complete DynamicQueue!
 
* Draw the before-and-after diagrams (all SIX scenarios) for the LinkedList's remove() method
 
 
 
== Monday (11/2/09) ==
 
'''Warmup:'''
 
* Assume that you have allocated memory for a new int array of 10000 elements.  An int is 32-bits in size, and there are 8-bits in 1 byte.  How many bytes of memory are you taking up?
 
* If there are 1024 bytes in a kilobyte, how many kilobytes are you taking up?
 
 
 
'''Agenda:'''
 
* Dynamically-sized Stacks
 
** Create a new class called DynamicStack
 
*** [[Media:DynamicStack.java]]
 
** What attribute must we keep track of when we talk about stacks?
 
** Create a Node reference for the most important stack attribute
 
** Implement push(int num) using Nodes.
 
*** push() should not return anything
 
*** push() creates a new Node with the num, and set the new Node's next reference to the top
 
*** Don't forget to update the top to be the new node!
 
** Implement pop(), which should POP and return the value on top of the stack and update the top
 
** Implement top(), which should just return the value on top of the stack
 
** Implement isEmpty() which returns true if the stack is empty
 
** Implement print() which should print your entire stack
 
** TEST YOUR STACK USING MR. BUI'S STACK MAIN OR YOUR OWN MAIN METHOD
 
 
 
== Thursday (10/29/09) ==
 
* 1st Quarter Exam
 
 
 
== Tuesday (10/27/09) ==
 
'''Warmup:'''
 
* Pass in your Prototype Solution to Mr. Bui
 
* Given the following code, draw the memory diagram:
 
 
 
<source lang="Java">
 
Node fun = new Node(42);
 
Node general = new Node (11);
 
Node a, b, c;
 
 
 
a = general;
 
b = a;
 
fun.next = b;
 
c = fun;
 
</source>
 
 
 
'''Agenda:'''
 
* Pass back Stacks quiz
 
* Prototype Solution peer review
 
* 1st Quarter Exam Review
 
** Java programming
 
** class construction
 
** methods
 
*** components of the method header
 
** Stacks
 
*** how they work
 
*** operations: push(), pop(), top(), isEmpty()
 
*** why we use them
 
*** example uses
 
** Queues
 
*** how they work
 
*** operations: add(), remove(), head(), tail(), isEmpty()
 
*** why we use them
 
*** example uses
 
** Nodes and reference variables
 
*** Memory diagram and tracing code
 
 
 
== Friday (10/23/09) ==
 
'''Agenda:'''
 
* Object and References Review
 
** [[Media:Point.java]]
 
** [[Media:ReferencesReview.java]]
 
* Node class
 
** [[Media:Node.java]]
 
** [[Media:NodeFun.java]]
 
* Node references practice
 
** [[Media:NodeFunAgain.java]]
 
 
 
'''Homework:'''
 
* Dossier - Prototype Solution rough draft due Tuesday (10/27/09)
 
 
 
== Wednesday (10/21/09) ==
 
'''Warmup:'''
 
* Give 2 specific examples of when a queue should be used
 
* Identify the following parts in each of the method declarations: access type, return type, method name, parameters
 
** public int getSize()
 
** private String whatNot(String whatFor)
 
** public void print(int size, String stuff)
 
 
 
'''Agenda:'''
 
* Make-up stack quiz for people who were absent on Monday
 
* Demo your fixed [[Media:Queue.java]] by using [[Media:QueueMain.java]]
 
* Criteria for Success peer review
 
* Object and References Review
 
** [[Media:Point.java]]
 
** [[Media:ReferencesReview.java]]
 
* Node class
 
** [[Media:Node.java]]
 
** [[Media:NodeFun.java]]
 
* Node references practice
 
* Read through [[Media:CriterionA3_prototypeSolution.doc]]
 
* Begin working on your Prototype Solution.  It will be due next Tuesday (10/27/09).
 
 
 
'''Homework:'''
 
* Dossier - Prototype Solution rough draft due Tuesday (10/27/09)
 
 
 
== Monday (10/19/09) ==
 
'''Warmup:'''
 
* What does LIFO stand for? 
 
* What does LIFO describe? 
 
* When would you want a LIFO?
 
 
 
'''Agenda:'''
 
* Stack quiz
 
* Queues
 
** [[Media:Queues.ppt]]
 
** [[Media:Queue.java]]
 
** [[Media:QueueMain.java]]
 
* Fix Queue.java so that it works. You must fill in all the method bodies
 
 
 
'''Homework:'''
 
* Dossier - Criteria for Success rough draft due Wednesday (10/21/09)
 
* Turn in late assignments! Examples: AddressBook sorting, Problem Analysis, etc.
 
 
 
== Thursday (10/15/09) ==
 
'''Warmup:'''
 
* Demo any missing work
 
* Finish adding bubble sort and selection sort to your AddressBook
 
** Hint1: You cannot simply compare Contacts, but you can compare their last names
 
** Hint2: You cannot sort the ENTIRE Contact array, you can only sort the ones that you have added
 
** Hint3: You should test our the sorting methods by adding a (s)ort option to your AddressBookMain
 
 
 
'''Agenda:'''
 
* Introduction to Data Structures
 
* Stacks
 
** [[Media:Stacks.ppt]]
 
** [[Media:Stack.java]]
 
** [[Media:StackMain.java]]
 
* Go through [[Media:CriterionA2_criteriaforSuccess.doc]]
 
* Begin working on your Criteria for Success.  It will be due next Wednesday (10/21/09).
 
 
 
'''Homework:'''
 
* Stacks quiz on Monday (10/19/09)
 
* Dossier - Criteria for Success rough draft due Wednesday (10/21/09)
 
* Turn in late assignments! Examples: AddressBook sorting, Problem Analysis, etc.
 
 
 
== Tuesday (10/13/09) ==
 
'''Warmup:'''
 
* Please complete this [https://spreadsheets.google.com/viewform?formkey=dGx5Uy1JVGRXcDNJV0NHOEJvZ21vX2c6MA password request form]
 
* What are the advantages and disadvantages of the binary search algorithm?
 
 
 
'''Agenda:'''
 
* Dossier peer review - Analysis of the Problem
 
* Demo any missing work
 
* Sorting & Searching Review
 
** Selection Sort
 
** Bubble Sort
 
** Linear Search
 
** Binary Search
 
* Examples of using the String.compareTo() method
 
** [[Media:CompareToDemo.java]]
 
** [[Media:CompareToDemo2.java]]
 
* Fix [[Media:StringBinarySearch.java]] such that it uses binary search to find a String. Hint: You will be using the compareTo()
 
* Demo StringBinarySearch to Mr. Bui by the end of today.
 
 
 
* You should then add selectionSort() to your AddressBook class.  It sorts your AddressBook Contact array by last name using the selection sort algorithm. You may assume that everybody will have a different last name.
 
* You should then add bubbleSort() to your AddressBook class.  It sorts your AddressBook Contact array by last name using the bubble sort algorithm. You may assume that everybody will have a different last name.
 
* Demo the two sorting methods to Mr. Bui before Thursday.
 
* Read through [[Media:CriterionA2_criteriaforSuccess.doc]]
 
* Begin working on your Criteria for Success.  It will be due next Wednesday (10/21/09).
 
 
 
== Thursday (10/8/09) ==
 
'''Warmup:'''
 
* Given the array of integers: 3, 6, 2, 7, 9, 5, 2, 3
 
* Illustrate the bubble sort algorithm to sort the numbers
 
 
 
'''Agenda:'''
 
* Introduction to Linear Search
 
* Download [[Media:LinearSearch.java]]
 
* Fill in the commented parts of LinearSearch.java and demo a working linear search to Mr. Bui
 
* Linear Search performance evaluation
 
# What is the best case scenario? i.e. What is the minimum # of comparisons?
 
# What is the worst case scenario? i.e. What is the maximum # of comparisons?
 
# What is the average # of comparisons?
 
# Can we do better than a linear search?
 
 
 
* Introduction to Binary Search
 
# Assume sorted list
 
# Go to the middle point
 
# If the middle element matches the key, then the search is over
 
# If the key is less than middle element, go to the left (down), else go to the right (up)
 
# Repeat steps 2-4 until the key is found or when the left and right bounds pass each other
 
 
 
* [http://euler.slu.edu/~goldwasser/demos/BinarySearch/ Binary Search Demo]
 
* [http://www.cosc.canterbury.ac.nz/people/mukundan/dsal/BSearch.html Binary Search Demo2]
 
* [[Media:BinarySearch.java]]
 
* Binary Search performance evaluation
 
# What is the best case scenario? i.e. What is the minimum # of comparisons?
 
# What is the worst case scenario? i.e. What is the maximum # of comparisons?
 
# What is the average # of comparisons?
 
* Binary Search Advantages & Disadvantages
 
 
 
'''Homework:'''
 
* 1st rough draft of Analysis of the Problem due Tuesday (10/13/08)
 
* Any missing assignments (e.g. AddressBook, SelectionSort, BubbleSort)
 
 
 
== Tuesday (10/6/09) ==
 
'''Warmup:'''
 
* Upload AddressBook.java and AddressBookMain.java to SchoolWebLockers
 
* Demo SelectionSort.java to Mr. Bui
 
* Turn in your Dossier idea sentence
 
 
 
'''Agenda:'''
 
* Introduction to Bubble Sort
 
# Initialize the front to be the top or beginning of the array
 
# Now go to the bottom/end of the array
 
# Compare the two adjacent elements to see if they are in proper sequential order
 
## Swap the elements if they are out of order (bigger number to the left of smaller number)
 
# Move to the next pair of adjacent elements/numbers
 
# Repeat steps 3 and 4 until the smallest number has "floated" to the top/front
 
# After you traverse the entire array
 
## Move the front so that the sorted numbers are ignored
 
## Go back to the end of the array
 
## Repeat steps 2 through 6 for the unsorted part of the array
 
* [http://web.engr.oregonstate.edu/~minoura/cs162/javaProgs/sort/BubbleSort.html Bubble Sort Animation]
 
* Download [[Media:BubbleSort.java]]
 
** Fill in the commented parts of the BubbleSort.java file. Where there is a comment, you need to write code.
 
** Demo to Mr. Bui at the end of class or at the beginning of class tomorrow
 
* Introduction to Program Dossier
 
** [[Media:CriterionA1_problemAnalysis.doc]]
 
** 1st rough draft of Analysis of the Problem due Tuesday (10/13/08)
 
** Work on your Analysis of the Problem section
 
 
 
== Friday (10/2/09) ==
 
'''Warmup:'''
 
* Swapping elements warmup
 
 
 
'''Agenda:'''
 
* Demo [[AddressBook class lab assignment]] and any other missing assignments
 
* Submit your AddressBook and AddressBookMain on-line to Mr. Bui's SchoolWebLockers
 
* Review Selection Sort
 
* Download [[Media:SelectionSort.java]]
 
** Fill in the commented parts of the SelectionSort.java file. Where there is a comment, you need to write code.
 
** Demo to Mr. Bui at the end of class today
 
* Introduction to Program Dossier
 
** [[Media:CriterionA1_problemAnalysis.doc]]
 
 
 
'''Homework:'''
 
* Complete your [[AddressBook class lab assignment]] AND [[Media:SelectionSort.java]]
 
* Have a 1 sentence description of your dossier ready at the beginning of next class
 
 
 
== Archives ==
 
* [[IBCS2 - May]]
 
* [[IBCS2 - April]]
 
* [[IBCS2 - March]]
 
* [[IBCS2 - February]]
 
* [[IBCS2 - January]]
 
* [[IBCS2 - December]]
 
* [[IBCS2 - November]]
 
* [[IBCS2 - October]]
 
* [[IBCS2 - September]]
 

Latest revision as of 11:21, 24 August 2010