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.
  1. If f(n) = log log n, what is f*(n)? (Asymptotically.) Prove your answer.
  2. What is the solution to the recurrence F(n) = (n/log log n)F(log log n) + n
  3. 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.
  4. Suppose that G is a weighted directed graph where
    1. The vertices of G are labeled v1 ... vn .
    2. 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.
  5. 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.
  6. 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.
  7. Does the ez really behave like a power? In particular, which of these statements are true?
    1. e(z+w)= ez ew
    2. (ez)n=enz if n is an integer
  8. 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.
  9. 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.
  10. 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