Discrete Structures
SuperClass
229342_122508_1_tm_c_hit400-assignment1-2-solution.docAssignment 1
HIT400 – Discrete Structures
This assignment is worth 20% of the assessment for this unit. Late submissions will not be accepted unless prior arrangements have been made.
Show all working and explanations. Remember to write sentences.
Successfully completion of tutorial exercises is worth 20% of your mark
Question 1 (40 Marks)
Choose one of the exercised from the award winning book Computer Science Unplugged. Record a creative presentation of this material. This may consist of:
· A video of a session with children where you demonstrate the exercise.
· A creative dance – See Erik Stern and Karl Schaffer’s TEDx Video
· Props and materials
· Any other excellent creative idea
Solution:
Twenty Guesses
In this activity, we will learn about the amount of information contained in a message. It is not the length of the message that determines the amount of information. The information contained in a message is directly proportional to the fact that how hard it is to predict.
Students are asked number of questions and convened the above statement. Some of the interesting questions asked are:
1. Sun rises in the east. Does this statement contains any information.
Students Response : Yes by almost all of them.
My explanation: I convinced them that There is no information contained in the statement for computers.
2. “My name is Tom”. Does this contains any information.
Student Response: No.
My explanation: I convinced them that There is a lot of information contained in the statement unless you all know my name.
Therefore, 20 such questionnaire, student’s got convinced that it the toughness to guess that determines the content of information and not the lengthiness.
Activity:
I explained following algorithm to the students:
What strategies did you use? Which were the best ones?
Point out that it takes just 7 guesses to find a number between 1 and 100 if you halve the range each time. For example:
Is it less than 50? Yes.
Is it less than 25? No.
Is it less than 37? No.
Is it less than 43? Yes.
Is it less than 40? No.
Is it less than 41? No.
It must be 42! Yes!
Interestingly if the range is increased to 1000 it doesn’t take 10 times the effort—just three more questions are needed. Every time the range doubles you just need one more question to find the answer.
A good follow up would be to let the children play Mastermind.
This made a very interesting topic of discussion for next few months in the school.
Question 2 (10 Marks)
a) Explain how a DFS can be used to look for cycles in a graph.
DFS can be used to find the cycles in a graph. As the algorithm stores the information that whether a vertex has been visited before or not therefore one can easily find if a graph contains a cycle or not. A graph, which has either backward tree edge or cross edge is considered cyclic else it is acyclic.
b) Explain why DFS trees cannot contain cross edges. (It may help to think about what it would mean if they did contain cross edges).
A example of DFS Tree and its various edges are shown below.
undirected graphs cannot contain forward edges and cross edges, since in those cases, the edge (v, u) would have already been traversed (classified) during DFS before we reach u and try to visit v.
Let us prove the above statement by the method of contradiction.
Suppose that we have a DFS trees and a cross edge exists as shown then,
Therefore we can conclude that , the assumption that we made in the beginning is incorrect. And hence DFS trees cannot contain cross edges.
c) Prove that any connected graph G with n vertices and
1
-
n
edges must be a tree.(Hint: Use a proof by contradiction. Show that the assumption that G is not a tree, ie that G contains a cycle, will lead to the contradiction that G is not connected).
Solution Let G is not a tree then there must be at least two path from every node to every other node. This means that there are n edges I the graph:
Let n=2
Then no of edges to have two paths will be 2.
Therefore we can conclude that any connected graph G with n vertices and
1
-
n
edges must be a tree.Question 3 (10 Marks)
Write the adjacency matrix for each graph in Figure 1.
Figure 1
Solution:
Adjacency matrix: since these are undirected graphs hence
(a)
1 0 1 0 0
0 0 1 1 1
1 1 0 1 0
0 1 1 0 1
0 1 0 1 0
B
éù
êú
êú
=
êú
êú
ëû
(b)
0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 0 0 0
0 0 0 0 1 1
0 0 0 1 0 1
0 0 0 1 1 0
C
éù
êú
êú
=
êú
êú
êú
ëû
(c)
0 1 1 0 0 0 0
1 0 0 1 0 1 1
1 0 0 0 1 1 1
0 1 0 0 0 1 0
0 0 1 0 0 0 1
0 1 1 1 0 0 1
0 1 1 0 1 1 0
D
éù
êú
êú
êú
=
êú
êú
êú
ëû
(d) E= [
|
0 |
1 |
0 |
0 |
|
1 |
0 |
1 |
1 |
|
0 |
1 |
0 |
2 |
|
0 |
1 |
2 |
0 |
]
(e) F = [
|
0 |
2 |
1 |
0 |
|
2 |
1 |
1 |
1 |
|
1 |
1 |
0 |
1 |
|
0 |
1 |
1 |
0 |
]
Question 4 (10 Marks)
a) For the graph in Figure 1(d), determine
2
A
to find the number of paths of length 2 from node 2 to node 6.Solution:
A =[
0 1 1 0 0 0 0
1 0 0 1 0 1 1
1 0 0 0 1 1 1
0 1 0 0 0 1 0
0 0 1 0 0 0 1
0 1 1 1 0 0 1
0 1 1 0 1 1 0 ]
A^2= A*A= [
2 0 0 1 1 2 2
0 4 3 1 1 2 1
0 3 4 1 1 1 2
1 1 1 2 0 1 2
1 1 1 0 2 2 1
2 2 1 1 2 4 2
2 1 2 2 1 2 4]
From above matrix, we can see that there are 2 paths from node 2 to node 6 of length 2.
b) For the graph in Figure 1(a), count the number of paths of length 3 from vertex 5 to vertex 2. Check your answer by calculating
3
A
.Solution:
A =
1 1 0 0 2
1 1 1 1 1
0 1 0 1 0
0 1 1 0 0
2 1 0 0 0
A^2 =
6 4 1 1 3
4 5 2 2 3
1 2 2 1 1
1 2 1 2 1
3 3 1 1 5
A^3 =
16 15 5 5 16
15 16 7 7 13
5 7 3 4 4
5 7 4 3 4
16 13 4 4 9]
The Total number of path of length 3 from node 2 to 5 is 13.
Question 5 (15 Marks)
(a) Prove that
n
K
contains÷
ø
ö
ç
è
æ
2
n
edges using mathematical induction. (5 marks)Solution: In case of un directed graph. Let n be the number of nodes then the maximum number of total edges in an undirected graph is given by nC2.
Proof:
Let n=1.
Then no of edges =0
= 1C2
Hence it is true for n=1.
For n=2 ,
Then no of edges =1 = 2C2
For n=3 ,
Then no of edges =3 = 3C2
Therefore for n= k
Then no of edges == kC2 = K*(K-1) /2
Addition of (k+1)th node will increase the edges by k
So new no of edges for n= k+1
k*(k-1) /2 + k = k*(k+1)/2= k+1C2
Hence proved.
(b) Hence prove that in a simple graph,
2
n
E
<
for all possible graphs of order n. (2 marks)Solution: The above statement can be proved in following manner, There are two scenarios:
· Undirected graph
Adjacency matrix consumes huge amount of memory for storing big graphs. All graphs can be divided into two categories, sparse and dense graphs. Sparse ones contain not much edges (number of edges is much less, that square of number of vertices,
|E| << |V|2)
2
n
E
<
.· Directed graph:
No of edges = n*(n-1) < n^2
Therefore
2
n
E
<
.(c) Consider the following statement.
If
b
a
|
andc
b
|
thenbc
ab
b
a
-
+
|
.Either prove the statement or provide a counter example. (3 marks)
Solution:
The above statement is false.
Let a|b : 12 is divisible by 2.
b|c: 2 is divisible by 2.
a+b= 12+2 =14
ab-bc= 24-4= 20.
But 14 is not divisible by 20.
Hence If
b
a
|
andc
b
|
thenbc
ab
b
a
-
+
|
is a false statement.Question 6 (15 Marks)
(a) What is the difference between a polynomial time algorithm and an exponential time algorithm?
Solution:
Algorithms which have exponential time complexity grow much faster than polynomial algorithms. The difference happens to be where the variable is in the equation that expresses the run time. Equations that show a polynomial time complexity have variables in the bases of their terms. Examples: n^3 Notice n is in the base, NOT the exponent. In exponential equations, the variable is in the exponent. Examples: 2^n. As said before, exponential time grows much faster. If n is equal to 1000 (a reasonable input for an algorithm), then notice 1000^3 is 1 billion, and 2^1000 is simply huge! For a reference, there are about 2^80 hydrogen atoms in the sun, this is much more than 1 billion.
n2^nn^3
1.00E+0021.00E+00
2.00E+0048.00E+00
1.00E+0110241.00E+03
1.00E+021.00E+301.00E+06
1.00E+031.07E+3011.00E+09
We can see that even for n=1000.
There is a large difference in the two column. This indicates that exponential Time complexity is worse than the polynomial complexity.
(b) Give three examples of problems for which only inefficient algorithmic solutions exist.
Solution:
1. Boolean satisfiability problem
2. Hamiltonian path problem and
3. vertex cover problem
(c) Given an example of a problem for which an algorithm of complexity O(
n
2
log
) exists. Explain why the algorithm is so efficient.Solution:
It is given that complexity of the algorithm is O(
n
2
log
)|
n |
Time |
|
1.00E+00 |
0 |
|
2.00E+00 |
1 |
|
1.00E+01 |
3 |
|
1.00E+02 |
7 |
|
1.00E+06 |
20 |
|
1.00E+09 |
30 |
|
1.00E+12 |
40 |
|
1.00E+45 |
149 |
|
1.00E+60 |
199 |
We can see that for a huge n=10^60 complexity is just 10 times when there were 10^6 nodes. Therefore we can say that it is an efficient algorithm.
(a)
(b)
(c)
(d)
(e)
(f)
1
1
