Table of Contents

Mike Short's Opus[Prime]

“Ave Dominus Nox”

The Intro

My name is Michael (Mike) Short. I have been attending CCC for a total of 3.5 years now getting two degrees. One in Computer Information Science and the second in Web Technology. Hopefully this will be my last semester and I will be done with school for a little while and then pursue a job in the field most of my knowledge is in. I love making websites, and I am currently working on a service site for a fencing company and our school plans on doing something really cool with other schools and online courses and wants CCC students to be the creators. I am one of them, and proud to be a part of the team.

<html>

<img src="http://lab46.corning-cc.edu/~mshort3/pictures/27.jpg">

</html>

Part 1

Entries

September 02, 2011

<html>

<p>It was the best of times, and it was the worst of times... oh wait... wrong story. Anyway, disregard that previous statement. I hopefully will accomplish my task in being able to formulate words for these journal entries that are sufficient enough in my struggles to understanding these highler level programming concepts. Now, sadly I miss half of my classes for this course so I missed out on what was most likely a pretty awesome first day. I am obtaining half of the knowledge compared to the entire class and I hope I am capable of keeping up. This semester is nothing but classes with labs attached to them so I have an incredibly massive work load and at times it is hard for me to manage, but I am trying to do my best. Anyway enough with the brief introduction and onto the good bits. On this day as I sat and attentively payed attention and tried wrapping my measly little brain around the terminology and concept of just a singly linked list. I slowly became capable of such feats and somewhat conqured it. I still need to reference back to my old code but I am kind of capable of writing one out. We at first, went over the creation of a list. The birth, if I may, and boy was it glorious. Afterwards we moved our way to the insertion technique and not wanting to be impolite we inserted before the node that we wanted to put stuff in. Then came appending. Being a bully and pushing our way to the front. All in all, I learned a great deal moar on my first day in this class and I am looking forward to moar cakey goodness.</p>

</html>

September 09, 2011

<html> <p>Brimming with the knowledge and excitement the last class had brought me, I dared to venture out into the wild a little and I spoke up and tried giving some of the input I had. Very little and somewhat off but was an easy fix! I was kind of impressed with myself seeing as how even I consider myself to be a weaker breed of a programmer. It takes me a little longer to grasp some things and I pretty much need my hand held during the time of first learnings. If not I tend to struggle and tumble my way through… But… for some reason this came fairly quickly and somewhat easily to me. So when we were working on deletion of the nodes, I was pretty comfortable and was able to follow along easily. I even lended a hand to a fellow classmate and helped troubleshoot his code. After about 10 - 15 minutes we had it up and working properly. I have the code still, all I need to do is find a spot for it to put it in here.</p> </html>

September 16, 2011

<html> <p>Things are really starting to get interesting. And the climate control has most certainly improved! The training is still somewhat difficult but we're working on doubly linked lists now. I had a pretty hard time catching up but I managed to tag along at a reasonable rate. Very much like a singly linked list besides the fact that we are now able to traverse the list. Meaning going up or down it, or even left to right. Heck, lets get crazy and make it a circle! Now then, I will not be doing that for I prefer to keep my sanity intact… and that definitely would have broken me… (looking ahead into the future a little bit, say about a week from now, I will have made a doubly linked list on my own with a star wars theme… holy $^@#$%^@ did that r4p3 my brain) So far these lists are cool and kind of a nice challenge to try and wrap your head around the logic and syntax. But it has me thinking… if this is what the first half of the year is going to be like… I dont really want to know what is still in store for us…</p> </html>

September 30, 2011

<html>

<p>On this day, as this month comes to an ending. We were taught something glorious! Stacks (aka stax, yo) as it was writtin on the board! Seriously matt, you employ some of the coolest teaching methods evAR. A stack is essentially a bunch of "blocks" or nodes in a list, a vertical one that is and using push() we can put rainbow colored candies into them and then with the help of our dear friend pop() we can take them back and not only that but reverse the order! Amazing! Also, the shortest proper sentence in the American/English language is, go. Weird, anyway, my job now is to get this stack to work with my doubly linked list that is star wars themed. push(bobafet) trololol I am having a hard time trying to figure out how to turn my stuff into a library but I feel like I'm getting close and I'll get there soon. As for this stack, since we just learned about it today, I wonder if it could be stand alone. As in it doesnt have to go on top of a list. The theory and logic behind it is very simple and easy to understand... I am however unsure of how the syntax will treat us... until next time journal, stay classy.</p>

</html>

Terminology

Pointer

A data type whose value refers directly to (or “points to”) another value stored elsewhere in the computer memory using its address.

#include<stdio.h>
        int main()
                {
                        int a;
                        int *b; //the star is pixie dust (pointer)
                        char c;
                        a = 5;
                                printf("a is: %d\n", a);
                        b = &a;
                                printf("b is 0x%x\n", b);
                                printf("&b is 0x%x\n", &b);
                                printf("*b is 0x%d\n", *b);
                                printf("a is %d\n", a);
                        return(0);
                }

<html> <body>

<table>
  <tr>
    <th>Output:</th>
  </tr>
  <tr>
    <td>a is:</td>
    <td>5</td>
  </tr>
  <tr>
    <td>b is:</td>
    <td>0x209d90d8</td>
  </tr>
  <tr>
    <td>&b is:</td>
    <td>0x209d90d0</td>
  </tr>
  <tr>
    <td>*b is:</td>
    <td>0x5</td>
  </tr>
  <tr>
    <td>a is:</td>
    <td>5</td>
  </tr>
</table>

</body> </html>

<html> <body>

<p>b will never hold the contents of "a" but it can point to it and be like I want that</p>
  <ul>
    <li>Pointer ops</li>
  <ul>
    <li>* - Dereferencing Operator</li>
    <li>& - Address of</li>
      <ul>        
        <li>b  -> 0x123</li>
        <li>&b -> 0x234</li>
        <li>*b -> 5</li>
      </ul>
  </ul>
  </ul>
<p>Pointers can only point to things of the same data type</p>

</body> </html>

Version Control

<html>

<p>It is a repository where you can store all of your data. It takes a snapshot of what you gave it and then you can add comments stating what changes you made. The repository allows you to access all of the committed files at the various versions you submitted them.</p>

