Ahh, the sweet smell of victory! On this sixth day of october i have already finished all 12 of my data structures keywords for this month!!! I have learned a LOT about sorting algorithms, and i am so ready to ask a lot of questions requarding sorting, especially selection sorting.
I am also working on 2 other programming projects. One is a doubly linked list implementation that is not going well, and the other is a String difference function that i now have to delete 3/4 of what i wrote because appearently, i took it out of context… I made the function to:
i guess it was a little much…
Just finished coding Projects 2 and 3, also known as queue and stack. Pretty simple concepts, deffinitely fundamental to more advanced lists. The main things that i walked away from this project with are a better understanding of the ar command, and the creation of libraries.
On a side note, i want the old journals back… Whereas opuses are a great was organize your current projects and journal entries, they seem to be taking away from the great deffinition / learning time that we spent in class in C.
Running in circles in dicrete, trying to finish this program, writing this library, understanding what the heck we are trying to accomplish! Then bam! Joe hits us with a program. We are going to take all of the functions we are trying to write and try to build a card game. We are going to use these broad functions to write a texas hold'em poker game. We are currently writing the game in a very high level pseudo code, so high we are outlining like such:
We are establing a rough list of major functions before breaking them down into smaller groups to get specific. After we have finished this major outline we will move into the functions individually and define elements like:
As this Opus is wrapping itself up, this will be my last edition to to it. I have finished:
Over the past week I have been studying concurrency based on forking. We are currently discussing forking in class through a half written program provided by matt. He is going to show us the functionality of the concept, and then let us loose on the code so that we can experiment and learn through trial and error. It is an awesome concept, really makes me wonder about Asynchronous I/0. I'd love to see a real-time application of the fork function in a already written and working program.
Enqueuing is most easily express through an example of a coffee shop. Since we all know that coffee shops always have a line, picute this! enqueuing is like someone walking up to the end of the line. yep, that's pretty much it!
example of enqueuing below.
enqueue(&Q, (rand() % 100) + 1); /* Fill with random numbers from 1 to 100 */
Queues are common in computer programs, where they are implemented as data structures coupled with access routines, as an abstract data structure or in object-oriented languages as classes. Common implementations are circular buffers and linked lists.
Since most arrays are limited in space, queuing and dequeuing become very useful when editing them.
Dequeuing can also be expressed via a coffee shop, so imagine you are standing in line. You walk to the counter and order a caramel cappacino, pay, and leave the line. As soon as you have left the front of the line, you have dequeued.
unsigned int k = 0; while (k < 100) { enqueue(&Q, (rand() % 100) + 1); /* Fill with random numbers from 1 to 100 */ ++k; } k = 1; while (!queue_empty_p(&Q)) { int data; dequeue(&Q, &data); printf("(%d) %d\n", k, data); ++k; }
Queues are common in computer programs, where they are implemented as data structures coupled with access routines, as an abstract data structure or in object-oriented languages as classes. Common implementations are circular buffers and linked lists.
Since most arrays are limited in space, queuing and dequeuing become very useful when editing them.
A queue is a collection of items or data that are kept in a specified order and the principal operations performed on the collection are the addition and subtraction from the front and end of a line. A queue can be expressed as a singly linked list. As i said in other examples, a queue is like a line, you can leave the front, or join the back.
struct queue_node { struct queue_node *next; int data; }; struct queue { struct queue_node *first; struct queue_node *last; };
This code may look familiar, that is because it is a linked list, a singly linked list to be exact.
Buffer overrunning or overflowing is caused when a program, when writing to the buffer, overruns or overflows the boundary's of the buffer and writes to adjacent memory. This is called a violation of memory safety.
Wikipedia states: “Buffer overflows can be triggered by inputs that are designed to execute code, or alter the way the program operates. This may result in erratic program behavior, including memory access errors, incorrect results, a crash, or a breach of system security. They are thus the basis of many software vulnerabilities and can be maliciously exploited.”
Buffer overflowing is very unlikely because of the implementation of segfaults. This is done by checking that the stack has not been altered when the function returns. If it has been altered, the program exits with a segmentation fault. Three systems that do this are Stackguard, libsafe, and ProPolice, all of which are gcc compiler patches.
Buffer underruning, or underflowing is cause when a buffer is sent data at a speed lower than the speed the data is being read from it. This means that whatever is reading from the buffer has to pause and wait for the stream to send data to the buffer so that the data can be read. In computing, this is most commonly refered to as lagging. “dang laggers!”.
This can be prevented/fixed by increasing the size of the buffer. If you wish to read data at a speed of 5, and the stream is sending it at a speed of 4, you are going to experience buffer underflow. So, you can increase you buffer size to 10, leaving you a 2 second window, or even to 300 to give you a full minute window. The unfortunate side to this is an increase in latency between the input and output, which is very undesirable in applications like video gaming.
LIFO - Last in, First out. FIFO - First in, First out.
LIFO can be expressed like a stack of plates. You can take a plate from the top, but no where else, hence the term “last in, first out”. By definition, a lifo is a linear structured list. YOu can take something from the top, but no where else. If you had such a thing as a linear array, where you loaded information in, but could not access any member, only the last one in, if you loaded the numbers {6,3,8,5,4} into the LIFO array in that order, the last one in would be 4, so the first one out, LIFO, would be 4.
FIFO is slightly different, and can be expressed through the example of a hose. If you have a piece of hose that is 6“ in diameter, and you put a couple balls in it that are just over 3” in diameter, what ball is the first one out the other end? The first ball put in. Hence the term “first in, first out”. If you loaded the numbers {6,3,8,5,4} into a FIFO array in that order, the first one in would be 6, so the first one out, FIFO, would be 6.
Sorting algorithms are an algorithm that puts members of a list in a specified order. ex:
Sorting is most useful when you plan to search through your data to find a specific value, or if you wish to output your data in any specific order, like sorted by last names, or age.
A few popular sorting methods:
There are many more sorting methods, but for this example, we will only list these methods. Below is a C implementation of a bubble sort.
void bubbleSort(int numbers[], int array_size) { int i, j, temp; for (i = (array_size - 1); i > 0; i--) { for (j = 1; j <= i; j++) { if (numbers[j-1] > numbers[j]) { temp = numbers[j-1]; numbers[j-1] = numbers[j]; numbers[j] = temp; } } } }
Bubble sorting begins at the top of the data, and if the first is greater than the second, it swaps them and so on and so forth. Below is an example of a bubble sort.
void bubbleSort(int numbers[], int array_size) { int i, j, temp; for (i = (array_size - 1); i > 0; i--) { for (j = 1; j <= i; j++) { if (numbers[j-1] > numbers[j]) { temp = numbers[j-1]; numbers[j-1] = numbers[j]; numbers[j] = temp; } } } }
This type of sorting is good for sorting arrays of numbers or letter into alphebetical or numerical order.
Insertion sort takes items one by one from the list and inserts them into their correct position. this type of sorting is very easy to implement and is very effective on small groups of data. Below is a quick look at some pseudo code for an insert loop in a 0 based array like in C.
for j ←1 to length(A)-1 key ← A[ j ] > A[ j ] is added in the sorted sequence A[0, .. j-1] i ← j - 1 while i >= 0 and A [ i ] > key A[ i +1 ] ← A[ i ] i ← i -1 A [i +1] ← key
below is a quick visual representation of what goes on during an insert sort:
Note: some items used from wikipedia as visual aids.
Shell sorting was created by a man named Donald Shell in 1959. It runs on a sorting method devised by Donald, and finishes with insertion sort by moving out of place elements more than one place at a time. While this method of sorting may not be the best for all cases of data, it is highly effective on small and medium groups of data.
“The algorithm begins by performing a gap insertion sort, with the gap being the first number in the increment sequence. It continues to perform a gap insertion sort for each number in the sequence, until it finishes with a gap of 1. When the increment reaches 1, the gap insertion sort is simply an ordinary insertion sort, guaranteeing that the final list is sorted. ” ~wikipedia
This simply means that the numbers in the set of data are arranged into n number of columns, lets say 5 columns, the columns are then sorted so that they are in order, lowest to highest. The sorting then aranges them into n - x columns, say 3 columns, these columns again are sorted from lowest to highest, providing more number to be in the right order. The sorting will eventually get down to 1 column where a regular insertion sort is perfomed which arranges the data into one long column where all the data is properly sorted.
13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 10 14 13 25 23 33 27 25 59 39 65 73 45 94 82 94
At this point the data is arranged again into a line and sorted using the insertion sort.
Selection sort algorithm finds the lowest value and swaps it with the first position for n amount of times, O(n^2) making it inefficient on larger lists.
The algorithm operates as so:
This breaks the list up into two parts, the items already sorted, and the sublist of items stuck at the end, waiting to be sorted.
Below is an example of this algorithm sorting 6 elements:
64 2 9 40 28 15 init. 2 64 9 40 28 15 [1] 2 9 64 40 28 15 [2] 2 9 15 40 28 64 [3] 2 9 15 28 40 64 [4] 2 9 15 28 40 64 [5]
as you can see, this method is very effective on a small list, only taking 5 steps to sort 6 elements of data.
Implementation of this in C is below:
int iPos; int iMin; for (iPos = 0; iPos < n; iPos++) { iMin = iPos; for (i = iPos+1; i < n; i++) { if (a[i] < a[iMin]) { iMin = i; } } if ( iMin != iPos ) { swap(a, iPos, iMin); } }
Heap sorting is a popular variant of this sorting algorithm as it has taken the basic structure and improved it using an implicit heap data structure.
Quick sort, a comparison algorithm, was designed by Tony Hoare and is faster in use than other O(nlogn) algorithms.
This alrogithm divides the list into 2 smaller sublist of higher and lower values. Quick sort can then sort these values by three steps:
cprogramming.com has given a simple pseudocode implementation of this topic:
function quicksort('array') //pass the function the array of all elements create empty lists 'less' and 'greater' //sort out the lesser from the greater if length('array') ≤ 1 //if 1 or less elements return 'array' // an array of zero or one elements is already sorted select and remove a pivot value 'pivot' from 'array' //find a value in the center, or some other means of grabbing a pivot value for each 'x' in 'array' //for every element in the array if 'x' ≤ 'pivot' then append 'x' to 'less' //self explanitory else append 'x' to 'greater' return concatenate(quicksort('less'), 'pivot', quicksort('greater')) //return the final sorted array
User space is the area of memory where all user applications are run. This involves software that works with file manipulations and performs input/output. Each user process has its own virtual memory location and cannot access the memory locations of other proccesses without permission.
referenceed cprogramming.com
The Jargon File
In computing, the kernel is the main part of most computer operating systems, it is a bridge between applications and the actual data processing done at the hardware level. The kernel's responsibilities include managing the system's resources and the communication between hardware and software components.
A computers operating system usually seperates virtual memory into kernel space and user space. Kernel space is reserved for running the kernel, kernel extensions, and most device drivers.
A file descriptor is an indicator for accessing a file. In C, and most other languages, a file descriptor is an integer, like C type int. Aside from this, every file proccess has 3 basic commands or operations. File in, File out, and Standard file error. A file descriptor is usualy an index for entry in a kernel-resident data structure that contains all the details for openning and accessing file. All applications pass commands via system calls where the files are then access by the kernel based on the commands sent.
Some operations that can be used with file descriptors are:
As refered to in the last keyword, a system call is how a program requests something from a computer systems kernel. This can include hardware or software related calls and can be things like scheduling, accessing the hard disk and many more.
System calls can be divided into 5 catagories:
side note: On POSIX operating systems usual calls are:
A unix pipe provides a one way flow of data. If someone was to enter the command : who | sort , the unix shell who evaluate the who command, and send that data into the sort command as its entry data.
who —–> | —–> sort
write read
The same goes for functions, as you can run a function that returns data, and pipe that data to another function
I/0 redirection is simply redirection input or output signals to a location other than it's standard direction. For instance, “concatenate > confile” would send the output of the concatenate function to the file confile, truncating the data to the end of the file. To append data simply use » instead of >.
To redirect standard input, use concatenate < confile, resulting in concatenate using confile as input.
| symbol | |||
| input | < | ||
| output | » | ||
| truncate | > |
Since a unix shell reads commands from the left to the right, pipes and I/0 redirection can be used in conjunction with each other.
Ex: concatenate | file1 > sort > filesorted
This will run the program concatenate, pipe the output to a file so that sort can use the contents of that file and run a sorting expression and place the input in the file “filesorted”.
similarly, a pipe can be used in place of I/0 redirection, and vice versa.
Ex: concat1 | concat2 ~this will pipe the output of concat1 to be used as the input for concat2 Ex: concat1 > file1 concat2 < file1 rm tmpfile ~this is equivalent to the piping command above.
An internet socket or network socket is an endpoint of a bidirectional inter-process communication flow across an Internet Protocol-based computer network, such as the Internet. ~wikipedia.
Internet sockets constitute as a mechanism for delivering incoming data packets to the appropriate application process or thread, and is all based on a combination of ip addresses, remote and local. Each socket is mapped by the operating system to an application. Within these application and the operating system, these sockets are refered to by an integer called a socket number.
Every socket has an address which is a combination of a port number and an ip address. Each socket also runs on a transport protocol, UDP, TCP, Raw IP, and many others.
A server creates on startup that remain in the listening state untill called by client programs.
For a listening TCP socket, the remote address presented by netstat may be denoted 0.0.0.0 and the remote port number 0.
A TCP server may serve several clients concurrently, by creating a child process for each client and establishing a TCP connection between the child process and the client.
Unique dedicated sockets are created for each connection. These are in established state, when a socket-to-socket virtual connection or virtual circuit (VC), also known as a TCP session, is established with the remote socket, providing a duplex byte stream. ~wikipedia
Therefore, a server socket is a socket created by a server at startup that runs in the listening state until called by a client program. These sockets establish a TCP connection between the server and client. IF it is a TCP server, multiple clients can be run simultaneously.
A signal is a type of inter-process communication used in UNIX operating systems. It is a type of message sent to a process to notify it that an event happend. When the process gets the signal it stops it's normal flow and allows its signal handler to execute.
Ex:
| Signal | Description | Signal number on Linux | |||
| SIGABRT | Process aborted | 6 | |||
| SIGALRM | Signal raised by <tt>alarm</tt> | 14 | |||
| SIGBUS | Bus error: “access to undefined portion of memory object” | 7 | |||
| SIGCHLD | Child process terminated, stopped (or continued*) | 17 | |||
| SIGCONT | Continue if stopped | 18 | |||
| SIGFPE | Floating point exception: “erroneous arithmetic operation” | 8 | |||
| SIGHUP | Hangup | 1 | |||
| SIGILL | Illegal instruction | 4 | |||
| SIGINT (POSIX) | Interrupt | 2 | |||
| SIGKILL | Kill (terminate immediately) | 9 | |||
| SIGPIPE | Write to pipe with no one reading | 13 |
These are only a few of the 64 unix signals.
<signal.h> can also be referenced for more information on this topic.
blocking and non-blocking are forms of input/output processing.
Operating systems implement many functions to use Asynchronous I/0 at many different levels. This type of processing only requires basic functionality to check if steps have checked in or completed, and alerts the other steps accordingly.
Discuss the representation and use of primitive data types and built-in data structures
I will research primitive data types and built-in-structures to determine their formal definition and a few examples, i will then bring that data before another individual to discuss the use of primitive data types and built-in-structures to help myself and the other individual better learn the uses and need for primitive data types and built-in-structures.
This objective took me roughly 4-5 hours to complete, I reserched many of these data types and structures, and presented the information before an individual who proceeded to discuss and explain a few of these in depth. I now plan to record the use of these structures as learned in class and review them in a drive to better understand the representation and use of primitive data types and built-in-structures.
Primitive data types:
Built-in-structures:
and many others.
I believe that yet again i achieved a very good understanding of the course objective and put a lot of effort into this objective. I believe it was done effectively and well and since there is much room for improvement with these topics, it is a good thing the class is only 25% done!
To develop a better understanding of concurrency.
I will now start to ask questions about concurrency, and concurrency in the programs we are writing to see if there is any concurrency going on in our current programs. I will then document that concurrency and try to find or create more concurrency in other programs to better understand it.
concurrency is sahweeeeet! We are going to be touching on the fork() function possibly this Friday in an attempt to really understand concurrency at its finest. It is running more than one thing at a time in a function. So if a function is going to process 400 items, but you need it done in the time it would take to process 100, you can fork the function 3 times and have each fork of the program process 100 items, all at the same time!
What will happen if you give the squaring function [pow()] an invalid value? Like an array?
The man page for this function, and a test program to see hand in hand the results of at valid and invalid entry.
Based on the manual recordings for the pow() function, a non integer value entered into the pow() will return a domain error.
I will test this by running through a program and passing a non integer value for the y coordinate of the pow(x,y) function.
z = pow(x,zero); where x is a positive integer and zero is a character array, does not evaluate. Instead, it returns the error:
showing that an evaluation where x > 0 and y is a non integer, cannot be executed.
Based on the data collected:
Based on my evaluations, i ascertain that the pow function does exactly what it is supposed to, and returns a reasonable statement “domain error”. It returns this because its input cannot be non integer, meaning it cannot accept an array.
Can randomness create order??
Using the monroe method for estimating pi, we can get a rough estimate for pi by generating x amount of points in a quadrant. Also, monkeys are quite fast typers.
I do believe that you can get pi, respectively, by using randomness.
How are you going to test your hypothesis? By using the monte carlo method for calculating pi. I will create a function that runs through some math based on a user define number of iterations.
/* Program to compute Pi using Monte Carlo methods */ #include <stdlib.h> #include <stdio.h> #include <math.h> #include <string.h> #define SEED 35791246 main(int argc, char* argv) { unsigned long int niter=0; double x,y; int i,count=0; /* # of points in the 1st quadrant of unit circle */ double z; double pi; printf("Enter the number of iterations used to estimate pi: "); scanf("%u",&niter); /* initialize random numbers */ srand(SEED); count=0; for ( i=0; i<niter; i++) { x = (double)rand()/RAND_MAX; y = (double)rand()/RAND_MAX; z = x*x+y*y; if (z<=1) count++; } pi=(double)count/niter*4; printf("# of trials= %u , estimate of pi is %g \n",niter,pi); return 0; }
lab46:~/src/DataS$ ./pi Enter the number of iterations used to estimate pi: 1 # of trials= 1 , estimate of pi is 4 lab46:~/src/DataS$ ./pi Enter the number of iterations used to estimate pi: 2 # of trials= 2 , estimate of pi is 2 lab46:~/src/DataS$ ./pi Enter the number of iterations used to estimate pi: 4 # of trials= 4 , estimate of pi is 2 lab46:~/src/DataS$ ./pi Enter the number of iterations used to estimate pi: 16 # of trials= 16 , estimate of pi is 2.5 lab46:~/src/DataS$ ./pi Enter the number of iterations used to estimate pi: 256 # of trials= 256 , estimate of pi is 2.98438 lab46:~/src/DataS$ ./pi Enter the number of iterations used to estimate pi: 65536 # of trials= 65536 , estimate of pi is 3.14227 lab46:~/src/DataS$ ./pi Enter the number of iterations used to estimate pi: 4294967296 # of trials= 0 , estimate of pi is -nan lab46:~/src/DataS$ ./pi Enter the number of iterations used to estimate pi: 131072 # of trials= 131072 , estimate of pi is 3.1423 lab46:~/src/DataS$ ./pi Enter the number of iterations used to estimate pi: 262144 # of trials= 262144 , estimate of pi is 3.14171 lab46:~/src/DataS$ ./pi Enter the number of iterations used to estimate pi: 524288 # of trials= 524288 , estimate of pi is 3.13922
Based on this data collected, as we increase the number of random numbers, we get a closer and closer approximation of pi.
The monte carlo method for computing pi is a great way to show that randomness can produce order.
Dave Schoeffler asks: How does the system handle unexpected input. Such as a character when an integer is expected.
I believe that when you enter a character when an integer is expected the program will output an error and terminate. This will happen because the system does not know what with the character value.
I used the same code as Dave.
lab46:~/src/data$ ./inttest Enter integer: 1 Int is 1 lab46:~/src/data$ ./inttest Enter integer: q Int is 0 lab46:~/src/data$ ./inttest Enter integer: s Int is 0 lab46:~/src/data$
Answer the following:
Answer the following: