Group members

DRAGONSMATH GROUP MEMBERS



SAIFUL BAHRY BIN M.HISSHAM (TBA10027273)

RAJA ABDUL SYUKOR BIN RAJA ABDULLAH (TBA10027160)

FARIZHUL HAIQAL (TBA10027969)

MOHD. ZULHAFIZ

Read more »

Answer question 3

Answer for question 3


no of vertices : 8
no of edges : 7
total weight : = 0.5 + 0.6 + 0.7 + 0.8 + 0.9 + 0.9 + 1.3
= 6

Read more »

answer question 2

Answer for Question 2


no of vertices : 7
no of edges : 6
total weight : = 1 + 1 + 2 + 3 + 4 + 5
= 16




Reason for the name of minimum spanning-tree is because it minimize the total cost of providing highspeed communicatons between every pairs. In order to get the lowest cost we choose the minimum cost among the pairs. The lowest cost is 1 million dollars which connected between C with D and E with F. Since there is no more lines have the values of 1 milion dollar we take the second lowest value which is 2 million dollars which connect between A and B. The next one we take the cost of 3 million dollars which connect between C with F. Then we take the cost of 4 million dollars which connect between A with B but we do no take between C with E since it will form a cycle. There are onlu edges needed, so the last edges is the line that cost the lowest value among the cost that have not being choose which is 5 million dollars which connect between E with G.When all the cost of the cost being sum, the summation is 16 million dollars which is the minimum cost that can be get from the graph.

Read more »

answer question 1

Answer for question 1

Tree

In telecommunication networks, a tree network is a combination of two or more star networks connected together. Each star network is a local area network (LAN) in which there is a central computer or server to which all the workstation nodes are directly linked. The central computers of the star networks are connected to a main cable called the bus. Thus, a tree network is a bus network of star networks.

The illustration shows a tree network with five star networks connected to a common bus. The workstations are shown as small spheres, the central computers of the star networks are shown as larger spheres, connections within star networks are shown as short lines, and the bus is shown as a long, heavy line. The connections can consist of wire cables, optical fiber cables, or wireless links.


Spanning Tree

Spanning trees are a standard technique used in local area network (LAN) switching. Spanning tree algorithms were developed to prevent redundant transmission of data along intermediate hops between a source and destination host on a mesh network topology. Without spanning trees, a mesh network can be flooded and rendered unusable by messages circulating in an infinite loop between hosts.
The primary Spanning Tree Protocol (STP) is IEEE standard 802.1D, an algorithm commonly used on Ethernet networks. This algorithm works by limiting the paths messages can travel at any given time to a fully connected tree rather than a mesh. As hosts join and leave the network, this protocol dynamically updates the tree accordingly.


Minimum spanning tree

minimum spanning tree (MST) or minimum weight spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree. More generally, any undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of minimum spanning trees for its connected components.
One example would be a cable TV company laying cable to a new neighborhood. If it is constrained to bury the cable only along certain paths, then there would be a graph representing which points are connected by those paths. Some of those paths might be more expensive, because they are longer, or require the cable to be buried deeper; these paths would be represented by edges with larger weights. A spanning tree for that graph would be a subset of those paths that has no cycles but still connects to every house. There might be several spanning trees possible. A minimum spanning tree would be one with the lowest total cost.


Minimum spanning tree objectives

• They can be computed quickly and easily, and they create a sparse subgraph that reflects a lot about the original graph.
• They provide a way to identify clusters in sets of points. Deleting the long edges from a minimum spanning tree leaves connected components that define natural clusters in the data set, as shown in the output figure above.
• They can be used to give approximate solutions to hard problems such as Steiner tree and traveling salesman.
• As an educational tool, minimum spanning tree algorithms provide graphic evidence that greedy algorithms can give provably optimal solutions.



Method to solve minimum spanning tree

there are 4 method to solve minimum spanning tree...

Kruskal's algorithm

