Coding Bat Recursive Problems – Day 1

Today, we are looking at a primer for recursion using problems in CodingBat in Computer Science 2. We looked at 3 different problems from CodingBat.

Bunny Ears

http://codingbat.com/prob/p183649

Here is the setup of the problem:

We have a number of bunnies and each bunny has two big floppy ears. We want to compute the total number of ears across all the bunnies recursively (without loops or multiplication).

public int bunnyEars(int bunnies) {
  if (bunnies == 0){
    return 0;
  } else {
    return 2 + bunnyEars(bunnies-1);
  }
}

Let’s use an input of 6. With this, we would anticipate the output to be 12, since each bunny has 2 ears.

Line 3 will not be run since the condition set in line 2 is FALSE. Currently, bunnies is set to 6.

So, we move on to line 4, which is the start of the default case, and is executed on line 5. So with bunnies set to 6, we return a 2 and then add that to the number of bunny ears from the next bunny (bunnies – 1), which is bunny #5.

Now, bunnies = 5, so line 2 is still FALSE, so we run the default case on line 6. We return a 2 and add that to the number of bunny ears from the next bunny (bunnies – 1), which is bunny #4.

Now, bunnies = 4, so line 2 is still FALSE, so we run the default case on line 6. We return a 2 and add that to the number of bunny ears from the next bunny (bunnies – 1), which is bunny #3.

Now, bunnies = 3, so line 2 is still FALSE, so we run the default case on line 6. We return a 2 and add that to the number of bunny ears from the next bunny (bunnies – 1), which is bunny #2.

Now, bunnies = 2, so line 2 is still FALSE, so we run the default case on line 6. We return a 2 and add that to the number of bunny ears from the next bunny (bunnies – 1), which is bunny #1.

Now, bunnies = 1, so line 2 is still FALSE, so we run the default case on line 6. We return a 2 and add that to the number of bunny ears from the next bunny (bunnies – 1), which is 0.

Now, bunnies = 0, so line 2 is now TRUE, so we return a 0 and exit the loop.

We now add the following together:

  • 0 from when bunnies = 0 (cumulative total = 0)
  • 2 from when bunnies = 1 (cumulative total = 2)
  • 2 from when bunnies = 2 (cumulative total = 4)
  • 2 from when bunnies = 3 (cumulative total = 6)
  • 2 from when bunnies = 4 (cumulative total = 8)
  • 2 from when bunnies = 5 (cumulative total = 10)
  • 2 from when bunnies = 6 (cumulative total = 12)

The total is returned as 12 ears.

Bunny Ears 2

http://codingbat.com/prob/p107330

Here is the setup of the problem:

We have bunnies standing in a line, numbered 1, 2, … The odd bunnies (1, 3, ..) have the normal 2 ears. The even bunnies (2, 4, ..) we’ll say have 3 ears, because they each have a raised foot. Recursively return the number of “ears” in the bunny line 1, 2, … n (without loops or multiplication).

public int bunnyEars2(int bunnies) {
  if (bunnies == 0){
    return 0;
  } else if (bunnies % 2 != 0){
    return 2 + bunnyEars2(bunnies-1);
  } else{
    return 3 + bunnyEars2(bunnies-1);
  }
}

For this one, let’s use an input of 5. We would expect the output to be 12 since bunnies 1, 3, & 5 have a total 6 ears and bunnies 2 & 4 have a total of 6 ears.

Line 3 will not be run since the condition set in line 2 is FALSE. Currently, bunnies is set to 5.

So, we move on to line 4. This condition is looking to see if we are working with an even numbered or odd numbered bunny. We have set the condition to use the modulus of 2 of the integer of bunnies. If the modulus is NOT 0, then the statement is TRUE and therefore it is an ODD numbered bunny.

Line 6 is the start of the default case which is used if we are working with an EVEN numbered bunny.

Now, bunnies = 5, so line 2 is FALSE, and line 4 is TRUE. We return a 2 and add that to the number of bunny ears from the next bunny (bunnies – 1), which is bunny #4.

