5/18/13 The end (for now)

Please note: in this post, I will be talking about my experience in AP computer science. If you just want to hear about what is going to happen to the blog, just read the last two paragraphs.

Thought this year, I have learned a lot about programming and java. In the beginning of the year, I was making the system council display “hello world” but by the end, I have created an AI that can play Quiz Bowl. I feel that by taking this AP computer science course, I feel confident to say that I can code fluent java. Not only do I feel that I know java, but I am also confident that I scored a 4 or 5 on the AP exam.

During the beginning of the year, we were learning about strings and I thought it inconceivable that indices start counting at 0 while the .length() method returns the last index as if the first index was 1. Later on, when we were learning about arrays, I found the idea to make perfect sense. I find it very cool how these things (like the length method and the rules for indices, as well as the range from a call of substring and the range for Math.random()) that appear to have completely nonsensical rules fit together in such an elegant manor (If you have arr[(int) (Math.random()*arr.length)], you will get a random index of arr).

I also found it cool to learn about evaluating Boolean expressions, but I wish that we would have spent more time doing that (learning about expressions like Xor and nor) and also looked at some graphic examples of the expressions (like Venn diagrams). I like how the class both prepared us for the AP, but also allowed room for learning fun and amazing concepts. The only thing that I wish I would have known better for the AP exam was Grid World (a case scenario used by the AP exam that has different actors on a Grid).

Thought the year, my favorite thing was probably when we programmed pong (and brick break for extra credit). I liked programming pong because it took all the knowledge that we had learned up to that point in the year, and use it to make a playable video game. My favorite topic that we learned this year was sorting. As you can probably tell from some of my pervious posts, I really like sorting data structures. Sorting seems like such a simple task when you first look at it (you are just sorting a list after all), but there are so many ways to do it, and they each have their own set of advantages/disadvantages. I also liked the labs where we would write a sorting algorithm and compare its speed to that of Collections.sort();.

Now that the AP exam is over, we get to spend our periods in Computer Science working on whatever CS project we want (everything from a Windows Kinect to Google apps script to coding Android apps with Java), and I wish that we would have gotten to do this kind of thing more often thought the year. As you can tell from the title of this post, it will be the last one that I am to do this year; however, my computer science teacher will probably have us continue blogging in advanced computer programming (a class that I will be taking next year), and so you may see more posts next fall.

In advanced computer programming, we will either be learning data structures in C++, Java, and Python (all programming languages), or the class will be an Independent study where we can work on our own computer science projects. As this will be the case, my future posts will be not only about Java, but also about other languages (I also plan to learn Javascript over the summer). As always, thanks for reading, and have a good summer!

4/7/13 Recursion and divide and conquer

Recursion is when a function calls itself inside the function unless a stop condition is reached. In computer science, Recursion is not the most efficient way to solve a problem; however, it allows for you to use some algorithms that would otherwise be impossible. One such algorithm is quick sort, which works in O(n log n) time.

In quick sort, you are taking one element of an array to become a pivot point. After this, you go through all the other elements and sort them into two arrays; one with all the elements smaller than the pivot and the other with all the larger elements. After doing this, you return a new array that has the following things in the following order: A call of quick sort on the smaller array, the pivot, and then a call of quick sort on the larger array. If an array is ever one element long, quick sort just returns that one element.

Another O(n log N) sorting algorithm is called merge sort. In merge sort, you take your array and brake it down into two smaller ones. After that, you call merge sort on both of these arrays. After the arrays have been merge sorted, you know that each of them is in order, and now you just need to merge the two sub arrays. To do this, you have a counter for each sub array and you add the smaller element to your array out of the two counter's indexes and add one to that counter. If one counter is past the final element of its sub array, you just add the rest of the other sub array to the array. Then you return the newly sorted array. Again, this algorithm just returns the array if it only contains one element.

Both of these two recursive algorithms are called divide and conquer algorithms because they take the larger problem (sorting an array), and break it up into manageable peaces (one element arrays) to solve the initial problem. Such algorithms are very fast, despite the need for recursion. In general, quick sort and merge sort are two of thee fastest sorting algorithms.

