Rachelle Lopez and Diomlael Gunting

1. The purpose of packages is to organize use case diagrams and class diagrams, although the use of package diagrams is not limited to these UML elements.

2.A component diagram in the Unified Modeling Language, depicts how components are wired together to form larger components and or software systems while the Class diagram is a type of static structure diagram that describes the structure of a system by showing the system's classes, their attributes, and the relationships between the classes.

3. A deployment diagram in the Unified Modeling Language serves to model the physical deployment of artifacts on deployment targets.Deployment diagrams show "the allocation of Artifacts to Nodes according to the Deployments defined between them."Deployment of an artifact to a node is indicated by placing the artifact inside the node.Instances of nodes (and devices and execution environments) are used in deployment diagrams to indicate multiplicity of these nodes. For example, multiple instances of an application server execution environment may be deployed inside a single device node to represent application server clustering.

4. A.) Defining the use case model.

• Find the actors domain problem by reviewing the reviewing the system requirements & interviewing some business experts.
• identify major events initiated by the actors.
• Develop a use case diagrams
• Review the usu case scenarios.

B.) UML diagramming system analysis phase.

• Derive activity from use case diagrams.
• Develop sequence and collaboration diagram from scenarios.
• Review the sequence diagram with the businesses area..

C.) Develop the class diagrams.

• Look for noun in use cases.
• Define the major relationships between the classes.
• “Has a” and “is a” relationships between class.
• Examine use case and sequence diagrams to determine the class.
• Create class diagrams that show the classes and relationships that exist in the use case.

D.) Draw state chart diagrams.

• Develop state chart diagrams to aid in understanding complex process.
• Determine method by examining state chart diagrams, Derive state, Attributes of the class are public (accessible externally), Private – internal to the class.
.

E.) Begin systems design by refining UML diagrams

• Write class specifications.
• Develop methods specifications of input and output requirements for the method.
• Create set of sequence diagrams.
• Create class diagrams using specialized class symbols.
• Analyze the class diagrams derived system components.



5. UML is important for modeling because it can greatly improve the quality of your systems analysis and designs.

Shell Sort

Shell sort is a sorting algorithm that is a generalization of insertion sort, with two observations:
insertion sort is efficient if the input is "almost sorted", and insertion sort is typically inefficient because it moves values just one position at a time.Shellsort is one of the oldest sorting algorithms, named after its inventor D.L. Shell (1959) [She 59]. It is fast, easy to understand and easy to implement. However, its complexity analysis is a little more 

Reference:http://en.wikipedia.org/wiki/Shell_sort

http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm

Insertion Sort

Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:
simple implementation
efficient for (quite) small data sets
efficient for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions
more efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort: the average running time is n2/4, and the running time is linear in the best case
stable (i.e., does not change the relative order of elements with equal keys)
in-place (i.e., only requires a constant amount O(1) of additional memory space)
online (i.e., can sort a list as it receives it)

Most humans when sorting—ordering a deck of cards, for example—use a method that is similar to insertion sort.

http://en.wikipedia.org/wiki/Heapsort

Bucket Sort

Bucket sort, or bin sort, is a sorting algorithm that works by partitioning an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a cousin of radix sort in the most to least significant digit flavour. Bucket sort is a generalization of pigeonhole sort. Since bucket sort is not a comparison sort, the Ω(n log n) lower bound is inapplicable. The computational complexity estimates involve the number of buckets.

Bucket sort works as follows:
Set up an array of initially empty "buckets."
Scatter: Go over the original array, putting each object in its bucket.
Sort each non-empty bucket.
Gather: Visit the buckets in order and put all elements back into the original array.

A common optimization is to put the elements back in the original array first, then run insertion sort over the complete array; because insertion sort's runtime is based on how far each element is from its final position, the number of comparisons remains relatively small, and the memory hierarchy is better exploited by storing the list contiguously in memory.[1]

The most common variant of bucket sort operates on a list of n numeric inputs between zero and some maximum value M and divides the value range into n buckets each of size M/n. If each bucket is sorted using insertion sort, the sort can be shown to run in expected linear time (where the average is taken over all possible inputs).[2] However, the performance of this sort degrades with clustering; if many values occur close together, they will all fall into a single bucket and be sorted slowly.

Another variant of bucket sort known as histogram sort adds an initial pass that counts the number of elements that will fall into each bucket using a count array. Using this information, the array values can be arranged into a sequence of buckets in-place by a sequence of exchanges, so that there is no space overhead for bucket storage.

Implementation:

Reference:http://en.wikipedia.org/wiki/Bucket_sort

