• SI 335
• Calendar
• Classes
• Projects
• Exams
• Admin

This exam will cover the material of Units 1 through 4.

Concepts

You should have a solid understanding of the meaning and uses of the following concepts

• Problem to Algorithm to Program
• Abstract machine
• Asymptotic notation (big-O, big-Θ , big-Ω )
• Worst-case running time
• Primitive operation
• Difficulty measure
• Cost function
• Comparison model
• Lower bound for a problem
• Size vs value of an integer
• Polynomial-time
• Cobham-Edmonds thesis
• Modular arithmetic (addition, subtraction, multiplication, division)
• Greatest common divisor
• Public-key cryptography
• Multiple-precision integers (digits, base, representation)

Techniques

You should know the following techniquesand be able to apply them:

• Loop invariants
• Iterative analysis (loops)
• Solving arithmetic and geometric series summations
• Recursive analysis (recurrences)
• Solving recurrences by expansion
• Solving recurrences by a Master Method
• Divide-and-conquer
• Linear-time lower bounds
• Information-theoretic lower bounds (like the Ω (nlogn) lower bound for sorting)
• Memoization
• Dynamic programming

Algorithms

You should be very familiar the following algorithms, including their analysis and how to apply them:

• Sorted Array Search Problem

  • LinearSearch
  • BinarySearch
  • GallopSearch

• Sorting problem

  • SelectionSort
  • InsertionSort
  • MergeSort
  • HeapSort
• Factorization (leastPrimeFactor)
• Square-and-multiply exponentiation
• Euclidean algorithm (GCD)
• Extended Euclidean algorithm (XGCD)

• RSA

  • Key generation
  • Encryption with public key
  • Decryption with private key

• Integer multiplication

  • Standard algorithm
  • Karatsuba's algorithm
• Standard algorithm for matrix multiplication

• Recursive, memoized, and dynamic programming algorithms for matrix chain multiplication

You should also be familiar with what these algorithms do, and how much they cost, although you don't need to remember every detail:

• Miller-Rabin primality test
• Toom-Cook and Schoenhage-Strassen integer multiplication
• Strassen's algorithm for matrix multiplication