Thursday, January 7, 2016

Bin Sort

Assume that
  1. the keys of the items that we wish to sort lie in a small fixed range and
  2. that there is only one item with each value of the key.
Then we can sort with the following procedure:
  1. Set up an array of "bins" - one for each value of the key - in order,
  2. Examine each item and use the value of the key to place it in the appropriate bin.
Now our collection is sorted and it only took n operations, so this is an O(n) operation. However, note that it will only work under very restricted conditions.

Wednesday, January 6, 2016

UML Basics: Class Diagrams

The basics

The purpose of the class diagram is to show the types being modeled within the system. Its describes the static view of the system. In most UML models these types include:
  1. a class
  2. an interface
  3. a data type
  4. a component.

Class name

The UML representation of a class is a rectangle containing three compartments stacked vertically.We can see the figure 1.0 describes the three components.  The top compartment shows the class's name. The middle compartment lists the class's attributes. The bottom compartment lists the class's operations. When drawing a class element on a class diagram, you must use the top compartment, and the bottom two compartments are optional. (The bottom two would be unnecessary on a diagram depicting a higher level of detail in which the purpose is to show only the relationship between the classifiers.) 
Figure 1.0

Class attribute list

The attribute section of a class (the middle compartment) lists each of the class's attributes on a separate line. The attribute section is optional, but when used it contains each attribute of the class displayed in a list format. The line uses the following format:
name : attribute type
length: Double

Inheritance

A very important concept in object-oriented design, inheritance, refers to the ability of one class (child class) to inherit the identical functionality of another class (super class), and then add new functionality of its own. (In a very non-technical sense, imagine that I inherited my mother's general musical abilities, but in my family I'm the only one who plays electric guitar.) To model inheritance on a class diagram, a solid line is drawn from the child class (the class inheriting the behaviour) with a closed, unfilled arrowhead (or triangle) pointing to the super class. Consider types of bank accounts: 
Figure 2 shows how both CheckingAccount and SavingsAccount classes inherit from the BankAccount class.
Figure 2: Inheritance is indicated by a solid line with a closed, unfilled arrowhead pointing at the super class
Inheritance indicated by a solid line with a closed, unfilled arrowhead pointing at the super class
However, there is an alternative way to draw inheritance called tree notation. You can use tree notation when there are two or more child classes, as in Figure 2, except that the inheritance lines merge together like a tree branch. Figure 3 is a redrawing of the same inheritance shown in Figure 2, but this time using tree notation.
Figure 3: An example of inheritance using tree notation
Example of inheritance using tree notation

Abstract classes and operations

The observant reader will notice that the diagrams in Figures 2 and 3 use italicized text for the BankAccount class name and withdrawal operation. This indicates that the BankAccount class is an abstract class and the withdrawal method is an abstract operation. In other words, the BankAccount class provides the abstract operation signature of withdrawal and the two child classes of CheckingAccount and SavingsAccount each implement their own version of that operation.
However, super classes (parent classes) do not have to be abstract classes. It is normal for a standard class to be a super class.

Associations

When you model a system, certain objects will be related to each other, and these relationships themselves need to be modelled for clarity. There are five types of associations. I will discuss two of them — bi-directional and uni-directional associations .

Bi-directional (standard) association

