IB Computer Science II

From WLCS
Revision as of 09:08, 5 November 2009 by Admin (talk | contribs)

Wednesday (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
    • Test out your DynamicQueue using the original QueueMain file
  • Introduction to Linked Lists
    • 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:

  • Draw the before-and-after diagrams for the 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
    • 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:
Node fun = new Node(42);
Node general = new Node (11);
Node a, b, c;

a = general;
b = a;
fun.next = b;
c = fun;

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:

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:

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:

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:

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 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
  • 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
  1. What is the best case scenario? i.e. What is the minimum # of comparisons?
  2. What is the worst case scenario? i.e. What is the maximum # of comparisons?
  3. What is the average # of comparisons?
  4. Can we do better than a linear search?
  • Introduction to Binary Search
  1. Assume sorted list
  2. Go to the middle point
  3. If the middle element matches the key, then the search is over
  4. If the key is less than middle element, go to the left (down), else go to the right (up)
  5. Repeat steps 2-4 until the key is found or when the left and right bounds pass each other
  1. What is the best case scenario? i.e. What is the minimum # of comparisons?
  2. What is the worst case scenario? i.e. What is the maximum # of comparisons?
  3. 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
  1. Initialize the front to be the top or beginning of the array
  2. Now go to the bottom/end of the array
  3. Compare the two adjacent elements to see if they are in proper sequential order
    1. Swap the elements if they are out of order (bigger number to the left of smaller number)
  4. Move to the next pair of adjacent elements/numbers
  5. Repeat steps 3 and 4 until the smallest number has "floated" to the top/front
  6. After you traverse the entire array
    1. Move the front so that the sorted numbers are ignored
    2. Go back to the end of the array
    3. Repeat steps 2 through 6 for the unsorted part of the array
  • 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

Friday (10/2/09)

Warmup:

  • Swapping elements warmup

Agenda:

Homework:

Archives

Retrieved from "https://www.paulbui.net/wiki/index.php?title=IB_Computer_Science_II&oldid=4371"