Part 3

Entries

November 3, 2011

I added and committed queue data structure library project files after completing the project.

lab46:~/src/data$ svn add queue
A         queue
A         queue/createFixedQueue.c
A         queue/deQueue.c
A         queue/copyQueue.c
A         queue/destroyFixedQueue.c
A         queue/isEmpty.c
A         queue/enQueue.c
A         queue/listQueueSize.c
A         queue/makeQueue.bat
A         queue/queue.h
A         queue/queueTest.c
A         queue/makeQueue.old
A         queue/makeQueue.sh
A  (bin)  queue/queueTest
lab46:~/src/data$ svn commit -m "Added and committed queue files -John T. Rine"
Sending        data/Stack/libdll.a
Adding         data/queue
Adding         data/queue/copyQueue.c
Adding         data/queue/createFixedQueue.c
Adding         data/queue/deQueue.c
Adding         data/queue/destroyFixedQueue.c
Adding         data/queue/enQueue.c
Adding         data/queue/isEmpty.c
Adding         data/queue/listQueueSize.c
Adding         data/queue/makeQueue.bat
Adding         data/queue/makeQueue.old
Adding         data/queue/makeQueue.sh
Adding         data/queue/queue.h
Adding  (bin)  data/queue/queueTest
Adding         data/queue/queueTest.c
Transmitting file data ..............
Committed revision 24.
lab46:~/src/data$

November 4, 2011

I cleaned up (finalized) my queue library and then committed it to the Subversion repository.

lab46:~/src/data/queue$ svn commit -m "Cleaned up queue library -John T. Rine"
Sending        queue/deQueue.c
Sending        queue/queueTest
Sending        queue/queueTest.c
Transmitting file data ...
Committed revision 25.
lab46:~/src/data/queue$

November 11, 2011

I worked on data and system programming topics.

November 13, 2011

I worked on data and system programming topics.

November 14, 2011

Once again, I worked on data and system programming topics. In particular, I wrote selection and bubble sorting code for data topics. I then added and committed the code to the Subversion repository:

lab46:~/src/data$ svn add selection*
A         selection.bat
A         selection.c
lab46:~/src/data$ svn add bubble*
A         bubble.bat
A         bubble.c
lab46:~/src/data$ svn commit -m "Added and committed selection and bubble sort example code -John T. Rine"
Adding         data/bubble.bat
Adding         data/bubble.c
Adding         data/selection.bat
Adding         data/selection.c
Transmitting file data ....
Committed revision 26.

November 15, 2011

I worked on data and system programming topics. In particular, I wrote insertion sorting code for data topics. I then added and committed the code to the Subversion repository:

lab46:~/src/data$ svn add insertion*
A         insertion.bat
A         insertion.c
lab46:~/src/data$ svn commit -m "Added and committed insertion sort files -John T. Rine"
Adding         data/insertion.bat
Adding         data/insertion.c
Transmitting file data ..
Committed revision 27.
lab46:~/src/data$

Next, I updated the insertion.c file and then re-committed it.

lab46:~/src/data$ svn commit -m "Updated insertion sort file -John T. Rine"     Sending        data/insertion.c
Transmitting file data .
Committed revision 28.
lab46:~/src/data$

November 25, 2011

For one of my data topics, I wrote, compiled, and executed a file demonstrating the binary search algorithm.

lab46:~/src/data/binarySearch$ gcc binarySearch.c -o binarySearch
lab46:~/src/data/binarySearch$ ./binarySearch ABCDEFGHIJKLMNOPQRSTUVWXYZ U 0 25
Now performing a binary search for element U, between elements 0 and 25
left = 0, right = 25, middle = 0, element = -1, value = U
left = 13, right = 25, middle = 12, element = -1, value = U
left = 20, right = 25, middle = 19, element = -1, value = U
left = 20, right = 21, middle = 22, element = -1, value = U
The element containing the value is 20 (-1 indicates element not found)
lab46:~/src/data/binarySearch$ cd ..
lab46:~/src/data$ svn add binarySearch
A         binarySearch
A         binarySearch/binarySearch.c
A  (bin)  binarySearch/binarySearch.exe
A         binarySearch/binarySearch.bat
A  (bin)  binarySearch/binarySearch
lab46:~/src/data$ svn commit -m "Added and committed binary search files -John T. Rine"
Adding         data/binarySearch
Adding  (bin)  data/binarySearch/binarySearch
Adding         data/binarySearch/binarySearch.bat
Adding         data/binarySearch/binarySearch.c
Adding  (bin)  data/binarySearch/binarySearch.exe
Transmitting file data ....
Committed revision 29.
lab46:~/src/data$