<ul>

<li>Checkout: - This copies the latest revision of a file from the repository to your workspace. When you check out a directory, you check out all files and subdirectories under it</li>
<li>Commit: - This is what you use to add your file</li>
<li>Update: - Allows you to update one of the versions</li>
<li>Add: - Adds a version</li>
<li>Log: - Prints out everything within the repository</li>

</ul> </html>

Pointers to pointers

<html>

<p>Double splat (**) (makes a half kirby) and points to another spot in memory</p>

</html>

#include<stdio.h>
int main(int argc, char **argv)
{
  printf("This program was ran by typing: %s\n", argv[0]);
  return 0;
}

<html>

<p>The output is:</p>
<p>This program was ran by typing: ./double_pointer</p>

</html>

Memory allocation (malloc(), new)

<html>

<p>Malloc is the function used to create space inside of memory</p>

</html>

#include <stdio.h>
#include <stdlib.h>
 
struct node 
{
  int value;
  struct node *next;
  struct node *prev;
};
 
typedef struct node Node;
 
int main()
{
  int i = 0;
  int input;
  int input2;
  Node *start, *end, *tmp, *tmp2;
    start = end = tmp = tmp2 = NULL;
 
  printf("Enter a number (-1 to quit): ");
    scanf("%d", &input);
 
  while(input != -1)
  {
    if(start == NULL)
    {
      start = (Node *)malloc(sizeof(Node));
      end = start; 
      start -> next = NULL; 
      start -> prev = NULL; 
      tmp = start; 
      start -> value = input; 
    }
    else
    {
      tmp = (Node *)malloc(sizeof(Node));
      end -> next = tmp;
      tmp -> prev = end;
      end = end -> next;
      end -> value = input;
      end -> next = NULL;
    }
    printf("Enter a number (-1 to quit): ");
      scanf("%d", &input);
  }
 
  i = 0;
  tmp = start;
  while(tmp != NULL)
  {
    printf("index[%d] input: %d\n", i, tmp -> value);
    i++;
    tmp = tmp -> next;
  }
}

<html>

<p>And the output would be...</p>
<pre>
  Enter a number (-1 to quit): 12
  Enter a number (-1 to quit): 23
  Enter a number (-1 to quit): 345
  Enter a number (-1 to quit): -1
  index[0] input: 12
  index[1] input: 23
  index[2] input: 345
</pre>

</html>

Linked Lists

<html>

<p>A dynamic list where you can add and subtract the elements whenever you want to</p>
<pre>
  For example:
    [1]->[2]->[3]->[4]->NULL  
</pre>

</html>

#include <stdio.h>
#include <stdlib.h>
 
struct node
{
        int value;
        struct node *next;
};
 
typedef struct node Node;
 
int main()
{
        int input;
        int input2;
        int i = 0;
        Node *start, *tmp, *tmp2;
                start = tmp = NULL;
 
        printf("Enter a number (-1 to quit): ");
                scanf("%d", &input);
        do
        {
                if(input == -1)
                        break;
                if(start == NULL)
                {
                        start = (Node *)malloc(sizeof(Node));
                        start -> value = input;
            start -> next = NULL;
            tmp = start;
        }
        else
        {
                tmp -> next = (Node *)malloc(sizeof(Node));
            tmp -> next -> value = input;
            tmp -> next -> next = NULL;
            tmp = tmp -> next;
        }
        printf("Enter a number (-1 to quit): ");
                scanf("%d", &input);
        }
        while(input != -1);
 
        tmp = start;
 
        while(tmp != NULL)
    {
        printf("index[%d] value = %d\n", i, tmp -> value);
        tmp = tmp -> next;
        i++;
    }
}

<html>

<p>The output would be...</p>
<pre>
  Enter a number (-1 to quit): 12
  Enter a number (-1 to quit): 12
  Enter a number (-1 to quit): 12
  Enter a number (-1 to quit): 12
  Enter a number (-1 to quit): 12
  Enter a number (-1 to quit): -1
  index[0] value = 12
  index[1] value = 12
  index[2] value = 12
  index[3] value = 12
  index[4] value = 12
</pre>

</html>

Doubly Linked Lists

<html>

<p>A multi-directional dynamic list. Similar to linked list except the ladder is a linear dynamic list</p>
<pre>
  For example:
    NULL<->[1]<->[2]<->[3]<->[4]<->NULL
</pre>

</html>

#include <stdio.h>
#include <stdlib.h>
 
struct node
{
  int value;
  struct node *next;
  struct node *prev;
};
 
typedef struct node Node;
 
int main()
{
  int i = 0;
  int input;
  int input2;
  Node *start, *end, *tmp, *tmp2;
    start = end = tmp = tmp2 = NULL;
 
  printf("Enter a number (-1 to quit): ");
    scanf("%d", &input);
 
  while(input != -1)
  {
    if(start == NULL)
    {
      start = (Node *)malloc(sizeof(Node));
      end = start;
      start -> next = NULL;
      start -> prev = NULL;
      tmp = start;
      start -> value = input;
    }
    else
    {
      tmp = (Node *)malloc(sizeof(Node));
      end -> next = tmp;
      tmp -> prev = end;
      end = end -> next;
      end -> value = input;
      end -> next = NULL;
    }
    printf("Enter a number (-1 to quit): ");
      scanf("%d", &input);
  }
 
  i = 0;
  tmp = start;
  while(tmp != NULL)
  {
    printf("index[%d] input: %d\n", i, tmp -> value);
    i++;
    tmp = tmp -> next;
  }
 
  printf("Enter the index to insert before: ");
    scanf("%d", &input);
 
  tmp = start;
 
  for(i = 0; i < input; i++)
  {
    tmp = tmp -> next;
  }
 
  printf("Enter a number for new node: ");
    scanf("%d", &input2);
 
  if(start == NULL)
  {
    start = (Node *)malloc(sizeof(Node));
    end = tmp = start;
    start -> prev = NULL;
    end -> prev = NULL;
    start -> value = input2;
  }
  else if(start == tmp)
  {
    tmp2 = (Node *)malloc(sizeof(Node));
    tmp2 -> next = start;
    start -> prev = tmp2;
    start = start -> prev;
    start -> value = input2;
  }
  else
  {
    tmp2 = (Node *)malloc(sizeof(Node));
    tmp2 -> next = tmp;
    tmp2 -> prev = tmp -> prev;
    tmp -> prev -> next = tmp2;
    tmp -> prev = tmp2;
    tmp2 -> value = input2;
  }
 
  i = 0;
  tmp = start;
 
  while(tmp != NULL)
  {
    printf("index[%d] value: %d\n", i, tmp -> value);
    i++;
    tmp = tmp -> next;
  }
 
  return(0);
}

