• SI 335
• Calendar
• Classes
• Assignments
• Exams
• Admin

This is the archived website of SI 335 from the Spring 2015 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, except for dynamic programming (the very end of Unit 4).

The following list is meant as a rough guide; it is not necessarily exhaustive! Anything we covered in class or in the notes is fair game for the exam.

(But mostly, if you're solid with what's on this list, you're going to be in good shape.)

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
• Divide and Conquer
• 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)
• Memoization

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
• Designing Divide-and-conquer algorithms
• Analyzing Divide-and-conquer algorithms
• Linear-time lower bounds
• Information-theoretic lower bounds (like the Ω (nlogn) lower bound for sorting)
• Using memoization to speed up a recursive algorithm

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
  • Cracking (decrypting without the private key
• Integer addition and subtraction

• Integer multiplication

  • Standard algorithm
  • Karatsuba's algorithm

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

• Miller-Rabin primality test
• Strassen's algorithm for matrix multiplication