Tangible Introduction to Stacks

After we spend a day getting back into a coding mindset in Computer Science, we’ll be starting a new unit over data structures. The first structure we’ll be looking at are stacks.

I’m reflecting on something that Dr. Sabrina McCullough used to tell us when she was leading our elementary math training sessions about the importance of introducing a new skill or concept using concrete / real-world / tangible examples.

I applied this when I introduced iterative structures such as for loops, while loops, and do while loops. My students can tell you that I had them walking in circles for a while, but they understood the difference between the types of loops before we ever coded anything!

To start, I am going to have the students tear a sheet of paper into 8 semi-equal pieces. They are going to answer the following questions in this order recording an answer on each piece of paper and stacking them one on the other face-down as they record their answers.

  1. What is your favorite breakfast food?
  2. What is your favorite junk food?
  3. What is your favorite school holiday?
  4. How old are you?
  5. What grade are you in?
  6. What month is your birthday?
  7. What year is it now?
  8. What is your favorite color?

Once the last question is answered, I will have them look at their small stack and ask them the following questions:

  1. As you added a new item to your stack, where did you put it? (top, bottom, or middle)
  2. If you needed to search through your stack for something, where would you start? (top, bottom, or middle)

Next, I will give each student a stack of 8 index cards. The cards will be randomly numbered with the exception of the 3rd card in each stack, which will have the number 25.

Before the students are given their cards, they will be given the rules:

  • Do not do anything with the cards until you are told to do so.
  • You can only have one card face-up at a time.
  • You can only take from the top of the stack.
  • If you perform any sort of calculation beyond a search on a card, that card is removed from the stack and “discarded”.

I will then walk them through a series of exercises with their stack of cards:

  1. Write down the cards in the stack in order.
    Return stack to original.
  2. Search for the card with 25. How many cards were above it?
    Return stack to original.
  3. Take top card and multiply it by 10.
    Discard top card from stack.
  4. Search for the card with 25. How many cards were above it?
    Return stack.
  5. Take top card and multiply by 5.
    Discard top card from stack.
  6. Search for the card with 25. How many cards were above it?
    Return stack.
  7. Write down the cards in the stack in order.
    Return stack.

Once this information has been recorded, the following questions will be asked:

  1. How many cards can we interact with at a time?
    (Answer = 1)
  2. What was the pattern each time you searched for the card with 25 on it?
    (Answer = it was getting closer to the top)
  3. Can we do any calculations with cards below the current top of the stack?
    (Answer = No)
  4. When I place an item on a stack, where does it go?
    (Answer = On the top)
  5. When I take an item off of a stack, where does it come from?
    (Answer = On the top)
  6. How does the term LIFO (Last In – First Out) apply to a stack?
    (Answer = The last item added to the stack is the first item to be removed)

Once we go through this, we’ll then move into basic programming that was discussed in the post http://funmultiplies.com/starting-with-stacks

Hopefully, giving them a tangible example of how a stack works will assist them with the abstract reasoning of working with stacks as a Computer Science data structure.

AP or Dual Credit Computer Science

In addition to Robotics, Computer Science, and Principles of Technology, I teach 4 sections of Business Information Management I (BIM) I. The BIM class is offered as a dual credit course through Navarro College in Corsicana, TX.

While I was completing the credentialing process for Navarro, I noticed that they offer several Computer Science courses that are in-line with our 3 proposed courses. This made me wonder for a moment, is Advanced Placement the best option for our students?

The Case For Dual Credit / Against AP

I have spoken with several different administrators and they are excited about the possibility of offering the Computer Science courses as dual credit as opposed to Advanced Placement.

The reasoning for their excitement is that if the course is offered as dual credit, the student must complete the assigned work and assessments satisfactorily and at the conclusion they receive college credit. Under the Advanced Placement option, the student must do this as well and meet a minimum score of a College Board created/administered exam.

The dual credit solution also allows us to offer Computer Science I, Computer Science II, and Computer Science III as college-level courses. Under the Advanced Placement option, only Computer Science I and Computer Science II would be college-level courses.

In a dual credit scenario, the students will know exactly which college-level courses they are receiving credit for at Navarro College. Under the Advanced Placement option, students have an idea of which courses the Advanced Placement credit will cover but there is no guarantee.

The Case for AP / Against Dual Credit

