CPS 102, Spring 2012, Test 1

TEST 1 topics

• Chapter 1.1-1.6
  • Propositional Logic, Quantifiers, Rules of Inference
    • Know the basic truth tables - and, or, -> , <->
    • Will give you other tables

• Chapter 2.1-2.5
  • Sets, Functions, Sequences, Cardinality, Countability
  • 2.6, Matrices are not on the test

• Chapter 13.3
  • Finite state machine

• Chapter 3.1-3.3
  • Algorithms, growth of functions, complexity of algorithms (big-O, big-Omega, big-Theta)
  • If I were to ask you to write pseudocode on the test, you can write in english, that is, you do not have to follow the pseudocode format in the book.

• Chapter 4.1-4.2
  • Divisibility and Modular Arithmetic, Integer representations
    • Decimal, binary, octal, hexidecimal representations and others.
    • Convert between two representations such as binary to hexidecimal
    • Since we did not do much with this chapter yet, for this test you only need to understand the two ways to use mod with numbers (similar to problems on recitation 5 that are not proof type problems) and how to convert between two different base representations (such as from decimal to hexidecimal, from octal to binary, etc.).

  ---

  Ways to Study for the Exam

  • recitation problems
  • homework problems
  • problems in the book (answers to odd numbered problems)
  • lecture notes - definitions and problems
  • use JFLAP to check DFA problems - but note you will not have JFLAP on the exam.

  ---

  TEST 1 Logistics

  • Closed book, closed notes, closed neighbor
  • Here are types of problems on the exam:
    • write a DFA
    • Use rules of inference to prove an argument.
    • convert an integer from one form to another
    • there are other problems too!

  ---

  Office Hours between now and exam

  • Prof Rodger - LSRC D237 -
    Thursday Feb 16, 2:10-3:30pm
    Monday, Feb 20, 2pm-4:15pm

  ---