Posted in Miscellaneous on November 18, 2009| 1 Comment »
Topic Submitted by : Rafiul Sabbir
Dept. : CSE
Institution : United International University
Submitted at : 18/11/09
*/
Print the following as output for a number n. Here the sample for n=5
1
121
12321
1234321
123454321
1234321
12321
121
1
Posted in Miscellaneous on November 17, 2009| 1 Comment »
/*
Topic Submitted by : Rafiul Sabbir
Dept. : CSE
Institution : United International University
Submitted at : 17/11/09
*/
Print the following as output for a number n. Here the sample for n=5
1
121
12321
1234321
123454321
Posted in 1 on November 11, 2009| 1 Comment »
A Programming Contest will be held in order to recruit new members for UIU Programming Contest Teams. The tentative date of Contest is after MID – II. Exact Date will be announced later. Basic knowledge of C Programming Language will be sufficient to solve all the problems. No Registration fee is required for participation.
For more details & Registration :
Moderator : Md. Faisal Kabir sir.
Room # 116. Cell : 01712025763.
Sheikh Faiyaz Moorsalin.
Cell : 01915472173.
Email Id : sheikh303@gmail.com
Rafiul Sabbir.
Cell : 01915686454.
Email Id : oparthibo@gmail.com
Sajid Rabbani.
Cell : 01817046667.
Email Id : sjdrabbani@gmail.com
Posted in Topic Discussion on November 4, 2009| 2 Comments »
/*
Topic Submitted by : Rafiul Sabbir
Dept. : CSE
Institution : United International University
Submitted at : 04/11/09
*/
In the branch of mathematics called Graph Theory, a graph bears no relation to the graphs that chart data, such as the progress of the stock market or the growing population of the planet. Graph paper is not particularly useful for drawing the graphs of Graph Theory.
In Graph Theory, a graph is a collection of dots that may or may not be connected to each other by lines. It doesn’t matter how big the dots are, how long the lines are, or whether the lines are straight, curved, or squiggly. The “dots” don’t even have to be round!
All that matters is which dots are connected by which lines.
Two dots can only be connected by one line. If two dots are connected by a line, it’s not “legal” to draw another line connecting them, even if that line stretches far away from the first one.
If you look at a graph and your eyes want to zip all around it like a car on a race course, or if you notice shapes and patterns inside other shapes and patterns, then you are looking at the graph the way a graph theorist does.
1. Edges & vertices of a graph :
A graph is made up of dots connected by lines.
A “dot” is called a vertex .
When there is more than one vertex, they are called vertices .
A “line” is called an edge. (The plural is simply edges)
2. The degree of a vertex in a graph :
The degree of a vertex in a graph is the number of edges that touch it.
The number on each vertex of this graph is the degree of that vertex.
3. Size of a graph :
The size of a graph is the number of vertices that it has.
4. Regular graphs :
A graph is regular if every vertex has the same degree.
5. Paths & cycles in a graph :
A path is a route that you travel along edges and through vertices in a graph. All of the vertices and edges in a path are connected to one another.
A cycle is a path which begins and ends on the same vertex. A cycle is sometimes called a circuit.
The number of edges in a path or a cycle is called the length of the path. Is the length of the path also the number of vertices?
6. A Hamiltonian path in a graph :
A hamiltonian path in a graph is a path that passes through every vertex in the graph exactly once. A hamiltonain path does not necessarily pass through all the edges of the graph, however.
A hamiltonian path which ends in the same place in which it began is called a hamiltonian circuit or a hamiltonain cycle .
7. An Eulerian path in a graph :
An eulerian path in a graph is a path that travels along every edge of the graph exactly once. An eulerian path might pass through individual vertices of the graph more than once.
An eulerian path which begins and ends in the same place is called an eulerian circuit or an eulerian cycle
8. Planar graphs :
A planar graph is a graph that can be drawn so that the edges only touch each other where they meet at vertices.
You can usually re-draw a planar graph so that some of the edges cross. Even so, it is still a planar graph. When it is drawn so that the edges cross, the drawing is called a non-planar representation of a planar graph.
9. Non-planar graphs :
The graph above is nonplanar. No matter how you stretch the edges around, you cannot redraw the graph so that none of the edges cross each other between the vertices .
A non-planar graph should not be confused with a planar graph that just happens to be drawn in such a way that two or more edged cross. The graph below is a planar graph, but it is drawn here in a nonplanar representation.
10. Distance in a graph :
Distance in a graph isn’t measured in inches or kilmoters. This isn’t surprising, because you don’t do any measuring in inches or kilometers when you draw a graph in the first place.
Still, when you look at a graph, you can see how it might be possible to say that some vertices are closer together then others.
The distance between two vertices is a count of the number of edges along which you must travel to get from one of the verticesto the other.
If there is more than one path between two vertices, the number of edges in the shortest path is the distance.
The number of edges in a path is called the length of the path.
11. The diameter of a graph :
The diameter of a graph is the longest distance you can find between two vertices.
When you are measuring distances to determine a graph’s diameter, recall that if 2 vertices have many paths of different distances connecting them, you can only count the shortest one.
An interesting problem in graph theory is to draw graphs in which both the degrees of the vertices and the diameter of the graph are small. Drawing the largest graphs possible that meet these criteria is an open problem .
12. Isomeric graphs :
Two graphs are isomorphic if you can re-draw one of them so that it looks exactly like the other.
To re-draw a graph, it helps to imagine the edges as infinitely stretchable rubber bands. You can move the vertices around and stretch the edges any way you like — as long as they don’t become disconnected.
Sometimes it is very hard to tell whether two graphs are isomorphic or not. In fact, no one knows a simple method for taking two graphs and determining quickly whether or not they are isomorphic.
13. Complete graphs :
In a complete graph, every pair of vertices is connected by an edge . It is impossible to add an edge to a complete graph because every possible edge has been drawn.
Complete graphs always have diameter 1.
14. Neighboring vertices in a graph :
In a graph, the neighbors of a vertex are all the vertices which are connected to that vertex by a single edge.
The distance between two vertices which are neighbors is always 1.
15. Dominating sets in graphs :
In a graph, the neighbors of a vertex are all the vertices which are connected to that vertex by a single edge. A dominating set for a graph is a set of vertices whose neighbors, along with themselves, constitute all the vertices in the graph.
Posted in Topic Discussion on November 1, 2009| Leave a Comment »
/*
Topic Submitted by : Rafiul Sabbir
Dept. : CSE
Institution : United International University
Submitted at : 02/11/09
*/
If you’ve been doing math for any period of time, you’ve probably run into a formula that looks like this:
a2 + b2 = c2
This very useful bit of math is called the Pythagorean Theorem, named after Greek mathematician Pythagoras. Put into words, the above equation tells us that the sum of the square of the two legs of a right triangle equals the square of the hypotenuse (the longest side of a right triangle).
This formula has many potential uses. If you know the length of both legs, or one leg and the hypotenuse, of a right triangle, then you can solve for the missing side using the Pythagorean Theorem.
For example, we are given that a = 3 and b = 4. Let’s solve for c.
32 + 42 = c2
9 + 16 = c2
25 = c2
5 = c
You can also use the Pythagorean Theorem to prove whether or not a triangle is a right triangle. For this example, let’s have a = 5, b = 10, and c= 13.
52 + 102 = 132
25 + 100 = 169
125 = 169
Wait a second! 125 does not equal 169. Therefore, a triangle with sides 5, 10, and 13 is not a right triangle.
Let’s try it again with a triangle with the sides 7, 24, and 25.
72 +242 = 252
49 + 576 = 625
625 = 625
This triangle is a right triangle!
In a bind where a right triangle is involved? Try out the Pythagorean Theorem and see if it helps!
Posted in Topic Discussion on November 1, 2009| 1 Comment »
/*
Topic Submitted by : Rafiul Sabbir
Dept. : CSE
Institution : United International University
Submitted at : 02/11/09
*/
We’re going to find the LCM for 12 and 16. So we’ll start by finding the prime factors for both numbers.
12 factors to 2 * 2 * 3
16 factors to 2 * 2 * 2 * 2
Both 12 and 16 have two 2s in their list of factors, so we’ll ignore those. That leaves us with the following factors.
12: 3
16: 2 * 2
To find the least common multiple, we multiply the original number by the remaining factors of the other number.
12 * 2 * 2
16 * 3
If you multiply both lines out, you’ll find they both equal 48. The least common multiple for12 and 16 is 48.
You’ll notice this took a lot less work than the other LCM method, so you might want to try it out yourself the next time you’re staring down a page full of LCM questions.
Posted in Topic Discussion on November 1, 2009| Leave a Comment »
/*
Topic Submitted by : Rafiul Sabbir
Dept. : CSE
Institution : United International University
Submitted at : 02/11/09
*/
A prime number is any number that can be divided only by itself and 1. Some people find this a more useful way to find common denominators,and it can actually make simplifying radical expressions much simpler.To start factoring a number to its primes, we need to either apply the multiplication facts or the rules of divisibility to it.
Let’s use 72 for this example. 72 is 8 * 9.
72
/\
8 9
Neither 8 nor 9 is prime, so we’re going to factor both of them. We know that 8 is 4 * 2; and 9 is 3 * 3, so let’s add those to our factor tree.
72
/ \
8 9
/\ /\
2 4 3 3
Now we’re getting somewhere! Both 2 and 3 are prime, leaving us only the 4 to factor. The factor tree looks like this now.
72
/ \
8 9
/ \ /\
2 4 3 3
/\
2 2
I’ve bolded the prime numbers at the end of each branch so we can see them clearly. The prime factorization of 72 is 2 * 2 * 2 * 3 * 3.
If you use this method to find GCFs, then you’ll need to find all the primes both numbers have in common and multiply them back together. For example, if you were comparing 72 to 12, you’d find that both numbers have two 2s and a 3 in their list of prime factors. 2 * 2 * 3 equals 12, so 12 would be the GCF for 12 and 72.
Posted in Topic Discussion on November 1, 2009| 1 Comment »
/*
Topic Submitted by : Rafiul Sabbir
Dept. : CSE
Institution : United International University
Submitted at : 01/11/09
*/
Another Algorithm finding gcd (x, y)
step 1: find the prime factors of x
step 2: find the prime factors of y
step 3: multiply the common prime factors of x and y
Example :
gcd (60, 24)
prime factors of 60 = 2 * 2 * 3 * 5
prime factors of 24 = 2 * 2 * 2 * 3
common prime factors = 2, 2, 3
multiply them = 2 * 2 * 3 = 12
Posted in Topic Discussion on November 1, 2009| Leave a Comment »
/*
Topic Submitted by : Gultu
Dept. : CTE
Institution : United International University
Submitted at : 01/11/09
*/
Find the greatest common divisor (gcd) of two integers
Euclid’s algorithm: // most efficient
gcd (x, y) {
step 1: if y = 0, return x. otherwise goto step 2
step 2: gcd (y, x mod y) // recursive call
}
Example:
gcd (80, 50)
gcd (50, 80 mod 50) = gcd (50, 30)
gcd (30, 50 mod 30) = gcd (30, 20)
gcd (20, 30 mod 20) = gcd (20, 10)
gcd (10, 20 mod 10) = gcd (10, 0)
return 10.
Algorithm:
1. gcd (x, y) {
if ( y == 0 )
return x;
gcd (y, x % y)
}
2. while ( y <> 0 ) { // <> = not equals to
a = x % y
x = y
y = a
}
return x
Posted in Topic Discussion on November 1, 2009| 1 Comment »
/*
Topic Submitted by : Gultu
Dept. : CTE
Institution : United International University
Submitted at : 01/11/09
*/
Often we have to calculate the value of 100! or 1000! or 2^1000.
Surely, it’s a very large value even for double/long double. One of the efficient way is to split the value in array. In next few paragraphs we are going to discuss the process. You can use this process in manipulating,
1. Big Integer Addition
2. Big Integer Subtraction
3. Big Integer Multiplication
4. Factorial of 1000!, 10000!……….
5. Combination nCm (tho combination have another more efficient algorithm, we will discuss later)
6. Exponential value i.e. 2^1000, 1000^1000………..
and many mores.
Lets start……..
Suppose, we are calculating 1234 * 999. Let, A = 999
1234
x A
3996 (4 * A = 4 * 999 = 3996)
2997 (3 * A = 3 * 999 = 2997)
1998 (2 * A = 2 * 999 = 1998)
0999 (1 * A = 1 * 999 = 999)
Now, 3996 + 2997 + 1998 + 999 = 1232766
1. Split the Number 1234 in an Array. u can use string to take the value and then just subtract 48, to convert it into integer. Or, u can use (atoi) function in C/C++.
| 1 | 2 | 3 | 4 |
2. Now, we multiply First Index with 999 and keep the carry in hand, I.e
999 * 4 = 3996
Assign (3996 % 10) in the First index (by replacing 4) and keep the (3996 / 10 = 399) in Carry. Array will look like,
| 1 | 2 | 3 | 6 |
Carry = 399
3. Second Index * 999 = 3 * 999 = 2997 + Carry = 2997 + 399 = 3396
Assign (3396 % 10) in the Second index (by replacing 3) and keep the (3396 / 10 = 339) in Carry.
| 1 | 2 | 6 | 6 |
Carry = 339
4. Third Index * 999 = 2 * 999 = 1998 + Carry = 1998 + 339 = 2337
Assign (2337 % 10) in the Third index (by replacing 2) and keep the (2337 / 10 = 233) in Carry.
| 1 | 7 | 6 | 6 |
Carry = 233
5. Forth Index * 999 = 1 * 999 = 999 + Carry = 999 + 233 = 1232
Assign (1232 % 10) in the Forth index (by replacing 1) and keep the (1232 / 10 = 123) in Carry.
| 2 | 7 | 6 | 6 |
Carry = 123
6. All index are multiplied by 999 successfully. Concatenate Carry with the Array.
For instance, our array values are 2766 and Carry = 123
So, final output: 1234 * 999 = 1232766.
Topcodes for the coders........ 
