======Part 3====== =====Entries===== ====Week of November 7==== This week, we covered the concept of the data structure called a tree. I rather like the idea of a tree, and find it to be one of thew simplest data structure concepts we've covered thus far. The idea of a tree follows the general outline of a linked list. The first node in this list holds an initial value, against which all new values will be compared against. Once a new value is entered, if it is greater than the original value, then it is sent to the designated "side" of the tree list, and sent to the other "side" if it is less. These sides, in our examples, are explained to be the "next" and "prev" of the original node. For example-- a value is given for the "start" node, and it is 9. The next value is given, and it is 11-- this becomes start->next. Another value is given, and it is 8, making it start->prev. One more value is given, and it is 10. This becomes start->next->prev. Some people had trouble with the concept, but it came rather easily to me, I think. It's okay though, there will always be one concept that will be hard to grasp initially regardless of what it is. ====Week of November 14==== In class this week, we went over a program that makes use of the process ids (PIDs) of various programs. In order to work, it needs the unistd.h library included. Basically, it takes the process id of the program and assigns it to one variable, breaks from the function, forks to create a new process id for the first element in an array to be assigned, then assigns a new process id to the remaining array elements while breaking each pid after each iteration. It was a nice exercise to show us how to use the process ids on a system in a program. #include #include /* 11/14/11 Process ID examples */ int main() { int i, j; pid_t me, them[10]; me=getpid(); printf("Parent process ID is %hu\n", me); for(i=0;i<10;i++) { if(getpid()==me) { them[i]=fork(); } else { break; } } if(me==getpid()) { sleep(20); for(i=0;i<10;i++) { wait(j); } } else { printf("I am child %d, my PID is %hu\n", i,getpid()); sleep(i+1*10); printf("Child %d is done\n", i); } return(0); } ====Week of November 21==== We only had one class this week, as it is the week of Thanksgiving break. As is such, no one was really motivated to do much in class. Unless it had to do with watching Troll 2, which seemed to motivate people enough to do just that. While it was an enjoyable experience to share with everyone as we all laughed, it also caused a bit of an existential crisis-- How could something so horrible actually exist? How did this actually get released as an actual motion picture? On an actual program related note-- I've finished (or just about finished) 3 projects-- doubly linked list library, stack library and queue library. The portfolio reports just need to be written, is all. The tree library and implementation should be done soon, and I don't anticipate doing the other 3 projects will be much of an issue. I'm going to make the code for a deck of cards for one (I think). I'm also thinking about how the logic for tetris can be done using linked lists, but I'm not sure how I'd get that done in two weeks, all things considered. I'll have to keep them simple, yet effective in terms of being a project. ====Week of November 28==== This week is also relatively uneventful. At this point, I have half of my fourth project done, the binary tree library and minor implementation. The opus is obviously due this week, so that will take up most of my programming work time. In class, though, Matt let us know that the EOCE is released. It appears to be simpler than past EOCEs, probably due to the fact that our opus and projects take a lot of work. Not that I'm complaining! It definitely all seems manageable, and I, for one, am glad to have everything that needs to be done laid before me. =====data Topics===== ====Queue Overrun condition==== A queue overrun happens when a program is manipulating a queue data structure that is full, and the program tries to add an element to the queue. Since the queue is full, adding another element makes it "overrun," hence the term "queue overrun." {{:opus:fall2011:tgalpin2:queueoverrun.png}} ====Queue Underrun condition==== A queue underrun is the opposite of an overrun. It occurs when a queue is empty and the program in use attempts to remove another element from the empty queue. Obviously, there is nothing there to remove, so an underrun occurs. {{:opus:fall2011:tgalpin2:queueunderrun.png}} ====Binary Tree==== A binary tree is a type of data structure, based off of the concept of a linked-list in our class examples. The tree is dependent on a sorting algorithm that compares a given node with the nodes in the tree already. First, a number is given to the tree. This is the first parent node, the node which all subsequent nodes will be compared to. With the next values, if a value is greater than this node, it goes to one "side" of the tree, and the other side if it is lesser. This process continues for as long as needed. A tree is useful because the algorithm that creates it can be used to search for values, and the creation process leaves a tidy ordered list of values. {{:opus:fall2011:tgalpin2:treeex.png}} ====Tree Node==== A tree node is simply an element in a binary tree style linked list. There are two types of these nodes-- parent and child nodes. Each node can have two other nodes attached to it as their "next" and "prev," to use terminology from our class. The tree nodes make up the body, so to speak, of the tree data structure. //The code for the node structure of a tree. struct node { int value; struct node *next; struct node *prev; }; typedef struct node Node; Node *start, *tmp, *tmp2; ====Tree Parent Node==== A tree parent node is a node in a tree that has one or two children nodes attached to it. The parent node can either have a next, a prev, or a next and a prev, but no more than that, because a binary tree is being used. /* start -- the original parent node start->next -- child node to start, greater than start, parent to start->next->next and start->next->prev start->prev -- child node to start, less than start, parent to start->prev->next and start->prev->prev */ ====Tree Child(ren) Node(s)==== Identification and definition of the chosen keyword. Substitute "keyword" with the actual keyword. If you want to demonstrate something on the command-line, you can do so as follows: /* start -- the original parent node start->next -- child node to start, greater than start start->prev -- child node to start, less than start start->next->next -- child to start->next, greater than parent start->next->prev -- child to start->next, less than parent */ ====Insertion==== Insertion is the process of inserting a node in to an already established instance of a data structure, such as a freshly created linked list within a program. An insertion function takes a given value and places it in a given place. Code for an insertion function may look something like the following-- int insert() { // Insert a new node int i=0; printf("Enter node position to insert before: "); scanf("%d", &input); tmp = start; for(i=0; i next; } printf("Enter a value for new node: "); scanf("%d", &input2); if (start == NULL) // if our list is empty { start = (Node *) malloc (sizeof(Node)); end = tmp = start; start -> prev = NULL; end -> prev = NULL; start -> value = input2; } else if (start == tmp) // we're inserting before start of list { tmp2 = (Node *) malloc (sizeof(Node)); tmp2 -> next = start; // point new node's next at start start -> prev = tmp2; // point start's prev at tmp2 start = start -> prev; // move start to new node start -> value = input2; // put value in node } else // we're inserting before a node in the list { tmp2 = (Node *) malloc (sizeof(Node)); tmp2 -> next = tmp; // point new node's next at tmp tmp2 -> prev = tmp -> prev; // point new node's prev at tmp's prev tmp -> prev -> next = tmp2; // tmp's previous next is new node tmp -> prev = tmp2; // tmp's prev is new node tmp2 -> value = input2; // put value in node } return(0); } ====Removal==== Removal is the process of removing a node from an established instance of a data structure, such as a linked list in a program. A removal function typically takes a node position as input to delete, or it takes a specific value to look for an delete. An example of a removal function is below: int removeNode() { // Remove a node from the list tmp = start; int i=0; printf("Enter node # to delete: "); scanf("%d", &input); // Move tmp to exact node we wish to delete for(i=0; i next; } if ((tmp != start) && (tmp != end)) { tmp -> next -> prev = tmp -> prev; // The node after points to the node before tmp tmp -> prev -> next = tmp -> next; // Now, the now before points to the node after tmp tmp -> prev = NULL; tmp -> next = NULL; // tmp is now disconnected from the list free (tmp); // deallocate the node tmp is pointing to } else if (start == end) // list is only a single node { free(start); start=end=tmp=NULL; } else if (tmp == start) { tmp -> next -> prev = NULL; // The node following tmp is no longer pointing to us start = start -> next; // Adjust start to point to the new start of the list tmp -> next = NULL; // Disconnect tmp from the list free(tmp); // deallocate the node tmp is pointing to } else // tmp is equal to end { tmp -> prev -> next = NULL; // The node preceding tmp is no longer pointing to us end = end -> prev; // Adjust end to point to the new end of the list tmp -> prev = NULL; // Disconnect tmp from the list free(tmp); // deallocate the node tmp is pointing to } return(0); } ====Searching==== Searching is when a specific node or value is searched for through an established instance of a data structure in a program, via an algorithm. A search function accepts a value as input that represents an initialized value to search for or a given position of a node, then prints out the results of the search (whether or not the search was conclusive, what was found, etc.). An example code can be found below. int search() { //Find if node exists (search by value) printf("Enter a value to search for: "); scanf("%d", &input); tmp=start; int i = 0; int found=0; //if found = 0, then no node matches the search. while (tmp != NULL) { if(tmp->value == input) { printf("Node at position [%d] matches the search value.\n", i); printf("Node [%d]: %d\nSearch value: %d\n\n", i, tmp->value, input); found=1; } i++; tmp = tmp -> next; } if (found == 0) { printf("No node matches the search value.\n"); } return(0); } ====Sorting Algorithm==== A sorting algorithm takes the elements (in our case, it is most often nodes) of a set or list (data structure), and puts them in a specific order (numerical order, for example). Sorting algorithms are used in the functions for insertion, removal and searching that can be found above. Code for a program that makes use of a couple simple sorting algorithms can be found below. #include char concatString(char *, char *); int main() { char string1[1000], string2[1000], junk; printf("Please enter string 1: "); scanf("%s", string1); scanf("%c", &junk); printf("Please enter string 2: "); scanf("%s", string2); scanf("%c", &junk); concatString(string1, string2); return(0); } char concatString(char *string1, char *string2) { int s1=0, s2=0; while (string1[s1] != '\0') { s1++; } while (string2[s2] != '\0') { string1[s1+s2]=string2[s2]; s2++; } printf("After concatenating, your string is now '%s.'\n", string1); return(0); }; ====Selection Sort==== A selection sort is a sorting algorithm that finds the a lowest value in a list, then puts it in the first position. It does this for each item in the list until it is completely sorted. An animation of a selection sort in action can be found below.
Image source: [[http://en.wikipedia.org/wiki/Selection_sort|Wikipedia]] ====Bubble Sort==== A bubble sort is a sorting algorithm that takes compares each item in a given list, and switches the two compared items if they are not correctly ordered. It is also called a sinking sort for this reason, as the lower values will "sink" to the bottom of the list, so to speak. An illustration of how a bubble sort works can be found below.
Image source: [[http://en.wikipedia.org/wiki/Bubble_sort|Wikipedia]] =====data Objective===== ====Objective: Using Data Structures in a program==== From the syllabus: "Write programs that use the following data structures: linked lists, stacks, queues, binary trees, and hash tables." This means exactly what it says, simply write programs that implement data structures. ===Method=== This is also simple-- I'll just use a data structure we've learned about in a program, run it, and see if it works logically like the data structure is supposed to I will use my stack program to do this. ===Measurement=== lab46:~/src/data/stack$ ./stacktest1 Please enter a value (-1 to stop:): 54 Please enter a value (-1 to stop:): 23 Please enter a value (-1 to stop:): 14 Please enter a value (-1 to stop:): 63 Please enter a value (-1 to stop:): -1 Please choose a function: [1: Push][2: Pop][3: Display][0: Quit] 3 [Top of Stack] [1]: 63 [2]: 14 [3]: 23 [4]: 54 [Bottom of Stack] Please choose a function: [1: Push][2: Pop][3: Display][0: Quit] 2 Please choose a function: [1: Push][2: Pop][3: Display][0: Quit] 3 [Top of Stack] [1]: 14 [2]: 23 [3]: 54 [Bottom of Stack] Please choose a function: [1: Push][2: Pop][3: Display][0: Quit] 1 Please enter a value (-1 to stop:): 1 Please enter a value (-1 to stop:): -1 Please choose a function: [1: Push][2: Pop][3: Display][0: Quit] 3 [Top of Stack] [1]: 1 [2]: 14 [3]: 23 [4]: 54 [Bottom of Stack] Please choose a function: [1: Push][2: Pop][3: Display][0: Quit] 0 lab46:~/src/data/stack$ ===Analysis=== Wow, wow, wow. Look at that data structure. It looks like a stack. It functions as a stack. I think it is a stack. It is also in a program! Thereby meeting the objective. Look at how much I have learned! :D This objective is obviously very relevant and applicable to all that we do. =====Experiments===== ====Causing a Stack Underflow on Stack Library Implementation==== ===Question=== I am going to try to cause a stack underflow on my stack library project implementation. My question, I suppose, would be-- is it possible to do with my code? Will it underflow like I expect it to? ===Resources=== My resources would be class lectures and my own stack library. ===Hypothesis=== I think my program will let be pop every element, then attempt to pop in an empty stack, thereby causing a stack underflow. I do not believe that I've set any sort of condition that guards against an underflow, so this should be the result. ===Experiment=== How am I going to test it? By running the program of course! I'll try to cause an stack underflow using my user interface. ===Data=== lab46:~/src/data/stack$ ./stacktest1 Please enter a value (-1 to stop:): 3 Please enter a value (-1 to stop:): 2 Please enter a value (-1 to stop:): 1 Please enter a value (-1 to stop:): -1 Please choose a function: [1: Push][2: Pop][3: Display][0: Quit] 2 Please choose a function: [1: Push][2: Pop][3: Display][0: Quit] 2 Please choose a function: [1: Push][2: Pop][3: Display][0: Quit] 2 Segmentation fault lab46:~/src/data/stack$ ===Analysis=== My hypothesis was not correct. A segmentation fault occurred as the last element of the stack was being popped. I did not expect a segmentation fault then! ===Conclusions=== Evidently, my program is not yet equipped to fill a stack, then empty it, then allow for further manipulation. This requires further examination. ====Causing a Queue Underrun on Queue Library Implementation==== ===Question=== This is a similar experiment as the last one, except we're trying to cause a queue underrun with my queue library project implementation. Question being-- is it possible with my program? ===Resources=== Resources include class lectures and my own queue library implementation. ===Hypothesis=== Based on the results of my last experiment, I think that a segment fault will occur just as the last element of the queue is being dequeued. I think this because this happened with my last program experiment, and this program is very similar, only difference being that it is using a queue. ===Experiment=== I'll try to cause a queue underrun using my program and its user interface. ===Data=== lab46:~/src/data/queue$ ./queue Please enter a value (-1 to stop:): 3 Please enter a value (-1 to stop:): 2 Please enter a value (-1 to stop:): 12 Please enter a value (-1 to stop:): -1 Please choose a function: [1: Enqueue][2: Dequeue][3: Display][0: Quit] 3 [Front of queue] [1]: 3 [2]: 2 [3]: 12 [End of queue] Please choose a function: [1: Enqueue][2: Dequeue][3: Display][0: Quit] 2 Please choose a function: [1: Enqueue][2: Dequeue][3: Display][0: Quit] 3 [Front of queue] [1]: 2 [2]: 12 [End of queue] Please choose a function: [1: Enqueue][2: Dequeue][3: Display][0: Quit] 2 Please choose a function: [1: Enqueue][2: Dequeue][3: Display][0: Quit] 3 [Front of queue] [1]: 12 [End of queue] Please choose a function: [1: Enqueue][2: Dequeue][3: Display][0: Quit] 2 Segmentation fault lab46:~/src/data/queue$ ===Analysis=== My hypothesis was correct. It helps that my last experiment was very similar, but I did not know for sure, as I'm using different data structures. ===Conclusions=== This program is also not currently equipped to deal with an empty queue, something that also requires further evaluation. ====Retest==== If you're doing an experiment instead of a retest, delete this section. If you've opted to test the experiment of someone else, delete the experiment section and steps above; perform the following steps: ===State Experiment=== Whose existing experiment are you going to retest? Prove the URL, note the author, and restate their question. ===Resources=== Evaluate their resources and commentary. Answer the following questions: * Do you feel the given resources are adequate in providing sufficient background information? * Are there additional resources you've found that you can add to the resources list? * Does the original experimenter appear to have obtained a necessary fundamental understanding of the concepts leading up to their stated experiment? * If you find a deviation in opinion, state why you think this might exist. ===Hypothesis=== State their experiment's hypothesis. Answer the following questions: * Do you feel their hypothesis is adequate in capturing the essence of what they're trying to discover? * What improvements could you make to their hypothesis, if any? ===Experiment=== Follow the steps given to recreate the original experiment. Answer the following questions: * Are the instructions correct in successfully achieving the results? * Is there room for improvement in the experiment instructions/description? What suggestions would you make? * Would you make any alterations to the structure of the experiment to yield better results? What, and why? ===Data=== Publish the data you have gained from your performing of the experiment here. ===Analysis=== Answer the following: * Does the data seem in-line with the published data from the original author? * Can you explain any deviations? * How about any sources of error? * Is the stated hypothesis adequate? ===Conclusions=== Answer the following: * What conclusions can you make based on performing the experiment? * Do you feel the experiment was adequate in obtaining a further understanding of a concept? * Does the original author appear to have gotten some value out of performing the experiment? * Any suggestions or observations that could improve this particular process (in general, or specifically you, or specifically for the original author).