Quick Sort

Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, makes Θ(nlogn) (big O notation) comparisons to sort n items. However, in the worst case, it makes Θ(n2) comparisons. Typically, quicksort is significantly faster in practice than other Θ(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data, it is possible to make design choices which minimize the probability of requiring quadratic time.Quicksort is a comparison sort and, in efficient implementations, is not a stable sort.

Analysis:

From the initial description it's not obvious that quicksort takes Θ(nlogn) time on average. It's not hard to see that the partition operation, which simply loops over the elements of the array once, uses Θ(n) time. In versions that perform concatenation, this operation is also Θ(n).

In the best case, each time we perform a partition we divide the list into two nearly equal pieces. This means each recursive call processes a list of half the size. Consequently, we can make only logn nested calls before we reach a list of size 1. This means that the depth of the call tree is Θ(logn). But no two calls at the same level of the call tree process the same part of the original list; thus, each level of calls needs only Θ(n) time all together (each call has some constant overhead, but since there are only Θ(n) calls at each level, this is subsumed in the Θ(n) factor). The result is that the algorithm uses only Θ(nlogn) time.

An alternate approach is to set up a recurrence relation for the T(n) factor, the time needed to sort a list of size n. Because a single quicksort call involves Θ(n) factor work plus two recursive calls on lists of size n / 2 in the best case, the relation would be:


The master theorem tells us that T(n) = Θ(nlogn).

In fact, it's not necessary to divide the list this precisely; even if each pivot splits the elements with 99% on one side and 1% on the other (or any other fixed fraction), the call depth is still limited to 100logn, so the total running time is still Θ(nlogn).

In the worst case, however, the two sublists have size 1 and n − 1 (for example, if the array consists of the same element by value), and the call tree becomes a linear chain of n nested calls. The ith call does Θ(n − i) work, and . The recurrence relation is:
T(n) = Θ(n) + T(0) + T(n − 1) = O(n) + T(n − 1)

This is the same relation as for insertion sort and selection sort, and it solves to T(n) = Θ(n2). Given knowledge of which comparisons are performed by the sort, there are adaptive algorithms that are effective at generating worst-case input for quicksort on-the-fly, regardless of the pivot selection strategy.[4]

Sample code:

Bubble Sort

definition:

Bubble sort -is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing two items at a time and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort.Bubble sort is a simple and well-known sorting algorithm. It is used in practice once in a blue moon and its main application is to make an introduction to the sorting algorithms. Bubble sort belongs to O(n2) sorting algorithms, which makes it quite inefficient for sorting large data volumes. Bubble sort is stable and adaptive.

Analysis:

Performance

Bubble sort has worst-case and average complexity both О(n²), where n is the number of items being sorted. There exist many sorting algorithms with the substantially better worst-case or average complexity of O(n log n). Even other О(n²) sorting algorithms, such as insertion sort, tend to have better performance than bubble sort. Therefore bubble sort is not a practical sorting algorithm when n is large.

[edit]
Rabbits and turtles

The positions of the elements in bubble sort will play a large part in determining its performance. Large elements at the beginning of the list do not pose a problem, as they are quickly swapped. Small elements towards the end, however, move to the beginning extremely slowly. This has led to these types of elements being named rabbits and turtles, respectively.

Various efforts have been made to eliminate turtles to improve upon the speed of bubble sort. Cocktail sort does pretty well, but it still retains O(n2) worst-case complexity. Comb sort compares elements large gaps apart and can move turtles extremely quickly, before proceeding to smaller and smaller gaps to smooth out the list. Its average speed is comparable to faster algorithms like Quicksort.

Sample code:

public void bubbleSort(int[] arr) { 

  boolean swapped = true; 

  int j = 0; 

  int tmp; 

  while (swapped) { 

  swapped = false; 

  j++; 

  for (int i = 0; i < arr.length - j; i++) {  

  if (arr[i] > arr[i + 1]) {  

  tmp = arr[i]; 

  arr[i] = arr[i + 1]; 

  arr[i + 1] = tmp; 

  swapped = true; 

  } 

  }  

  } 

}

Reference: http://en.wikipedia.org/wiki/Bubble_sort

                http://simpleprogrammingtutorials.com/tutorials/sorts/bubble-sort.php

Queue Implementation

class Link {
public int iData;
public Link next;
public Link(int id) {
iData = id;
}

public String toString() {
return "{" + iData + "} ";
}
}

class LinkList {
private Link first;

public LinkList() {
first = null;
}

public boolean isEmpty() {
return (first == null);
}

public void insertFirst(int dd) {
Link newLink = new Link(dd);
newLink.next = first;
first = newLink;
}

public int deleteFirst() {
Link temp = first;
first = first.next;
return temp.iData;
}

public String toString() {
String str = "";
Link current = first;
while (current != null) {
str += current.toString();
current = current.next;
}
return str;
}
}

class FirstLastList {
private Link first;

private Link last;

public FirstLastList() {
first = null;
last = null;
}

public boolean isEmpty() {
return first == null;
}

public void insertFirst(int dd) {
Link newLink = new Link(dd);
if (isEmpty())
last = newLink;
newLink.next = first;
first = newLink;
}

public void insertLast(int dd) {
Link newLink = new Link(dd);

if (isEmpty())
first = newLink;
else
last.next = newLink;
last = newLink;
}

public int deleteFirst() {
int temp = first.iData;
if (first.next == null)
last = null;
first = first.next;
return temp;
}

public String toString() {
String str = "";
Link current = first;
while (current != null) {
str += current.toString();
current = current.next;
}
return str;
}
}

class LinkQueue {
private FirstLastList theList;

public LinkQueue() {
theList = new FirstLastList();
}

public boolean isEmpty() {
return theList.isEmpty();
}

public void insert(int j) {
theList.insertLast(j);
}

public double remove() {
return theList.deleteFirst();
}

public String toString() {
return theList.toString();
}
}

public class MainClass {
public static void main(String[] args) {
LinkQueue theQueue = new LinkQueue();
theQueue.insert(20);
theQueue.insert(40);
System.out.println(theQueue);

theQueue.insert(60);
theQueue.insert(80);

System.out.println(theQueue);

theQueue.remove();
theQueue.remove();

System.out.println(theQueue);
}
}


Reference:http:www.java2s.com/Tutorial/Java/0140_Collections/AQueueImplementedbyaLinkedList.html