Discrete Computational Structures

Offered during Fall and Spring Semesters each year.

1. Credits and contact hours: 3 credits, 4 contact hours
2. Instructor’s or course coordinator’s name: Jack Lutz
3. Text book, title, author, and year: Discrete Mathematics and its Applications, Kenneth Rosen, 7th edition; Mathematics for Computer Science, Eric Lehman, F. Thompson Leighton and Albert Meyer.
4. Other supplemental materials: Introduction to Algorithms, Cormen, Leiserson, Rivest, and Stein

Specific course information

1. Brief description of the content of the course: Concepts in discrete mathematics as applied to computer science. Logic, set theory, functions, relations, combinatorics, discrete probability, graph theory and number theory. Proof techniques, induction and recursion.
2. Prerequisites or co-requisites: Minimum of C- in COMS 227 and MATH 165; ENGL 150
3. Required, elective, or selected elective? Required

Specific goals for the course

1. Specific outcomes of instruction: Upon completing this course the students should have the following abilities.

• Ability to think mathematically; skills to read, comprehend, and construct mathematical arguments. (1)
• Ability to apply various proof techniques towards developing formal proofs about algorithm correctness.
• Ability to apply concepts in combinatorics and number theory towards problem solving and algorithm design. (1, 6)
• Ability to use abstract mathematical structures to come up with abstract computational models for real problems.

Brief list of topics to be covered

• Logic
• Methods of Formal Proof
• Sets
• Functions and relations
• Countable and uncountable sets
• Induction
• Recursion
• Number Theory
• Basics of Counting
• Graphs