I added and committed sorting source files to the Subversion repository.

lab46:~/src/data$ svn add sorting
A         sorting
A         sorting/bubble.bat
A         sorting/bubble.c
A  (bin)  sorting/bubble.exe
A         sorting/insertion.bat
A         sorting/insertion.c
A  (bin)  sorting/insertion.exe
A         sorting/selection.bat
A         sorting/selection.c
A  (bin)  sorting/selection.exe
A         sorting/quick.bat
A         sorting/quick.c
lab46:~/src/data$ svn commit -m "Added and committed sorting source files -John T. Rine"
Adding         data/sorting
Adding         data/sorting/bubble.bat
Adding         data/sorting/bubble.c
Adding  (bin)  data/sorting/bubble.exe
Adding         data/sorting/insertion.bat
Adding         data/sorting/insertion.c
Adding  (bin)  data/sorting/insertion.exe
Adding         data/sorting/quick.bat
Adding         data/sorting/quick.c
Adding         data/sorting/selection.bat
Adding         data/sorting/selection.c
Adding  (bin)  data/sorting/selection.exe
Transmitting file data ...........
lab46:~/src/data$ svn commit "Added and committed sorting source files -John T. Rine"

November 27, 2011

I researched and documented the following system programming topics: file system structure, directories, links, re-entrant code, and interval timers.

Data Topics

Version Control

Version control software manages changes to documents, programs, and other information stored as files on a computer. It is most commonly used among software development teams, where more than one person may modify the same files. Changes are usually identified by a designator known as the “revision number”, “revision level”, or simply “revision”.

References

Selection Sort

The selection sort is conceptually the most simple of all the sorting algorithms. It works by selecting the smallest (or largest, if you want to sort from big to small) element of the array and placing it at the head of the array. Then the process is repeated for the remainder of the array; the next largest element is selected and put into the next slot, and so on down the line. Since a selection sort looks at progressively smaller part of an array each time through the loop, a selection sort is a little faster than bubble sort.

//selection.c
//John T. Rine
//November 14, 2011
 
#include<stdio.h>
#include<stdlib.h>
 
int cntChars(char *);
 
int main(int argc, char **argv)
{
 
	int x, y;
	int n;
	if(argc != 2)
	{
		printf("usage: selection string_to_sort\n");
		exit(1);
	}
	n = cntChars(*(argv + 1));
 
	//for (x = 0; x < n; x++) printf("%c", *(*(argv + 1) + x));
	//printf("\n");
 
	char *charPTR;
	charPTR = malloc(sizeof(char) * (n + 1));
 
	for (x = 0; x <= n; x++) *(charPTR + x) = *(*(argv + 1) + x);
	printf("Before sorting: ");
	printf("%s\n", charPTR);
 
	for(x = 0; x < n; x++)
	{
 
		int min = x;
 
		for(y = x; y < n; y++) if(*(charPTR + min) > *(charPTR + y)) min = y;
 
		/*Swap*/
		char temp = *(charPTR + x);
		*(charPTR + x) = *(charPTR + min);
		*(charPTR + min) = temp;
	}
	/*print after sorting*/
	printf("After  sorting: ");
	for(x = 0; x < n; x++) printf("%c", *(charPTR + x));
	printf("\n");
 
	free(charPTR);
	return 0;
}
 
	int cntChars(char *inputString)
	{
		// returned value "count" does not include '\0'
		int count = 0;
		while(*(inputString + count) != '\0') ++count;
		return(count);
	}

rem selection.bat
rem John T. Rine
rem November 14, 2011

gcc selection.c -o selection
pause
selection "badcfeghijklnmoprqsutvwxzy"
pause

C:\Users\John\Desktop\New Folder>gcc selection.c -o selection

C:\Users\John\Desktop\New Folder>pause
Press any key to continue . . .

C:\Users\John\Desktop\New Folder>selection "badcfeghijklnmoprqsutvwxzy"
Before sorting: badcfeghijklnmoprqsutvwxzy
After  sorting: abcdefghijklmnopqrstuvwxyz

C:\Users\John\Desktop\New Folder>pause
Press any key to continue . . .

References

Bubble Sort

The simplest sorting algorithm of all is the bubble sort. The bubble sort works by comparing each pair of array elements and swapping their positions, if necessary, to order them by value. This process is repeated as many times as necessary, until the array is sorted. Since the worst case scenario is that the array is in reverse order, and that the first element in sorted array is the last element in the starting array, the most swaps that will be necessary are equal to the length of the array.

//bubble.c
//John T. Rine
//November 14, 2011
 
