CS421 - Advanced Data Structures and Algorithm Development Spring 1999 Test 1 Study Guide

Test Format (You may bring in one index card with notes but no books)
Matching (2 pts each)
Short Answer Questions and Problems

Study Material

1. Chapter 1 - Overview
   • Define algorithm, model, problem, analysis, upper bound, lower bound, worst cost, average cost, instance, optimal, aymptotically optimal, reduction strategy, approximation algorithm, probabilistic algorithm, randomized algorithm, greedy strategy, balance strategy, simplicity stragegy
   • Problem types classified by level of difficulty. (pg. 10)
   • Given resource usage graphs, find upper bound, lower bound, worst cost and average cost (pg. 18, 22)
   • Be able to solve a recurrence relation, that is find its closed form and then use an induction proof to verify it. (pg. 21, 86, 87, 468)
   • Be able to look at code fragment and find its worst cost. (Appendix B)
   • Know order of functions on pg. 41, 45 by growth rates
   • Know and be able to use definitions of order notations o(g), O(g), Q(g), W(g) (pg. 43)
   • Compare growth rates and determine which are faster (using L'Hopital's Rule) (pg. 72:24, 75:4)

2. Chapter 6 - Numbers
   • Define powers, LCF(GCD), prime numbers, coprime, totient, Fermat's Theorem, primes, pseudoprime, secrecy problem, authentication problem, cryptology, cryptography, cryptoanalysis, public authentication, covert channels, zero-knowledge proofs, chromatic numbers, unifor distribution, independence, pseudorandom numbers
   • Know and be able to use the algorithm for raising m to the nth power (pg. 359-362)
   • Know and be able to use the algorithm for finding the largest common factor (greatest common divisor) of two numbers m and n (pg. 362-366)
   • Know and be able to use the sieve algorithm for finding prime numbers (pg. 366-367)
   • Be able to determine if two numbers are coprime (mutually prime) (pg. 369)
   • Be able to determine the totient of a number (pg. 369)
   • Be able to determine if a number is a Carmichael number (pg. 370)
   • Be able to determine if n is a base m pseudoprime (pg. 372)
   • Be able to discuss and compare private key systems (DES, Caesar substitution, transpositions) and public key systems (Diffie-Hellman, RSA, Knapsack) (pg. 373-384)
   • Be able to discuss the authentication problems and various solutions (message encryption, MAC, hash functions, digital signatures) [pg. 385-393]
   • Be able to determine whether a sequence of numbers might be random (pg. 394)
   • Be able to use the linear congruential method to generate a pseudorandom number

:-) Good Luck!!!!! :-)

Back to Class List Page