IT265 Summary and pseudocode

This individual Project for this section one, I will discuss Linked lists and how to Add, Remove and Display them using pseudo code. The second section of the document includes description of hash tables and how to implement them. The third section of third section of this project will consist of a compare and contrast of 5 Sort Algorithms, with a part 2 of how Big O is utilized.

This Individual Project will go over the understanding of Data Structures using Java. The 1st section of this project will go into detail Links, Stacks and Queues and how they are implemented. A linked list is a Data Structure that allow data to be stored at certain nodes connected by pointers. There are multiple linked lists though the 1st section will focus on Stacks and Queues. (Olorunnisola, 2016). The following 2nd Section will be Heaps and Trees, which will take the pseudo code and add them to a hash table and resolve collisions. The 3rd Section will sort Algorithm and 4th will show how to search a value in a linked list or array. The 5th Section will focus on Recursion and take a factorial of a number. The final portion of the Individual Project will bring an overall basic understanding of data structures based on the knowledge gained through the 5 sections.

This type of Stack will be utilizing Last-in-first out (LIFO). This shows that the list is empty, with null meaning empty and Head being the initial node:

Head = null

Push (item), this is inserting or adding data to a stack. Essentially if head = null the list is empty, then (else) nextref (node) = top of the stack. Printf to validate insertion of data to stack. Printf shows the node data

{

struct (nextRef);

nextRef->(data)=value;

If (Head = null)

nextRef -> next = null;

else

nextRef -> next = top;

top = nextRef;

print (add (data) to stack successs)

}

Pop (), this is deleting data from the stack. If head = null the list is empty, then (else) Adding a temporay spot (temp) to the pointer or top of the stack. Set the temp as top then set top to next. Data should be in the temp node at this point. Then free (delete) the temp. printf shows the node data