<html>

<p>The output is...</p>
<pre>
  Enter a number (-1 to quit): 12
  Enter a number (-1 to quit): 200
  Enter a number (-1 to quit): 1
  Enter a number (-1 to quit): -1
  index[0] input: 12
  index[1] input: 200
  index[2] input: 1
  Enter the index to insert before: 1
  Enter a number for new node: 23
  index[0] value: 12
  index[1] value: 23
  index[2] value: 200
  index[3] value: 1
</pre>

</html>

Popping

<html>

<p>Takes something off of the TOP of the list/stack</p>

</html>

int pop(Stack *pointer)
{
  Some stuff goes here
}

Bubble Sort Algorithm

<html>

<p>It takes the first number in your list and it traverses your list and compares to see if it is bigger. When its not it places it in that spot, so it then grabs that element and starts all over again. Produces a goliath baby for overhead</p>

</html>

Trees

<html>

<p>trees naturally sort numbers. depending on your logic it will put the lowest or highest number on the bottom most leaf of the tree, on either the right or left side.</p>

<ul>

<li>Nodes - The star on the tree... I believe. Or it could be referencing an individual child or parent</li>
<li>Parents - The very first node is the parent. Any node with branches is a parent. (leaflets)</li>
<li>Children - They do not have branches. Essentialy the end of that branch. They were not touched by the parents to have children.(leaflets)</li>

</ul>

<p>You can have an infinite amount of children and parents</p> <p>parents spawn children. Those children can become parents if they themselves have children. But we do not ever let the parents touch the children. (but yet we do, because we're just sick like that)</p>

</html>

Hash Tables

<html>

<p>Can be thought of as a phone book. Such as, it is a multiple linked list. Typically used in searching if you are using a hash then outcome is a table. You would have a triply (possibly quadriply) linked list with a single alphabetic character per node with branching lists from each node containing the first character.</p>

</html>

((LIFO && FILO) != FIFO)

<html>

<ul style="list-style-type: none">
  <li>L: Last</li>
  <li>I: In</li>
  <li>F: First</li>
  <li>O: Out</li>
  <li>----------------</li>
  <li>F: First</li>
  <li>I: In</li>
  <li>L: Last</li>
  <li>O: Out</li>
  <li>----------------</li>
  <li>F: First</li>
  <li>I: In</li>
  <li>F: First</li>
  <li>O: Out</li>
</ul>
<p>LIFO && FILO, both of these mean the same thing</p>
  <dl>
    <dt>Stack:</dt>
      <dd>- Imagine functions that are stacked on top of each other; the last one added to the stack is the first one taken off. It's because of this the data structure itself enforces the proper order of calls.</dd>    
  </dl>
  
  <br />    
  
<p>And as a side note it was also discovered that this would be a very easy way to test if a word was a palindrome.</p>
  
  <br />
<hr />
  <br />
  
<p>This is referencing a stack, for example:</p>  
<pre>
  Input:
     1, 2, 3, 4, 5
     1st         last
  Output:
     5, 4, 3, 2, 1
     1st         last   
</pre>  
</html>

BIG-O Notation

<html>

<p>Big-O notation is used to describe the behavior of a function when the argument is infinity. However it is a little different when it comes to computers. Big-O notation is then used to classify algorithms by how they react to changes with input size.</p>

</html>

Objectives

My first linked list

Within this section I will tackle the endeavor of my first linked list. ever. (and as an added bonus! :D I've included the notes and steps I took to get here)

Method

If i have success, great joy will be had by all… if not… well, death to the masses may insue.

Measurement

After many a hour I was able to write my first linked list. And it had it all. Granted it's very procedural…

Analysis

  • How did you do? - Fairly well I think. I may have patted myself on the back
  • Room for improvement? - Is too tall Jones, too tall?… Yes. I would say I am not at the jedi master level yet… not even close
  • Could the measurement process be enhanced to be more effective? - Turn it into an infinite loop with a terminator. Right now it just goes through the processes once.
  • Do you think this enhancement would be efficient to employ? - Heck to the yes.
  • Could the course objective be altered to be more applicable? How would you alter it? - I'm not sure houw you could alter it to make it easier to understand… honestly he does a really good job at breaking the code down and attempting to essplain (done on purpose) it in fun and simple terms.

The Code

#include <stdio.h>
#include <stdlib.h>
        struct node
                {
                        int value;
                        struct node *next; //dereferencing the node
                };
 
        typedef struct node Node; //shortand to make structs - without having to type out struct for every variable
 
        int main()
                {
                        Node *start, *tmp, *tmp2; //creating pointers for the struct
                        int input;
                        int input2;
                        int i;
                        start = tmp = NULL; //make them both = to NULL
                                printf("Enter a value (-1 to exit): ");
                                        scanf("%d", &input);
 
                                while(input != -1)
                                        {
                                                if(input == -1)
                                                        {
                                                                break;
                                                        }
                                                if(start == NULL)
                                                        {
                                                                start = (Node*)malloc(sizeof(Node)); //allocate space for struct
                                                                start -> next = NULL; //The -> is a structure pointer //next is my chain link and is pointing to NULL
                                                                        tmp = start; //tmp is now pointing to the first node
                                                                start -> value = input; //pointing the struct to the value which is equal to the users input
                                                        }
                                                else
                                                        {
                                                                tmp -> next = (Node*)malloc(sizeof(Node)); //allocating space for the next node in the struct
                                                                        tmp = tmp -> next;
                                                                tmp -> next = NULL;
                                                                tmp -> value = input;
                                                        }
                                                printf("Enter a value (-1 to exit): ");
                                                        scanf("%d", &input);
                                        }
 
                        tmp = start;
 
                                while(tmp != NULL)
                                        {
                                                        printf("[%d] value = %d\n", i, tmp -> value);
                                                                tmp = tmp -> next;
                                                                        i++;
                                        }
                        printf("Enter node to insert before: ");
                                scanf("%d", &input2);
 
                        tmp = start;
 
                                for(i = 0; i < (input - 1); i++)
                                        {
                                                tmp = tmp -> next;
                                        }
 
                        printf("Enter a value: ");
                                scanf("%d", &input);
 
                        tmp2 = (Node*)malloc(sizeof(Node));
                        tmp2 -> value = input;
 
                                if((tmp == start) && (input2 != 1))
                                        {
                                                tmp2 -> next = start; //or tmp since they are pointing to the same place
                                                start = tmp2;
                                        }
                                else
                                        {
                                                tmp2 -> next = tmp -> next;
                                                tmp -> next = tmp2;
                                        }
 
                        i = 0;
                        tmp = start;
 
                                while(tmp != NULL)
                                        {
                                                printf("[%d] value = %d\n", i , tmp -> value);
                                                        tmp = tmp -> next;
                                                                i++;
                                        }
 
                        return(0);
                }

Experiments

Java Arrays

Question

Amongst the three programming classes I am currently taking, one (being Java) had a unique scenario laid out in front of me. Is it possible to make an array dynamic? If so, how? I can tell you it wont be as easy as it seems (I think anyway) because the array themselves need to be defined as to what their size should be in the beginning.

Resources

<html> <a href=“http://download.oracle.com/javase/6/docs/api/”>Java API</a> </html>

Hypothesis

Based on what I know right at this momment. I believe, with the help of vectors and list I can create an array that is dynamic.

Experiment

//Author: Michael Short
//Purpose: Dynamic Array
 
import java.util.*;
import java.lang.*;
 
public class DArray
{
	public static void main(String[] args)
	{
		Vector<Integer> numbers = new Vector<Integer>();
		Scanner console = new Scanner(System.in);
		int input;
 
		do
		{
			System.out.println("Please enter a number");
				input = console.nextInt();
				if(input != -1)
				{
					numbers.addElement(new Integer(input));
				}
		}
		while(input != -1);
 
		System.out.println();
		for(int i = 0; i < numbers.size(); i++)
		{
			System.out.println("Index[" + i + "]: " + numbers.elementAt(i));
		}
	}
}

<html> <img src=“http://lab46.corning-cc.edu/~mshort3/darray/DArray.png” title=“Output of the program” alt=“Output of the program” /> </html>

Data

Vectors cannot/do not deal with primitive data types, such as integers so I had to turn the integers into objects .length() is associated with Arrays, so to get the size of a vector I had to use .size() Throw in some controlled loops and fill er up, regular the elementAt() function does exactly as it sounds. At whatever index you specify it grabs that element

Analysis

Based on the data collected:

  • was your hypothesis correct?
    • yes, yes it was. =D this array is dynamically created.
  • was your hypothesis not applicable?
    • it was applicable in every way? Sort of?
  • is there more going on than you originally thought? (shortcomings in hypothesis)
    • Why yes, one thing that is note worthy is that Vectors are synchronized. whereas arrayList I believe it is called is not synchronized. Meaning you can only perfrom one thing at a time with a vector. Great for a database structure (My thoughts are that you can't update and view/delete at the same time, as this could cause loss os precision in the data) && you can't deal with primitive data types such as the ints, chars, doubles, etc. unless you turn them into objects.
  • what shortcomings might there be in your experiment?
    • I could fail horribly… but within failing, there is still knowledge gained
  • what shortcomings might there be in your data?
    • Not fully understanding what I am doing since this is all self taught

Conclusions

Well, for one, it worked! Took me a little while to figure it out but I got there finally. There is a way to iterate through the array without a for loop

Iterator iter = numbers.iterator();
  while(iter.hasNext()) //hasNext() is looking to see if there is an element at that index
  {
    Object o = iter.next();
  }

I attempted this but couldnt get it to work, just showing there is more than one way to do this. I would rather use vectors over an array everytime unless I knew what the limitations were going to be. If it did have to go beyond the capabilities of that array then you would have to employ a larger array and copy all of the elements from the old one to the new one… the question is, why do that? when vectors exist.

Variable Play[not finished]

Question

Resources

Hypothesis

Experiment

Data

Analysis

Conclusions

Doubly Linked List in Java

Question

Can you make a linked list in Java?

Resources

<html> <p><a href=“http://download.oracle.com/javase/6/docs/api/java/util/LinkedList.html”>Java API</a></p> </html>

Hypothesis

It is possible to make a linked list in Java, given the right amount of cake.

Experiment

//Author: Michael Short
//Purpose: Singly Linked List.
 
import java.lang.*;
import java.util.*; //imports everything in the util package
//OR
//import java.util.LinkedList;
 
public class SingleLinkedList
{
	public static void main(String[] args) 
	{
		//LinkedList MyList = new LinkedList(); //without defining its type
		LinkedList<Integer> MyList = new LinkedList<Integer>();
		Scanner console = new Scanner(System.in);
		int input;
		int location;
 
		//Creates The List
		do
		{
			System.out.println("Please enter a number (-1 to exit)");
			input = console.nextInt();
 
			if(input != -1)
			{
				MyList.add(input);
			}
		}
		while(input != -1);
 
		System.out.println(); //new line
		System.out.println("This list contains: " + MyList.size() + " elements");
		System.out.println("=======================================");
 
		//Prints the list out
		for(int i = 0; i < MyList.size(); i++)
		{
			System.out.println("Index[" + i + "]: " + MyList.get(i));	
		}
 
		//Inserts into the list
		do
		{
			System.out.println("Where would you like to insert? (-1 to exit)");
			location = console.nextInt();
 
			if(location != -1)
			{
				System.out.println("Please enter the number you wish to insert");
				input = console.nextInt();
				MyList.add(location, input);
			}
		}
		while(location != -1);
 
		//Prints out the list
		for(int i = 0; i < MyList.size(); i++)
		{
			System.out.println("Index[" + i + "]: " + MyList.get(i));	
		}
 
		//Removes from the list
		do
		{
			System.out.println("Which node would you like to delete? (-1 to exit)");
			input = console.nextInt();
 
			if(input != -1)
			{
				MyList.remove(input);
			}
		}
		while(input != -1);
 
		//Prints out the list
		for(int i = 0; i < MyList.size(); i++)
		{
			System.out.println("Index[" + i + "]: " + MyList.get(i));	
		}
	}
}

Data

<html>

<p><img src="http://lab46.corning-cc.edu/~mshort3/singley_linked_list/images/single.png"></p>

</html>

Analysis

Based on the data collected:

  • was your hypothesis correct?
    • Yes, and it was awesome!
  • is there more going on than you originally thought? (shortcomings in hypothesis)
    • Linked lists in Java cant deal with primitive data types as well and needs an integer wrapper.
  • what shortcomings might there be in your experiment?
    • I used the linked list class making this actually a lot easier than it was supposed to be =D When I brought this idea up to Matt he said it Java did it weird and actually made it harder… well it is true! My god, brain splatter on my monitor after I looked at some code examples of it. But using the class makes it so incredibly easy!
  • what shortcomings might there be in your data?
    • it not working… -.- and the insert took me a little bit to find out because apparently I don't know how to readz. *sigh*

Conclusions

This wasn't so bad but making your own classes and defining them is an incredibly difficult thing to do. Also, I came at this with a very procedural approach, this could become very complex very easily. But for a comparison between doing this in C and in Java this was done in about 20-30 minutes and with very little brain surging amounts of pain haha

Part 2

Entries

October 07, 2011

<html> <p>Well we spent a little time going over the concept of queues and talked a little bit about stacks again. Other than that I showed up an hour early due to forgetting what time I was supposed to be there… oh well haha. Anyway, I spent some of my time working on one of the experiments for my opus and got some more work done on that one. Other than that it was a pretty laid back day and we did work.</p> </html>

October 14, 2011

<html> We went over queues again and we were all like, they're sideways staxs, yo. They follow the FIFO ruling, which is first in, first out. And a nice example he gave us was planting a seed in the ground and watching it grow.

<pre> A little demonstration:

 Enqueue - put stuff on it
+- - - -+
|1|2|3|4|
      +- - - -+
             Dequeue - get stuff off it

</pre> </html> And we also discussed a real life scenario for LIFO (Last in, first out) and it would be a pezz dispenser

And now for a little starter code

Node **dequeue(list *);
void enqueue(list *, Node *);

October 21, 2011

<html> <p>Today we went over File i/o.</p>

<p>Files: Theory and Practice Also makes a good data structure topic</p> <p>Philosophy/Quote: “Everything is a file”</p> <p>3 Types of files</p> <ul style=“list-style-type: none;”> <li>Regular - Pretty much most things that we interact with on a daily basis</li> <li>Directory - A file that holds/has information of other files, it doesn't actually have any data itself</li> <li>Special - hardware such as harddrive and pipes and sockets on the software side. Also anything else that is not of the other 2</li> </ul> <p>Fields and records</p> <p>“Column and Rows”</p> <p>File Access/Operations</p> <ul style=“list-style-type: none;”> <li>Open</li> <li>Create</li> <li>Close</li> <ul style=“list-style-type: none;”> <li>read</li> <li>Write (>)</li> <li>Append (») - Moves the file pointer to the very end of the file</li> </ul> </ul> <pre> Some extra goodies: ————————————————————— r Open text file for reading. The stream is positioned at the beginning of the file. +r Open for reading and writing. The stream is positioned at the beginning of the file. w Truncate file to zero length or create text file for writing. The stream is positioned at the beginning of the file. +w Open for reading and writing. The file is created if it does not exist, otherwise it is truncated. The stream is positioned at the beginning of the file. a Open for appending (writing at end of file). The file is created if it does not exist. The stream is positioned at the end of the file. +a Open for reading and appending (writing at end of file). The file is created if it does not exist. The initial file position for reading is at the beginning of the file, but output is always appended to the end of the file. ————————————————————— </pre> </html> <file c> Example Program

#include <stdio.h>
int main()
{
	FILE *fPointer;	//Declare file pointer
	//fPointer = fopen("filename", "r"); //Opens the file, if there is a porblem it returns NULL, Check if the 

pointer is NULL, if so, DONT PROCEED

	fPointer = fopen("/etc/motd","r");
	char value;		
	while((value = fgetc(fPointer)) != EOF)
	{
		printf("%c", value);
	}
	
	fclose(fPointer);
	return(0);
}

</file>

October 28, 2011

I wasn't able to attend this class on this date due to some rather unforseen circumstances… There was a sudden death in the family and I was needed by my family.

But upon emailing the Great One, if there were to be a lecture today it would have been about Trees! And i thought I was only in one bio class this semester haha but anyway, here is what I know…

In a programming paradigm, unlike lists which use next and previous the common place formatting is to use right and left. The “bark” of a tree is to sort, preferably numbers. The lowest number on the left with the highest on the right as far down as it can go.

A little pseudo code example:
----------------------
if(value > current -> value)
  current = current -> right;
else
  current = current -> left;

Terminology

arrays, pointer arithmetic

The C language allows us to perform integer addition or subtraction operations on pointers. If pointer1 points to an integer, pointer1 + 1 is the address of the next integer in memory after pointer. pointer - 1 is the address of the previous integer before pointer.

#include <stdio.h>
#include <stdlib.h>
 
int main()
{
    int value = 10;
    int *pointer = &value;
 
    printf("Pointer: %d\n", pointer);
    printf("Pointer + 1: %d\n", pointer + 1);
    printf("Pointer + 2: %d\n", pointer + 2);
    printf("Pointer - 1: %d\n", pointer - 1);
}

<html> <pre> Output:


Pointer: -2077239964 Pointer + 1: -2077239960 Pointer + 2: -2077239956 Pointer - 1: -2077239968 </pre> </html>

Void pointers

A void pointer is known as generic pointer, which can refer to variables of any data type.

#include <stdio.h>
 
void use_int(void *);
void use_float(void *);
void greeting(void (*)(void *), void *);
 
int main(void) {
  char ans;
  int i_age = 22;
  float f_age = 22.0;
  void *p;
  printf("Use int (i) or float (f)? ");
  scanf("%c", &ans);
  if (ans == 'i') {
    p = &i_age;
    greeting(use_int, p);
  }
  else {
    p = &f_age;
    greeting(use_float, p);
  }
  return 0;
}
void greeting(void (*fp)(void *), void *q) {
  fp(q);
}
void use_int(void *r) {
  int a;
  a = * (int *) r;
  printf("As an integer, you are %d years old.\n", a);
}
void use_float(void *s) {
  float *b;
  b = (float *) s;
  printf("As a float, you are %f years old.\n", *b);
}
 
//Found online and thought it was a really good example

<html> <pre> Output:


Use int (i) or float (f)? i As an integer, you are 22 years old.

Use int (i) or float (f)? f As a float, you are 22.000000 years old. </pre> </html>

Function pointers

A function pointer is a variable that stores the address of a function that can later be called through that function pointer. This is useful because functions encapsulates code so you dont have to keep re-writing it.

simply put, a pointer that points to a function.

#include <stdio.h>
 
void myFunction(int x)
{
    printf("%d\n", x);
}
 
int main()
{
    void (*test)(int);
    test = &myFunction;
 
    test(2); //Or type (*test)(2) that will work also
 
    return 0;
}

<html> <pre> Output:


2 </pre> </html>

Null pointers

These little guys point to a void in the space time continuum

#include <string.h>
#include <stdio.h>
//I think there might be an include that defines null... im not sure and if not then i guess you could make one?
//The reason is because the output is a seg fault
 
int main()
{
    char *string = NULL;
 
    strcpy(string, "Test");
    printf("%s", string);
 
    return 0;
}

<html> <pre> Output:


Segmentation fault </pre> </html>

Memory De-allocation (free(), delete)

Free deletes the space of memory

//Taken from my doubly linked list star wars themed program
if(force == yoda)
{
  chewbacca = (sith_lord*)malloc(sizeof(sith_lord));
  force -> anakin = chewbacca;
  chewbacca -> anakin = NULL;
  chewbacca -> darth_vader = force;
  chewbacca -> lightsaber = jedi_rank;
  yoda = chewbacca;
  free(chewbacca);
}

Pushing

“First in last out” Puts something on top of the stack, also a singly linked list

void push(Stack *pointer, int value)
{
  Some stuff goes here
}

Top [not finished]

Top of the stack

void push(stuff)
{
    struct stack_test *temp;
    temp = (struct stack_test *)malloc(sizeof(struct stack_test));
    temp -> data = x;
    temp -> next = top;
    top = temp;
}

LIFO or FIFO [not finished]

Last in First Out - This is how stacks work. FIFO (beinf First in First out) I believe is a queue

Overflow condition (where applicable?) [not finished]

Underflow condition [not finished]

Enqueuing

Adds elements to a queue

myQueue.enqueue("I am adding stuff to my queue")

Dequeuing

Removes an element from a queue

  myQueue.dequeue(some_stuff)

data Objective

Star Wars Themed Doubley Linked List Goodness

I will be taking the Singly Linked List and making it a Doubly Linked List… but wait… there's moar! It will be star wars themed! Oh, yeah!

Method

Did the amount of brain pain equal out to the feeling of accomplishment… I tell you I had to take some advil with the massive headaches the ensued…

Measurement

Writing it from scratch and constantly having to look back at things it took me about 5 hours in all to write this code… very time consuming and rather difficult… But I do feel like I did very well and learned quite a few things. I can look at the code and interact with it but I still need to look back at past examples of codes in order to write it out. But thats not a bad thing persay.

Analysis

Reflect upon your results of the measurement to ascertain your achievement of the particular course objective.

  • How did you do?
    • I did give myself a small round of applause and then promptly lapsed into a brain hemorrhaging coma…
  • Room for improvement?
    • Yes! lots! for one I need to get to the point where I can just write it wihout looking at my past work for references.
    • Less procedural
    • It is just themed… some of the things could make moar sense
  • Could the measurement process be enhanced to be more effective?
    • If it didn't take so long to write the code… I mean the guy could have made it easier -_-#
  • Do you think this enhancement would be efficient to employ?
    • It would make writing code especially when it seems to be rather high level stuff much easier and easier to learn. Like How I wrote it in Java as well. The code (class) does not show all the things happening in the background, but there is where a teacher can hop in and explain all of that. That as long as you understand the concept and how things are actually working then I do believe further simplifing things would make it easier.
  • Could the course objective be altered to be more applicable? How would you alter it?
    • I wouldn't alter the objective at all. It is accomplishable and it does teach you a lot. It will just take some time is all.

Code

#include <stdio.h>
#include <stdlib.h>
        struct sith_lord
                {
                        int lightsaber;
                        struct sith_lord *darth_vader; //Pointer to the next Node in the list
                                        struct sith_lord *anakin; //Pointer to the previous Node in the list
                };
 
        typedef struct sith_lord sith_lord; //just say jedi_council instead od struct jedi_council
 
        int main()
         {
                sith_lord *yoda, *force, *chewbacca; //start, current, temp //declaring three pointers for me to use of this struct type
                        int jedi_rank;
                        int i = 0;
 
                yoda = force = chewbacca = NULL; //making them all equal to NUL
 
                        printf("Enter your rank (-1 to exit): ");
                                scanf("%d", &jedi_rank);
 
                while(jedi_rank != -1)
                        {
                                if(jedi_rank == -1)
                                        break;
                                if(yoda == NULL)
                                        {
                                                yoda = (sith_lord*)malloc(sizeof(sith_lord));
                                                yoda -> darth_vader = NULL;
                                                yoda -> anakin = NULL;
                                                yoda -> lightsaber = jedi_rank;
                                                force = yoda;
                                        }
                                else
                                        {
                                                force -> darth_vader = (sith_lord*)malloc(sizeof(sith_lord));
                                                force -> darth_vader -> anakin = force;
                                                force = force -> darth_vader;
                                                force -> lightsaber = jedi_rank;
                                                force -> darth_vader = NULL;
                                        }
                         printf("Enter your rank (-1 to exit): ");
                        scanf("%d", &jedi_rank);
                        }
         force = yoda;
                printf("Going Forwards\n");
                while(force != NULL)
                        {
                                        printf("[%d] rank = %d\n", i, force -> lightsaber);
                                        if ( force -> darth_vader != NULL )
                                                force = force -> darth_vader;
                                        else
                                                break;
                                        i++;
                        }
 
                printf("Going backwards\n");
                while(force != NULL)
                                {
                                        printf("[%d] rank = %d\n", i, force -> lightsaber);
                                        force = force -> anakin;
                                        i--;
                                }
                //inserting a node into the struct
                printf("Enter a level to insert before: ");
                        scanf("%d", &jedi_rank);
 
                force = yoda;
                        for(i = 0; i < jedi_rank; i++)
                                {
                                        force = force -> darth_vader;
                                }
                printf("Enter a new rank: ");
                        scanf("%d", &jedi_rank);
                        if(force == yoda)
                        {
                                chewbacca = (sith_lord*)malloc(sizeof(sith_lord));
                                force -> anakin = chewbacca;
                                chewbacca -> anakin = NULL;
                                chewbacca -> darth_vader = force;
                                chewbacca -> lightsaber = jedi_rank;
                                yoda = chewbacca;
                                //free(chewbacca);
                        }
                        else
                        {
                                chewbacca = (sith_lord*)malloc(sizeof(sith_lord));
                                chewbacca -> darth_vader = force;
                                chewbacca -> anakin = force -> anakin;
                                force -> anakin -> darth_vader = chewbacca;
                                force -> anakin = chewbacca;
                                chewbacca -> lightsaber = jedi_rank;
/*
                                force -> anakin -> darth_vader = chewbacca;
                                chewbacca -> darth_vader = force;
                                chewbacca -> anakin = force -> anakin;
                                force -> anakin = chewbacca;
                                chewbacca -> lightsaber = jedi_rank;
*/
                                //free(chewbacca);
                        }
                 force = yoda;
                 i = 0;
            printf("Going Forwards\n");
            while(force != NULL)
                {
                        printf("[%d] rank = %d\n", i, force -> lightsaber);
                        if ( force -> darth_vader != NULL )
                            force = force -> darth_vader;
                        else
                            break;
                        i++;
                }
 
            printf("Going backwards\n");
            while(force != NULL)
                    {
                        printf("[%d] rank = %d\n", i, force -> lightsaber);
                        force = force -> anakin;
                        i--;
                    }
                //Appending
                printf("Enter the level to apend to: ");
                scanf("%d", &jedi_rank);
 
            force = yoda;
                for(i = 0; i < jedi_rank; i++)
                    {
                        force = force -> darth_vader;
                    }
            printf("Enter a new rank: ");
                scanf("%d", &jedi_rank);
                if(force -> darth_vader == NULL)
                {
                                chewbacca = (sith_lord*)malloc(sizeof(sith_lord)); //give birth to chewbacca
                                force -> darth_vader = chewbacca;
                                chewbacca -> darth_vader = NULL;
                                chewbacca -> anakin = force;
                                chewbacca -> lightsaber = jedi_rank;
                                //free(chewbacca); //i want to free chewbacca... he deserves it... how can he escape?
                        }
                        else
                        {
                                chewbacca = (sith_lord*)malloc(sizeof(sith_lord));
                                chewbacca -> darth_vader = force -> darth_vader;
                    force -> darth_vader = chewbacca;
                                chewbacca -> darth_vader -> anakin = chewbacca;
                                chewbacca -> anakin = force;
                    chewbacca -> lightsaber = jedi_rank;
                        }
                force = yoda;
             i = 0;
            printf("Going Forwards\n");
            while(force != NULL)
                {
                        printf("[%d] rank = %d\n", i, force -> lightsaber);
                        if ( force -> darth_vader != NULL )
                            force = force -> darth_vader;
                        else
                            break;
                        i++;
                }
 
            printf("Going backwards\n");
            while(force != NULL)
                    {
                        printf("[%d] rank = %d\n", i, force -> lightsaber);
                        force = force -> anakin;
                        i--;
                    }
                //Deleting
                printf("What rank would you like to delete: ");
                        scanf("%d", &jedi_rank);
                force = yoda;
                for(i = 0; i < jedi_rank; i++)
                    {
                        force = force -> darth_vader;
                    }
                        if(force == yoda)
                        {
                                yoda = yoda -> darth_vader;
                                force -> darth_vader = NULL;
                                yoda -> anakin = NULL;
                                free(force);
                        }
                        else if ( force -> darth_vader == NULL )
                        {
                                force -> anakin -> darth_vader = NULL;
                                force -> anakin = NULL;
                                free(force);
                        }
                        else
                        {
                                force -> darth_vader -> anakin = force -> anakin;
                                force -> anakin -> darth_vader = force -> darth_vader;
                                free(force);
                        }
                force = yoda;
             i = 0;
            printf("Going Forwards\n");
            while(force != NULL)
                {
                        printf("[%d] rank = %d\n", i, force -> lightsaber);
                        if ( force -> darth_vader != NULL )
                            force = force -> darth_vader;
                        else
                            break;
                        i++;
                }
 
            printf("Going backwards\n");
            while(force != NULL)
                    {
                        printf("[%d] rank = %d\n", i, force -> lightsaber);
                        force = force -> anakin;
                        i--;
                    }
         }

Experiments

JQuery Random Circles

Question

Using the JQuery library is it possible to create a random amount of shapes (circles in this case) with a random set of color fill and color edging?

Resources

<html> <body>

<a href="http://jquery.com/">JQuery API</a>

</body> </html>

Hypothesis

I want to do something cool and challenging with JQuery, I believe this to be possible by attempting and hopefully being able to implement a way to draw random shapes (circles, im restricting myself so I dont go too overboard and have my brains blow up). Using canvas and its methods I will be able to draw things… at a click of a button!

Experiment

<head>
<title>Michael Short</title>
</head>
 
<script type="text/javascript" src="jquery-1.6.2.min.js"></script>
<script type="text/javascript">
	$(document).ready(function()
	{
		$("#create").click(draw);
		$("#destroy").click(clear);
	});
 
	function draw()
	{
		var canvas = document.getElementById("canvas");
		var ctx = canvas.getContext("2d");
 
			for(i = 0; i <= 100; i++)
			{
				ctx.fillStyle = "rgb(" + Math.floor(Math.random() * 255) + "," + Math.floor(Math.random() * 255) + "," + Math.floor(Math.random() * 255) + ")";
 
        		ctx.strokeStyle = "rgb(" + Math.floor(Math.random() * 255) + "," + Math.floor(Math.random() * 255) + "," + Math.floor(Math.random() * 255) + ")";
 
        		ctx.lineWidth = "2";
 
        		var x = Math.floor(Math.random() * 500);
        		var y = Math.floor(Math.random() * 500);
        		var radius = 0.1 + Math.floor(Math.random() * 10);
 
        		ctx.beginPath();
        		ctx.arc(x, y, radius, 0, Math.PI * 2, true);
 
        		ctx.stroke();
        		ctx.fill();
    		}
	}
 
	function clear()
	{
		var ctx = canvas.getContext("2d");
		ctx.clearRect(0, 0, 500, 500);
	}
 
</script>
 
<body>
 
<canvas id="canvas" width="500" height="500" style="border: 3px solid red"></canvas>
 
<button id="create">Draw</button>
<button id="destroy">Clear</button>
 
</body>
</html>

Data

<html> <body>

<a href="http://lab46.corning-cc.edu/~mshort3/jCircles/Lab10.html" target="_blank">Click here for the funz</a>Also, it will not work in IE

</body> </html>

Analysis

Based on the data collected:

  • was your hypothesis correct?
    • It was, everything worked out just fine and amazingly i might add :D
  • is there more going on than you originally thought? (shortcomings in hypothesis)
    • There is, for one you can do 3D shapes… now that might be an experiment for later on. And you cant just do/add things to the canvas without first getting the content.
  • what shortcomings might there be in your experiment?
    • Besides failing and not getting anything to work, there was the whole thing with making circles… rectangles/squares were a little too easy… and also only drawing one at a time. Making them circles and adding the functionality of choosing how many drawn at once was adding a nice depth to this experiment.
  • what shortcomings might there be in your data?
    • It's not fun…

Conclusions

With canvas you can draw more than just circles, for example: rectangles, triangles, and smiley faces! And most likely many moar.

HTML 5 Drawing FUN

Question

Can I… nay… Am I ready to take on some of HTML 5's new features… I say… YES!!! One new thing I'd like to see if I can do is draw using their new SVG tags or (Scalable Vector Graphics).

Resources

<html> <p>Before you can go any further you will need either one of two things:</p> <ul style=“list-style-type: none;”>

<li>Most recent version of Firefox (which, why wouldn't you?)</li>
<li>Or you may have to go into the about:config page and enable HTML5 support (with the newest version you shouldn't have to do this though)</li>

</ul> <p>The Links!!! They be down below, arrrgghhh</p> <a href=“http://www.tutorialspoint.com/html5/html5_svg.htm” target=“_blank”>TutsPoints</a> </html>

Hypothesis

With the growing support of the new HTML standard more and more browsers are starting to have support for the new HTML5 KING!!! I would like to perform one of its new features and see how it works and display browser compatibility.

Experiment

<!DOCTYPE html>
<head>
<title>Some cool and new HTML5 stuff!!!</title>
</head>
<body>
 
<svg id="svg1" height="200" xmlns="http://www.w3.org/2000/svg">
	<rect id="redrect" width="300" height="100" fill="black" /> <!-- Draws the rectangle -->
	<circle id="redcircle" cx="50" cy="50" r="50" fill="red" /> <!-- Draws the circle -->
	<circle id="redcircle" cx="250" cy="50" r="50" fill="red" /> <!-- Draws the circle -->
	<text x="75" y="55" stroke="purple">Look, you can also put text in real easily!</text>
</svg>
 
</body>
</html>

Data

<html> <p>Follow the link below to behold the greatness!</p> <a href=“http://lab46.corning-cc.edu/~mshort3/html5/” target=“_blank”>Click Here</a>

<p>Browsers that support it… or at least have some support</p> <ul style=“list-style-type: none;”>

<li>Yes</li>
  <ul style="list-style-type: none;">
    <li>Firefox</li>
    <li>Chrome</li>
    <li>Internet Explorer 9</li>
  </ul>
<li>No</li>
  <ul style="list-style-type: none;">
    <li>Opera (Although a newer version perhaps does support it... I don't use it enough (does anyone?)</li>
  </ul>
  <li>And im not sure on Safari... I dont have a mac...</li>

</ul> </html>

Analysis

Based on the data collected:

  • was your hypothesis correct?
    • Yes it was my dear watson
  • is there more going on than you originally thought? (shortcomings in hypothesis)
    • I only performed a few of the basic ideas, as you will see with the link you can do so much more than I demonstrated. Looks like making logos and the like in photo shop/illustrator will become a thing of the past?
  • what shortcomings might there be in your experiment?
    • Browser support is a big downfall on all things web tech… I seriously hate how I have to write the code 50 different ways so old and 50 different browsers will know how to interact with the page properlly
  • what shortcomings might there be in your data?
    • Took me a little bit at first as to why it wasnt working in firefox… then i looked at my version and it was 3.6… super outdated. So kids, keep things up-to-date

Conclusions

There is plenty of room here to grow. Someone could make their own custom images. And with the promise of HTML5 to grow and expand over time I see the SVG and Canvas attributes becoming very popular.

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> <p>Traversing a tree - 3 common ways:</p> <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 1) { 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> <p><a href=“http://www.w3schools.com/html5/tag_datalist.asp” target=“_blank”>W3Schools</a></p> </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>

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

<p>Browser Support</p> <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

<html> The <a href=“http://docs.oracle.com/javase/6/docs/api/” target=“_blank”>Java API</a> </html>

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.

1)
lo ⇐ end_low) && (start_high ⇐ high