Now, bunnies = 4, so line 2 is FALSE, line 4 is FALSE, so we run the default case at line 6. We return a 3 and add that to the number of bunny ears from the next bunny (bunnies -1), which is bunny #3.

Now, bunnies = 3, so line 2 is FALSE, and line 4 is TRUE. We return a 2 and add that to the number of bunny ears from the next bunny (bunnies – 1), which is bunny #2.

Now, bunnies = 2, so line 2 is FALSE, line 4 is FALSE, so we run the default case at line 6. We return a 3 and add that to the number of bunny ears from the next bunny (bunnies -1), which is bunny #1.

Now, bunnies = 1, so line 2 is FALSE, and line 4 is TRUE. We return a 2 and add that to the number of bunny ears from the next bunny (bunnies – 1), which is 0.

Now, bunnies = 0, so line 2 is now TRUE, so we return a 0 and exit the loop.

We now add the following together:

  • 0 from when bunnies = 0 (cumulative total = 0)
  • 2 from when bunnies = 1 (cumulative total = 2)
  • 3 from when bunnies = 2 (cumulative total = 5)
  • 2 from when bunnies = 3 (cumulative total = 2)
  • 3 from when bunnies = 4 (cumulative total = 10)
  • 2 from when bunnies = 5 (cumulative total = 12)

The total is returned as 12 ears.

Triangle

http://codingbat.com/prob/p194781

Here is the setup of the problem:

We have triangle made of blocks. The topmost row has 1 block, the next row down has 2 blocks, the next row has 3 blocks, and so on. Compute recursively (no loops or multiplication) the total number of blocks in such a triangle with the given number of rows.

public int triangle(int rows) {
 if (rows == 0){
   return 0;
 } else {
   return rows + triangle(rows - 1);
 }
}

Here, we are building something that looks like this:

Like the cases before it, line 2 is a condition looking for when we are to row 0. If line 2 is FALSE, we will move to line 4. For this example, let’s use rows = 4. With this, the output should be 10 as there are 10 cubes needed to complete a 4 row triangle.

So, we start with rows = 4. Line 2 is FALSE, so we move to line 4 to execute line 5, where we return the row number and add it to the number of cubes on the next row (rows – 1), which is row #3.

We are returning the row number as that is equal to the number of cubes of each row (e.g. row 7 = 7 cubes, row 4 = 4 cubes, etc…).

We now move to rows = 3. Line 2 if FALSE, so we move to line 4 to execute line 5, where we return the row number and add it to the number of cubes on the next row (rows – 1), which is row #2.

We now move to rows = 2. Line 2 if FALSE, so we move to line 4 to execute line 5, where we return the row number and add it to the number of cubes on the next row (rows – 1), which is row #1.

We now move to rows = 1. Line 2 if FALSE, so we move to line 4 to execute line 5, where we return the row number and add it to the number of cubes on the next row (rows – 1), which is 0.

Now, rows = 0, so line 2 is now TRUE, so we return a 0 and exit the loop.

We now add the following together:

  • 0 from when rows = 0 (cumulative total = 0)
  • 1 from when rows = 1 (cumulative total = 1)
  • 2 from when rows = 2 (cumulative total = 3)
  • 3 from when rows = 3 (cumulative total = 6)
  • 4 from when rows = 4 (cumulative total = 10)

CS2 12-Jan-2018

Lesson Name:

2-D Arrays

TEKS – §126.34 (Computer Science 2):

  • c.3 – Research and information fluency. The student locates, analyzes, processes, and organizes data. The student is expected to:
  • c.3.D – manipulate data structures using string processing;
  • c.3.F – identify and use the structured data type of one-dimensional arrays to traverse, search, modify, insert, and delete data;
  • c.3.G – identify and use the structured data type of two-dimensional arrays to traverse, search, modify, insert, and delete data;