Having worked for a time in higher education, I have had the chance to see what lies on the other side of the fence. In the world of higher education, faculty are many times admonished if their percentage of “A’s” or passing is too high. This is the concept of grade inflation. Institutions of higher education don’t want to appear that “everyone passes and gets an A!” They have an appearance of academic rigor to uphold.

In the world of K-12 education, we have almost the exact opposite. In K-12, faculty are admonished if their failure percentage is too high. For example, where I am at now, a failure rate above 15% is unacceptable.

As such, let’s look at some grades for 15 fictional students:

  • Student A – 90
  • Student B – 88
  • Student C – 57
  • Student D – 65
  • Student E – 97
  • Student F – 73
  • Student G – 94
  • Student H – 82
  • Student I – 76
  • Student J – 79
  • Student K – 82
  • Student L – 88
  • Student M – 94
  • Student N – 45
  • Student O – 85

In this example, the class average is 79.67% with a failure rate of 20%.

To bring that failure rate down to under the 15% threshold, I would have to find some way to bring the grade of “Student D” up to passing as they are the closest to passing.

If we apply a curve based upon the formula of
grade + (square root (grade) X 0.6)
we get the following:

  • Student A – 90 –> 96
  • Student B – 88 –> 94
  • Student C – 57 –> 62
  • Student D – 65 –> 70
  • Student E – 97 –> 100
  • Student F – 73 –> 78
  • Student G – 94 –> 100
  • Student H – 82 –> 87
  • Student I – 76 –> 81
  • Student J – 79 –> 84
  • Student K – 82 –> 87
  • Student L – 88 –> 94
  • Student M – 94 –> 100
  • Student N – 45 –> 49
  • Student O – 85 –> 91

The class average is now 85% with a failure rate of 13.3%.

So, in the world of K-12 education, this class is now clear of any additional scrutiny of its grades. However, “Student D” who did not demonstrate mastery of the skills has passed.

Let’s assume that “Student D” performs the same way for the entire year – just barely passing due to the curves. This student leaves high school receives college-level credit for the class and believes they are ready for the next-level course, when they are not.

In contrast, an Advanced Placement course could also be held to the same grading guidelines and “Student D” would receive their passing grade in the course. However, to have the possibility to receive college credit, “Student D” would have to score high enough on the College Board exam for that course. Given the performance of “Student D” in the class, they would likely not score high enough to receive college-level credit.

Personal Opinion

I have spoken with administrators at both the K-12 and higher education levels and have come to a final decision.

My initial thoughts are that dual credit Computer Science would be a great solution for my students in the short term as they would be all but guaranteed college-level credit. They would get the “feel good” feeling of receive college credit.

However, in the long-term, I feel that Advanced Placement is the best solution because if counteracts the grade inflation inherent in K-12 education with the College Board exam. Here, the “feel good” feeling of receiving college credit would be genuine as they would have passed an effective 3rd party exam.

As the majority of students taking the class will pursue college after high school, the long-term solution of Advanced Placement seems to be the best option at this time.

How to Make It Better

There are a few different options that could be done to make this better for everyone involved all-around and level the attractiveness of both options for the short-term and long-term:

  1. Remove punitive actions for failure rates in excess of 15% in college-credit classes.
  2. Add oversight to monitor failure rates in college-credit classes and transfer students to non-college-credit classes when justified.
    NOTE: This is already done for many Advanced Placement courses but not Dual Credit.
  3. Genuinely align classroom, campus, and district expectations of college-credit participants (teachers & students) to those of the college that the credit is awarded through.

Starting with Stacks

Our next unit in Computer Science is working with data structures. So far, all we have done is take keyboard input or hard-coded input and done immediate calculations with it. We’ve not actually stored or manipulated any data.

We’re going to start with stacks as those are arguably the easiest data structure to understand.

//Program Name: Starting with Stacks
//Programmer Name: Eric Evans, M.Ed.
//Programmer Organization: Ferris High School
//Program Date: Spring 2017

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