{

If (head=null)

Printf (Stack is empty);

Else {

Temp = top;

Print(delete (data), temp -> (data))

Top = temp -> next;

Free (temp);

}

Display(), the nodes in the stack. If head = null the list is empty, then (else). Display temp data. And move to next node until temp reaches first node or top of the stack. Then display the temp with the data in it.

{

If(head = null)

Printf (stack is empty)

Else{

struct temp = top;

While(temp -> next)

Print (temp ->(data))

Temp = temp -> next;

Print (temp -> (data));

}

This type of Queue will be using First-in-First Out (FIFO). This will show that the list is empty with front and rear of code being empty (NULL).

{front = NULL, rear = null}

Enqueue (item) is adding data to either the front or rear of the data structure. Struct shows building of new nextRef (node). NextRef then adds data to the node. If front has no node then a node with data is added to the rear of the structure. Print verifies that data is added.

{

Struct(nextRef)

NextRef -> (data)

If (front =NULL)

Front=rear =nextRef

Else (rear -> next = nextRef);

Rear = nextRef;

Print (add (data) to queue success)}

Dequeue () is deleting data to either the front or rear of the data structure. If front of queue is empty, hit print to verify. If not struct (create a temp node) in front. Move data to next. Print again to verify data and free (delete) temp.

{

if (front =NULL)

print (this verifies that queue is empty)

else

struct temp = front;

front = front -> next;

print (verify (data) necessary)

free (temp);

}

Display () the queue is necessary for verification of data in the queue. If the front is null then the queue is empty. Else implies that if not, construct a temp in front while temp is next. Print will show data in temp node. Type temp to next until front gets to rear of structure. Print to show data in temp or rear.

{

If (front = NULL)

Print (this verifies that queue is empty)

Else

Struct temp = front;

While(temp -> next)

Print (temp ->(data))

Temp = temp -> next;

Print (temp -> (data));

}

A hash table is a type of data structure that allows data to implemented in a specific way. This type of data structure can be used to take information and give it a value, so that it can be insert or removed when the item needs to be found. This data can be broken down in multiple ways, depending on how the user determines that it needs to be broken down. Examples of this would be by Name, word count or address. This is so that when the user needs to insert more data, the information goes to the right location. A hash table does not always need to be set up in a certain manner. The data can sometimes be put into the first available node or if the table is full, have a collision of the value. A Collison is when 2 or more keys are in an element have been given the same value. The location in the array for a collision are elements stacked on top of each other.

(Goodrich, Tamassia, Goldwasser, 2014)

At the basic level of a hash table a simple linear array is displayed. For this example I will be creating an a hash table array with the size of 8. This will be represented with values from 0-7. Keys or data will be assigned to the hash table dependent on the value it is given.

For this table we will create a set of keys that are based on alphabetical order. The keys will be given will are based on first names.

(Key, Value)

(Adam, 0)

(John, 3)

(Stephen,6)

How it appears in the array, is essentially.

Inserting an additional name is going to be dependent on whether the node is empty, or the hash table is full. The hash function is represented as such below.

Inserting data into the hash table with a new key it is necessary to a has function will be need. The pseudo code will be created to determine the insertion of a new key. The code will initially look to see if the node is empty or null then either place key into the node or go to then next node represented in Node + 1. This is done by probing node after node to find an empty node, while looping back to 0 if necessary.

Insert (Key, Value)

IF

Node = Null

Node = (Key, Value)

ELSE

Node = Node + 1 (n = n + 1)

Removing of the data in the node is different due to data can’t just be removed and made null. This node will have to represented as deleted so that the when the user utilizes search it does fail the process. A pseudo code will be created to remove a new key. In the hash function take that wants the node to be 0 or Node = 0. Find the key and value, make it deleted or go to the next node to find the key and value to delete. Once this process is done the pseudo code for inserting will need to be changed to determine if the node is null or deleted.

Remove (Key, Value)

Node = (Key, Value)

IF

Node Key = Key

Node = deleted

ELSE

Node = Node + 1 (n = n + 1)

Sorting Algorithms is an algorithm that has steps that uses an array to do specific steps to take an unsorted array and make it sorted. Selecting the right sorting algorithm can be based on how fast you need the sort to take place. This can be dependent on the speed of the program you are using. Understanding the differences of Sorting Algorithms is understanding the Big O Notation. The Big O Notation determines the performance of the algorithm. This uses an algorithm that shows a running time taken for something to grow in a best, worst and average-case scenario. This formula can also be used to determine space complexity. Space complexity determines the amount of storage needed.

· Merge Sort: This algorithm takes the number of elements in the array and divides them. This algorithm is use the divide-and-conquer approach. Essentially if you have an unsorted array of 8 values. You break them down into 4 sub-arrays. The 4 sub arrays would then be sorted till there is 2 sorted array. The 2 sub arrays would then be sorted together to make 1 sorted array. This array has fairly fast, which is at worst case and average case faster than Insertion sort or bubble, but slower than the 2 at best. The space complexity is also slower than other sort algorithms.

· Insertion Sort: This algorithm takes an element at a time and moves it in ascending order to allow the unsorted algorithm to become sorted. While this Type of sort has a higher space complexity, the worst and average case are slower than merge sort. Though at best-case is faster than merge sort.

· Bubble Sort: This type of algorithm is simple for sorting lists. This algorithm takes 2 at a time and sorts them in ascending order. If there was 8 elements it would take 1 and 2 and sort them, then 2 and 3, and so on until the array is sorted. This type of array is similar in speed and space complexity as Insertion Sort.

· Quicksort: This type of algorithm is a fast sorting algorithm. This algorithm is similar to merge sort of how it uses divide-and conquer. This algorithm will take an unsorted array and select an element value in the array. At each step it will take the outer most elements and determine them from least to greatest in ascending order. This will be done till you reach the selected element value. Then a new prime element will be selected and the outer element swap will begin again. This will be done until the array is sorted. This type of sort is fast running time for best-case with great space complexity.

· Heapsort: This type of algorithm utilizes a binary heap data structure. This type of sort is similar to merge sort in running time and similar to insertion and bubble sort for space complexity. The Idea is to take the array and place the values into a binary tree. The parent node will always be the greater value or less value, this depends on min or max heap. Go from the left child to the right child and place them back into the array depending on the how they are sorted.

(Moore, Pilling, Khim, 2016)

The statement has been made that the Big O is not always the best way to determine a way to compare and contrast performance since the number of keys change. Well this is true base on the locality of sorts. If the elements in the array are small, the sorting options will be fast. So a smaller amount is easier to sort based on locality. For larger elements in an array or the type of sort you use can make a large difference. An example of this is a quick sort opposed to a heap sort.

TBD

TBD

TBD

Goodrich, M., Tamassia, R., Goldwasser, M. (2014). Data Structures & Algorithms in JAVA. Retrieved from datastructures.maximal.