Lesson 03 In-Class Exercises

Part 1: PCE 02 Review Items

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.

  1. What is the running time, in Big Oh notation, of SmartArray constructor?  Why?
  2. What is the average running time, in Big Oh notation, of the SmartArray.Find method?
  3. Look at the online documentation for the C# / .Net Stack.Push method.  Within the Remarks section it says:

    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.

    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)

Part 3: Stacks: Pseudocode & "Tracing"

(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:

  1. You need to write up pseudocode for each of the methods of the Stack class that you'll be implementing during this week's PCEs using this document
  2. Do a "trace" of your pseudocode using an example program provided by the instructor using this document

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"

Part 4: Circular Queue: Pseudocode & "Tracing"

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:

  1. You need to write up pseudocode for each of the methods of the Stack class that you'll be implementing during this week's PCEs using this document
  2. Do a "trace" of your pseudocode using an example program provided by the instructor using this document

Part Null: Stacks: Ideas that are being saved for next time :)

(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?

One Minute Paper

"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:

  1. What was the thing that you were most confused about at the start of this lecture? (Also let me know if you're still confused about this)
  2. Which of the in-class exercises and activities were most helpful to you, and why?

Head on over to the Google Docs form, and fill out the One Minute Paper for this lecture.