Midterm Exam Study Guide

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

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

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)

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 Ω (
*n*log*n*) lower bound for sorting)

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