public class stacks {
    public static void main(String args[]){
        Stack myStack = new Stack();
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        myStack.push(5);
        myStack.push(6);
        myStack.push(7);
        myStack.push(8);
        myStack.push(9);
        myStack.push(0);
        System.out.println("Current Stack: " + myStack);
        System.out.println("Value of 1 is located " + myStack.search(1) + " positions from the top of the stack.");
        System.out.println("");
        System.out.println("First Removed Object is: " + myStack.pop());
        System.out.println("Current Stack: " + myStack);
        System.out.println("Value of 1 is located " + myStack.search(1) + " positions from the top of the stack.");
        System.out.println("");
        System.out.println("Next Removed Object is: " + myStack.pop());
        System.out.println("Current Stack: " + myStack);
        System.out.println("Value of 1 is located " + myStack.search(1) + " positions from the top of the stack.");
        System.out.println("");
        System.out.println("Next Removed Object is: " + myStack.pop());
        System.out.println("Current Stack: " + myStack);
        System.out.println("Value of 1 is located " + myStack.search(1) + " positions from the top of the stack.");
        System.out.println("");
        System.out.println("Next Removed Object is: " + myStack.pop());
        System.out.println("Current Stack: " + myStack);
        System.out.println("Value of 1 is located " + myStack.search(1) + " positions from the top of the stack.");
        System.out.println("");
        System.out.println("Next Removed Object is: " + myStack.pop());
        System.out.println("Current Stack: " + myStack);
        System.out.println("Value of 1 is located " + myStack.search(1) + " positions from the top of the stack.");
    }
}

As you can see here, we created a new stack on line 11 named myStack and then pushed the integer 1, 2, 3, 4, 5, 6, 7, 8, 9, & 0 into that stack on lines 12 through 21.

Line 22 displays the content of the stack, which at this moment is the following:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 0]

Line 23 uses the search method to display the current position of a searched item, in this case, the integer “1”. Remember, the search method of a stack returns the position relative to the top of the stack. At this point in the application, the integer “1” is located at position 10.

At Line 25, we use the pop method to return the value at the top of the stack. Since this object was handled, it has now been removed from the stack.

Line 26 is identical to line 22 in that it displays the content of the stack at that moment. However, since the top item has been removed from the stack, it now looks like the following:

[1,2,3,4,5,6,7,8,9]

Line 27 is identical to line 23 and provides the position of the searched item, in this case the integer “1” in relation to the top of the stack. Since the top item has been removed, the search item is now one position closer to the top of the stack.

Lines 29-31, 33-35, 37-39, and 41-43 all perform the same functions as lines 25-27. Each time, the top item from the stack is removed, the current stack is displayed, and the position of the searched item in relation to the top of the stack is provided.

Interactive Stacks

Additionally, we will look at adding interactivity to the process as opposed to hard-coding the data.

//Program Name: Starting with Stacks
//Programmer Name: Eric Evans, M.Ed.
//Programmer Organization: Ferris High School
//Program Date: Spring 2017

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

public class stacks {
    public static void main(String args[]){
        Stack myStack = new Stack();
        Scanner myInput = new Scanner(System.in);
        System.out.print("Enter 10 Integers Separated by a Space and Press Enter: ");
        for(int myCounter=1; myCounter <11; myCounter++){
            myStack.push(myInput.nextInt());
        }
        System.out.println("Current Stack: " + myStack);
        System.out.println("Value of 1 is located " + myStack.search(1) + " positions from the top of the stack.");
        System.out.println("");
        System.out.println("First Removed Object is: " + myStack.pop());
        System.out.println("Current Stack: " + myStack);
        System.out.println("Value of 1 is located " + myStack.search(1) + " positions from the top of the stack.");
        System.out.println("");
        for(int myPopCounter=1; myPopCounter < 5; myPopCounter++){
            System.out.println("Next Removed Object is: " + myStack.pop());
            System.out.println("Current Stack: " + myStack);
            System.out.println("Value of 1 is located " + myStack.search(1) + " positions from the top of the stack.");
            System.out.println("");
        }
    }
}

Here, you can see that we’ve streamlined the code considerably. What was lines 25 through 43 is now lines 24 through 29! We utilized a for loop to execute the segment of code through 5 iterations.

In addition, the keyboard inputs are being processed through a for loop located at lines 14-16. This loop runs 10 iterations of the nextInt() method of the scanner object myInput and using the push method of the stack object myStack places them into the stack.

This code runs identical to the code above but the user can enter their own data as opposed to having to utilize the hard-coded data.

Items to Discuss

Next class, we’ll be discussing how the search handles multiple occurrences of the same item. For example, let’s say that a user entered their data to create the following stack:

[1,2,3,4,5,1,2,3,4,5]

In this case, if we used the search method to locate the integer “1”, which integer “1” would be displayed?

We will also analyze the advantages and the disadvantages of stacks as a data structure. This will take us to the next data structure, 1-dimensional arrays.

