For this exercise you should find a partner(s) (pairs are best, but triples are ok) and discuss the following items from the PCEs from Lesson 02. Be prepared to present any of your answers to the entire class.
Explain the running time of the Push method by offering a possible explanation of how the Push method is implemented (paying particular attention to how the array(s) are tracked by the Stack class, and when they're allocated)Stack is implemented as a circular buffer.
If Count already equals the capacity, the capacity of the Stack is increased by automatically reallocating the internal array, and the existing elements are copied to the new array before the new element is added.
null can be pushed onto the Stack as a placeholder, if needed. It occupies a slot in the stack and is treated like any object.
If Count is less than the capacity of the stack, Push is an O(1) operation. If the capacity needs to be increased to accommodate the new element, Push becomes an O(n) operation, where n is Count.
(You may want to examine the StackOfInts as specialized SmartArray document for a specification of the StackOfInts that you will implement)
For this exercise you need to do two things:
The overall idea here is that the first activity will help you clarify your thinking about how each of the methods should work, and the second activity will give you a structured opportunity to check your thinking from the first activity.
The way that the second activity should be done is that
you should open the file, and work your way down the sheet. Each section
consists of a line of code and the state of the Stack object after that line is
finished. It's your job to mentally run through your pseudocode, adjusting
the state of the Stack as you do so. Obviously if you find any errors in
your pseudocode you should fix them (but be careful that your fixes don't break
earlier lines of code!)
(Note that unlike BIT 115 there is NO table to fill out in order to force you to
go through the program line by line)
Be ready to present your pseudocode to the class, and to walk the class through your "trace"
This exercise is basically the same as the Pseudocode & "Tracing" exercise for stacks, except that this is for a circular queue, instead)
(You may want to examine the QueueOfIntegers as specialized SmartArray document for a specification of the QueueOfInts that you will implement)
For this exercise you need to do two things:
(Ignore these - they're activity ideas for next time)
ADT: Why is it useful?
Stack ADT: What methods, what do they typically do?
Do RPN example by hand?
Detecting palindromes?
Use the Net stack to do something?
"A “one-minute paper” may be defined as a very short, in-class writing activity (taking one-minute or less to complete) in response to an instructor-posed question, which prompts students to reflect on the day’s lesson and provides the instructor with useful feedback." (from http://www.oncourseworkshop.com/Awareness012.htm).
For this One Minute Paper, I would like you to think back on both the preview videos / viewing quiz and today's in-class exercises, and quickly write up answers to two questions:
Head on over to the Google Docs form, and fill out the One Minute Paper for this lecture.