An association is a linkage between two classes. Associations are always assumed to be bi-directional; this means that both classes are aware of each other and their relationship, unless you qualify the association as some other type. Going back to our Flight example, Figure 4 shows a standard kind of association between the Flight class and the Plane class.
Figure 4: An example of a bi-directional association between a Flight class and a Plane class
An example of a bi-directional association between a Flight class and a Plane class
A bi-directional association is indicated by a solid line between the two classes. At either end of the line, you place a role name and a multiplicity value. Figure 4 shows that the Flight is associated with a specific Plane, and the Flight class knows about this association. The Plane takes on the role of "assignedPlane" in this association because the role name next to the Plane class says so. The multiplicity value next to the Plane class of 0..1 means that when an instance of a Flight exists, it can either have one instance of a Plane associated with it or no Planes associated with it (i.e., maybe a plane has not yet been assigned). Figure 4 also shows that a Plane knows about its association with the Flight class. In this association, the Flight takes on the role of "assignedFlights"; the diagram in Figure 4 tells us that the Plane instance can be associated either with no flights (e.g., it's a brand new plane) or with up to an infinite number of flights (e.g., the plane has been in commission for the last five years).
For those wondering what the potential multiplicity values are for the ends of associations, Table 1 below lists some example multiplicity values along with their meanings.
Table 3: Multiplicity values and their indicators
Potential Multiplicity Values
IndicatorMeaning
0..1Zero or one
1One only
0..*Zero or more
*Zero or more
1..*One or more
3Three only
0..5Zero to Five
5..15Five to Fifteen

Uni-directional association

In a uni-directional association, two classes are related, but only one class knows that the relationship exists. Figure 5 shows an example of an overdrawn accounts report with a uni-directional association.
Figure 5: An example of a uni-directional association: The OverdrawnAccountsReport class knows about the BankAccount class, but the BankAccount class does not know about the association
An example of a uni-directional association
A uni-directional association is drawn as a solid line with an open arrowhead (not the closed arrowhead, or triangle, used to indicate inheritance) pointing to the known class. Like standard associations, the uni-directional association includes a role name and a multiplicity value, but unlike the standard bi-directional association, the uni-directional association only contains the role name and multiplicity value for the known class. In our example in Figure 5, the OverdrawnAccountsReport knows about the BankAccount class, and the BankAccount class plays the role of "overdrawnAccounts." However, unlike a standard association, the BankAccount class has no idea that it is associated with the OverdrawnAccountsReport. [Note: It may seem strange that the BankAccount class does not know about the OverdrawnAccountsReport class. This modeling allows report classes to know about the business class they report, but the business classes do not know they are being reported on. This loosens the coupling of the objects and therefore makes the system more adaptive to changes.]

Aggregation

Aggregation is a special type of association used to model a " whole to its parts" relationship. In basic aggregation relationships, the life cycle of a part class is independent from the whole class's lifecycle.
For example, we can think of Car as a whole entity and Car Wheel as part of the overall Car. The wheel can be created weeks ahead of time, and it can sit in a warehouse before being placed on a car during assembly. In this example, the Wheel class's instance clearly lives independently of the Car class's instance. However, there are times when the part class's lifecycle is not independent from that of the whole class — this is called composition aggregation. Consider, for example, the relationship of a company to its departments. Both Company and Departments are modeled as classes, and a department cannot exist before a company exists. Here the Department class's instance is dependent upon the existence of the Company class's instance.
Let's explore basic aggregation and composition aggregation further.
Basic aggregation
An association with an aggregation relationship indicates that one class is a part of another class. In an aggregation relationship, the child class instance can outlive its parent class. To represent an aggregation relationship, you draw a solid line from the parent class to the part class, and draw an unfilled diamond shape on the parent class's association end. Figure 6 shows an example of an aggregation relationship between a Car and a Wheel.
Figure 6: Example of an aggregation association
Example of an aggregation association
Composition aggregation
The composition aggregation relationship is just another form of the aggregation relationship, but the child class's instance lifecycle is dependent on the parent class's instance lifecycle. In Figure 7, which shows a composition relationship between a Company class and a Department class, notice that the composition relationship is drawn like the aggregation relationship, but this time the diamond shape is filled.
Figure 7: Example of a composition relationship
Example of a composition relationship
In the relationship modeled in Figure 7, a Company class instance will always have at least one Department class instance. Because the relationship is a composition relationship, when the Company instance is removed/destroyed, the Department instance is automatically removed/destroyed as well. Another important feature of composition aggregation is that the part class can only be related to one instance of the parent class (e.g. the Company class in our example).

Reflexive associations

We have now discussed all the association types. As you may have noticed, all our examples have shown a relationship between two different classes. However, a class can also be associated with itself, using a reflexive association. This may not make sense at first, but remember that classes are abstractions. Figure 8 shows how an Employee class could be related to itself through the manager/manages role. When a class is associated to itself, this does not mean that a class's instance is related to itself, but that an instance of the class is related to another instance of the class.
Figure 8: Example of a reflexive association relationship
Example of a reflexive association relationship
The relationship drawn in Figure 8 means that an instance of Employee can be the manager of another Employee instance. However, because the relationship role of "manages" has a multiplicity of 0..*; an Employee might not have any other Employees to manage.

Visibility

In object-oriented design, there is a notation of visibility for attributes and operations. UML identifies four types of visibility: public, protected, private, and package.
The UML specification does not require attributes and operations visibility to be displayed on the class diagram, but it does require that it be defined for each attribute or operation. To display visibility on the class diagram, you place the visibility mark in front of the attribute's or operation's name. Though UML specifies four visibility types, an actual programming language may add additional visibilities, or it may not support the UML-defined visibilities. Table 2 displays the different marks for the UML-supported visibility types.
Table 2: Marks for UML-supported visibility types
MarkVisibility type
+Public
#Protected
-Private
~Package
Now, let's look at a class that shows the visibility types indicated for its attributes and operations. In Figure 9, all the attributes and operations are public, with the exception of the updateBalance operation. The updateBalance operation is protected.
Figure 9: A BankAccount class that shows the visibility of its attributes and operations
A BankAccount class showing visibility of attributes and operations

Interfaces
An interface is a specification of behavior that implementers agree to meet; it is a contract. By realizing an interface, classes are guaranteed to support a required behavior, which allows the system to treat non-related elements in the same way – that is, through the common interface.
Interfaces may be drawn in a similar style to a class, with operations specified, as shown below. They may also be drawn as a circle with no explicit operations detailed. When drawn as a circle, realization links to the circle form of notation are drawn without target arrows.

Tuesday, January 5, 2016

UML basics: Use Case Diagrams

use case diagrams overview the usage requirements for a system. They are useful for presentations to management and/or project stakeholders, but for actual development you will find that use cases provide significantly more value because they describe "the meat" of the actual requirements. 


Use case diagrams depict:
  • Use cases. A use case describes a sequence of actions that provide something of measurable value to an actor and is drawn as a horizontal ellipse.

  • Actors. An actor is a person, organization, or external system that plays a role in one or more interactions with your system. Actors are drawn as stick figures.

UML basics: The sequence diagram

The diagram's purpose

The sequence diagram is used primarily to show the interactions between objects in the sequential order that those interactions occur. Much like the class diagram, developers typically think sequence diagrams were meant exclusively for them. However, an organization's business staff can find sequence diagrams useful to communicate how the business currently works by showing how various business objects interact. Besides documenting an organization's current affairs, a business-level sequence diagram can be used as a requirements document to communicate requirements for a future system implementation. During the requirements phase of a project, analysts can take use cases to the next level by providing a more formal level of refinement. When that occurs, use cases are often refined into one or more sequence diagrams.
An organization's technical staff can find sequence diagrams useful in documenting how a future system should behave. During the design phase, architects and developers can use the diagram to force out the system's object interactions, thus fleshing out overall system design.

Solve the given equations using Stack(Post fix Notation)

Steps:
1. Read the equation as a string.
2.first pop two operand from the equation
3.If the third character is an operator we do the calculate the value for that operator and the operands.
4.Then push the calculated value in to the stack.
5.finally print the final value.


Implementation


Decimal to binary Representaion using stack

Steps;

1.Read the decimal number.
2.Divide the decimal number until get zero
3.Find the remainder from rem= dec%2.
4.Push the remainder values int to the stack
6.Then pop the values from the stack until the stack become empty.


Implementation



Friday, January 1, 2016

Selection Sort

Selection Sort


Selection sort is among the simplest of sorting techniques and it work very well for small files. Furthermore, despite its evident "naïve approach "Selection sort has a quite important application because each item is actually moved at most once, Section sort is a method of choice for sorting files with very large objects (records) and small keys. Algorithm 

Selection Sort(int []A)


1. for i=0 to n

2.         k=i
3.                for j=i+1 to n 
4.                    if(A[j]<A[i])
5.                        k=j
6.                    end if
7.                end for
8.            swap A[i,k]
9.  end for 





The worst case occurs if the array is already sorted in descending order. Nonetheless, the time require by selection sort algorithm is not very sensitive to the original order of the array to be sorted: the test "if A[j] < min x" is executed exactly the same number of times in every case. The variation in time is only due to the number of times the "then" part (i.e., min jj; min xA[j] of this test are executed.
The Selection sort spends most of its time trying to find the minimum element in the "unsorted" part of the array. It clearly shows the similarity between Selection sort and Bubble sort. Bubble sort "selects" the maximum remaining elements at each stage, but wastes some effort imparting some order to "unsorted" part of the array. Selection sort is quadratic in both the worst and the average case, and requires no extra memory.

For each i from 1 to n - 1, there is one exchange and n - i comparisons, so there is a total of n -1 exchanges and (n -1) + (n -2) + . . . + 2 + 1 = n(n -1)/2 comparisons. These observations hold no matter what the input data is. In the worst case, this could be quadratic, but in the average case, this quantity is O(n log n). It implies that the running time of Selection sort is quite insensitive to the input.


Implementation

 
output is:
 

       




Parenthesis Matching using stack



Problem is given a string of parenthesis ‘(‘ and ‘)’ ,'{' and '}' , '[' and ']'  find out if there are matching pairs or not, typically this known as parenthesis matching problem.

For example : ‘((()))’ input will return TRUE, but ‘)(())’ will return FALSE.



 

© 2013 CSC. All rights resevered. Designed by Templateism

Back To Top