Rolling a Six-Sided Die 6000 Times (Java Coding)

import java.util.Random;

public class RollDie {

public static void main(String[] args) {

Random randomNumbers = new Random();

int freq1 = 0;

int freq2 = 0;

int freq3 = 0;

int freq4 = 0;

int freq5 = 0;

int freq6 = 0;

int face;

for(int roll=1; roll<=6000; roll++)

{

face = 1 + randomNumbers.nextInt(6);

switch(face)

{

case 1:

++freq1;

break;

case 2:

++freq2;

break;

case 3:

++freq3;

break;

case 4:

++freq4;

break;

case 5:

++freq5;

break;

case 6:

++freq6;

break;

}

}

System.out.println("Face\tFrequency" );

System.out.printf("1\t%d\n2\t%d\n3\t%d\n4\t%d\n5\t%d\n6\t%d\n",

freq1, freq2, freq3, freq4, freq5, freq6);

}

}

Algorithms & Data Structures - Searching

Searching
√The process used to find the location of a target among the list of object.
√We begin with list searching and a discussion of two basic search algorithm

List Searches
√The two basic searches for arrays are the sequential search and the binary search.

Sequential Search
√The sequencial search is used whenever the list is not ordered.
√It is useful for small lists or lists that are not searched often.
√In sequential search, we start searching for the target at the beginning of the list and continue until we find the target or we are sure that it is not in the list.
√The efficiency of sequential search is O(n).










Binary Search
√The binary search starts by testing the data in the element at the middle of the array to determine if the target is in the first or the second half of the list.
√If it is in the first half, we do not need to check the second half.
√If it is in the second half, we do not need to check the first half.
√To find the middle of the list, we need 3 variables: one to identify the beginning of the list, one to identify the middle of the list and one to identify the end of the list.
√The formula to calculate the mid is:
   Mid = [(begin + end ) / 2 ]
√The efficiency of the binary search is O(log n).









Binary Search Tree
√The array structure provides a very efficient search algorithm, but its insertion and deletion algorithms are very inefficient.
√The binary search tree and AVL tree (chapter 3)provides a very efficient search and at the same time efficient insertion and deletion algorithm.

Basic Concepts
A binary search tree is a binary tree with the following properties:
√All items in the left subtree are less than the root.
√All items in the right subtree are greater than or equal to the root.
√Each subtree is itself a binary search tree.

Algorithms & Data Structures - Sorting

Objective:
At the end of the class you should be in a position to answer:
√Understand the basic concepts of internal and external sorts
√Discuss the relative efficiency of different sorts
√Recognize and discuss selection, insertion and exchange sorts
√Discuss the design and operation of external sorts
√Design and implement sequential searches
√Discuss the relative merits of different sequential searches
√Design and implement binary searches


Sort Concepts
√Sorts arrange data according to their value.
√Sorting algorithm are classified as either internal or external.



Insertion Sorts
In each pass of an insertion sort, one or more pieces of data are inserted into their correct location in an ordered list. In this section we study two insertion sorts: the straight insertion sort and the shell sort.



Explanation
In a straight insertion sort, the list at any moment is divided into sorted and unsorted sublists. In each pass the first element of the unsorted sublist is inserted into the sorted sublist.
If we have a list of n elements, it will take at most n-1 passes to sort the data.
The straight selection sort efficiency is O(n²)





Shell Sort
The shell sort algorithm named after its creator, Donald L.Shell.
It is an improved version of the straight insertion sort in which diminishing partitions are used to sort the data.
The Worst case running time of shell sort using shell’s increment is O(N²).









Selection Sort
In each pass of the selection sort, the smallest element is selected from the unsorted sublist and exchanged with the element at the beginning of the unsorted list.
The straight selection sort efficiency is O(n²)





Bubble Sort
Bubble sort is an exchange sort. The basic operation is the exchange of an adjacent pair of elements. So in the single bubble sort algorithm, the program will pass through the data, switching consecutive items which are out of order. After each pass through the list, the program checks to see if any switches were made. If there were, it passes through the list again, switching consecutive items which are still out of order. If no switches are made during an entire pass through the list, the data is sorted.

In the best case the efficiency of bubble sort is O(N).
In the worst case the efficiency of bubble sort is O(NM²)

Example of Bubble sort
Here is an example : we want to sort 390, 205, 182, 45, 235
Bubble sort for the first pass (exchange of an adjacent pairs)
390 205 182 45 235 (Switch 1)
205 390 182 45 235 (Switch 2)
205 182 390 45 235 (Switch 3)
205 182 45 390 235 (Switch 4)
205 182 45 235 390 ( First pass-sorted list)

the first pass moves the largest element (390) to the n^th position ,forming a sorted list of length one
the second pass only has to consider (n-1) elements and moves the second largest element to the (n-1) position.    

