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