|
|
| (113 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| − | == Monday (11/2/09) ==
| + | #REDIRECT [[IB Computer Science 2]] |
| − | '''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-size 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]]
| |
