Part 3

Entries

November 4, 2011

First off I would like to annotate this wikipedia link <html> <a href=“http://en.wikipedia.org/wiki/Binary_tree” target=“_blank”>Trees</a> </html> Sure it's easy to just go out and find it again but I found this to be too helpful to give chance to forgeting. As that link would suggest we bagan talking about trees and sorting methods.

A tree begins with a root which is also the top of the tree, i know a little upside… okay, very upside down haha and that root is made out of the very first value entered into the tree. Then we took the definition of a tree a little furthur, size: our next stop. The size of a tree is how many total nodes there are within that tree. Lastly is the height of this mighty behemoth! and this keeps track of how many levels the tree has, starting at 0. So what i mean is that the root is level 0 and then its two children are level 1 and then their children are level 2 and then the next set of children is level 3 and so on. Such that it is represented with 2^0, 2^1, 2^2, etc…

Alrighty then, i will be splitting up my notes since one friday fell on a holiday and the other friday the school was closed and only being in class once a week :'( I miss out on a lot of cool stuff

November 11, 2011

Continuing with the tree discussion… Left and Right, how the tree sorts its values can also be represented with next and previous (for a reference to the list lingo) anyway, what this ultimately means is that if the value is greater then the node it is currently being tested against it will move to the right and if it less then then it will move to the left… to clear that up a little bit: <html> <ul style=“list-style-type: none;”>

<li>Greater Than (>)</li>
  <ul style="list-style-type: none;">
    <li>Right</li>
  </ul>
<li>Less Than (<)</li>
  <ul style="list-style-type: none;">
    <li>Left</li>
  </ul>

</ul> </html> <html> Traversing a tree - 3 common ways: <ul style=“list-style-type: none;”>

<li>While/Iteration</li>
<li>Recursion</li>
<li>Stacks</li>

</ul> </html>

Off topic notes: Hashtable = array index with either lists, trees, or stacks as the elements Code Complexity and the infinite depth of “n” is Big-O Notation

November 18, 2011

<html> <pre> The Bible of sorting Book: Sorts Chapter: yay for sorting Verse 1: </pre>

I loved this when matt said this… *clears throat* ahem!

“EAT YOUR BROCOLI, [random arm flailing] DO YOUR SORTS!”

Random Fact: Did you know, that if you say the word “Bubble Sort” quickly and kind of leave of the “t” in sort it kind of sounds like Bulbasaur.

Anyways this is the Bubble Sort… smaller elements “bubble” to the top of the list by comparing them to each other, this however is only good/acceptable means for a small amount of things to sort, there are much better methods of sorting then this one. </html>

November 25, 2011

