CMP 232: Elementary Discrete Structures & Applications to Computer Science

Lehman College, CUNY
Spring 2014
TT 6pm-7:40pm
225 Gillet


Course Description

CMP 232 - Elementary Discrete Structures & Applications to Computer Science: Sets, relations and functions; propositional calculus, Boolean algebras, and combinatorial circuits, counting methods; proof techniques; analysis of algorithms; graphs and trees, puzzles; finite machines, sequential circuits and recognizers.


Texts

  • Main text: Mathematics for Computer Science
    by Eric Lehman, F Thomson Leighton, Albert R Meyer
    PDF available here.

  • Optional reference: Discrete Mathematics and its Applications
    by Kenneth H. Rosen
    Hardcover: 1072 pages
    Publisher: McGraw-Hill Science/Engineering/Math;
    7th edition (June 14, 2011)
    ISBN: 0073383090
    Shipping Weight: 5.2 pounds
    Available at Amazon, and possibly elsewhere.


Grading

  • 25% - quizes (around 8-10 randomly timed, one-problem quizzes in class)
  • 25% - midterm 1
  • 25% - midterm 2
  • 25% - final

  • People

    Instructor: Prof. Matthew P. Johnson
    email: mpjohnson@gmail.com
    Office hours: Monday and Wednesday, 5-6pm and by appointment, Gillet 220B.

    1. When you need help please come to office hours! Seriously. It's not bad students who come to office hours; good students to office hours.
    2. When you're going to come in, if possible please email me earlier that day to tell me to expect you.

    Advice

    This is a difficult class. To do well, you will need to keep up with the reading and study the material you learn in each class. The quizzes, which in general will be questions that you should be able to solve after attending the previous class (and studying its material), are intended to incentivize this. Without consistent study, most students will be unable to wait until the first exam and then catch up. You should expect to spend at least two hours studying and doing homework outside of class for every hour you spend inside of class. Again, seriously.

    It is a very good idea to form study groups with classmates and work on homeworks together.

    Please also take advantage of the Math Lab, located in Gillet 222.

    I want the course to run smoothly, enjoyably and profitably. Feel free to let me know what you find good, interesting, and fun about the course. Let me know sooner about the opposite.


    Practice Problem Sets


    (Tentative) Schedule

    • logic and proofs
    • induction
    • algorithms, complexity, recursion
    • 3/4 3/13: midterm 1
    • number theory, crypto, matrices
    • graphs, planar graphs, coloring
    • trees
    • 4/8: midterm 2
    • counting, counting, counting
    • probability
    • 5/20, 6:15-8:15: final exam

    mpjohnson@gmail.com