CSC3171 Quiz 5

Fall 2011
Herbert J. Bernstein ( )

CSC3171 Quiz 5
Fall 2011

 		 

This web page is http://www.bernstein-plus-sons.com/.dowling/CSC3171F11/CSC3171_Quiz_5.html
Copyright © 2007, 2011 Herbert J. Bernstein and other parties. All rights reserved.

This is the fifth weekly quiz to be taken on of before the start of class Thursday, 6 October 2011. You should do it after you read the second third of Knuth's Seminumerical Algorithms. You should expect to spend 30 minutes to 2 hours on this quiz. You may use your text and any other resources to do this quiz, but if you do not know the answers well or are unable to discuss them in class, you will lose credit for the quiz.

  <==== Do this AFTER you've answered all the questions

You probably DON'T want to do this ===>  

Please fill in the following information:

Name:


Email:

Please answer the following questions on this form (or on a paper copy of this form).

  1. What is the approximate percentage of numbers with leading digit 1 in a randomly selected set of randomly chosen normalized decimal floating point number?

  2. What are the classical algorithms?

  3. Explain how to divide one multi-precision integer by another.

  4. What is the main disadvantage of modular representation?

  5. Does every general computer algorithm for multiplying two n-place numbers require an execution time proportional to n2, as n increases? Explain your answer?

  6. Explain how to convert a decimal integer to a hexadecimal integer.

  7. State Euclid's algorithm and give an example of it in action.

  8. What is a unique factorization domain?

  9. What is Berlekamp's algoritm used for?

  10. Explain how to find the irreducible factors of a polynomial over the integers.

  11. What is an addition chain for n?

  12. As of 1997 what was the best upper bound the total number of operations to multiply two n x n matrices?

  13. When evaluating a discrete Fourier transform by Yates' method, how many additions are involved?

  <==== Do this AFTER you've answered all the questions

You probably DON'T want to do this ===>  

Revised 19 September 2011