We'll start with Kruskal's algorithm, which is easiest to understand and probably the best one for solving problems by hand.
Kruskal's algorithm:
sort the edges of G in increasing order by length
keep a subgraph S of G, initially empty
for each edge e in sorted order
if the endpoints of e are disconnected in S
add e to S
return S
Note that, whenever you add an edge (u,v), it's always the smallest connecting the part of S reachable from u with the rest of G, so by the lemma it must be part of the MST.
This algorithm is known as a greedy algorithm, because it chooses at each step the cheapest edge to add to S. You should be very careful when trying to use greedy algorithms to solve other problems, since it usually doesn't work. E.g. if you want to find a shortest path from a to b, it might be a bad idea to keep taking the shortest edges. The greedy idea only works in Kruskal's algorithm because of the key property we proved.
Analysis: The line testing whether two endpoints are disconnected looks like it should be slow (linear time per iteration, or O(mn) total). But actually there are some complicated data structures that let us perform each test in close to constant time; this is known as the union-find problem and is discussed in Baase section 8.5 (I won't get to it in this class, though). The slowest part turns out to be the sorting step, which takes O(m log n) time.

Prim's algorithm

Rather than build a subgraph one edge at a time, Prim's algorithm builds a tree one vertex at a time.
Prim's algorithm:
let T be a single vertex x
while (T has fewer than n vertices)
{
find the smallest edge connecting T to G-T
add it to T
}
Since each edge added is the smallest connecting T to G-T, the lemma we proved shows that we only add edges that should be part of the MST.
Again, it looks like the loop has a slow step in it. But again, some data structures can be used to speed this up. The idea is to use a heap to remember, for each vertex, the smallest edge connecting T with that vertex.
Prim with heaps:
make a heap of values (vertex,edge,weight(edge))
initially (v,-,infinity) for each vertex
let tree T be empty
while (T has fewer than n vertices)
{
let (v,e,weight(e)) have the smallest weight in the heap
remove (v,e,weight(e)) from the heap
add v and e to T
for each edge f=(u,v)
if u is not already in T
find value (u,g,weight(g)) in heap
if weight(f) < weight(g) replace (u,g,weight(g)) with (u,f,weight(f)) } Analysis: We perform n steps in which we remove the smallest element in the heap, and at most 2m steps in which we examine an edge f=(u,v). For each of those steps, we might replace a value on the heap, reducing it's weight. (You also have to find the right value on the heap, but that can be done easily enough by keeping a pointer from the vertices to the corresponding values.) I haven't described how to reduce the weight of an element of a binary heap, but it's easy to do in O(log n) time. Alternately by using a more complicated data structure known as a Fibonacci heap, you can reduce the weight of an element in constant time. The result is a total time bound of O(m + n log n).

Boruvka's algorithm

(Actually Boruvka should be spelled with a small raised circle accent over the "u".) Although this seems a little complicated to explain, it's probably the easiest one for computer implementation since it doesn't require any complicated data structures. The idea is to do steps like Prim's algorithm, in parallel all over the graph at the same time.
Boruvka's algorithm:
make a list L of n trees, each a single vertex
while (L has more than one tree)
for each T in L, find the smallest edge connecting T to G-T
add all those edges to the MST
(causing pairs of trees in L to merge)
As we saw in Prim's algorithm, each edge you add must be part of the MST, so it must be ok to add them all at once.
Analysis: This is similar to merge sort. Each pass reduces the number of trees by a factor of two, so there are O(log n) passes. Each pass takes time O(m) (first figure out which tree each vertex is in, then for each edge test whether it connects two trees and is better than the ones seen before for the trees on either endpoint) so the total is O(m log n).

A hybrid algorithm


This isn't really a separate algorithm, but you can combine two of the classical algorithms and do better than either one alone. The idea is to do O(log log n) passes of Boruvka's algorithm, then switch to Prim's algorithm. Prim's algorithm then builds one large tree by connecting it with the small trees in the list L built by Boruvka's algorithm, keeping a heap which stores, for each tree in L, the best edge that can be used to connect it to the large tree. Alternately, you can think of collapsing the trees found by Boruvka's algorithm into "supervertices" and running Prim's algorithm on the resulting smaller graph. The point is that this reduces the number of remove min operations in the heap used by Prim's algorithm, to equal the number of trees left in L after Boruvka's algorithm, which is O(n / log n).



Applications of Minimum Spanning Tree Problem


Network design.

– telephone, electrical, hydraulic, TV cable, computer, road
The standard application is to a problem like phone network design. You have a business with several offices; you want to lease phone lines to connect them up with each other; and the phone company charges different amounts of money to connect different pairs of cities. You want a set of lines that connects all your offices with a minimum total cost. It should be a spanning tree, since if a network isn’t a tree you can always remove some edges and save money.

Approximation algorithms for NP-hard problems.

– traveling salesperson problem, Steiner tree
A less obvious application is that the minimum spanning tree can be used to approximately solve the traveling salesman problem. A convenient formal way of defining this problem is to find the shortest path that visits each point at least once.
Note that if you have a path visiting all points exactly once, it’s a special kind of tree. For instance in the example above, twelve of sixteen spanning trees are actually paths. If you have a path visiting some vertices more than once, you can always drop some edges to get a tree. So in general the MST weight is less than the TSP weight, because it’s a minimization over a strictly larger set.
On the other hand, if you draw a path tracing around the minimum spanning tree, you trace each edge twice and visit all points, so the TSP weight is less than twice the MST weight. Therefore this tour is within a factor of two of optimal.

Indirect applications.

– max bottleneck paths
– LDPC codes for error correction
– image registration with Renyi entropy
– learning salient features for real-time face verification
– reducing data storage in sequencing amino acids in a protein
– model locality of particle interactions in turbulent fluid flows
– autoconfig protocol for Ethernet bridging to avoid cycles in a network

Cluster analysis

k clustering problem can be viewed as finding an MST and deleting the k-1 most
expensive edges. See this for more details.

no of vertice : 7
no of edges : 6
total weight : = 1 + 1 + 2 + 4 + 4 + 6
= 18

Read more »

question

QUESTION 1

1. In the terminology of network theory, what is a tree? A spanning tree? A minimum spanning tree?
2. What is an easiest way to recognize a spanning tree?
3. What is the objective of an minimum spanning tree problem?
4. How many methods will solve a minimum spanning tree problem?
5. What are a few types of applications of minimum spanning tree problems?
6. Use a Kruskal’s algorithm to find a minimum spanning tree for a network with the following nodes.

QUESTION 2

The Modern Corp. Problem
Management of the modern corp. has decided to have a state-of-the-art fiber-optic network install to provide high-speed communications (data, voice, and video) between its major centers.
The nodes in figure 1 show the geographical layout of the corporation’s major centers which include corporate headquarters, s supercomputer facility, and a research park, as well as production and distribution centers. The dashed lines are the potential locations of fiber-optic cables. The number next to each dashed line give the cost (in millions of dollars) if that particular cable is chosen as one to be installed.
Determine which cable should be installed to minimize the total cost of providing high-speed communications between every pair of centers?
Explain the reason for the name of minimum spanning tree.

QUESTION 3
The Wirehouse Lumber Company will soon begin logging eight groves of trees in the same general area. Therefore, it must develop a system of dirt road that makes each grove accessible from every other grove. The distance (in miles) between every pair of groves is as follows:

Management now wants to determine between which pairs of groves the roads should be constructed to connect all groves with a minimum total length of road.
a. Describe how this problem fits the network description of a minimum spanning tree problem.
b. Use the suitable algorithm to solve the problem.

Read more »

set

Introduction to Discrete Mathematics Set Theory
In discrete mathematics, the set theory are the branch of mathematics that learned about the sets, which are the collections of objects. Even though any type of objects can be collected into a set, set theory is applied most often to objects that are related to mathematics. Now we will see the examples of discrete mathematics set theory.


The natural numbers
The 'counting' numbers (or whole numbers) starting at 1, are called the natural numbers. This set is sometimes denoted by N. So N = {1, 2, 3, ...}

Integers
All whole numbers, positive, negative and zero form the set of integers. It is sometimes denoted by Z. So Z = {..., -3, -2, -1, 0, 1, 2, 3, ...}

Real numbers
If we expand the set of integers to include all decimal numbers, we form the set of real numbers. The set of reals is sometimes denoted by R.
e.g. 8.127127127...

Rational numbers
Those real numbers whose decimal digits are finite in number, or which recur, are called rational numbers. The set of rationals is sometimes denoted by the letter Q.
For example: 0.5, -17, 2/17, 82.01, 3.282828..

Irrational numbers
If a number can't be represented exactly by a fraction p/q, it is said to be irrational.

•  Examples include: √2, √3, π.

Universal Set
The set of all the 'things' currently under discussion is called the universal set (or sometimes, simply the universe). It is denoted by U.

Empty set
The set containing no elements at all is called the null set, or empty set. It is denoted by a pair of empty braces: {} or by the symbol .

Equality
Two sets A and B are said to be equal if and only if they have exactly the same elements. In this case, we simply write:
A = B

Subsets
If all the elements of a set A are also elements of a set B, then we say that A is a subset of B, and we write:
A ⊆ B

Disjoint
Two sets are said to be disjoint if they have no elements in common. For example:

• If A = {even numbers} and B = {1, 3, 5, 11, 19}, then A and B are disjoint.

Intersection
Region iii, where the two loops overlap (the region corresponding to 'Y' followed by 'Y'), is called the intersection of the sets A and B. It is denoted by A ∩ B. So we can define intersection as follows:

• The intersection of two sets A and B, written A ∩ B, is the set of elements that are in A and in B.

(Note that in symbolic logic, a similar symbol, , is used to connect two logical propositions with the AND operator.)

Union
In a similar way we can define the union of two sets as follows:

•       The union of two sets A and B, written A ∪ B, is the set of elements that are in A or in B (or both).

The union, then, is represented by regions ii, iii and iv in Fig. 7.
(Again, in logic a similar symbol, , is used to connect two propositions with the OR operator.)

Difference

•       The difference of two sets A and B (also known as the set-theoretic difference of A and B, or the  relative complement of B in A) is the set of elements that are in A but not inB.

This is written A - B, or sometimes A \ B.

Complement
So far, we have considered operations in which two sets combine to form a third: binary operations. Now we look at a unary operation - one that involves just one set.

• The set of elements that are not in a set A is called the complement of A. It is written A′ (or sometimes AC, or ).

Cardinality

• Finally, in this section on Set Operations we look at an operation on a set that yields not another set, but an integer.

The cardinality of a finite set A, written | A | (sometimes #(A) or n(A)), is the number of (distinct) elements in A. So, for example:
If A = {lower case letters of the alphabet}, | A | = 26.

A∪B

A∩B

 
A –B

Read more »

Logic

Definition:The study of principles of valids using rules of operate on a statement or several statements to reach a correct solution.

Truth Value;
Definition:Any sentence or statements which can be either true or false but not both. That sentence can be assigned the truth value, true ( T or 1) or False (F or 0).

Proposition
A declarative sentence that is either true or
false, but not both.
Examples:
• CS19 is a required course for the CS major.
• Tolkien wrote The Lord of the Rings.
• Pigs can fly.
Non-examples:
• What a beautiful evening!
• Do your homework.
Compound Proposition
One that can be broken down into more
primitive propositions.
E.g.,
• If it is sunny outside then I walk to work; otherwise
I drive, and if it is raining then I carry my umbrella.
This consists of several primitive propositions:
t = “I carry my umbrella”
r = “I drive” s = “It is raining”
p = “It is sunny outside” q = “I walk to work”
Connectives: “if… then”, “otherwise”, “and”

Compound Proposition
If it is sunny outside then I walk to work; otherwise I
drive, and if it is raining then I carry my umbrella.

p = “It is sunny outside” q = “I walk to work”
r = “I drive” s = “It is raining”
t = “I carry my umbrella”

If p then q; otherwise r and if s then t.
If p then q and (if not p then (r and (if s then t))).
p implies q and ((not p) implies (r and (s implies t))).


Logical Connectives
Used to form compound propositions from
primitive ones.

There are different types of compound statements which can be formed by using NOT, OR , AND etc. Let us discuss one by one in detail.


Negation
If p is any statement, then the statement “not p” is called the negation of p denoted by "~p".
~p is true, when p is false and ~p is false, when p is true.









Conjunctions
If p and q are two statements, then the compound statement “p and q”, is called the conjunction
denoted by “p q”. p q is true when both p and q are true.
The truth table for p q:











Disjunctions
If p and q are two statements, then the compound statement “p or q” is called the disjunction, denoted
by "p v q", p v q is false when both p and q are false.
The truth table for p v q is given below:










Conditional statement
If p and q are two statements, then the compound statement "If p then q" is called the conditional
statement denoted "p q". p q is false when p is true and q is false.









Note:
(i) In p q, p is called the antecedent and q is called the consequent.
(ii) q p is called the converse of p q
(iii) ~p ~q is called the inverse of p q
(iv) ~q ~p is called the contrapositive of p q




Biconditional statement
If p and q are two statements then the compound statement “p if and only if q”, is called the biconditional
statement denoted by “p q”. “p q” is true when both p and q are
true or when both p and q are false.










Note:
Suppose a compound proposition is given, we first split it into simple propositions containing a single
connective. Using the rules discussed above, we construct the truth table in the form of columns and
the last column gives the truth value of the given proposition for different combinations of the truth
values of its components.
Tautology
A compound statement is said to be a tautology, if it is always true for all possible combinations of the truth values of its components.
A tautology is also called a theorem or a logically valid statement pattern.
Contradiction
A compound statement is said to be a contradiction, if it is always false for all possible combinations of the truth values of its components.
Note:
(i) The negation of a tautology is a contradiction.
(ii) The negation of a contradiction is a tautology.
Logical Equivalence
Two compound propositions p and q are said to be logically equivalent, if their truth values are the same for each different combination of the truth values of the components involved in them. If p and q are logically equivalent, then it is represented by p q.

For example,
show that (p q) r = p (q r)
Suggested answer:

Observe that last two columns are identical.
(p q) r p (q r)

Read more »