Due to the lack of classes this past month I have had to split my notes up into four days… so sadly these are not as beefy as they normally would be… Looking back at the bubble sort again we talked about how theres this “black box” that magically does all the sorting :D hurray for magikz! It was also mentioned that the Bubble Sort is rather unique to most of the other sorts, that being it can detect when it has finished sorting stuff. Then we went into the complexity of the sort itself: <html> <pre> Best Case: 0(n) Order N Worst Case: 0(n^2) Order Nsquared Has to scan the list multiple times </pre> </html> Then we took a quick look at the Library Sort or the Gapped Insertion Sort… Now then instead of me explaining of how it works and failing at it this is the link for it <html> <a href=“http://en.wikipedia.org/wiki/Library_sort” target=“_blank”>Library Sort</a> </html> <html> <pre> And we thought it was a decent sort… Best Case: 0(n) Average Case: 0(nLOGn) Worst Case: 0(n^2) </pre> </html> And essentially what it did was allocate space where things can be placed but not have anything there. =====data Topics===== ====Structure Pointer==== It is possible to create a pointer to almost any type in C, including user-defined types. <file c> typedef struct { char name[21]; char city[21]; char state[3]; } Rec; typedef Rec *RecPointer; RecPointer r; r = (RecPointer)malloc(sizeof(Rec)); </file> ====Queues: Overrun and Underrun Conditions [Not Finished]==== ====Stacks: Underflow Condition==== A pop reveals previously concealed items, or it results in an empty stack, but if the stack is empty then it goes into an underflow state (which means no items are present in the stack to be removed) <file c> int pop(STACK *ps) { if (ps→size == 0){ fputs(“Error: stack underflow\n”, stderr); abort(); } else return ps→items[–ps→size]; } </file> ====Selection Sort Algorithm==== The algorithm works as follows: Step 1: Find the minimum value in the list Step 2: Swap it with the value in the first position Step 3: Repeat the steps above for the remainder of the list (starting at the second position and advancing each time) Effectively, the list is divided into two parts: the sublist of items already sorted, which is built up from left to right and is found at the beginning, and the sublist of items remaining to be sorted, occupying the remainder of the array. <file java> public void selectionSort(int[] arr) { int i, j, minIndex, tmp; int n = arr.length; for(i = 0; i < n - 1; i++) { minIndex = i; for(j = i + 1; j < n; j++) { if(arr[j] < arr[minIndex]) minIndex = j; } if(minIndex != i) { tmp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = tmp; } } } </file> ====Insert Sort Algorithm==== Every repetition of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list, until no input elements remain <code> public class InsertionSorter { private static int[] a; private static int n; public static void sort(int[] a0) { a=a0; n=a.length; insertionsort(); } private static void insertionsort() { int i, j, t; for (i=1; i<n; i++) { j=i; t=a[j]; while (j>0 && a[j-1]>t) { a[j]=a[j-1]; j–; } a[j]=t; } } } </code> ====Quick Sort Algorithm==== Step 1: Pick an element, called a pivot, from the list. Step 2: Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation. Step 3: Recursively sort the sub-list of lesser elements and the sub-list of greater elements. <file java> public void quickSort(int array[]) { quickSort(array, 0, array.length - 1); } public void quickSort(int array[], int start, int end) { int i = start; int k = end; if(end - start >= 1) { int pivot = array[start]; while(k > i) { while(array[i] ⇐ pivot && i ⇐ end && k > i) i++; while(array[k] > pivot && k >= start && k >= i) k–; if(k > i) swap(array, i, k); } swap(array, start, k); quickSort(array, start, k - 1); quickSort(array, k + 1, end); } else { return; } } public void swap(int array[], int index1, int index2) { int temp = array[index1]; array[index1] = array[index2]; array[index2] = temp; } </file> ====Merge Sort Algorithm==== Step 1: If the list is of length 0 or 1, then it is already sorted. Otherwise: Step 2: Divide the unsorted list into two sublists of about half the size. Step 3: Sort each sublist recursively by re-applying the merge sort. Step 4: Merge the two sublists back into one sorted list. <file java> public class mergeSort{ public static void main(String a[]){ int i; int array[] = {12,9,4,99,120,1,3,10}; System.out.println(“Values Before the sort:\n”); for(i = 0; i < array.length; i++) System.out.print( array[i]+“ ”); System.out.println(); mergeSort_srt(array,0, array.length-1); System.out.print(“Values after the sort:\n”); for(i = 0; i <array.length; i++) System.out.print(array[i]+“ ”); System.out.println(); System.out.println(“PAUSE”); } public static void mergeSort_srt(int array[],int lo, int n){ int low = lo; int high = n; if (low >= high) { return; } int middle = (low + high) / 2; mergeSort_srt(array, low, middle); mergeSort_srt(array, middle + 1, high); int end_low = middle; int start_high = middle + 1; while ¹⁾ { if (array[low] < array[start_high]) { low++; } else { int Temp = array[start_high]; for (int k = start_high- 1; k >= low; k–) { array[k+1] = array[k]; } array[low] = Temp; low++; end_low++; start_high++; } } } } </file> ====Tree: Insertion==== <file c> if(root == NULL) { root = (Tree*)malloc(sizeof(Tree)); current = root; root → right = NULL; root → left = NULL; root → value = input; root → height = 0; } else { current = root; travel(current, input); } </file> ====Tree: Removal==== <file c> int jsw_remove ( struct jsw_tree *tree, int data ) { if ( tree→root != NULL ) { struct jsw_node *p = NULL, *succ; struct jsw_node *it = tree→root; int dir; for ( ; ; ) { if ( it == NULL ) return 0; else if ( it→data == data ) break; dir = it→data < data; p = it; it = it→link[dir]; } if ( it→link[0] != NULL && it→link[1] != NULL ) { p = it; succ = it→link[1]; while ( succ→link[0] != NULL ) { p = succ; succ = succ→link[0]; } it→data = succ→data; p→link[p→link[1] == succ] = succ→link[1]; free ( succ ); } else { dir = it→link[0] == NULL; if ( p == NULL ) tree→root = it→link[dir]; else p→link[p→link[1] == it] = it→link[dir]; free ( it ); } } return 1; } </file> ====Tree: Searching==== <file c> int jsw_find_r ( struct jsw_node *root, int data ) { if ( root == NULL ) return 0; else if ( root→data == data ) return 1; else { int dir = root→data < data; return jsw_find_r ( root→link[dir], data ); } } int jsw_find ( struct jsw_tree *tree, int data ) { return jsw_find_r ( tree→root, data ); } </file> ====Tree: Traversal==== <file c> void travel(Tree *current, int input) { if(input < current → value) { if(current → left != NULL) { current = current → left; travel(current, input); } else { current → left = (Tree*)malloc(sizeof(Tree)); current = current → left; current → value = input; current → left = NULL; current → right = NULL; } } else { if(current → right != NULL) { current = current → right; travel(current, input); } else { current → right = (Tree*)malloc(sizeof(Tree)); current = current → right; current → value = input; current → left = NULL; current → right = NULL; } } } </file> ====Graphs [Not Finished]==== =====data Objective===== ====Baby Tree==== Plant meh first tree! ===Method=== Does it compile… does it work ===Measurement=== Looking at the linked list examples helped a little bit… until you get to the traversing where recursion is needed… that was not fun… ===Analysis=== * How did you do? * In order to get things done in time I took out figuring out the height of the tree… If i am even capable of doing so… just thinking about it hurts… * Room for improvement? * One: keep track of how many nodes * Two: Keep track of the height of the tree * Three: Print it out so it looks like a tree and not a list (this would be a great mind blowing challenge as well) * Four: is there another way besides using recursion for a tree? * Could the measurement process be enhanced to be more effective? * Going over recursion again haha its been a long time since I've taken C++ * Do you think this enhancement would be efficient to employ? * I would, it took some googling to figure out but wasn't that bad until you get to the output of the tree… where it stops making sense. Like a quick lecture and some examples of it before hand would be terrific :D * Could the course objective be altered to be more applicable? How would you alter it? * No altering needed here, similar in the ways of a list but different with its sorting power. It helps bring a lot of things together ===The Code=== <file c> #include <stdio.h> #include <stdlib.h> struct tree { int value; int height; struct tree *right; struct tree *left; }; typedef struct tree Tree; int main() { int input; Tree *root, *current, *temp; root = current = NULL; printf(“Please enter a number (-1 to exit) \n”); scanf(“%d”, &input); Input into the tree

      while(input != -1)
      {
              //Create the tree
              if(root == NULL)
              {
                      root = (Tree*)malloc(sizeof(Tree));
                      current = root;
                      root -> right = NULL;
                      root -> left = NULL;
                      root -> value = input;
                      root -> height = 0;
              }
              else
              {
                      current = root;
                      travel(current, input);
              }

              printf("Please enter a number (-1 to exit) \n");
              scanf("%d", &input);
      }

      plantTree(root);

}

