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.

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