计算机原理代写 | Compsci 120 Assignment 3

这个作业是完成计算机原理相关的数学计算问题
Compsci 120 Assignment 3

1. (a) Find the following limits. Explain your answer.
i. limn→∞
√
n3 + 100n + 6 + √
7n4 + 20
2n2 + 6n + 100
ii. limn→∞
2
n + log2
(n)
4
n + n100
iii. limn→∞
n
2 + 4
9 − 3
n2+1
n3+5n
+2
(b) Consider the following algorithm:
Input: A positive natural number m.
1) Set n = m and s = 0.
2) If n ≤ 0 then stop.
3) Else, that is n > 0, increase s by 1, update the value of n to be n − s and go to 2)
Output: s.
Calculate the number of times the algorithm goes through Step 2) on input m. Justify
your answer.
Hint: If you do not know how to solve a quadratic inequality with a parameter you can
use software which will do it for you instead.
2. (a) Consider the following algorithm:
Input: A positive natural number n.
1) If n is either 0, 1, 2, 3, 4 or 5 output n and stop. Otherwise, go to 2).
2) If n is odd, replace n with n − n%3
3
and go back to 1). Otherwise, go to 3).
3) Replace n with n + 6 and go to 1).
Output: n.
i) Find a value of n for which this algorithm runs forever. Explain your answer.
ii) Prove that if the output of this algorithm is 1 then the input should be 1 as well.
(b) Give an infinite set of functions {fi
|i ∈ N} with the property that fi grows faster than
fi+1 for each i ∈ N and such that f0 grows faster than a
n
for each a > 1. Make sure you
show that your set of functions has the required properties!
3. (Vertex colorings.)
Given a graph G, a vertex colouring of G with k colours is any way
to assign each vertex of G one of k different colours, so that no two
adjacent vertices get the same color.
We say that the chromatic number χ(G) of a graph G is the smallest number of colours k such that G’s vertices can be coloured with
k colours.
χ(G) = 3 χ(H) = 2
G H
1
(a) Find the chromatic numbers of the three graphs below. Justify your answers; i.e. explain
why you can’t use fewer colours!
(b) Find the chromatic number of a cycle graph Cn, for every integer n ≥ 3. Explain your
answer.
(c) Find the chromatic number of a complete graph Kn for every positive integer n.
4. (a) Given a rooted tree of height h such that every vertex has at most m children, find the
following:
i) the least possible number of vertices;
ii) the least possible number of edges;
iii) the largest possible number of vertices;
iv) the largest possible number of edges.
Explain your answer.