Expert answer:Numeric Summary and pseudocode
Solved by verified expert:Key Assignment Draft: Include session changesThe first two Individual Projects used linked lists for stacks, queues, and hashing implementations. With this task, searching performance with linked lists will be addressed. Part 1: Your tasks for this assignment are the following:Discuss the use of a binary tree when searching for keys in an array.Discuss the use of a binary tree when searching for keys in a linked list. Part 2: Complete the following program:Describe a linked list structure to support binary searching.Create pseudo code to describe a binary search with this linked list variation. Week 4 Deliverables:Summary of binary search with an array.Summary of binary search with a linked list.1 fully documented pseudo code implementation of a linked list useful for binary searches. Part 3: Key Assignment Draft: Once you have completed this section, submit the pseudocode and summary of binary searches from all of the following in your Key Assignment template:Section 1: Lists, Stacks, and QueuesSection 2: Heaps and TreesSection 3: Sorting AlgorithmsSection 4: Searching
it265__ip1.doc.docx
it265__ip2.doc.docx
it265__ip3.doc.docx
Unformatted Attachment Preview
Running head: DATA STRUCTURES IN JAVA
Data Structure Using Java
Lists, Stacks, and Queues
James Larkin
10-6-17
1
DATA STRUCTURES IN JAVA
2
Abstract
Data structure organizes data in a more efficient programs. An efficient program utilizes less
space and system resources. Data structures are meant to be data organization for such items.
They form a basic part or an algorithm or a program. Any collection of data can be searched,
processed or manipulated in any order or it can be modified. Data structures and algorithm
choice can make a program to take the shortest time possible or longest time ever. Data
structures require resources like space, time and programming effort hence the above named
effect. Most common used algorithms in computer science includes the merge sort, stacks and
queues, heaps and trees, recursion and searching algorithms. Efficiency and usefulness of these
algorithms can be determined using Java programs. The study will entail discussions and
implementation of these algorithms in details. Selection process in data structures entails
analyzing a problem and determine the resources requires and constraints, determining the basic
operation that must be meat for a program to run and selection the best data structure that meets
the requirements of a program.
DATA STRUCTURES IN JAVA
3
Table of Content
Section 1: Lists, Stacks, and Queues………………………………………………………………………………………………. 4
Stacks …………………………………………………………………………………………………………………………………….. 4
Queues …………………………………………………………………………………………………………………………………… 6
Section 2: Heaps and Trees …………………………………………………………………………………………………………… 9
Hash table pseudo code …………………………………………………………………………………………………………….. 9
Collision in linked list ………………………………………………………………………………………………………………. 9
Section 3: Sorting Algorithms …………………………………………………………………………………………………….. 10
Compare sort algorithms …………………………………………………………………………………………………………. 10
Section 4: Searching ………………………………………………………………………………………………………………….. 11
pseudo code search linked list or array ……………………………………………………………………………………… 11
Section 5: Recursion ………………………………………………………………………………………………………………….. 12
pseudo code for factorial of a number using recursion. ……………………………………………………………….. 12
References:……………………………………………………………………………………………………………………………….. 13
DATA STRUCTURES IN JAVA
Section 1: Lists, Stacks, and Queues
Stacks
Import java.io. *;
Class Node {
Public String element;
Public Node next;
Public Node (String Value) {
Element = Value;
}
Public void showNode(){
System.out.printLn(“Element [ “ + element + “]”);
}
}
Class LinkedList {
Private Node start;
Private Node end;
Public LonkedList ()
{
Start = null;
End = null;
}
Public boolean is Empty(){
Returns start == null;
}
Public void enqueue(String Value){
Node newNode = new Node(Value);
If (isEmpty())
4
DATA STRUCTURES IN JAVA
Start = newNode;
else
end.next = newNode;
end = newNode;
}
Public String dequeue(){
String temp = start.element;
if(start.next == null)
end = null;
start = start.next;
return temp;
}
Public void displayList()
{
System.out.println(“Elements:”);
Node current = start;
While (current != null){
current.displayNode();
current = current.next;
}
System.out.println(“”);
}
}
Class Queue {
Private LinkedList queueLinkedList;
Public Quueue(){
QuueLinkedList = new LinkedList();
}
5
DATA STRUCTURES IN JAVA
Queues
Import java.io. *;
Class Node {
Public String element;
Public Node next;
Public Node (String Value) {
Element = Value;
}
Public void showNode(){
System.out.printLn(“Element [ “+ element + “]”);
}
}
Class LinkedList {
private Node first;
public LinkedList(){
first = null;
}
Public Boolean is Empty(){
return (first ==null);
}
public void push(String value){
Node newNode = new Node(value);
NewNode.next = first;
First = newNode;
}
6
DATA STRUCTURES IN JAVA
Public Node pop(){
Node temp = first;
first = first.next;
return temp;
}
public void display()
{
System.out.println(“Elements: ”);
Node current = first;
While (current !=null){
current.displayNode();
current = current.next;
}
System.out.println(“”);
}
}
class Stack{
private LinkedList stackLinkedList;
public Stack()
{
StackLinkedList = new LinkedList();
}
Public void push(String value){
7
DATA STRUCTURES IN JAVA
StackLinkedList.push(value);}
Public Node pop()
8
DATA STRUCTURES IN JAVA
9
Section 2: Heaps and Trees
Hash table pseudo code
Collision in linked list
DATA STRUCTURES IN JAVA
Section 3: Sorting Algorithms
Compare sort algorithms
10
DATA STRUCTURES IN JAVA
11
Section 4: Searching
pseudo code search linked list or array
DATA STRUCTURES IN JAVA
12
Section 5: Recursion
pseudo code for factorial of a number using recursion.
DATA STRUCTURES IN JAVA
References:
Weiss, Mark A. (2009). Data Structures and Problem Solving Using Java, 4th Edition.
Retrieved from https://bookshelf.vitalsource.com/#/books/9781323417645/
13
Running Head: DATA STRUCTURE IN JAVA
DATA STRUCTURE IN JAVA
James Larkin
Section 2 Heaps, Trees and Hashing
10-14-17
1
DATA STRUCTURE IN JAVA
2
Insertion
class Node {
Node next;
String data;
public Node (String x) {
data=x;
next=null
}
}
class HashTable {
Node [] node;
int size
public HashTable (int tablesize) {
size=8;
node=new Node[size]
}
public insert (int val) {
val %=node. length
Node nodeptr=new Node(Val)
if(node[val]==null) {
node[val]=nodeptr;
DATA STRUCTURE IN JAVA
3
} else {
nodeptr. next=node[val];
node[val]=nodeptr;
}
}
public void main (){
HashTable hashtable=new HashTable (8)
hashtable. Insert(val);}}
Removal
class Node {
Node next;
String data;
public Node (String x) {
data=x;
next=null
}
}
class HashTable {
Node [] node;
int size
public HashTable (int tablesize) {
size=8;
DATA STRUCTURE IN JAVA
node=new Node[size]
}
public remove (int val){
val %=node.length;
Node start=Node[val];
Node end=start;
if(start.data==val){
node[val]=start.next;
size–;
return;
}
while(end.next!=null&&end.next.data!=val){
end=end.next;
if(end.next.next==null){
end.next=null
return;
}
end.next=end.next.next;
node[val]=start;
}
}
4
DATA STRUCTURE IN JAVA
5
public void main (){
HashTable hashtable=new HashTable (8)
hashtable. remove(val);}}
Documentation
We have to create the class Node, object node to form data type that would be used in the list
structure (Yazdani et al., 2016).
class Node {
Node next;
String data;
public Node (int x) { //construct
data=x;
next=null
}
}
Another class HashTable has to be created. This is the class that is used to manage all the
methods used in the implementation of the Hash Table (Laarman, 2014).
DATA STRUCTURE IN JAVA
6
class HashTable {
Node [] node;
int size
public HashTable (int tablesize {
size=8;
node=new Node[tableSize]
}
An array list of the type Node is created with the name node; A variable size is also set to hold
the size of the Array (Qiao, 2014).
Both these variables are instantiated by a constructor with takes single parameter.
Method to insert an element
public insert (int val) {
val %=node. length
Node nodeptr=new Node(Val)
if(node[val]==null) {
node[val]=nodeptr;
} else {
nodeptr. next=node[val];
node[val]=nodeptr;
DATA STRUCTURE IN JAVA
7
}
}
This method takes one parameter “val” which is a key representative. Using mod (8, n)
hashfuction the key is derived which is then tested in the hashtable to check whether it is null
(Yazdani et al., 2016).
val %=node. length
node. length would be equivalent to 8 hence satisfies the function mod (8, n);
Create an object of the type Node and give the key position.
Node nodeptr=new Node(Val)
After creating the object, the object position has to be tested whether the position is null. If it is
empty the addition operation is performed else the addition is shifted to the next position.
if(node[val]==null) {
node[val]=nodeptr;
} else {
nodeptr. next=node[val];
node[val]=nodeptr;
}
}
Method to remove an element
public remove (int val){
DATA STRUCTURE IN JAVA
val %=node.length;
Node start=Node[val];
Node end=start;
If(start.data==null) {
Return;}
if(start.data ==val){
node[val]=start.next;
size–;
return;
}
While (end.next!=null&& end.next.data!=val){
end=end. next;
if(end.next.next==null){
end.next=null
return;
}
end. next=end.next.next;
node[val]=start;
8
DATA STRUCTURE IN JAVA
9
}
The method takes a parameter that is used to get the key using the following function.
val %=node.length; //equivalent to mode(8, n)
Create an instance object at the position mapped by the key.
Node start=Node[val];
Check whether the node ‘start ‘is empty. If empty then do nothing because there is no element to
remove.
If(start.data==null) {
Return;
}
If the start node is not empty then proceed to test whether the node start data is equivalent to the
“val” our key mapper.
If (start.data ==val){
node[val]=start.next;
size–;
return;
}
If this is true the node start .data is assigned the start. next and size is decremented. Followed by
a return statement to end the function.
DATA STRUCTURE IN JAVA
10
If the result is false then it proceeds to the while loop and transverses through the node testing
whether the next elements are null (Klein, 2016).
While (end.next!=null&& end.next.data!=val){
end=end. next;
if(end.next.next==null){
end.next=null
return;
}
}
When one of the above condition is successful the following statement would be executed
Assigning end.next and node at the current pointer to the start.
end. next=end.next.next;
node[val]=start;
Method Main
In the main method create an istance object of the class HashTable and pass a parameter 8.
Call the method insert(val) and remove carry out the operations
DATA STRUCTURE IN JAVA
11
References
Yazdani, M., Paseh, H., & Sharifzadeh, M. (2016). Performance comparisons of bonding boxbased contact detection algorithms and a new improvement technique based on
parallelization. Engineering Computations, 33(1), 7-27.
Laarman, A. W. (2014). Scalable multi-core model checking (Doctoral dissertation, Centre for
Telematics and Information Technology, University of Twente).
Qiao, Y. (2014). Efficient data structures and protocols with applications in space-time
constrained systems (Doctoral dissertation, University of Florida).
Klein, S. T. (2016). Basic concepts in data structures. Cambridge University Press.
Running Head: SORTING ALGORITHMS
Sorting Algorithms
James Larkin
Institutional Affiliation
1
SORTING ALGORITHMS
2
Sorting Algorithms
Introduction
Sorting technique/algorithm is an algorithm that is used to arrange items in a list in a
certain order. There are many different sorting techniques/algorithms and in this article, I will be
looking at some of the different major sorting algorithms and the key differences between these
sorting algorithms. Some of the sorting algorithms that I will be looking at include the following:
Bubble sort, Insertion sort, Heap sort, Tree sort, Selection sort, Shell sort and Quick sort.
Bubble Sort
This is a sorting technique that uses comparison as a means of sorting elements.
Usually, in this algorithm, the elements that are next to each other are compared to check if they
are in order and if they are not in order, the item is swapped. This algorithm is usually not
appropriate or satisfactory for a lot of data-sets because it’s complexity level is Ο(n2) where n
represents the number of items.
Insertion Sort
The insertion algorithm is a simple algorithm that works in the same manner that we sort
gambling cards using our hands. It usually sorts one element at a particular time by taking the
element and placing it at its correct location. The process goes on until all the items in that list
have been sorted (Hougardy & Vygen, 2016).
SORTING ALGORITHMS
3
Select Sort
The major concept behind this algorithm is that it usually divides a list into two major
parts. The first part is the sorted list which is on the left side and the second part is the unsorted
list on the right side. The sorted list is usually empty at first and the unsorted list has all the
elements that need to be arranged. Then smallest element from the unsorted side is placed on the
left side of the sorted part and it becomes a member of the sorted list. These processes continue
until all the elements are sorted.
Shell Sort
The shell is considered to be an improvement of the insertion sort in which the original
list is broken down into several sub-lists in which these sub-lists are sorted using the insertion
sort. The elements that are widely spread are first sorted and then the elements which are not
widely spread are sorted later. This algorithm is suitable for data sets which are medium in size
and usually its complexity is Ο(n).
Quick Sort
Just like the merge sort, the quick sort also uses divide and conquer algorithm but the
quick sort usually selects a value which will be the pivot value or point and usually this value is
the first item in the list. The main concept behind using the pivot value is that it is used to assist
in splitting the values in the list. Now after the list has been sorted, the final position where this
pivot belongs will be used to further divide the list (Moore & Takvam, 2016).
SORTING ALGORITHMS
4
Heap Sort
The heap sort is an algorithm that arranges the data to be sorted into a binary tree called a
heap. Usually, the largest values are found at the top of the heap tree and thus it is the work of
this algorithm to reverse this sequence.
Tree Sort
This is an algorithm that utilizes a binary search tree to arrange the elements of a list.
After the elements have been sorted the tree is usually traversed so that the items can be sorted in
the required order.
The Big-O Notation
This is a method of measuring how an algorithm executes depending on the time and the
memory required for a number of items to be sorted.
Bubble Sort
For bubble sort, it is usually not efficient where there is a large data-set because of its
average and worse case complexity of Ο(n2) where n is the number of elements in that list
(Rajagopal & Thilakavalli, 2016).
Insertion Sort
This algorithm is not also suitable for large data sets because it has an average of and
worse case complexity of Ο(n2).
SORTING ALGORITHMS
5
Selection Sort
This algorithm’s average and worse case complexity is Ο(n2) and therefore also it is not
suitable for large data-sets.
Merge Sort
This algorithm has a worse case complexity of Ο(n log n) and thus it is considered as one
of the best sorting algorithms.
Shell Sort
This algorithm is usually used for the medium-sized data-sets because it has a complexity
of Ο(n).
Quick Sort
This algorithm is more efficient for large data sets and it has a complexity of Ο(n2).
Tree Sort
The tree sort has a worse case complexity of O(log n) which makes this algorithm to be
so fast.
Conclusion
Different sorting algorithms may have the same worse case complexity but this does not
mean that these algorithms have the same efficiency in the way they sort items in a list. Each of
these algorithms has its own way of sorting items and thus best sorting algorithm should always
be used in a particular situation.
SORTING ALGORITHMS
6
References
Hougardy, S., & Vygen, J. (2016). Sorting Algorithms. In Algorithmic Mathematics (pp. 91107). Springer International Publishing.
Moore, K., & Takvam, K. (2016). Sorting Algorithms.
Rajagopal, D., & Thilakavalli, K. (2016). Comparison of different sorting algorithms in Data
Structure based upon the Time Complexity. International Journal of Technology, 6(1),
23-30.
…
Purchase answer to see full
attachment
How it works
- Paste your instructions in the instructions box. You can also attach an instructions file
- Select the writer category, deadline, education level and review the instructions
- Make a payment for the order to be assignment to a writer
- Download the paper after the writer uploads it
Will the writer plagiarize my essay?
You will get a plagiarism-free paper and you can get an originality report upon request.
Is this service safe?
All the personal information is confidential and we have 100% safe payment methods. We also guarantee good grades