THEORY I - CS 3500 D Spring 2003

Handout # 3 Tuesday, March 25, 2003

Mid-term Exam #2 Announcements

Second midterm exam will be held on Friday, March 28. The exam will be closed book. You may, however, bring one 8.5" x 11" sheet of paper as a crib sheet. Preparing a crib sheet can be a u seful study aid, so take time in selecting material for it. You may use ONLY ONE SIDE of the paper and write as small as you like. No mechanical or electronic reproductions are allowed. You must hand in your crib sheet when you hand in your exam.

Material covered: You are responsible for the material covered in lecture until Wednesday, March 26 (inclusive). In particular, it includes:

  1. Theory of Computation: Turing machines, Turing-recognizable and decidable languages, the halting problem, Turing undecidable and unrecognizable languages (Sipser: Chapters 3.1-4.2 p. 31-170). Complexity classes P and NP, NP-completeness. (Sipser: Chapters 7.1-7.5 p.225-276; also CLR: Chapter 34, p.966-1021)
  2. Theory of Algorithms: Introduction, insertion sort (Ch.2.1-2.3), asymptotic growth of functions (Ch.3.1-3.2), recurrences (Ch.4.1-4.3), heapsort(Ch.6.1-6.4), quicksort(Ch.7.1-7.4), sorting in linear time (Ch.8.1-8.2), medians and order statistics (Ch.9.1-9.3), Strassen's algorithm for matrix multiplication (Ch.28.2)

Review: There will be a review in class on Wednesday, March 26

Again, the best way to study for this exam is to

    review the assignments, make sure you can solve the problems, practice solving similar ones;
    review your lecture notes.

Sample problems: check class website.