CS 173, Fall 2008: Skills list for second midterm

The second midterm will cover the material presented in lectures 1-27. It will focus on the material since lecture 11 (the last lecture covered in depth on the first midterm). Since you have not yet had time to do homework problems on the material from lectures 26-27, only more basic aspects of this material will be tested. The corresponding sections of Rosen are listed on the Lectures web page.

Specific skills you should know include:

• Propositional and predicate logic
  • Understand the meanings of statements with two nested quantifiers. Understand how the meaning of a statement of the form ∀ x, ∃ y P(x,y) differs from that of the statement ∃ y, ∀ x, P(x,y).
  • Negate a statement, especially one involving quantifiers and if/then statements.
• Functions
  • Know definitions: domain/co-domain/image, one-to-one/onto/bijection, composition, (strictly) increasing
  • Be able to give examples of specific functions with specified properties, e.g. one-to-one but not onto.
  • Prove that a specific function is one-to-one or onto.
  • Prove that a function is one-to-one or onto given conditions such as it's strictly increasing, it's the composition of two one-to-one functions.
• Cardinality
  • Know definitions: two sets have same cardinality, set A is countable.
  • Know that the rationals are countable but not the reals.
  • Know that there are more functions than there are algorithms because algorithms are countable and functions aren't.
• Recursive definition
  • Write a recursive definition for a familiar concept (e.g. summation, factorial, full binary trees).
  • Given a new recursive definition, figure out what function or set it defines
  • Know the definition of the Fibonacci numbers.
• Inductive proofs
  • Be able to write a standard inductive proof. Know how to write multiple base cases and/or a "strong" inductive hypothesis.
  • Given a recursive definition (familiar or given in the problem), write a simple proof by structural induction based on that definition.
• Algorithms and Big-O
  • Define when f is big-O, big-omega, big-theta of g.
  • Recognize whether some specific function f is big-O, big-omega, big-theta of another specific function g.
  • Put standard functions into big-O order: polynomials in n, log n and n log n, factorial, and exponentials (e.g. 2^n).
  • Know how simple searching and sort algorithms work (linear and binary search; bubble, insertion, and merge sort). It would be hard to reproduce the full code from scratch. Expect to fill in key tidbits of code, or hand-simulate the algorithm.
  • Given a simple function in pseudo-code, analyze how long it takes using big-O notation. (We only plan to ask about examples very similar to those presented in lecture.)
• Counting
  • Be able to state the Pidgeonhole principle (simple version, not the generalized one) and be able to apply it.
  • We won't ask you to reproduce the sum and product rules (because they are hard to state). However, be able to apply them to concrete problems.
  • Know what the inclusion-exclusion principle is. Be able to apply it, i.e. know that when combining results from two sets that overlap, you need to subtract to avoid double-counting.
  • Know definitions of counting problems involving sets: permutation, k-permuation, k-combination. Know the formulas for computing them using factorials.
  • Know Pascal's identity and the fact that C(n,r) = C(n,n-r).