Quick Sort
Quick sort is an exchange sort in which a pivot key is placed in its correct position in the array while rearranging other elements widely dispersed across the list.
The efficiemcy of the Quick sort is :
Worst Case = O(N²) - the pivot is the smallest element
Average Case = O(N log n)
Best case = O(N log N) - the pivot is in the middle



Radix Sort
The bin sorting approach can be generalized in a technique that is known as radix sorting.
Assume that we have n integers in the range (0,n²) to be sorted. (For a bin sort, m = n², and we would have an O(n+m) = O(n²) algorithm.) Sort them in two phases:
1. Using n bins, place a_i into bin a_i mod n,
2. Repeat the process using n bins, placing a_i into bin floor(a_i/n), being careful to append to the end of each bin.
This results in a sorted list.

Example
Consider the list of integers
36 9 0 25 1 49 64 16 81 4
Step1: Arrange the element according to the least significant decimal digits








Step2:Arrange the elements according to the most significant digits












Step3: Sorted list is :
0 1 4 9 16 25 36 49 64 81


Merge Sort
The basic merging algorithm takes two input arrays A and B, an output array C, and three counters, Aptr, Bptr, and Cptr, which are initially set to the beginning of their respective arrays. The smaller of A[Aptr] and B[Bptr] is copied to the next entry in C, and the appropriate counters are advanced. When either input list is exhausted, the remainder of the order list is copied to C.

Example
If the array A (Aptr) contains 1, 13 and B (Bptr) contains 2, 15, 27, 38, then the algorithm proceeds as follows.


First, a comparison is done between 1 and 2.
1 is added to C, and then 13 and 2 are compared.



2 is added in C, and 13 and 15 are compared.


The remainder of the array B is then copied to C.

Algorithms & Data Structures - Queue

Definition

• Queue is an ordered collection of items.
• These items may be deleted at one end (called the HEAD of the queue) and inserted at other end (called the TAIL of the queue).
• Example, to withdraw money at ATM
• Also known as FIFO – first in first out

Array and linked list implementation



Operations of Queue

• Dequeue
• Enqueue
• QueueEmpty
• QueueFull

Enqueue

• Enqueue is the shortened version of "entering a queue".
• It refers to a situation where a new item is inserted to the queue.
• After a new insertion is made, the new item becomes the tail of the queue.

Dequeue

• Dequeue is a shortened version of "deleting from a queue".
• This is a situation where the data element at the head of the queue will be deleted.

Array implementation

• Using array to implement the queue
• Will create a problem when the queue is full – memory space are fixed.

Problem solution

• Create a circular queue. (using linked list)
• Circular queue wraps around to the beginning whenever the Head or the Tail reaches the end of the queue.

Linked list implementation
* Enqueue