#include<stdio.h>
#include<stdlib.h>
 
int cntChars(char *);
 
int main(int argc, char **argv)
{
	int x, y, n;
	char temp;
	if(argc != 2)
	{
		printf("usage: bubble string_to_sort\n");
		exit(1);
	}
	n = cntChars(*(argv + 1));
	char *charPTR;
	charPTR = malloc(sizeof(char) * (n + 1));
 
	for (x = 0; x <= n; x++) *(charPTR + x) = *(*(argv + 1) + x);
	printf("Before sorting: ");
	printf("%s\n", charPTR);
 
	for(x = 0; x < n; x++)
	{
		for(y = 0; y < n - 1; y++)
		{
			if(*(charPTR + y) > *(charPTR + y + 1))
			{
				/*sort*/
				temp = *(charPTR + y + 1);
				*(charPTR + y + 1) = *(charPTR + y);
				*(charPTR + y) = temp;
			}
		}
	}
	/*print after sorting*/
	printf("After  sorting: ");
	for(x = 0; x < n; x++) printf("%c", *(charPTR + x));
	printf("\n");
 
	free(charPTR);
	return 0;
}
 
int cntChars(char *inputString)
{
	// returned value "count" does not include '\0'
	int count = 0;
	while(*(inputString + count) != '\0') ++count;
	return(count);
}

rem bubble.bat
rem John T. Rine
rem November 14, 2011

gcc bubble.c -o bubble
pause
bubble "badcfeghijklnmoprqsutvwxzy"
pause

C:\Users\John\Desktop\New Folder>gcc bubble.c -o bubble

C:\Users\John\Desktop\New Folder>pause
Press any key to continue . . .

C:\Users\John\Desktop\New Folder>bubble "badcfeghijklnmoprqsutvwxzy"
Before sorting: badcfeghijklnmoprqsutvwxzy
After  sorting: abcdefghijklmnopqrstuvwxyz

C:\Users\John\Desktop\New Folder>pause
Press any key to continue . . .

References

Insertion Sort

An insertion sort is performed by repeatedly taking the next item to be sorted and inserting it into the array in its proper order with respect to items already inserted

//insertion.c
//John T. Rine
//November 15, 2011
 
#include<stdio.h>
#include<stdlib.h>
 
int cntChars(char *);
 
int main(int argc, char **argv)
{
	int x, y, n;
	char temp;
	if(argc != 2)
	{
		printf("usage: insertion string_to_sort\n");
		exit(1);
	}
	n = cntChars(*(argv + 1));
	char *charPTR;
	charPTR = malloc(sizeof(char) * (n + 1));
 
	for (x = 0; x <= n; x++) *(charPTR + x) = *(*(argv + 1) + x);
	printf("Before sorting: ");
	printf("%s\n", charPTR);
 
	for (x = 1; x < n; x++)
	{
		y = x;
		while (y > 0 && *(charPTR + y - 1) > *(charPTR + y))
		{
			temp = *(charPTR + y);
			*(charPTR + y) = *(charPTR + y - 1);
			*(charPTR + y - 1) = temp;
			y--;
		}
	}
 
	/*print after sorting*/
	printf("After  sorting: ");
	for(x = 0; x < n; x++) printf("%c", *(charPTR + x));
	printf("\n");
 
	free(charPTR);
	return 0;
}
 
int cntChars(char *inputString)
{
	// returned value "count" does not include '\0'
	int count = 0;
	while(*(inputString + count) != '\0') ++count;
	return(count);
}

rem insertion.bat
rem John T. Rine
rem November 15, 2011
gcc insertion.c -o insertion
pause
insertion "badcfeghijklnmoprqsutvwxzy"
pause

C:\Users\John\Desktop\New Folder>rem insertion.bat

C:\Users\John\Desktop\New Folder>rem John T. Rine

C:\Users\John\Desktop\New Folder>rem November 15, 2011

C:\Users\John\Desktop\New Folder>gcc insertion.c -o insertion

C:\Users\John\Desktop\New Folder>pause
Press any key to continue . . .

C:\Users\John\Desktop\New Folder>insertion "badcfeghijklnmoprqsutvwxzy"
Before sorting: badcfeghijklnmoprqsutvwxzy
After  sorting: abcdefghijklmnopqrstuvwxyz

C:\Users\John\Desktop\New Folder>pause
Press any key to continue . . .

References

Quick Sort

The quick sort uses the “divide and conquer” strategy to sort a list. It doesn't require extra memory to perform the sort and is said to perform the sort “in place”. The quick sort algorithm is composed of the following steps:

Select a pivot value to divide the list.
Reorder the list so that all of the elements before the pivot value are less than its value and all of the values greater than the pivot come after it in the list.
Sort both pieces of the list.

//quick.c
//John T. Rine
//November 25, 2011
 
#include <stdio.h>  
#include <stdlib.h>   
 
int cntChars(char *);
void quickSort(char[], int, int) ;
 
int main(int argc, char **argv)
{
	int x, n;
	if(argc != 2)
	{
		printf("usage: quick string_to_sort\n");
		exit(1);
	}
	n = cntChars(*(argv + 1));
	char *charPTR;
	charPTR = malloc(sizeof(char) * (n + 1));
 
	for (x = 0; x <= n; x++) *(charPTR + x) = *(*(argv + 1) + x);
	printf("Before sorting: ");
	printf("%s\n", charPTR);
 
	quickSort(charPTR, 0, n - 1);
 
	printf("After sorting: ");
	printf("%s\n", charPTR);
 
	free(charPTR);
	return 0;
}
 
int cntChars(char *inputString)
{
	// returned value "count" does not include '\0'
	int count = 0;
	while(*(inputString + count) != '\0') ++count;
	return(count);
}
 
void quickSort(char array[], int m, int n)  
{  
	int i,j,k;  
	char temp, pivot;
	if(m < n)  
	{  
		k = (m + n) / 2;
 
		temp = *(array + m);
		*(array + m) = *(array + n);
		*(array + n) = temp;
 
		pivot = *(array + m);  
		i = m + 1;  
		j = n;  
		while(i <= j)  
		{  
			while((i <= n) && (*(array + i) <= pivot)) i++;  
			while((j >= m) && (*(array + j) > pivot)) j--;  
			if(i < j)
			{
				temp = *(array + i);
				*(array + i) = *(array + j);
				*(array + j) = temp;
			}
		}
		temp = *(array + m);
		*(array + m) = *(array + j);
		*(array + j) = temp;
		quickSort(array, m, j - 1);  
		quickSort(array, j + 1, n);  
	}  
}

I wrote the following Windows batch file to automate compilation and execution, with command line arguments, of the source file-quick.c.

rem quick.bat
rem John T. Rine
rem November 25, 2011

gcc quick.c -o quick
pause
quick eafbgchdikjlnmopqsrtvwuyxz
pause

These are the results of compiling and executing the source file, quick.c, using the character string “eafbgchdikjlnmopqsrtvwuyxz” as its only commandline argument.

C:\Users\John\Desktop\sorting>rem quick.bat

C:\Users\John\Desktop\sorting>rem John T. Rine

C:\Users\John\Desktop\sorting>rem November 25, 2011

C:\Users\John\Desktop\sorting>gcc quick.c -o quick

C:\Users\John\Desktop\sorting>pause
Press any key to continue . . .

C:\Users\John\Desktop\sorting>quick eafbgchdikjlnmopqsrtvwuyxz
Before sorting: eafbgchdikjlnmopqsrtvwuyxz
After sorting: abcdefghijklmnopqrstuvwxyz

C:\Users\John\Desktop\sorting>pause
Press any key to continue . . .

References

Merge Sort

The merge sort is a divide and conquer algorithm just like the quick sort, however, unlike the quick sort, it requires extra memory to perform the sort.

References

Binary Search Algorithm

The binary search algorithm is a way to locate an element having a certain value within a list of sorted elements. The binary search algorithm eliminates half of the elements searched with each comparison.

//binarySearch.c
//John T. Rine
//November 25, 2011
 
#include<stdio.h>
#include<stdlib.h>
 
int main(int argc, char **argv)
{
 
	int i, n;
	int left, right, middle, element = -1;
	char value;
	char temp;
	if(argc != 5)
	{
		printf("usage: binarySearch string_to_search element_to_search_for left_element right_element\n");
		exit(1);
	}
 
	left = atoi(*(argv + 3));
	right = atoi(*(argv + 4));
	value = *(*(argv + 2) + 0);
	printf("Now performing a binary search for element %c, between elements %d and %d\n", value, left, right);
	while (left <= right) 
	{
		printf("left = %d, right = %d, middle = %d, element = %d, value = %c\n", left,right,middle,element,value);
		middle = (left + right) / 2;
		if (*(*(argv + 1) + middle) == value)
		{
			element = middle;
			break;
		}
		else if (*(*(argv + 1) + middle) > value) right = middle - 1;
		else left = middle + 1;
	}
	printf("The element containing the value is %d (-1 indicates element not found)\n", element);
 
	return 0;
}

I wrote a batch file to automate compilation and execution with command line arguments of the binarySearch.c source file.

