Table of Contents
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