3/16/13 Bubble sort and Insertion sort

In my last post I introduced big O notation, a way to categorize sorting algorithms by efficiency. Today I will teach you two O(n^2) algorithms that are good as an introduction to sorting. Because these algorithms are O(n^2), they are not very efficient and therefore are not used very often outside of introductory computer science.

The first sort algorithm that I will show you is bubble sort, the most basic of sorting algorithms. Bubble sort goes through the array until it finds something that is not in ascending order. Once it dose, it swaps this piece of data with the data that came before it. It will repeat the process until it has gone through the array as many times as the number of elements in the array. The code would look something like this:

public int[] bubbleSort(int[] arr){

 for(int x = 0; x < arr.length; x++){

  for(int i = 1; i < arr.length; i++){
   if(arr[i]<arr[i-1){
    int temp = arr[i-1];
    arr[i-1] = arr[i];
    arr[i] = temp;
   }
  }

 }

 return arr;

}

Now that you know bubble sort, I will teach you its faster cousin, Insertion sort. Despite still being inefficient, Insertion sort is a faster bubble sort. Rather than bubbling down like bubble sort, Insertion sort finds the index it wants to put a out of place number in and inserts it there. The code would look like this:

public int[] insertionSort(int[] arr){

 for(int i = 1; i < arr.length; i++){

  if(arr[i]<arr[i-1)){

   int value = arr[i]

   int toSet=0;

   for(int x = i; x>0 && arr[x-1]>value; x++){

    arr[x]=arr[x-1];

    toSet=x;

   }

   arr[toSet]=value;

  }

 }

}

Now I have shown you two different basic algorithms you can use for sorting, and If you want to find more, look here (links to wikipedia) or wait for more on them in my next few posts.

Oh and by the way, I went to the beach last week, which was a lot of fun!

3/3/13 Big O notation

If you want to preform a binary search on a set of numbers, you will first need to sort the numbers. There are many different ways that you can sort a set of numbers (which I will cover in future posts), but today I will teach you a method for defining the efficiency of a sorting algorithm, Big O notation. At its most basic level, Big O notation is simply put as O(some modification of n) where some modification of n would be representing how the time it takes to run the algorithm changes with the amount of input used. In this article, I will briefly explain each of the most commonly used modifiers with Big O notation.

The first Big O group that I will teach you is O(n^2). In this version, the time it takes for the sort to occur is directly related to the square of the number of items that you wish to sort. These types of algorithms usually use a nested for loop that will go through each element and compare it to every other element and will use this data to sort the list.

The next Big O group that I will teach you is O(n). In this version, the time it takes for the sort to occur is directly related to the number of items that you wish to sort. These types of algorithms usually use one for loop that will go through each element and sort it based off of what happens in that loop.

The last  Big O group that I will teach you is O(n log n). In this version, the extra time that It takes to add another element before sorting decreases with the more elements that you have. These types of algorithms are the most efficient and usually call another copy of their algorithm on sub sections of the list through a process called recursion (you can find the definition here). 

Now, I have shown you the three most common Big O groups; however, there are many more, but I will not discuss them all here. If you have any questions about this, just post them in the comments, and as always, I hope you have learned a thing or two about Big O notation.

2/16/13 Search basics

Lets say that you have a bunch of containers, each of which is a different size and you are looking for a container with a certain size. How would you find it? There are a couple of ways that you could go about doing this; you could look at the containers one at a time until you find one that is the correct size, or you could sort the jars by their size and then use the fact that the jars are sorted to find the jar you are looking for quickly. You may be wondering how this ties into computer science, and the answer is that you use these same basic ideas to find something inside of an array.

Lets say that you have an array of integers and you are looking for a location where you can find the number five. If the array is unsorted, you could find the index by using a for loop to go through each index until you find the number five. A generic method that will return the index of an integer in an integer array would look something like this (remember that if the index can not be found, a search algorithm will return -1):

public int search (int[] arr, int goal){
 for(int i = 0; i<arr.length; i++){
  if(arr[i]==goal){
   return i;
  }
 }
 return -1;
}

This is what is commonly known as a linear search, and is the only way to find something in an unsorted array. If your array is already sorted for you, there is a much faster way to find what you are looking for; through a binary search. A binary search will start in the middle of the array and compare what it is looking for (lets be looking for 5 again) to the middle value of the array. If 5 is larger than the middle value, you know that the index of 5 must be larger than the middle value. If 5 is smaller than the middle value, you know that the index of 5 must be smaller than the middle value. You then take this information and look for the middle index of your new selection of values and repeat the process until you find the number that you are looking for. A binary search algorithm is a little bit more tricky to code, but it would look like this (for a binary search, if the element is non existent, the search returns -1 minus (-1 times the index where it would have been)):

public int binarySearch (int[] arr, int goal){
 int min=0;
 int max=arr.length-1;
 while (min<=max){
  int middle = min+((max-min)/2);
  if(arr[middle]>goal){
   max=middle;
  }
  else if(arr[middle]<goal){
   min=middle;
  }
  else{
   return middle;
  }
 }
 return -middle;
}

So, hopefully you have learned a thing or two about searching and java. Thanks for reading!

2/9/13 Polymorphism

Have you ever wanted to create a arraylist that can only contain objects with a certain method? Believe it or not, this is completely possible using an idea called Polymorphism. You can make your arraylist only contain a certain interface, making it be so that all classes that implement the interface can be put into your arraylist. This has many advantages to it, including the ability to use the sort method without risking an error because an object in the list dose not have a compareTo method. This can also be used for objects in a game that are destroyed when they collide. In this scenario, you can have all the objects implement a collidable method and then create an arraylist of collidable objects. I want to point out that you can also do this with abstract super classes. If you have a supperclass called shape, subclasses for different shapes, and an arraylist of type shape, you could use a for each loop and print the area of each shape. I am sorry that this article is sort of short, but I have a lot of homework to get done. Anyway, I hope you learned a thing or two about java and Polymorphism.

2/3/13 Interface

Do you know where spotify gets it's music from? Well, there are is a list of methods that it uses to find your music for you. Whether or not you know how or where spotify gets its music from, it still will play music for you. This is called an Interface, and as you may have guessed,  you can use them in Java.

In Java, an Interface is a piece of code that you write that will give you a list of methods which the classes that implement it must include. Please note that this is just a list of methods, and not the methods themselves. If you implement an Interface into your code's class, you are saying that this class will define and write all the methods that the interface lists. This could be useful if you are writing classes for different shapes on a grid. Each shape could inherit from a super class that gives you the coordinates of the shape, but the area of different shapes is determined in different ways. This means that you should have an interface that says that all member classes must have a get area method. To give the shapes this Interface, you will type:

class name implements size{

where name is the shape that you want to implement this interface for. The size interface code would look something like this:

public interface size{
 public double getArea();
}

please note that an interface can have more than one method inside of it. This would look something like this:


public interface size{
 public double getArea();
 public void grow(int factor);
 public void shrink(int factor);
}

I hope that you have learned a thing or two about interfaces in java, and feel free to ask me questions in the comments.

1/26/13 Inheritance

Sometimes you are coding something using multiple classes, and you find yourself writing the same code for each of those classes. Did you know that you can make one class inherit methods and variables from another? This will allow you to create a class that contains everything that another class dose plus more! To make one class Inherit another, you would type the following after the class name and before the open brace:
extends supperclass
where supperclass is the class that you want to inherit. This will give your class access to all the methods in supperclass as well as giving a copy of all of the private variables that you can find in supperclass. If you want to run a constructor for supperclass inside of your class, you can just type:
supper(arguments);
Is this still confusing? If so, I will give you and example:
public class one{
 private int number;
 private boolean isTrue;

 public one(){
  number=0;
  isTrue=false;
 }

 public one(int num, boolean truth){
  number=num;
  isTrue=truth;
 }

 public int test(int i){
  if(isTrue){
   return number*i;
  }
  return number/i;
 }
}

public class two extends one{
 private string word;

 public two(){
  supper();
  word = "";
 }
 public two(int num, boolean truth, String str){
  supper(num, truth);
  word = str;
 }
 public int run(){
  return test(word.length);
 }
}

This code here is a very basic example for how to create a class that inherits another. As you can tell, this can be used to do a lot of things. If you do not fully understand what the relationship is between a supper and sub class, you can think of it like cars. A Honda accord would be a sub class of Honda, which in turn is a sub class of car. This would make Honda a supper class of the Honda accord and car a supper class of Honda. As this may infer, you can have two or more sub classes for one supper class. As always, I hope you learned a thing or two about Inheritance and java.

1/19/13 Eclipse

To this point in time, I have tough you how to use java, but you may be wondering, what software should I use to program in java? There are a lot of options out there to chose from, but I ultimately think that Eclipse is the best.

Eclipse is an open source software that runs java code. Unlike programs like Jgrasp, Eclipse is a lot more user friendly. While you are writing code, Eclipse is compiling it for you, and underlining your compile errors in red (much like Microsoft word does). Not only will it tell you exactly where your error is, but if you hover over the error, you will get a list of options that would fix it. Now, you don't even need to code the correction, just by clicking on the correction that you want to make, Eclipse will fix it for you! Speaking of fixing things, if you hit ctrl + shift + f, eclipse will auto format your code so that it looks nice! In the middle of calling a method? Eclipse will create a drop down list of all the programmed methods that start with what you have entered so far. Tired of typing all those set and get methods? Just go to source, and hit generate Getters and Setters, and Eclipse can do that too! Don't want to type your import statements? Just hit ctrl + shift + o, and Eclipse will do that for you. There are so many more ways to save time by using eclipse, but I will not list them here. Another useful tool is the ability to refactor your programs name. In all, I believe that Eclipse is the best platform to use when programming in java.

The one problem with Eclipse is that it is slow. Because it is constantly compiling, the computer may start lagging a little while you are writing code. Some of Eclipse's short cuts can also start getting in your way when you are trying to code things for yourself. If you want an efficient and simple platform for java, I recommend using Jgrasp. I hope that I have given you enough information to determine what platform you would like to use while programming, and if you have another platform that you use, just let me know by posting it in the comments.

1/12/13 Array Lists

A few posts ago, you learned about Arrays. The one major disadvantage to using an array is that it has a fixed size, so you need to know how many elements you will need before you create it. An arraylist is basically an array that's size can fluctuate as you use it. In this post, I will teach you how to do basic functions with arraylists.

To start of, you will need to create an arraylist. To do this, you would type:

Arraylist <Type> name = new Arraylist<Type>();

Where name is its name, and type is the data type that you want to use. When entering your data type, you will need to capitalize it . This is because you are filling the arraylist with an object that acts as the primitive data type that it represents (for an int, the object is called Integer). Fortunately, these objects can be used just like you use the primitive data type that they represent. This constructor will create an arraylist that has 10 indexes, all filled with their default value. To delete an index, you would type:

name.remove(index);

This would remove the index index from the arraylist name. After it is removed, all the other indices shift down to fill in the gap. If you are trying to go through every index in an array and delete some of them, you would need to re-check the deleted index, because the next element has shifted to that index. To add a value to the arraylist, you would type:

name.add(index, object);

This will add object at index index. If you just put object inside of the parentheses, it will be put in index 0. This will cause all the latter indices to shift up one to make space for the new one. Now that you know how to add and remove indices, you will need to return elements from your arraylist. To do this, you would type:

name.get(index);

This will return the index index from arraylist name. As you may think, to set the value of an index, you would type:

name.set(index);

There is one more arraylist method that I will teach you, the size method. Unlike other things, arraylists use a size method instead of a length one. To find the size of an arraylist, you would type:

name.size();

I hope that you learned a thing or two about java, and feel free to ask me if you have any questions about anything that I posted in any of my articles!