Notes to Couprie -

add String processing problem

check on what is needed for Practice IT, can they copy it in to Java after getting marked?

Where should Blue Pelican fibonacci go? - Check wording of assignment classes

Recursion Assignment 1

Read pages 421-425 of the Carter Textbook

Make a copy of this document and share it.

Answer questions 11.1 to 11.8 below

Assignment 2

Read all of Lesson 40 from the Blue Pelican Java textbook

Make a copy of this document and share it.

Complete the chapter exercises in the table below, making a prediction about what each piece of code will do before actually printing it.  You will NOT be marked on the accuracy of your predictions

Practice-IT Part 1

Go to the Practice-IT website and create an account

http://practiceit.cs.washington.edu/index.jsp 

Go to the Recursion set of lessons from Building Java Lessons, 3rd Edition

Complete 4 of the 7 self checks, screenshot and paste the marked results below.

Asssignment 3 Blue Pelican Project - Fibonacci

Recursion Theory Assignment 1 - Why Use Recursion

Create a new Google doc called Recursion 1 - Why Use Recursion and share it with your teacher.  Then answer the following questions.  You will likely need to research several of the answers.

1. What is the use and the purpose of a ‘base case’ (also known as the terminating condition in recursion?
2. Give a recursive description (such as those in the first few pages of the Carter textbook) for opening Russian Nesting Dolls.  Include ‘opening’ and ‘removing’ as separate steps.
3. Give a recursive description of the process of eating a bag of chips.  Be sure it is recursive, not iterative.
4. Compare the following aspects of recursion and iteration by giving an example

1. Programmer efficiency
2. Memory space efficiency
3. Time efficiency

5. What is the difference between ‘tail end’ recursion and ‘head end’ recursion.
6. What is a backtracking recursive algorithm?  Describe a problem where such an algorithm is used to find the solution

7. Final 10% - (Warning, this is a difficult question)  Read this definition of the HEAP.  Now, read this definition of the System Stack.

1. Find a YouTube video or good written explanation of how the System Stack is used to carry out recursion.  Then, using one of the example recursive methods from the textbook, explain or draw part of the System Stack.

Assignment 4 - Triangle

Note: this assignment is based on an exercise by John Carter

Create a new java class called StarTriangles

Suppose the following pattern is called a 5-Triangle

*

**

***

****

*****

First 80%

Write a recursive method called triangle () that takes in a single int parameter, N and prints out the triangle of asterisks with N rows. If N is less than one, it should print nothing.

Next 10%

Write a recursive method called pinetree() that takes in a single parameter, N and prints out a tree.

#

###

#####

#######

#########

#

Final 10%

alter the pineTree method so that it includes spaces, producing something similar to the following.

     #

   ###

  #####

 #######

#########

    #    

Assignment 4 - Euclid’s Algorithm

Read pages 428-429 from the Carter Textbook

Create a new class called EuclidPart1

Allow the user to input any 2 positive integers.  

Add a loop that will continue until the user enters a negative number.  It will then exit.  

Without looking for help online, write a recursive method that finds the GCD of the two numbers.

It should print out the following: The Greatest common denominator of __ and __ is ___.

Add println statement(s) within the method to show what is happening along the way.

Final 20%

There is a second way to implement Euclid’s algorithm using MOD math.  Find the algorithm online, comment out your first method and implement it .

Add println statement(s) within the method to show what is happening along the way.

Recursion with Strings

Create a new java class called StringRecursion in your Recursion folder..

Read pages 446-449 from the CarterRecursionPart2.pdf and implement the reverse() and permute() methods from examples 1, 2 and 3.  Be thoughtful about how and why 2 vs 3 would be more useful.

Choose Practice IT 12.12 IsReverse  OR 12.13 IndexOf.  You can complete one or both on the Practice IT website but you are also to create a Java class that implements this assignment

First 80%

Create EITHER the isReverse method or the indexOf method in your StringRecursion and complete a deep test with multiple inputs

Final 20%

Complete both with deep testing.

Practice-IT - Part 2

Go to the Practice-IT website and create an account

Choose two of the following Exercises and paste the marked results here:

12.2 writeNums

12.3 writeSequence

12.6 writeSquares

12.7 writeChars

Practice-IT - Part 3

Go to the Practice-IT website

Choose one of the following Exercises and paste the marked results here:

12.18 waysToClimb

12.19 countBinary

Recursion Theory Assignment 2 - Comparing Algorithms

Create a new Google doc called Recursion 2 - Comparing Algorithms and share it with your teacher.  Then answer the following questions.  You will likely need to research several of the answers.

1. Create a 2 cell table and then find and paste an Iterative binary search method next to a recursive binary search method.  You do NOT need to test and run the code.  Give credit to your source.
2. In a sentence or two, describe how they are different.
3. Create a 3 cell table and then find and paste a quicksort method, a merge sort method and a heapsort method.  (FYI: There is a really good description of Merge Sort starting on page 641 of the Big Java textbook). You do NOT need to test and run the code.  Give credit to your source.
4. Explain how each works in a sentence or two
5. List one advantage and/or disadvantage of each.
6. Imagine you are the teacher.  Create the instructions for a one class assignment that uses a recursive sort algorithm and a recursive search.  

Back tracking algorithms

Recursion Project

Options

Tower of Hanoi

Carter Queens Problem p 473

Notes to Couprie:

Add the Recursion Descendents project early on, perhaps as a no help project.

Consider using the Carter textbook instead for part or all of the content.

Assignments:

Blue Pelican Lesson 40 Exercises

Carter Book

Recursion

Recursion Credit - 2014/15

Alberta Ed Course Number: CSE3310

Prerequisites: Iterative Algorithms & Object Oriented Programming

At its most simple, recursion is the act of a method/function calling itself.  Simple right?

Well, if you think about it for a few seconds, you will probably ask yourself ‘when will I ever need to do that?’  That is one major concept in this credit.  Then, if you think about it for a few minutes, you will probably ask yourself ‘if a method calls itself, does it not cause an infinite loop?’.  The avoiding of this infinite loop is the second major concept of the credit.

You will be using a textbook  (blue binder) to complete this credit: Cay Horstman’s Big Java - Early Objects.

Evaluation

You will be earning the credit CSE3310 Recursive Algorithms 1. As this is a student led credit,  your marks will be determined as follows:

60% - Completion of the chapter exercises as described below

20% - Written Theory assignments based on the curriculum document

20% - Wrap up project

Instructions

Make a copy of this document and share it with your teacher.  As you complete each section, fill in the appropriate section of the chart on the next page

Create a new project in Netbeans called RecursionCredit

• For each exercise or project, use the exercise number in the title
• You do NOT need to fully implement the main method unless it is explicitly requested in the exercise.

1. Read through the chapter pausing at each set of Self check questions

• Answer these questions in your head and then compare your answers with those at the back of the chapter.  
• Fill in the table on the next page

2. After completing the self check questions, complete only the Practice It Exercises that appear in the table on the next page.

• Complete these in Netbeans.  
• For each exercise or project, use the exercise number in the title
• You do NOT need to fully implement the main method unless it is explicitly requested in the exercise.

3. Complete the 2 theory assignments described lower down in this document.

4. Wrap up project - Choose one of the following topics and design a java program around it.:

• P13.3 - Tower of Hanoi
• P13.4 - Escaping the maze

Recursion Theory Assignment 1 - Why Use Recursion

Create a new Google doc called Recursion 1 - Why Use Recursion and share it with your teacher.  Then answer the following questions.  You will likely need to research several of the answers.

8. What is the use and the purpose of a ‘base case’ (also known as the terminating condition in recursion?
9. Compare the following aspects of recursion and iteration by giving an example

1. Programmer efficiency
2. Memory space efficiency
3. Time efficiency

10. What is the difference between ‘tail end’ recursion and ‘head end’ recursion.
11. (Warning, this is a difficult question)  Read this definition of the HEAP.  Now, read this definition of the System Stack.

1. Find a YouTube video or good written explanation of how the System Stack is used to carry out recursion.  Then, using one of the example recursive methods from the textbook, explain or draw part of the System Stack.

Recursion Theory Assignment 2 - Comparing Algorithms

Create a new Google doc called Recursion 2 - Comparing Algorithms and share it with your teacher.  Then answer the following questions.  You will likely need to research several of the answers.

7. Create a 2 cell table and then find and paste an Iterative binary search method next to a recursive binary search method.  You do NOT need to test and run the code.  Give credit to your source.
8. In a sentence or two, describe how they are different.
9. Create a 3 cell table and then find and paste a quicksort method, a merge sort method and a heapsort method.  (FYI: There is a really good description of Merge Sort starting on page 641 of the Big Java textbook). You do NOT need to test and run the code.  Give credit to your source.
10. Explain how each works in a sentence or two
11. List one advantage and/or disadvantage of each.
12. Imagine you are the teacher.  Create the instructions for a one class assignment that uses a recursive sort algorithm and a recursive search.