IBCS2 - 1314 - October
From WLCS
Contents
Wednesday (10/30/13)
Warmup:
- Algorithm Analysis of Linked List
- What is the Big-O of adding something to a Linked List? Why?
- What is the Big-O of removing something to a Linked List? Why?
- What is the Big-O of finding something in a Linked List? Why?
Agenda:
- Complete the code for LinkedList_incomplete.py
- You can try testing out all your code using: Linked ListTest.py
- What does the IB expect you to know about Linked Lists?
- Diagrams and descriptions for adding, removing, modifying, and searching in a linked list
- What are the different types of Linked Lists? What do they look like?
- Singly linked list
- Doubly linked list
- Circular linked list
- Introduction to Binary Trees
- Media:BinaryTrees.ppt
- Binary Tree Code walk-through
- What does the IB expect you to know about Binary Trees?
- Diagrams and descriptions for building, adding, removing, and searching in a binary tree
Monday (10/28/13)
Warmup:
- If you already have started taking notes on Linked List, take those out
- AND take out several sheets of paper for new notes
- Take out a pencil (not a pen)
Agenda:
- Introduction to Linked Lists (walk-through)
- What does a Linked List look like?
- Linked List attributes
- first
- last
- size
- Linked List methods
- adding data (beginning, middle, end)
- deleting data (beginning, middle, end)
- getting data
- modifying data
- searching for data
- clearing all data
- Complete the code for LinkedList_incomplete.py
- You can try testing out all your code using: Linked ListTest.py
- What does the IB expect you to know about Linked Lists? Diagrams and descriptions
- What are the different types of Linked Lists? What do they look like?
- Singly linked list
- Doubly linked list
- Circular linked list
Thursday (10/24/13)
Warmup:
- Period 2
- Show Mr. Bui your dynamic queue's before-and-after drawings.
- Complete the dynamic queue code (head, tail, isEmpty(), enqueue(), dequeue())
- Period 4
- What does LIFO stand for? When specifically would a LIFO be used?
- What does FIFO stand for? When specifically would a FIFO be used?
- Complete the dynamic queue code (head, tail, isEmpty(), enqueue(), dequeue())
Agenda:
- Complete and demo dynamic queues
- Nodes and pointers (references) review
Tuesday (10/22/13)
Warmup:
- Execute the following code to demo/test your DynamicStack
dStack = DynamicStack()
#test out push
dStack.push(1)
dStack.push(2)
dStack.push(3)
#test out print
dStack.print()
#test out top()
print("Top =>", dStack.top)
#test out pop()
print("Pop!", dStack.pop())
print("Pop!", dStack.pop())
print("Pop!", dStack.pop())
#test out popping from an empty stack
print("Pop!", dStack.pop())
Agenda:
- Node Quiz
- Stack demos
- Dynamically-sized Queue
- On paper, draw the before-and-after pictures for enqueue()'s 2 scenarios:
- enqueueing to an empty queue
- enqueueing to a non-empty queue
- Draw the before-and-after pictures for dequeue()'s 3 scenarios:
- dequeueing an empty queue
- dequeueing the very last node
- dequeueing normally when the queue has more than one node
- Write the dynamically-sized queue code
- On paper, draw the before-and-after pictures for enqueue()'s 2 scenarios:
Homework:
- Period 2 - Complete the dynamic queue before-and-after drawings
- Period 4 - Complete the dynamic queue code and test it
Friday (10/17/13)
Warmup:
- Complete the Dual Enrollment Test Score Survey
- Grab a dry-erase board and marker
Agenda:
- Reference variables review
- Introduction to Nodes
- Node.py
- NodePractice1.py
- NodePractice2.py
- Practice writing code when given a memory diagram
- NodeLoop.py
- Node Quiz on Tuesday (10/22/13)
- Be able to trace code and draw memory diagram
- Be able to write code that creates a given memory diagram
- Dynamically-sized Stacks - due Tuesday (10/22/13)
- Stack scenarios and Before-&-After pictures
- What are the possible behaviors of a stack?
- What does the picture look like Before?
- What does the picture look like After?
- 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(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() using Nodes
- pop() removes the value on top of the stack, return it
- pop() should also update the top
- pop() returns None if the stack is empty
- Implement isEmpty() which returns True if the stack is empty, and False otherwise
- Implement print() which should print your entire stack from top down
- TEST YOUR STACK
- Be sure to push A LOT of data to test the dynamic size
- Also test popping A LOT of data to make sure it works too
- Stack scenarios and Before-&-After pictures
Homework:
- Node quiz on Tuesday (10/22/13)
- Completed Dynamic Stack by the beginning of Tuesday (10/22/13)
Wednesday (10/16/13)
Agenda:
- Work on your Internal Assessment Project
- Possible Resources
Friday (10/11/13)
Agenda:
- JAMTECH
- Turn in a printed copy of Criterion A: Planning of your Internal Assessment
- Demo completed NumQueue
- Circular Queue walk-through
- Primitive types vs. Reference types
- Nodes
Wednesday (10/9/13)
Agenda:
- Complete NumQueue
- __init__(self): initializes the head and tail indices to None or -1
- isEmpty(self): returns True if the queue is empty
- isFull(self): returns True if the queue is full
- print(self): prints the entire queue from head to tail
- getHead(self): returns the value at the head or None if there is no head
- getTail(self): returns the value at the tail or None if there is no tail
- enqueue(self, num): adds num to the tail of the queue (don't forget to check if the queue is full beforehand)
- dequeue(self): returns and removes the head of the queue (don't forget to check if the queue is empty)
- Test and demonstrate all your queue methods to Mr. Bui
- What's a circular queue?
Homework:
- Complete Criterion A: Planning of your Internal Assessment (due by Friday 10/11/13)
Monday (10/7/13)
Agenda:
- Stacks quiz
- Finish static stack implementation & review
- Queues - Media:Queues.ppt
- Create a NumQueue class (static size)
- Due on Wednesday (10/9/13)
- Use NumStack as a template
- Be sure to have all the queue attributes
- Be sure to have all the queue operations
- Create any other queue methods that may be useful
- Test your queue class to see if it works
Homework:
- Complete Criterion A: Planning of your Internal Assessment (due by Friday 10/11/13)
Thursday (10/3/13)
Agenda:
- Stacks - Media:Stacks.ppt
- Stacks quiz on Monday (10/7/13)
- Be able to describe the characteristics of a stack
- Be able to explain the operations of a stack
- Be able to describe different stack applications
- If given a list or an array, be able to explain their use as stacks
- Python Classes Review - Media:PythonClasses.pptx
- NumStack Class (static-size) walk-through
Tuesday (10/1/13)
Warmup:
- Did you complete the IBCS2 Project Ideas Survey?
Agenda:
- Searching & Sorting Quiz (~20 minutes)
- Demo missing matrixAdd() and matrixSub()
- Demo completed fliplr(m) and flipud(m)
- Internal Assessment Materials
- Henceforth...all free time...will be spent working on your IA