Lesson Objectives:

  1. The student will be able to create and manipulate a 2-D array.
  2. The student will be able to explain the difference and uses of a 1-D array and a 2-D array.

Materials Needed:

  1. NetBeans

Description of Lesson:

Students will analyze the purposes, functions, and uses of a 1-D array compared to a 2-D array using Excel. Students will then create a 2-D array of their class schedule with the period, class name, and teacher name.

public class carl {
    public static void main(String[] args){
        String[][] mySchedule = {
            { "1AB", "Principles of Applied Engineering", "Evans" },
            { "2A", "Computer Science 1", "Evans" },
            { "2B", "Computer Science 2", "Evans" },
            { "3A", "FTC 11242 Robotics", "Evans" },
            { "3B", "FTC 12645 Robotics", "Evans" },
            { "4A", "Computer Science 1", "Evans" },
            { "4B", "Conference & Planning", "Evans" },
            { "5AB", "Principles of Applied Engineering", "Evans" },
        };
        for(int row = 0; row < 8; row++){
            for(int col = 0; col < 3; col++){
                System.out.print(mySchedule[row][col] + " ");
            }
        System.out.println("");
        }
    }
}

Grade(s):

  • Daily Grade – 2-D Array

CS2 10-Jan-2018

Lesson Name:

Stacks vs Arrays

TEKS – §126.34 (Computer Science 2):

  • c.3 – Research and information fluency. The student locates, analyzes, processes, and organizes data. The student is expected to:
  • c.3.D – manipulate data structures using string processing;
  • c.3.F – identify and use the structured data type of one-dimensional arrays to traverse, search, modify, insert, and delete data;

Lesson Objectives:

  1. The student will be able to create and manipulate a stack data structure.
  2. The student will be able to create and manipulate a 1-d array structure.

Materials Needed:

  1. NetBeans
  2. stackedData.dat File (queued phone calls)
  3. arrayData.dat File (numbered list)

Description of Lesson:

Students will create a basic stack of 10 queued phone calls and pull the top item off of the stack. Discussion will focus on the fact that items are read from top to bottom from the data file. As such, items at the bottom of the file are the last ones placed into the stack.

import java.io.*;
import java.util.*;

public class adam {
    public static void main(String[] args) throws IOException{
    Scanner numbers = new Scanner( new File("stackedData.dat")); //Accesses the data file.
      Stack firstStack = new Stack(); //Constructor to build an empty stack called "firstStack".
      while(numbers.hasNextLine()){ //Opening loop that run as long as the file has a nextLine.
        firstStack.push(numbers.nextLine()); //Loop executes a push to enter the data from the data file to the stack.
      } //Closes the while loop.
      System.out.println("Next Call in Queue is " + firstStack.pop()); //Outputs the item on the top of the stack. Item is removed.
     }
}

Students will then create a 1-D array of a set of numbers. They will manipulate that data set as well.

import java.io.*;
import java.util.*;
import java.util.Arrays;

public class billy {
    public static void main(String[] args) throws IOException{
    Scanner nmbrs = new Scanner( new File("arrayData.dat"));
        int[] myNewArray = new int[10];
        int indexNumber = 0;
        while (nmbrs.hasNext()){
            int numberFromFile = nmbrs.nextInt();
            myNewArray[indexNumber] = numberFromFile;
            indexNumber++;
        }
    System.out.println("Unsorted: " + Arrays.toString(myNewArray));
    Arrays.sort(myNewArray);
    System.out.println("Sorted: " + Arrays.toString(myNewArray));
    int subtr = myNewArray[9] - myNewArray[8];
    System.out.println(myNewArray[9] + " - " + myNewArray[8] + " = " + subtr);
    }
}

Grade(s):

  • Daily Grade – Stack (50%) / Array (50%)

Computer Science 2 S&S

At the conclusion of last school year, I had a curve-ball thrown at me concerning my plans to offer AP Computer Science 2 based upon an adopted AP syllabus when I requested the course authorization. This course would align with the AP Computer Science – A Exam. In addition, the course would count as a Language Other Than English (LOTE) credit for our students.

