======Part 3======
=====Entries=====
====November 4, 2011====
First off I would like to annotate this wikipedia link
Trees
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:
Greater Than (>)
Right
Less Than (<)
Left
Traversing a tree - 3 common ways:
While/Iteration
Recursion
Stacks
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====
The Bible of sorting
Book: Sorts
Chapter: yay for sorting
Verse 1:
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.
====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:
Best Case: 0(n) //Order N
Worst Case: 0(n^2) //Order Nsquared //Has to scan the list multiple times
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
Library Sort
And we thought it was a decent sort...
Best Case: 0(n)
Average Case: 0(nLOGn)
Worst Case: 0(n^2)
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.
typedef struct
{
char name[21];
char city[21];
char state[3];
} Rec;
typedef Rec *RecPointer;
RecPointer r;
r = (RecPointer)malloc(sizeof(Rec));
====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)
int pop(STACK *ps)
{
if (ps->size == 0){
fputs("Error: stack underflow\n", stderr);
abort();
} else
return ps->items[--ps->size];
}
====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.
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;
}
}
}
====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
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; i0 && a[j-1]>t)
{
a[j]=a[j-1];
j--;
}
a[j]=t;
}
}
}
====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.
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;
}
====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.
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 = 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 ((lo <= end_low) && (start_high <= high)) {
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++;
}
}
}
}
====Tree: Insertion====
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);
}
====Tree: Removal====
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;
}
====Tree: Searching====
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 );
}
====Tree: Traversal====
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;
}
}
}
====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===
#include
#include
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);
}
}
=====Experiments=====
====HTML 5 Datalist====
===Question===
Using HTML 5 can I use a new form tag?
===Resources===
===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===
HTML 5 Datalist Example
This is how it works for browsers that support HTML 5
This is how it works for browsers that don't support HTML 5
===Data===
Click on the link below in both Firefox and IE to see how it reacts... it's kind of cool
===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===
The Java API
===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.
===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.