Exam Two Study Guide

Time: Tuesday, March 19th from 6pm-8pm
Location: CSI 437

• Exam 2 Practice Problems

• Exam 2 Definitions Sheet

Structure

• 5-6 Problems

• Shorter than HWs

• The simplest problems are similar to the reading assessments.

• The hardest problems are the easier starred problems on the HWs.

• You will be given all definitions, but not proof strategies.

Topics

• Homeworks 6 through 9

• Proofs

  • • Universal proofs ("Consider an arbitrary")

    • Existential proofs (proof by example/counterexample)

    • Direct proofs

    • Proof by cases

    • Proofs "in two directions"

    • Proof by contraposition

    • Proof by contradiction (not emphasized)

    • Not proofs by exhaustion

• Sets

  • • Properties and their proofs: Subset, equality

    • Operations: Union, intersection, set difference, cross product, powerset

    • Cross products, tuples, relations (sets of tuples)

• Functions

  • • Properties: Onto, one-to-one, and bijections

    • Operations: Composition, inverse

    • Not “because there exists an onto function .. the size of A and the size of B”

• Sequences (not emphasized)

  • • Mostly as mathematical objects, i.e. sequences vs sets vs tuples,  functions over sequences

    • Defining recurrence relations given a description or prefix of a sequence

    • Not finding closed forms given a recurrence relation

• No algebra (i.e. given x is even, prove x^4+2x+8 is even)

• No puzzles

Problem Types:

• Translate between claims about mathematical objects and English

• Determine properties of a mathematical  object, or define an object that satisfies a property

  • • i.e. find a counterexample to this lemma, is this function onto, or "define an onto function"

    • Diagrams are acceptable definitions of sets and functions

• Apply a proof strategy - identify what would be assumed and what would be proven

  • • Not a proof sketch

• Find the flaw in a proof

• Write a proof:

  • • Answers can use a "white-board" level of formality

      • • Bullet points are great

        • Complete sentences optional

        • Transitions are helpful, but not required

    • You may skip small steps in arguments, i.e. "As A ⊆ B and x ∈ A, we know x ∈ B" can be shortened to "• A ⊆ B so x ∈ B" 

      • • However, partial credit is easier to award when they are included

• Synthesis - apply knowledge in a new way.