rem binarySearch.bat
rem John T. Rine
rem November 25, 2011
gcc binarySearch.c -o binarySearch
pause
binarySearch abcdefghhijklmnopqrstuvwxyz b 0 25
pause

Here is the execution of the binary search algorithm on Windows with the lower case alphabet as the string to be searched, 'b' as the value to be found, left index as 0, and the right index as 25.

C:\Users\John\Desktop\binarySearch>rem binarySearch.bat

C:\Users\John\Desktop\binarySearch>rem John T. Rine

C:\Users\John\Desktop\binarySearch>rem November 25, 2011

C:\Users\John\Desktop\binarySearch>gcc binarySearch.c -o binarySearch

C:\Users\John\Desktop\binarySearch>pause
Press any key to continue . . .

C:\Users\John\Desktop\binarySearch>binarySearch abcdefghhijklmnopqrstuvwxyz b 0
25
Now performing a binary search for element b, between elements 0 and 25
left = 0, right = 25, middle = 212, element = -1, value = b
left = 0, right = 11, middle = 12, element = -1, value = b
left = 0, right = 4, middle = 5, element = -1, value = b
left = 0, right = 1, middle = 2, element = -1, value = b
left = 1, right = 1, middle = 0, element = -1, value = b
The element containing the value is 1 (-1 indicates element not found)

C:\Users\John\Desktop\binarySearch>pause
Press any key to continue . . .

Here is the execution of the binary search algorithm on Linux with the upper case alphabet as the string to be searched, 'U' as the value to be found, left index as 0, and the right index as 25.

lab46:~/src/data/binarySearch$ gcc binarySearch.c -o binarySearch
lab46:~/src/data/binarySearch$ ./binarySearch ABCDEFGHIJKLMNOPQRSTUVWXYZ U 0 25
Now performing a binary search for element U, between elements 0 and 25
left = 0, right = 25, middle = 0, element = -1, value = U
left = 13, right = 25, middle = 12, element = -1, value = U
left = 20, right = 25, middle = 19, element = -1, value = U
left = 20, right = 21, middle = 22, element = -1, value = U
The element containing the value is 20 (-1 indicates element not found)
lab46:~/src/data/binarySearch$

References

Big-O

Big O or Big Omicron represents the upper bound of asymptotic complexity. Big O notation describes the relative complexity of an algorithm by reducing the growth rate to the key factors when the key factor tends towards infinity, all other factors being ignored. This is why the phrase “asymptotic complexity” is used to describe its behavior. Listed below are common examples of big O notation; included is an explaination of what each example means:

O(1)

Describes an algorithm whose number of operations, the complexity, is always the same regardless of the size of the input data set.

O(n)

The complexity, the number of operations, is directly proportional to the size of the data. This is called linear complexity.

O(n^2)

Describes an algorithm whose number of operations,the complexity, is directly proportional to the square of the size of the input data set. This is common with algorithms that consist of nested loops over the data set. Deeper nested loops result in big O (n to higher powers).

O(2^n)

O(2^n) describes an algorithm whose growth will double with each additional element in the input data set.

References

Binary Trees

Binary trees are so called because when drawn pictorial look like inverted trees. Binary trees are made up of nodes that contain data and pointers to other nodes just like linked-list implementations. Binary trees, however, have “left” and “right” pointers rather than “next” and “previous” pointers. Also similar to linked lists, binary trees use null pointers to indicate an end of a tree; in a binary tree, however, it is the end of a branch or subtree. Since binary trees branch out, that is they spread out rather than being one node after another like a list, so binary trees are fast at searching for data.

References

http://cslibrary.stanford.edu/110/BinaryTrees.html
http://www.cprogramming.com/tutorial/lesson18.html
<html><a href=“http://msdn.microsoft.com/en-us/library/ms379572(v=vs.80).aspx”>http://msdn.microsoft.com/en-us/library/ms379572(v=vs.80).aspx</a></html>
http://www.cs.bu.edu/teaching/c/tree/binary/
http://cis.stvincent.edu/html/tutorials/swd/bintrees/bintrees.html

hpc1 Topics

Keyword 1

Identification and definition of the chosen keyword.

If you wish to aid your definition with a code sample, you can do so by using a wiki code block, an example follows:

/*
 * Sample code block
 */
#include <stdio.h>
 
int main()
{
    return(0);
}

Keyword 2

Identification and definition of the chosen keyword.

If you want to demonstrate something on the command-line, you can do so as follows:

lab46:~$ cd src
lab46:~/src$ gcc -o hello hello.c
lab46:~/src$ ./hello
Hello, World!
lab46:~/src$