Lesson 08 In-Class Exercises

Before starting any specific exercise, you may wish to download, extract, and open up the provided starter project for this lesson so that you'll have it ready when you need/want it.

New Plan:

Covered Recursive find

then recursive print

Exercises:

Code up the pseudocode that was covered
try out pre/post order printing
do a 'recursion by hand' exercise for (1) (the in-order traversal)
change code to print from the highest to the lowest
print only odd numbers
print every other number

Part 1: Pseudocode & "Tracing": BST.Print

For this exercise you need to write up pseudocode for a Print method on the BinarySearchTree class. You will need to use a recursive approach, since this problem cannot be solved without the use of a stack (and recusion will get you a stack very conveniently)

This class is defined in the starter project for the POST Class Exercises, and is listed below for convenience. If you need more detail on any given method you should find the document/exercise in the PCEs which describes what the method in question should do.

For this exercise you need to write up pseudocode for each of the methods of the BinarySearchTree class that you'll be implementing during this week's PCEs using this document (note that the document also contains spaces for the remove method, which w

Be ready to present your pseudocode to the class, and to walk the class through your "trace".

public class BinarySearchTree
{
	// Protected so that the BST_Verifier subclass can get at it
	// and verify that the tree looks right (for NUnit tests)
	// Normally this should be private.
	protected BSTNode top; // also (semi-)traditional to name this 'root', instead of 'top'

	// You should make the BSTNode class a nested class
	// Normally should be private; it's protected for the reasons explained above
	protected class BSTNode
	{
		public BSTNode Left;
		public BSTNode Right;
		public int Data;
		public BSTNode(int val)
		{
			Data = val;
		}
	}

	public void Print()
	{
		Console.WriteLine("PRINT IS NOT YET IMPLEMENTED!!!!\nYou need to implement this method, recursively!");
	}

	private void Print(BSTNode cur)
	{
	}

	public void PrintBeneathNode(int target)
	{
		Console.WriteLine("NOT YET IMPLEMENTED");
		return;

	}
}

Part 2: BST.Remove: "By Hand"

With a partner, work through the PCE "BST: Remove By Hand". Make sure to draw the trees out on paper, and make sure to try and mentally trace the process of removing a node from the tree (i.e., don't just draw the final tree with the target node removed, but instead actually think about how the program would walk through the tree to find the target node, how it would identify a replacement node (if needed), how it would remove that node, etc,etc)

Part 3: Recursion Exercises

For each of the following problems the instructor recommends consulting with a peer/partner, then each person working on their individual solution.

In order to practice writing recursive code, solve each of the following problems using recursion:

Print a string in reverse (note that in C# you can treat a string like an array: string s = "Hi"; Console.WriteLine(s[0]); will print the letter H)
Determine if a string is a palindrome.
Sum up all the elements in an array
A number, a, is a power of b if it is divisible by b and a/b is a power of b. Write a function called is_power that takes parameters a and b and returns True if a is a power of b. (this is from StackOverflow)
Take a string n and print out all n! permutations of the n letters starting at a (assume that n is no greater than 26). A permutation of n elements is one of the n! possible orderings of the elements. As an example, when n = 3 you should get the following output. Do not worry about the order in which you enumerate them.
```
bca cba cab acb bac abc 
```
(from http://introcs.cs.princeton.edu/java/23recursion/)
If you finish all of the above examples (or if you don't find them to be interesting) search the web to find more recursion problems

Future Ideas

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:

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)
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.