Semester Review – Computer Science

When my Computer Science I students return in January, I will be giving them the following assignment:

Create a JAVA application that has users guess a pre-selected number as a game. The application should provide the rules of the game which state a random number between 0 and 100 will be chosen and users will be given a maximum of 20 guesses.

When asking the user for each guess, the application should indicate which guess of the 20 the user is on and whether their guess was too high or too low.

If the user guesses the solution in under 20 guesses, they will be congratulated and given the number of guesses it took for them to arrive at the solution.

If the user exceeds the maximum number of allowed guesses, they will be told they have exceeded the allowed number of guesses and will be provided with what the solution was.

While there are numerous ways this problem could be tackled, here is one possible solution that is similar to what I would expect at this point in the year:

//Program Name: Guess My Number
//Programmer Name: Eric Evans, M.Ed.
//Programmer Organization: Ferris High School
//Program Date: Spring 2016
import java.util.*;
import java.lang.*;
import java.io.*;
public class guessNumber{
    public static void main (String[] args){
        System.out.println("Welcome to the Number Guessing Game");
        System.out.println("");
        System.out.println("I will pick a number at random and your job is to guess the number that I have chosen.");
        System.out.println("The number will be between 0 and 100. I will give you clues after each guess.");
        System.out.println("You will have up to 20 guesses to guess my number.");
        System.out.println("");
        Scanner ready = new Scanner(System.in);
        System.out.print("Are you ready to start? (Y or N)");
        String readyGo = ready.next();
        String readyGoUC = readyGo.toUpperCase();
        if (readyGoUC.equals("Y")){
            double randomNumber = Math.random() * 100;
            int randomNumberInt = (int)randomNumber;
            Scanner myGuessInput = new Scanner(System.in);
            System.out.print("What is your first guess? ");
            int myGuess = myGuessInput.nextInt();
            while(readyGoUC.equals("Y")){
                for (int score = 1; score < 20; score++){
                    if(randomNumberInt > myGuess){
                        System.out.println("Too Low. Try a Higher Number");
                        myGuessInput = new Scanner(System.in);
                        System.out.print("What is your #" + score + " guess? ");
                        myGuess = myGuessInput.nextInt();     
                    }else if(randomNumberInt < myGuess){
                        System.out.println("Too High! Try a Lower Number");
                        myGuessInput = new Scanner(System.in);
                        System.out.print("What is your #" + score + " guess? ");
                        myGuess = myGuessInput.nextInt();
                    }else if(randomNumberInt == myGuess){
                        System.out.println("");
                        System.out.println("Congratulations! You Guessed my Number!");
                        System.out.println("");
                        System.out.println("Number of Guesses = " + score);
                        System.out.println("");
                        System.out.println("Exiting Program");
                        System.exit(0);
                    }
                }
                System.out.println("");
                System.out.println("You have exceeded the maximum number of guesses.");
                System.out.println("");
                System.out.println("The number I picked was " + randomNumberInt);
                System.exit(0);
            }
        } else{
            System.out.println("Thank you for playing.");
            System.out.println("Exiting Program");
            System.exit(0);
        }
    }
}

This solution utilizes several of the skills covered in the first semester of Computer Science I including the use of character, string, integer, double, and scanner variable types. In addition, the toUpperCase and equals methods of the String class are used as is the random method of the Math class.

Also, in this possible solution, if/else, for, and while statements are all utilized along with various Boolean operators.

Coding Bat – mixStart

This exercise requires that the program return the value of true if what has been entered is a 3-letter word with the 2nd and 3rd letters being “ix”.

Here is the code that you start with:

public boolean mixStart(String str) {
  
}

As you can see, we have a String variable named “str”.

public boolean mixStart(String str) {
  if (str.length() < 3) return false;
  String two = str.substring(1, 3);
  if (two.equals("ix")) {
    return true;
  } else {
    return false;
  }
}

In the solution, first check the length of the statement using the length function of the String class. If the length is less than 3 characters long, the program stops running and returns “false”.

Assuming that the value of “str” is at least 3 characters long we move to using the substring function of the String class to create the value to be assigned to variable “two”. The substring starts at index 1 and stops at index 3. This means that the variable “two” will only have the 2nd and 3rd letters of the variable “str”.

We now begin the analysis of the variable “two”. If it is “ix” then the program returns true. However, if it is NOT “ix” then the program returns false.