Enqueue- Implementation
void Enqueue(QUEUENODEPTR *tailPtr, QUEUENODEPTR *headPtr, char Value)
{
QUEUENODEPTR newPtr;
newPtr = malloc(sizeof(LISTNODE)); //Create a new node
if (newPtr != NULL)
{
newPtr->data = Value;
newPtr->nextPtr = NULL;
(*tailPtr)->nextPtr = newPtr;
(*tailPtr) = (*tailPtr)->nextPtr;
if (*headPtr == NULL)
*headPtr = *tailPtr;
}


Dequeue - Implementation
char Dequeue(QUEUENODEPTR *headPtr)
{
char value;
QUEUENODEPTR tempPtr;
if (*headPtr != NULL)
{
tempPtr = *headPtr;
(*headPtr) = (*headPtr)->nextPtr;
value = tempPtr->data;
free(tempPtr);
return value;
{
else
printf(“Queue is empty”);
}


Application of queue

• Scheduling system
  • Advantages
• Support print spooling
• Information packet

Linked List Based Implementation of Stack and Queue

Why different implementations

• The way the data structure is implemented is a measure of its efficiency (time and space)
  
• It is important to see different alternatives
  
• So far we have discussed array based implementation (vector). What if we use second class arrays?
  

Objectives:
Discuss linked list based implementation of stack and queue.
Compare and contrast two implementations

Linked List based Stack

• Stack is LIFO data structure
  
  
  
  
  
  
  
  
  
• Linked list is a collection of nodes where each node has a data element and a pointer to the next element in the list.
  
  

Linked List based Stack- basic concepts

• Stack we push into and pop from the top of the stack.
  
• Therefore a special pointer “toOftheStack” which is pointing to the top of the stack is created.
  
• Intially toOftheStack is null.
  
• Try following operations
  
• push (a), push(b), push(c)
  
• pop()
  

Linked List based Stack- C++ Details
A Node: (figure 16.19)

struct ListNode
{
Object element;
ListNode *next;
ListNode ( const Object & theElement, ListNode * n = NULL ) : element( theElement ), next( n ) { }

};

Linked List based Stack- C++ Details
Template
template <class Object> class Stack {
public:
Stack( );
Stack( const Stack & rhs );
~Stack( ); bool isEmpty( ) const;
const Object & top( ) const;
void makeEmpty( );
void pop( );
void push( const Object & x );
Object topAndPop( );
const Stack & operator=( const Stack & rhs );

private:
struct ListNode { Object element; ListNode *next; ListNode( const Object & theElement, ListNode * n = NULL ) : element( theElement ), next( n ) { } };

ListNode *topOfStack; };

Linked List based Stack- C++ Details
Implementation
Stacklist.cpp
push, pop, top, makeEmpty and = operator

Linked List based Queue

• Queue if FIFO data structure
• Implementation is very similar to stack. Here, both from and back of the data structure need pointers.

Linked List based Queue- basic concepts

• Queue, enqueue into the front of the stack. Dequeue from the back of the stack
• Therefore two special pointers “front,” and “back,” are created.
• Initially both both front and back are null.
• Try following operations
• enqueue (a), enqueue(b), enqueue(c)
• dequeue()

Linked List based Queue - C++ Details
A Node:

struct ListNode {
Object element;
ListNode *next;
ListNode( const Object & theElement, ListNode * n = NULL ) : element( theElement ), next( n )
{ }
};

Linked List based Queue - C++ Details
Template
Queuelist.h
Notice that there are two pointers, front and back

Linked List based Queue - C++ Details
Implementation
Queuelist.cpp
Enqueue, dequeue, copy constructure and = operator

Array base vs. Linked list based Implementation

• For large size stacks and queue specially the size is not known linked list is better.
• For memory scare devices such as small handheld devices, linked list may perform better.

Algorithms & Data Structures - Linked List

Objectives
At the end of the class you should be able to answer:

Explain the design, use, and operation of a linear list

Implement a linear list using a linked list structure

Understand the operation of the linear list ADT

Write application programs using the linear list ADT

Design and implement different link-list structures

Basic Operations
The four basic list operations are :

1. Insertion
2. Deletion
3. Retrieval
4. Traversal

Insertion

• Insertion is used to add a new element to the list.
• List insertion can be ordered or random.
• Ordered list are maintained in sequence according to the data or, when available, a key that identifies the data.
• In random lists there is no sequential relationship between two elements.Random lists are sometimes called chronological lists.

Figure 5-1 Shows the insertion of data into a list



Deletion

• Deletion is used to remove an element from the list.
• Deletion from a list requires that the list be searched to locate the data being deleted
• Once located, the data are removed from the list.

Figure 5-2 Shows the Deletion operation


Retrieval

• Retrieval is used to get the information related to an element without changing the structure of the list.
• List retrieval requires that data be located in a list and presented to the calling module without changing the contents of the list.

Figure 5-3 Shows retrieving data from a list



Traversal

• List traversal processes each element in a list in sequence
• It requires a looping algorithm rather than a search.

Implementation

• Several data structures can be used to implement a list; we use a linked list.
• Linked list is a good structure for a list because data are easily inserted and deleted at the beginning, in the middle, or at the end of the list.

Data Structure
To implement a list, we need two different structures, a head node and data node.


Figure 5-5 Shows a head node and data node



Algorithm
Create List:
Create list allocate the head structure and initializes the metadata for the list.
Figure 5-6 shows the header before and after it is initialized by create list.


Figure 5-6 Create list



Algorithm for creating a list



Insert Node
Insert node adds data to a list. Given the predecessor, there are three steps to the insertion:
1. Allocate memory for the new node and move data to the node.
2. Point the new node to its successor.
3. Point the new node’s predecessor to the new node.


Figure 5-7 Add node to empty list



Insert at Beginning

• To insert a node at the beginning of the list, we simply point the new node to the first node of the list and then ser the head pointer to point to the new first node.
• Figure 5-8 shows inserting a node at the beginning

Figure 5-8 Shows Add node at Beginning



Insert in Middle

• To insert a node between two nodes, we point the new node to its successor and then point its predecessor to the new node.
  
• Figure 5-9 shows inserting a node in the middle.
  

Figure 5-9 Add node in Middle



Insert at End

• To add at the end of the list, we only need to point the predessor to the new node.
  
• The Figure5-10 insert the node at the end
  

Figure 5-10 Add node at End



Algorithm for Insertion is shown in figure 5-2



Delete Node

• The delete node algorithm logically removes a node from the list by changing various link pointers and then physically delete the node from dynamic memory.
  
• Figure 5-11 shows Deleting the first node
  

Delete First Node



Algorithm for Deleting a node


Retrieve Node
Figure 5-5 Shows retrieve list node algorithm








Advance Linked List

• Circular Linked List
  
• Circular linked list is a type of linked list where the last node will point back to the first node
  

Graphical view of a circular linked list