CSC3171 Quiz 1

Fall 2011
Herbert J. Bernstein ( )

CSC3171 Quiz 1
Fall 2011

 		 

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

This is the first weekly quiz to be taken on of before the start of the on-site class on Thursday, 8 September 2011. You should do it after you read Chapter I of Knuth's Fundamental 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. Briefly, give the modern definition of an algorithm according to Knuth.

  2. Briefly (just keywords) give the five important features of an algorithm according to Knuth

  3. Explain mathematical induction and give an example that relates to proving the correctness of an algoritm.

  4. Explain how to compute the logarithm base pi given a table or calculator that is willing to give you logarithms base 10.

  5. Give the formula for the sum of an arithmetic progression.

  6. Give the formula for the sum of a geometric progression.

  7. State and prove Fermat's Theorem from 1640.

  8. Give an algorithm for computing binomial coeffcients.

  9. Give an algorithm for computing Fibonacci Numbers

  10. Briefly, give a definition of big Oh notation, big Omega notation and big Theta notation.

  11. Using this notation explain the asymptotic behavior of a polynomial and compare it to the asymptotic behavior of a logarithm and to the asymptotic behavior of an exponential.

  12. Briefly, describe the registers in MIX.

  13. What is -0 and what does that have to do with MIX?

  14. Explain the meaning of a subroutine and compare it to the meaning of a coroutine

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

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

Revised 13 August 2011