You will notice that the comparison is being made using the following:

if (two.equals("ix")) {

Some have asked if we could use something similar to the following:

if (two == "ix") {

While this looks like this would work in comparing a string variable to an existing string, we must use the equals function of the String class to determine if two strings are equivalent.

Traditional boolean operators such as == and != do not work when comparing strings.

Coding Bat – parrotTrouble

This exercise requires that the program return the value of true if you are in “trouble” and a value of false if you are not in “trouble”. You are in trouble if the parrots are talking before 07:00am or after 08:00pm.

Here is the code that you start with:

public boolean parrotTrouble(boolean talking, int hour) {
  
}

As you can see, we have a boolean named talking and an integer named hour.

public boolean parrotTrouble(boolean talking, int hour) {
  return (talking && (hour < 7 || hour > 20));
}

The solution uses a nested boolean to see if the time is before 7 OR after 20. It is simultaneously looking to see if the parrots are talking.

We are using an AND to bridge these two boolean statements together because if the parrots are NOT talking, we can’t be in trouble regardless of the time of day.

Coding Bat – sumDouble

This exercise requires that the program return the sum of two provided numbers. If the two provided numbers are the same, the sum is to be doubled.

Here is the code that you start with:

public int sumDouble(int a, int b) {
  
}

As you can see, we have two integers (a and b) that have been declared.

public int sumDouble(int a, int b) {
  int sum = a + b;
  if (a == b) {
    sum = sum * 2;
  } 
  return sum;
}

In this solution, we have created an integer variable named “sum” which has the value of “a” added to “b”.

We then move to a conditional statement. If “a” equals “b”, the variable “sum” is multiplied by 2. We only enter this instruction if “a” and “b” are equal to each other.

Following either entry of the IF statement or bypassing it, we display the value of the variable “sum”.

Coding Bat – sleepIn

This exercise requires that the program return “true” if it is OK to sleep in on a given day. The rules are that you can sleep-in on a day that is not a weekday or on a vacation day.

Here is the code that you start with:

public boolean sleepIn(boolean weekday, boolean vacation) {
 
}

As you can see, we have a boolean named weekday and a boolean named vacation.

public boolean sleepIn(boolean weekday, boolean vacation) {
  if (!weekday || vacation) {
    return true;
  }  
  return false;
}

The solution uses a boolean conditional of if the value is NOT a weekday OR a vacation, it will return true, otherwise it will return false.

Fall Semester Grades Almost Done!

Almost to the finish line! Only have 1 1/2 days of school left! The 2nd quarter of the year is done, the semester exams are done, and we’re ready to start closing out the books on the first half of the 2016/2017 school year.

Semester 1 Grade Progress
Semester 1 Grade Progress

All of my classes are closed for the semester with the exception of one (BIM 3B). One of my students was absent today and missed his exam. He will make it up next week and then I’ll be ready to close out this semester.

It’s been an interesting first half of the school year! Have learned that we need a structured curriculum for robotics and alignment of it with the FIRST Tech Challenge robotics competition program.

We also need to reduce the number of students in Principles of Technology to a number that does not exceed the number of computers/seats in the room.

Quarter 2 Report Card Grades

It’s only been 3 weeks since we discussed grades, but it’s been 9-weeks since we last discussed grades in relation to loss of eligibility for UIL. We are closing out the 2nd quarter of the year and this is when students can both gain AND lose their eligibility.

Continuing the practice I started at PR4, I continued to adjust grades to be in alignment with the campus policies for grade distribution. In the graphs below, the black represents the original (uncurved) grades for the grading period and the orange represents the modified (curved) grades for the grading period.

The first cluster is percentage of A’s, the second cluster is percentage of B’s, the third cluster is percentage of C’s, and the final cluster is percentage of F’s.

2nd Quarter - Computer Science
2nd Quarter – Computer Science
2nd Quarter - Principles of Technology
2nd Quarter – Principles of Technology
2nd Quarter - Robotics & Automation
2nd Quarter – Robotics & Automation
2nd Quarter - BIM (All Sections)
2nd Quarter – BIM (All Sections)

At the time of this writing, my current enrollment numbers are as follows:

  • Computer Science I – 15 Students (1 Section)
  • Principles of Technology – 26 Students (1 Section)
  • Robotics & Automation – 18 Students (1 Section)
  • Business Information Management I – 84 Students (4 Sections)