Well, the State of Texas had other plans on that. According to TEA, Computer Science 2 can count as an AP credit OR a LOTE credit, but NOT both.

As we already have HB-5 students in progress that need CS2 as their second LOTE credit, we have elected to drop the AP designation. However, I am still modeling the course after the AP CS2 curriculum from the adopted syllabus, which will allow the students to be prepared to take the AP Computer Science – A Exam at the conclusion of the year, if they would like.

Here is what I am planning to cover in CS2 this year:

  • Weeks 1 – 2
    • Computer Systems
      • Numerical Representations, Limitations of Finite Representations, Number Bases & Conversions, Hardware, and Programming Languages
  • Weeks 3 – 4
    • Objects & Primitive Data
      • Simple Data Types (int, Boolean, double, char), Variable & Constant Declarations, Assignment & Arithmetic Expressions, Console Output, Primitives vs. Objects, Create Objects with Classes, References, JAVA Library Classes (String, Integer, Double, Math, & Scanner), and Random Numbers
  • Weeks 5 – 6
    • Conditional Programming Statements
      • Software Development Process, Control Flow, Boolean Expressions, Laws, Truth Tables, and Conditional Expressions
  • Weeks 7 – 9
    • Iterative Statements
      • Flow of Control, While, For, Infinite, and Nested Loops, and Algorithm Analysis (Running Time and Execution Counts)
  • Weeks 10 – 12
    • Writing Classes
      • Anatomy of Classes (Constructors & Methods, Declarations of Class, Interface, Instance, variable, Method and Parameter), Method Overloading, Method Decomposition, Object Relationships, Pre & Post Conditions, and Data Abstraction & Encapsulation
  • Weeks 13 – 15
    • Enhancing Classes
      • References, Exceptions, Class Design, == vs equals, Object Parameter Passing, Error Handling, Interfaces & Abstract Classes, JAVA Library Classes (Comparable & List Interfaces) and Identifications of Reusable Components from Existing Code Using Classes and Class Libraries
  • Weeks 16
    • Fall Semester Exam Review
  • Week 17
    • Fall Semester Exam
    • Week 18 – 21
      • 1D/2D Arrays & Searching
        • 1-Dimensional & 2-Dimensional Arrays (Creation, Insertions, Deletions, Transversals, & Algorithms), Searching Algorithms & Comparison (Sequential & Binary), and Choosing Appropriate Data Representation & Algorithms
    • Weeks 22 – 24
      • Lists, Array Lists, Selection & Insertion Sorts
        • Lists & Array Lists (Creation, Insertions, Deletions, Transversals, & Algorithms), Sorting Algorithms & Comparison (Selection & Insertions, and Choosing Appropriate Data Representation & Algorithms
    • Weeks 25 – 27
      • Inheritance
        • Inheritance (Subclass, Overriding, Hierarchies, Using Class Members, Polymorphism, & Class Hierarchy Design), Interfaces & Abstract Classes, JAVA Library Classes (Object), Reading & Understanding Class Specifications (is-a vs. has-a), Understanding & Implementing a Given Class Hierarchy, Extending a Given Class with Inheritance, and Applying Functional Decomposition.
    • Weeks 28 – 30
      • Recursion / Merge & QuickSorts
        • Recursive (Thinking, Programming, & Sorting), Flow of Recursive Control, Sorting Algorithms (Merge & Quick), and Comparison With Other Sort Options
    • Weeks 31 – 33
      • AP Practice Exam and Computer Ethics
        • Responsible Use of Computer Systems (Reliability, Privacy, Intellectual Property, Legal Issues, & Social/Ethical Ramifications of Computer Use), and AP Practice Exam
    • Week 34
      • AP Computer Science – A Exam
    • Weeks 35 – 36
      • RoboCode
        • Cooperative Programming, Research, Reading Code, and Comparing Strategies & Algorithms