Traverse through the tree and place the nodes void travel(Tree *current, int input) { if(input < current → value) { if(current → left != NULL) { current = current → left; travel(current, input); } else { current → left = (Tree*)malloc(sizeof(Tree)); current = current → left; current → value = input; current → left = NULL; current → right = NULL; } } else { if(current → right != NULL) { current = current → right; travel(current, input); } else { current → right = (Tree*)malloc(sizeof(Tree)); current = current → right; current → value = input; current → left = NULL; current → right = NULL; } } } Output the tree void plantTree(Tree *current) {

      if(current != NULL)
      {
              plantTree(current -> left);
              printf("%d\n", current -> value);
              plantTree(current -> right);
      }

} </file>

Experiments

HTML 5 Datalist

Question

Using HTML 5 can I use a new form tag?

Resources

<html> <a href=“http://www.w3schools.com/html5/tag_datalist.asp” target=“_blank”>W3Schools</a> </html>

Hypothesis

Depending on the browser or browser version I will be capable of utilizing the new and cool datalist tag. This tag acts like how google trys to guess what you are typing but without ajax.

Experiment

<!DOCTYPE html>
<html>
<head>
<title>HTML 5 Datalist Example</title>
</head>
<body>
 
<h4>This is how it works for browsers that support HTML 5</h4>
<label>
	Enter your favorite color:
  <br />
  	<input type="text" name="favColor" list="colors">
  	<datalist id="colors">
  		<option value="Red">
  		<option value="Green">
  		<option value="Blue">
  		<option value="Orange">
  	</datalist>
</label>
 
  <br />
 
<h4>This is how it works for browsers that don't support HTML 5</h4>
<label>
	Enter your favorite color:
  <br />
  	<input type="text" name="favColor" list="colors">
  <br />
</label>
 
<datalist id="colors">
<label>
	or select one from the list:
  <br />
  	<select name="favColor">
  		<option>Red</option>
  		<option>Green</option>
  		<option>Blue</option>
  		<option>Orange</option>
  	</select>
</label>
</datalist>
 
</body>
</html>

Data

<html>

Click on the link below in both Firefox and IE to see how it reacts… it's kind of cool <a href=“http://lab46.corning-cc.edu/~mshort3/datalist_html5/test.html” target=“_blank”>Click here</a>

Browser Support <ul style=“list-style-type: none;”>

<li>Yes</li>
  <ul style="list-style-type: none;">
    <li>Firefox</li>
    <li>Opera</li>
  </ul>
