INFO 150: Introduction to Computation

David Mix Barrington

Fall 2004

Learning Goals for the Course

This is a list of specific tasks that students might be asked to perform on the final exam -- it is posted here as a study guide.

• First Third of Course, Chapter 1, and Sections 2.1-2.2 (25%):
  • Work with number sequences as both closed and recursive formulas.
  • Translate statements to and from propositional logic.
  • Prove statements of propositional logic using truth tables and/or propositional proof rules.
  • Translate statements to and from predicate logic.
  • Convert implication statements to contrapositive form.
  • Express mathematical proofs using game semantics.
  • Prove statements about integers such as evenness, oddness, and primality
• Middle Third of Course, Chapters 2, 3 and 4 (25%):
  • Prove statements about natural numbers by ordinary induction.
  • Prove statements about natural numbers by strong induction.
  • Prove statements about statements in programs using induction.
  • Prove statements using the definitions of sets and set operations.
  • Prove statements about functions, including onto functions, one-to-one functions, and composition.
  • Prove statements about relations and equivalence relations.
• Last Third of Course, Chapters 5 and 6 (50%):
  • Use the Sum and Product rules to count finite sets.
  • Use the Binomial Theorem to count sets of combinations.
  • Use these rules to count the sets of binary strings with a given property.
  • Use combinatorial rules to determine probabilities.
  • Compute probabilities involving card and dice problems.
  • Compute expected values of random variables.
  • Demonstrate familiarity with definitions involving trees and graphs.
  • Use matrices to count the number of paths in a graph.

Last modified 2 September 2024