CISC 3220 -- Fall 2016

Assignment #1, Due: Wednesday, Sept 7

  1. Prove the following lemma:

    xlogb y=y logbx

    Hint: Begin by taking the log of both sides.


  2. Write a function (pseudocode is fine) to find the ceiling of lg(n+1), where n is a nonnegative integer, and lg represents log base 2. Assume that your programming language truncates the result of integer division, dropping the remainder, as most languages do. Hand calculate a table for inputs 16 and 10. ( Hint: repeatedly divide by the base of the logarithm.)


  3. Use the formulas in your textbook to give an equivalent equation without the summation. This is sometimes called the closed form of an equation.

     N  
    ∑
    i = 0    		 (5i2+i) 


  4. Give the formula for the average case time complexity, assuming that there are m possible different inputs, each of which is equally likely to occur.


  5. Suppose you are given an unsorted array of n elements, and you are also given the mean, or the average value for this list. Describe an algorithm that will report whether the number of elements in the array that are greater than the average exceeds the number of elements that are less than or equal to the average.

    1. What is the basic operation that is done by your algorithm?
    2. What does "worst case" or "best case" mean in terms of your algorithm?
    3. Can you estimate how many operations are done by your algorithm in the best case and in the worst case?