I finally got my stack working. The problem took some time to sort out. The issue wasn't with the stack implementation really. It was more of a problem with the linked list. When I created the insert function for the linked list it was assumed that if you were inserting into the list, the list already existed. To push onto the stack I was using the insert function to insert at position 0, however, since there was technically no list as stack→first was set to NULL, which in the insert function was considered an error. I ended up backtracking further and further using the error codes to figure out what was going on. In the end, I added a simple check to the push function. If stack→first is NULL, use the append function instead of the insert function. Still, the real weird thing is that a lot of these problems didn't pop up at first. Initially, I wasn't using the create function to create a list to use as a stack. Everything worked fine until I was popping the last value from the stack and then it would print the value but segfault immediately after. Once I used to the create function, it segfaulted immediately. That's just some kind of strange voodoo witch doctor nonsense.
As of right now, I'm going through the algorithms book and reading through all of the different sorting algorithms. It's pretty cool that you can do the same thing that many different ways. Each algorithm has a varying level of efficiency and purpose. So far, I've covered the selection sort and the bubble sort. The bubble sort causes the larger values to “float” to the top and the smaller values to “sink” to the bottom of the list. In a selection sort, the idea is to search through the list to find the smallest value and swap it with the element in the current position in the list.
In systems programming, I just finished covering socket programming. Socket programming is much different in C than in it is in Java. There's a lot more lower level things to worry about than in Java.
import java.net.*; import java.io.*; class Server { public static void main(String args[]) { try { ServerSocket ss = new ServerSocket(65000); for (int x = 0; x < 5; x++) { Socket s = ss.accept(); PrintWriter p = new PrintWriter(s.getOutputStream()); p.println("Connection number " + (x + 1) + "."); p.close(); } } catch (Exception e) { System.out.println(e.toString()); } } }
That's all there is to it in java.
#include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <sys/types.h> #include <sys/socket.h> #include <netinet/in.h> #include <netdb.h> #include <time.h> #include <string.h> #define PORT_NUM 13000 #define HOST_LEN 256 #define oops(msg) {perror(msg); exit(1);} int main(int argc, char **argv) { struct sockaddr_in saddr; struct hostent *hp; char hostname[HOST_LEN]; int sockID, sockFD, count = 0; FILE *sockFP; char *ctime(); time_t theTime; //Get a socket sockID = socket(PF_INET, SOCK_STREAM, 0); if (sockID == -1) oops("socket"); //Bind address to the socket bzero((void*)&saddr, sizeof(saddr)); gethostname(hostname, HOST_LEN); hp = gethostbyname(hostname); bcopy( (void*)hp -> h_addr, (void*)&saddr.sin_addr, hp -> h_length); saddr.sin_port = htons(PORT_NUM); saddr.sin_family = AF_INET; if (bind(sockID, (struct sockaddr *)&saddr, sizeof(saddr)) != 0) oops("bind"); //Allow incoming calls if (listen(sockID, 1) != 0) oops("listen"); //main loop while (1) { sockFD = accept(sockID, NULL, NULL); if (sockFD == -1) oops("accept"); sockFP = fdopen(sockFD, "w"); if (sockFP == NULL) oops("fdopen"); theTime = time(NULL); fprintf(sockFP, "The time here is.."); fprintf(sockFP, "%s", ctime(&theTime)); printf("Call number %d at %s", ++count, ctime(&theTime)); fclose(sockFP); } return 0; }
There's definitely more the user has to concern himself with here.
I got a start on the directory listing project. I've got some really basic functionality out of it which just consists of listing all the files within the directory except for the . files. Most of that comes from looking at what the book has and restricting . files really wasn't that hard. All you need to do is to check for whether or not the first character in the directory name is a . and if so don't display it. The book also says to alphabetize the listing, dump the listing to an array and run it through qsort. My problem here is that we have no real idea how many items will be in the directory. It could be 1 it could be more than 100. So, you could just make a 2 dimensional array of some size, however, you then could potentially have excess or insufficient space. I suppose you could also run through the items in the directory, count them, and then create a dynamic array for the number of items in the directory and then have the name length as a fixed size. As far as formatting goes i don't think that should be too difficult.
This is a sample format for a dated entry. Please substitute the actual date for “Month Day, Year”, and duplicate the level 4 heading to make additional entries.
As an aid, feel free to use the following questions to help you generate content for your entries:
Remember that 4 is just the minimum number of entries. Feel free to have more.
Computational Complexity focuses on classifying computational problems by their level of difficulty. The basic principle is that a problem is capable of being solved by a computer. A problem will be regarded as initially difficult if it requires a large amount of resources to solve. The resources in question can be disk space, memory usage, network resources, etc. This can help to establish the practical limits of current computers. This can also help to decide whether or not a particular problem can be solved with the given resources at hand.
In computer science, Big-O notation is used to describe how an algorithm responds to different input sizes. This can be used to describe an algorithm's efficiency. It can be formally defined as f(x) = O(g(x)) as x approaches infinity. Big-O notation can sometimes be replaced by Big-Theta notation. Depending on the bounds you wish to describe will determine which notation would be used.
In a selection sort the basic idea is to find the smallest value in a list and move it to the first position. From here we move tot he second position and search for the smallest value starting from this position and moving it to this position. After we find the smallest value and move it to the current position, we move to the next position and repeat.
#include <iostream> #include <cstdlib> using std::cout; using std::endl; void selectionSort(int[]); const int ELEMENTS = 25; int main() { srand(time(NULL)); int values[ELEMENTS], j, temp, min; for (int i = 0; i < ELEMENTS; i++) values[i] = rand() % 100; cout << "Before: "; for (int i = 0; i < ELEMENTS; i++) cout << values[i] << " "; cout << endl; selectionSort(values); cout << "After: "; for (int i = 0; i < ELEMENTS; i++) cout << values[i] << " "; cout << endl; return 0; } void selectionSort(int v[]) { int minIdx, temp; for (int i = 0; i < ELEMENTS - 1; i++) { minIdx = i; for (int j = i + 1; j < ELEMENTS; j++) { if (v[j] < v[minIdx]) minIdx = j; } if (minIdx != i) { temp = v[minIdx]; v[minIdx] = v[i]; v[i] = temp; } } }
brad@Lucid-Lynx:/media/50E9-B47B/Notepad++/Programs$ ./selectSort Before: 99 9 57 47 9 77 47 61 14 35 92 49 87 32 95 54 21 85 96 96 66 9 48 29 2 After: 2 9 9 9 14 21 29 32 35 47 47 48 49 54 57 61 66 77 85 87 92 95 96 96 99
The idea behind a bubble sort is that the higher values will rise to the top of the list while the lower values will sink to the bottom of the list. The list is sorted by checking adjacent array elements and if the element that is higher in the array is less than the element that is lower the two values will be exchanged.
#include <iostream> #include <cstdlib> using namespace std; const int SIZE = 25; void bubbleSort(int[], int); int main() { int values[SIZE]; srand(time(NULL)); for (int i = 0; i < SIZE; i++) values[i] = rand() % 100; cout << "Before: "; for (int i = 0; i < SIZE; i++) cout << values[i] << " "; cout << endl; bubbleSort(values, SIZE); cout << "After: "; for (int i = 0; i < SIZE; i++) cout << values[i] << " "; cout << endl; return 0; } void bubbleSort(int v[], int size) { int temp; for (int i = 0; i < size; i++) { for (int j = 0; j < size - 1; j++) { if (v[j] > v[j + 1]) { temp = v[j]; v[j] = v[j + 1]; v[j + 1] = temp; } } } }
brad@dhcp-181:/media/50E9-B47B/Notepad++/Programs$ ./bubbleSort Before: 78 97 77 0 48 64 94 77 31 86 22 2 68 2 42 42 21 35 13 36 46 98 16 12 22 After: 0 2 2 12 13 16 21 22 22 31 35 36 42 42 46 48 64 68 77 77 78 86 94 97 98
An insertion sort goes through a list one element at a time placing each element into its correct place. Each time an element is selected, its moved into down the list until it finds an element that it is greater than. If the current element is already greater than its previous element it moves to the next element in the list.
#include <iostream> #include <cstdlib> using namespace std; void insertionSort(int[], int, int); int *makeList(const int); const int SIZE = 25; int main() { int *values; values = makeList(SIZE); cout << "Before: "; for (int i = 0; i < SIZE; i++) cout << values[i] << " "; cout << endl; for (int i = 0; i < SIZE; i++) insertionSort(values, i, values[i]); cout << "After: "; for (int i = 0; i < SIZE; i++) cout << values[i] << " "; cout << endl; delete[] values; return 0; } int *makeList(const int size) { int *values = new int[size]; srand(time(NULL)); for (int i = 0; i < SIZE; i++) values[i] = rand() % 100; return values; } void insertionSort(int a[], int pos, int val) { int i = pos - 1; while (i >= 0 && a[i] > val) { a[i + 1] = a[i]; i--; } a[i + 1] = val; }
brad@Lucid-Lynx:/media/50E9-B47B/Notepad++/Programs$ ./insertSort Before: 61 49 66 97 46 16 29 23 42 76 8 52 65 7 29 3 96 64 93 28 25 55 47 90 50 After: 3 7 8 16 23 25 28 29 29 42 46 47 49 50 52 55 61 64 65 66 76 90 93 96 97
Right now I'm not entirely sure how this functions. I'm not very good with recursive logic. I'll keep pecking at it later and see if I can get any further with it.
#include <iostream> #include <cstdlib> using namespace std; int *makeList(const int); void quickSort(int[], int, int); const int SIZE = 25; int main() { int *values; values = makeList(SIZE); cout << "Before: "; for (int i = 0; i < SIZE; i++) cout << values[i] << " "; cout << endl; quickSort(values, 0, SIZE); cout << "After: "; for (int i = 0; i < SIZE; i++) cout << values[i] << " "; cout << endl; delete[] values; return 0; } int *makeList(const int size) { int *values = new int[size]; srand(time(NULL)); for (int i = 0; i < SIZE; i++) values[i] = rand() % 100; return values; } void quickSort(int v[], int left, int right) { int mid, temp, i, j; i = left; j = right; mid = v[(left + right) / 2]; do { while (v[i] < mid) i++; while (mid < v[j]) j--; if (i <= j) { temp = v[i]; v[i] = v[j]; v[j] = temp; i++; j--; } } while (i <= j); if (left < j) quickSort(v, left, j); if (i < right) quickSort(v, i, right); }
brad@Lucid-Lynx:/media/50E9-B47B/Notepad++/Programs$ ./quickSort Before: 49 75 62 19 11 12 70 96 16 95 2 83 99 30 69 73 80 20 41 84 28 86 82 23 54 After: 2 11 12 16 19 20 23 28 30 41 49 54 62 69 70 73 75 80 82 83 84 86 95 96 99
#include <iostream> #include <cstdlib> using namespace std; int *makeList(const int); int binarySearch(int[], int, const int); const int SIZE = 10; int main() { int grandpaSeth[] = {0, 2, 4, 7, 12, 15, 16, 19, 21, 22}, nilbog; cout << "Enter a value to search for: "; cin >> nilbog; if (binarySearch(grandpaSeth, nilbog, SIZE) == 0) cout << "Found " << nilbog << endl; else { cout << "Could not find " << nilbog << endl; for (int i = 0; i < SIZE; i++) cout << grandpaSeth[i] << " "; cout << endl; cout << "Try again..."; cin >> nilbog; if (binarySearch(grandpaSeth, nilbog, SIZE) == 0) cout << "Found " << nilbog << endl; else cout << "Could not find " << nilbog << endl; } return 0; } int binarySearch(int v[], int val, const int size) { int low = 0, high = size -1, i; while (low <= high) { i = (low + high) / 2; if (val == v[i]) return 0; else if (val < v[i]) high = i - 1; else low = i + 1; } return -1; }
brad@Lucid-Lynx:/media/50E9-B47B/Notepad++/Programs$ ./binSearch Enter a value to search for: 10 Could not find 10 0 2 4 7 12 15 16 19 21 22 Try again...12 Found 12
A binary search algorithm splits a sorted list down the middle and the checks to see what side of the list the desired value exists if it does exist within the list. Then, depending on what side of the list we're searching through, we keep moving through the list until we find a value that is either equal to, greater than, or less than the desired value. In the example above, 10 was the first value searched and was first compared to see if it was equal to 15. Since they're not equal we check if to see if 10 less than or greater than 15. Less than, so we check the first half of the list. We keep going down the list until we find the number in the list or we find a value that is less than the desired value.
A binary search tree is a programming data structure much like a linked list. Each node in the list has at most two child nodes, a right in left. The left child node contains values that are less than that of the current node while the right child node contains only values that are greater than the current node.
When inserting into a binary tree everything is relative to the current node. Lets say that we have a binary tree that contains the values 4, 2, 9, and 7. All of which we were inserted in that order. The tree would look as follows
[4]
/ \
/ \
[2] [9]
/
/
[7]
Now lets say that we wish to insert 8 into the tree. We would first compare 8 with 4. Since 8 > 4 we move to the right branch. We than compare 8 with 9. Since 8 < 9 we move to the left branch. Finally we compare 8 with 7. Since 8 > 7 we move to the right branch and also since we have now encountered NULL, the end of the list we can insert the value here.
When removing a leaf from a binary tree there are 3 possible scenarios.
If the node has no children, you can simply remove it from the tree. If a node has one child we remove the node from tree and then replace that node with its child. If the node has two children, we can shift the value of the right child node to the position of the node that we wish to remove.
Inserting and searching a binary tree are very similar. In order to insert into a tree we must first search the tree for the right spot to insert the value. However, in the case of simply searching through a tree if we reach NULL, the end of the tree, than the value we're searching for does not exist within the tree.
I'm not quite sure that I understand how to retrieve the values stored in a tree. Here is some material on the subject. http://en.wikipedia.org/wiki/Binary_search_tree#Traversal
http://encrypt3d.wordpress.com/2010/09/21/binary-search-tree-traversal/
A program is simply a list of executable machine instructions. The idea of a process is a bit different. A process is a program during execution, the memory space allocated for the program.
Threads can be thought of as multiple programs using the same source code but executing at different points within the source code. The processor will jump back and forth between the different threads quickly enough to that to the user it appears that the execution is all taking place simultaneously.
In UNIX, processes are created in a tree like manner. All processes are created by a parent process, in most cases bash using the fork system call. Any process created by fork is a child process of the process that called fork. the calling process is referred to as a parent process. Both parent and child have their own individual PIDs allowing the user to distinguish the two.
#include <unistd.h> #include <stdio.h> int main() { int myPid; myPid = getpid(); fork(); if (myPid == getpid()) printf("I'm the parent my PID is %d\n", myPid); else printf("I'm the child my PID is %d\n", getpid()); return 0; }
brad@brad-desktop:~/c_programs$ ./forkin I'm the parent my PID is 16251 I'm the child my PID is 16252
Shell variables are a set of variables that are used by the shell that can be manipulated by running processes. They can be used to specify file paths, the current shell version, the current user's name and many other things. For example, the bash shell has a shell variable for random numbers.
brad@brad-desktop:~/c_programs$ echo $RANDOM 21946 brad@brad-desktop:~/c_programs$ echo $USER brad brad@brad-desktop:~/c_programs$ echo $BASH_VERSION 4.1.5(1)-release
I/O can be redirected in several ways. One of the most common ways is to redirect output from the standard output device to some file. For instance, if a process outputs some information we don't really care about it can be redirected to /dev/null. Also, if we wish to save some output, we could redirect it to a file and use it later.
brad@brad-desktop:~/closet$ ./msg "Howdy, Stranger" >> msg.txt brad@brad-desktop:~/closet$ ls msg msg.cc msg.txt brad@brad-desktop:~/closet$ cat msg.txt Howdy, Stranger brad@brad-desktop:~/closet$
In UNIX, a pipe is a means to send the output from one process as input to another process.
bh011695@lab46:~/src/music/brad_notes$ cat MidiServer.java | wc -c 493
In the above command line, we cat MidiServer.java and send that output to wc which counts every character in MidiServer.java.
A server is a process which has some information that another process would like to retrieve. A socket is the means for retrieving this information. A socket is similar to a pipe, however, a socket is capable of bidirectional communication whereas a pipe can only send data in one direction. If the server process wishes to get information from the process that is communicating with it, it may do so.
The client/server model is a means of depicting the relationship between client and server processes. The server portion of the process provides some kind of data or service to the client(s). Examples of server applications are web servers and ftp servers. Client applications are things like web browsers and e-mail clients.
Coroutines both continue to run, however, control will pass from one process to the other to handle some phase of the task. If you have process1 and process2 such that they are coroutines, two pipes would be required for bidirectional communication. Data would be passed from process1 to process2. Process2 would manipulate the data and send the result back to process1 to perform other manipulations on and print the result.
A zombie process is a process that has finished executing but still has an entry remaining in the process table. Essentially it's a process that has not sent an exit status signaling completion to its parent. To remove a zombie, one can send the SIG_CHILD signal to the parent or attempt to kill the process. However, if this does not work it is possible to kill the parent at which point init will adopt the zombie and reap it itself.
A server socket waits for a request to come from some client application. It will perform some manipulation on the data from the request and then can return a result to the client application.
/* * Sample code block */ #include <stdio.h> int main() { return(0); }
A client socket is the end of a bidirectional communication with the purpose of retrieving some data from a server socket.
Compare alternative implementations of data structures with respect to performance
Time the execution to push and pop 10000 values to an array based stack and a linked list based stack.
brad@Lucid-Lynx:/media/50E9-B47B/Notepad++/Programs$ time ./aStack real 0m1.230s user 0m0.716s sys 0m0.000s brad@Lucid-Lynx:/media/50E9-B47B/Notepad++/Programs/LinkedList$ time ./lStack real 0m0.003s user 0m0.004s sys 0m0.000s
It seems that the array stack took longer to execute than the linked list based stack. This is not at all what I was expecting. I was assuming the opposite would happen. Furthermore, the time gap is off by more than a second. This makes me wonder whether or not I've done something wrong but I ran the linked list through gdb just to make sure it wasn't skipping the pop loop but that's not the case. Perhaps my array stack algorithms for pushing and popping aren't very efficient?
design programs that handle signals - write a program that can perform an action based on a single that it receives.
#include <stdio.h> #include <stdlib.h> #include <signal.h> int main(int argc, char **argv) { void wakeUp(int); int i; if (argc != 2) { exit(0); } else { i = atoi(argv[1]); printf("Sleeping for %d seconds.\n", i); signal(SIGALRM, wakeUp); alarm(i); pause(); } return 0; } void wakeUp(int i) { printf("Waking up...\n"); }
brad@Lucid-Lynx:/media/50E9-B47B/Notepad++/Programs$ ./alarm 3 Sleeping for 3 seconds. Waking up...
Reflect upon your results of the measurement to ascertain your achievement of the particular course objective.
What will be the output of the following code?
#include <stdio.h> int main() { char name1[] = "Egon"; char name2[] = "Peter"; int myPid = getPid(); fork(); if (getpid() == myPid) printf("Hello, %s\n", name1); else printf("Hello, %s\n", name2); return 0; }
forkdemo1.c in the Understanding Unix/Linux programming book.
The output of the above program wasn't quite what I was expecting. It seems that if you differentiate between the PID of the child and parent process, you can then use that value as a means of flow control in your program to split the load of the program between the parent and child processes.
I'm going to compile the code from above and check the output. In the previous example of fork, certain code was executed twice. In this case, it should split the execution of the print statements. It should give the output of each line only once, unlike what happened in forkdemo1.c.
brad@dhcp-181:/media/50E9-B47B/Notepad++/Programs$ gcc -o forkExp forkExp.c brad@dhcp-181:/media/50E9-B47B/Notepad++/Programs$ ./forkExp Hello, Egon Hello, Peter
My hypothesis was correct. Based on the PID, it is possible to use this as a means of flow control giving the user the possibility to pass certain tasks over to the child process.
It would be very interesting to investigate this further. Something that would be fairly interesting, a possible other experiment, would be to take a program which contains two functions that would be doing some fairly long calculations but neither function relies on the other. Using the method above split the two functions between the parent and child and clock the execution time and compare this with the execution time of calling the functions sequentially.
If you had multiple unrelated manipulations to perform, could you fork and use this to cut the overall execution time in half?
Collect information and resources (such as URLs of web resources), and comment on knowledge obtained that you think will provide useful background information to aid in performing the experiment.
Yes, this should speed up execution time as you have two processes running simultaneously instead of performing one set of manipulations followed by the next set.
I will create two programs, one that performs the manipulations sequentially and another that uses fork to perform the operations.
#include <limits.h> #include <unistd.h> int main() { unsigned long l, k; for (l = 0; l < ULONG_MAX; l++) ; for (k = 0; k < ULONG_MAX; k++) ; return 0; }
#include <limits.h> #include <unistd.h> int main() { unsigned long l; unsigned long k; int myPid; myPid = getpid(); fork(); if (myPid == getpid()) { for (l = 0; l < ULONG_MAX; l++) ; } else { for (k = 0; k < ULONG_MAX; k++) ; } return 0; }
brad@Lucid-Lynx:~/c_programs$ time ./seqUlong real 0m17.570s user 0m17.513s sys 0m0.000s brad@Lucid-Lynx:~/c_programs$ time ./forUlong real 0m12.831s user 0m12.029s sys 0m0.032s
Based on the data collected:
Forking between these two processes cut 5 seconds off of the program's execution time. 5 seconds is a lot when it comes to processor time. This means that this is a very good method for cutting down on execution time.
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:
Whose existing experiment are you going to retest? Prove the URL, note the author, and restate their question.
Evaluate their resources and commentary. Answer the following questions:
State their experiment's hypothesis. Answer the following questions:
Follow the steps given to recreate the original experiment. Answer the following questions:
Publish the data you have gained from your performing of the experiment here.
Answer the following:
Answer the following:
