This is the archived website of SI 335 from the Spring 2016 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.

Midterm Exam Study Guide

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
  • Divide-and-conquer
  • Linear-time lower bounds
  • Information-theoretic lower bounds (like the Ω(nlogn) lower bound for sorting)

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

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