<li>No</li>
  <ul style="list-style-type: none;">
    <li>Internet Explorer</li>
    <li>Google Chrome</li>
    <li>Safari</li>
  </ul>

</ul>

</html>

Analysis

Based on the data collected:

was your hypothesis correct?
- Yes it was captain. Except with a sad finding… only 2 lonely browsers support such a neat feature
is there more going on than you originally thought? (shortcomings in hypothesis)
- I was developing this first in IE, as i often do first since that is where most of the users are (out of habit, Firefox with its console and firebug are so much nicer for a developer) So it was acting weird and what I thought at first to be incorrect. So when I switched over to Firefox, all was well :D
what shortcomings might there be in your experiment?
- The browsers could be completely failtastic XD
what shortcomings might there be in your data?
- If someone is lacking one of the supporting browsers then there wouldnt be any cool data to collect :'(

Conclusions

It had reacted the way I had thought it might. Comparing the browsers between the ones that have support and the ones that do not was kind of neat. And it really makes me hate the fact that there really isnt one ultimate browser that supports everything… Making the developer constantly check to see if it is supported and is more than capable of losing out on a lot of cool features because the browser is fail… I would also like to appologize for any incoherentness, our fire alarms are going off and will not shut off >_< its been 20 minutes!!! MY BRAINS ARE LIQUIFING!!!

Bubble Sort - Java

Question

Can the Bubble Sort method be implemented into Java, of course right? But how? O.O

I shall hopefully be able to show this

Resources

Hypothesis

We've talked about and looked at some background information on sorting, namely the Bubble Sort. With the knowledge and information that I hold I believe that I can make a Bubble sort in the language of the kings, Java. (just because it's so new to me and I am really enjoying the language so far). I will create a program that performs the Bubble method to sort the users input.

Experiment

import java.util.*;
import java.lang.*;
import java.io.*;
 
public class BubbleSort
{
	private long[] x;
	private int elements;
 
	public BubbleSort(int max)
	{
		x = new long[max];
		elements = 0;
	}
 
	//Putting Elements into the array
	public void insert(long value)
	{
		x[elements] = value;
		elements++;
	}
 
	//Displays the arrays inerds
	public void display()
	{
		for(int j = 0; j < elements; j++)
		{
			System.out.print(x[j] + " ");
		}
 
		System.out.println("");
	}
 
	public void bubbleSort()
	{
		int out;
		int in;
 
		for(out = elements - 1; out > 1; out--)
		{
			//The outer loop backwards
			for(in = 0; in < out; in++)
			{
				//The inner loop forwards
				if(x[in] > x[in + 1]) //Out of order right now
				{
					swap(in, in + 1); //Its put the lotion on the skin!... I mean its swaps them
				}
			}
		}
	}
 
	private void swap(int one, int two)
	{
		long temp = x[one];
		x[one] = x[two];
		x[two] = temp;
	}
 
	public static void main(String[] args)
	{
		int maxSize = 100; //The size of the array
		BubbleSort arr; //Reference to the array
		arr = new BubbleSort(maxSize);
		Scanner console = new Scanner(System.in);
		int input = 0;
 
		do{
			System.out.println("Enter a number (-1 to exit)");
				input = console.nextInt();
			if(input != -1)
			{
				arr.insert(input);	
			}
 
		}while(input != -1);
 
 
		System.out.println("Before The Bubble Sort:");
			arr.display();
 
		arr.bubbleSort();
 
		System.out.println("After The Bubble Sort:");
			arr.display();
	}
}

Data

Analysis

Based on the data collected:

was your hypothesis correct?
- I was successful!… as far as I can tell at least. I ran many tests and all of the ones I did came back positive
is there more going on than you originally thought? (shortcomings in hypothesis)
- Logic-ing it out took some time and some random scribbles on a sheet of paper
what shortcomings might there be in your experiment?
- It could blow up and then take anywhere from 4-7 months for my eyebrows to grow back >_< after a couple of hours it was working
what shortcomings might there be in your data?
- Incorrect sorting… fail bubble sort of fail…

Conclusions

Sorting is not the easiest thing to do let alone comprehend and times. It seems easy enough to just think about it but when it came down to telling the computer how to do it, it was not all that easy.

¹⁾

lo ⇐ end_low) && (start_high ⇐ high

Lab46 Wiki

Table of Contents

Part 3

Entries

November 4, 2011

November 11, 2011

November 18, 2011

November 25, 2011

Experiments

HTML 5 Datalist

Question

Resources

Hypothesis

Experiment

Data

Analysis

Conclusions

Bubble Sort - Java

Question

Resources

Hypothesis

Experiment

Data

Analysis

Conclusions