University of Nevada Las Vegas
Howard R. Hughes
College of Engineering
School of Computer Science
My Home Page

CSC 715 Assignment 2
Due date: Thursday, February 28, 2012, 5:30 PM.
All assignments must be handwritten (not typed or printed from a computer
file) in your own handwriting, on 8.5 by 11 inch paper, or on A4 paper.
Write your name on each sheet, and do not fold the pages or crimp the corners.
(You may use a paper clip or a staple.)
Turn the pages in to me on or before the due date.
-
If f(n) = log log n, what is f*(n)? (Asymptotically.) Prove your answer.
-
What is the solution to the recurrence
F(n) = (n/log log n)F(log log n) + n
-
Suppose
A is a Monge matrix with
p
rows and
q
columns, and that
B is a Monge matrix with
q
rows and
r
columns.
Prove that the tropical
matrix product
AB is a Monge matrix.
-
Suppose that
G
is a weighted directed graph where
-
The vertices of
G
are labeled
v1 ...
vn .
-
If i < j
there is an edge from
vi
to
vj
of weight
(j-i)2 + 10. There are no other edges.
For any m, let
Gm
be the n by n matrix where
Gmij
is the smallest weight of any path of length exactly
m from
vi to
vj .
Length of a path is defined to be the number of edges.
If there is no path of length exactly
m from vi to vj , then
Gmij is infinity.
Prove that Gm is a Monge matrix.
-
We now consider a different version of the Traveler's Problem.
As before, the traveler can travel no more than a given distance each day,
and must stay at an inn during each night, and each inn has some cost.
But now, we assume that all the inns are located on a semi-circle, and
that the traveler can travel between inns using straight line paths instead
of sticking to the circle, as illustrated here
in postscript format (eps) and
in portable document format (pdf).
The traveler carries a heavy backpack, and thus he imputes a "carrying cost"
proportional to the distance he walks. Instead of just minimizing room costs,
the traveler wants to minimize his total cost, which is the room cost plus
the carrying cost, which he imputes to be one copper piece per furlong.
Explore this problem.
-
The exponential function ez.
Let e be the usual base of the natural logarithm, 2.1828 ...
If z is any complex number then ez is a complex number.
If z = a+ib, where a and b are real numbers, then
ez = eacos b + ieasin b.
Prove that if a=0, then ea+ib lies in the circle
of radius 1 centered at 0.
-
Does the ez really behave like a power? In particular,
which of these statements are true?
-
e(z+w)=
ez
ew
-
(ez)n=enz if n is an integer
-
Every non-zero complex number has two square roots, three cube roots,
four fourth roots, and so forth. Find the two square roots of
4+3i.
No trigonometric functions should appear in your answer.
-
Find all six of the sixth roots of unity, expressing the answers in
standard a+ib form.
No trigonometric functions should appear in your answer.
-
When I was in high school, my friend Bill Sinclair told me that
ii is a real number.
I could not even imagine what it could mean, and I quickly gave up trying to
figure it out.
As a freshman at Tulane University, I asked
my calculus teacher, who dismissed the
question by saying, "We haven't defined that." After that, I forgot about it
for a long time.
I cannot remember the real value Bill gave for
ii , but I do remember that it was positive
and less than 1. Now that I have a bit more insight, I think the number was
0.20789576 ... (that is only an approximation; the actual value is irrational.)
Explain what causes me to believe that. Are there any other real numbers that
could possibly be equal to ii ? [Answer: yes.]

Back to
Course Page