本次作业涉及算法作业代写、算法代写，是典型的算法理论题目
You may use a calculator
1. Compute, T(n), the time complexity of the following algorithm. Express your result
as simply as possible. Show as much work as you need to convince me that
you know what you’re doing.
r = a randomly generated integer greater than 26;
if (r is even)
int sum = 0;
int n = a very large positive integer;
for (int i = 1; i <= n; i*=2)
for (int j = 1; j <= n; j +=i)
sum++;
else
int n = a very large positive integer;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= log5(i); j +=3)
System.out.println(i+j);
2. Suppose we run timing experiments on an algorithm designed to do “something”
to n elements. We record the time required for various values of n and have the
following data points (n, T(n)):
{6, 1015),(7, 4515),(12, 145735),(14, 347319),(17, 1006305),
(20, 2408007),(22, 3993975),(23, 5050899),(25, 7831257)}.
You know, further, that the function, T(n), is a polynomial of unknown degree.
Determine this polynomial. You may ONLY use a calculator and your previously
written Gauss Elimination program. You must find the EXACT polynomial, which
is not impossible since the coecients
are integers. (That was a hint...).
3. Suppose that our analysis of a recursive algorithm shows a time complexity T(n) =
kn2T(n
2 ). Restricting values of n to only powers of 2 for convenience, determine
the explicit form of T(n), in terms of T(1) and k.
1
4. A magic square is an n by n matrix for which i) all integers from 1 to n2 reside in
exactly one position in the matrix, and ii) the sum of all rows, all columns, and
both diagonals is the same number, which we might call N. Answer the following:
(a) Verify that the value of N is given by: N = n3+n
2
(b) Write an algorithm which determines whether or not a given n by n matrix
is a magic square.
(c) Determine the time complexity of your algorithm above: T(n) =
(d) Treating an n by n magic square as an n by n matrix, determine the sum of
all n eigenvalues for any n by n magic square.
(e) Write an algorithm which finds EXACTLY ONE magic square of size n by
n, and STOPS once this first one is found.
(f) Determine the time complexity of your algorithm above: T(n) =
(g) Write an algorithm which finds ALL magic squares of size n by n.
(h) Determine the time complexity of your algorithm above: T(n) =
5. Write the most ecient
algorithm you can design to accept an integer n > 1,
and determine the prime factorization of n. For instance:
if you enter 255, your program should output 3, 5, 17.
If you enter 1809, your program should output: 3, 3, 3, 67.
If you enter 7899079, your program should output: 19, 31, 13411.
If you enter 33554432, your program should output
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2.
Your output factors must all be prime and listed in increasing order. Determine
the time complexity T(n) = O(…). Note: there is an easy and obvious algorithm
you could write, and you will receive a few points for it. But to receive full credit,
you should look at the examples above as a clue to things you might do to improve
your basic algorithm, and implement this/these idea(s).
2
6. During the course, we examined several discrete methods for approximating definite
integrals. We evaluated the function in question, f(x), at a set of n evenly
spaced points. For instance, using the Trapezoid method, we found that:
R b
a f(x) dx = ([f(a), f(b)] · [1, 1]) (ba)
2 + E1, or:
R b
a f(x) dx =
[f(a), f( 3a+b
4 ), f( 2a+2b
4 ), f( a+3b
4 ), f(b)] · [1, 2, 2, 2, 1]
(ba)
8 + E4
or using the Simpson method, we found that:
R b
a f(x) dx =
[f(a), f( a+b
2 ), f(b)] · [1, 4, 1]
(ba)
6 + E2, or:
R b
a f(x) dx =
[f(a), f( 3a+b
4 ), f( 2a+2b
4 ), f( a+3b
4 ), f(b)] · [1, 4, 6, 4, 1]
(ba)
12 + E4
We decided that a good measure of the quality of a method was the ratio of errors
as a power, r, of n or of x.
We say that our method is “of order r” if:
limn!1
Ekn
En = xkn
xn
=
n
kn
=
1
k
r
Let’s now create a new method:
R b
a f(x) dx ⇡
[f(a), f( 4a+b
5 ), f( 3a+2b
5 ), f( 2a+3b
5 ), f( a+4b
5 ), f(b)] · [19, 75, 50, 50, 75, 19]
(ba)
288
Determine the order of accuracy, r, for this method. Use this “six point” method
to approximate the value: R 2
1
px dx
7. Consider the Ring Z257. Verify that w = 241 is a fourth root of 1. Then use this
fact to use the Fourier Transform method using i) four by four matrices, and ii)
recursion, to find the product: 26 · 73. Show all work for both methods, including
any four by four matrices, or four by one vectors which are intermediate steps.
8. Consider the following local universe of web pages, represented by a directed graph
of six vertices and several edges:
3
This graph has the following adjacency matrix:
2
6
6
6
6
6
6
4
011011
001101
100010
001001
100101
010010
3
7
7
7
7
7
7
5
Determine the Page Rank for the six pages represented, listing the pages in the
order that they might be listed as the result of a search.