CIS 11     Introduction to Discrete Structures    Fall 2009

Eva Cogan   

cogan_at_sci.brooklyn.cuny.edu
Replace _at_ with @.

http://www.sci.brooklyn.cuny.edu/~cogan/

Office: 3208N (718)951-5000 X2046

I have a mailbox in the CIS Department office: 2109N (718)951-5657

Prerequisites

• Computer and Information Science 1.10 or 1.20 or 1.5 or 2.40 or 2.80
• Mathematics 2.9 or assignment to Mathematics 3.20, 3.3 or 4.10 by the Department of Mathematics
• CIS 15 and Calc 1 are recommended.
• Willingness and ability to do many exercises
• Chapter 1 of the text (no octal). Section 1.3 is especially important. Do it this week.

Course Objectives

By course-end the student will be able to understand and use:

• Simple proofs of mathematical statements (mathematical induction, indirect arguments) and logical propositions (including quantifiers).
• Fundamental concepts of set theory and Boolean Algebra. Functional and relational properties (one-to-one, onto, reflexive, symmetric, transitive, equivalence, partial ordering), and operations (composition, transitive closure).
• Basic matrix operations. Graph algorithms and their application to computer science. Tree traversal algorithms.
• Counting principles, countable and uncountable sets. Basic probability theory and applications.
• Big O Notation. Recursive definitions and solutions of simple of recurrence relations.

Required Textbook

A First Course in Discrete Mathematics Molluzo and Buckley.
Any publisher or Coursepak.
Bring the text and a highlighter to class. I expect to work from the text quickly.

Highly Recommended

You may find Schaum’s Discrete Mathematics helpful. It has many worked out examples and problems for you to solve. Our text does not have enough.

Topics

This is an abstract math/logic course that will provide the tools for your Computer Science courses. Don’t cram for exams. You’ll need the material in the future. We cover most of chapters 2 through 8 of the text and some material that is not in the text. You are responsible for everything we do in class as well as what is in the text. We switch topics quickly. Some of the material builds on previous material. Don’t fall behind. Get the phone number and/or the e-mail address of a classmate to use if you must be absent. The order is subject to change

• chapter 1 is prerequisite Integers (congruences), Reals, Binary.
• 2.5 - 2.8 Logic
• Quantifiers, Negation
• 1.3 Congruences
• 2.1 - 2.4 Sets
• 3.1 Mathematical Induction
• 5.1 Relations
• 5.2 - 5.5 Functions
• Exam 1
• 6.1 - 6.2 Matrices
• 7.1 - 7.2 Boolean Algebra and functions
• 8.1 - 8.6 Graph Theory
• Exam 2
• 3.2-3.5 Permutations, Combinations, Binomial Coefficients, Pascal's Triangle, Inclusion-Exclusion
• Pigeonhole principle
• 4.1 - 4.3 Probability
• Infinite sets, Countability
• Case Study 5A Recursive functions
• Ordering, Lattices
• Finite Automata
• Case Study 5B Algorithm Analysis: Orders of Magnitude
• Read the interesting case studies on your own. Except for Chapter 5, they won’t be on the exams.

Grading

• 2 or 3 exams 66%
• Cumulative final 34% Look up date and arrange to be available
• Class participation may affect up to 10% of the grade.
• No makeup exams. Let me know today if there are dates you can't take exams. The state law regarding non-attendance because of religious beliefs is on p. 53 in the Bulletin.
• No individual extra credit assignments to improve your grade.
• Several exam questions may be similar to the homework exercises.

Academic Integrity

The faculty and administration of Brooklyn College support an environment free from cheating and plagiarism. Each student is responsible for being aware of what constitutes cheating and plagiarism and for avoiding both.  The complete text of the CUNY Academic Integrity Policy and the Brooklyn College procedure for implementing that policy can be found at this site:  http://www.brooklyn.cuny.edu/bc/policies.  If a faculty member suspects a violation of academic integrity and, upon investigation, confirms that violation, or if the student admits the violation, the faculty member MUST report the violation.

Center for Student Disability Services

In order to receive disability-related academic accommodations students must first be registered with the Center for Student Disability Services. Students who have a documented disability or suspect they may have a disability are invited to set up an appointment with the Director of the Center for Student Disability Services, Ms. Valerie Stewart-Lovell at 718-951-5538. If you have already registered with the Center for Student Disability Services please provide your professor with the course accommodation form and discuss your specific accommodation with him/her.

Homework

• Join the (right) class mailing list.
• Homework will generally be assigned for each class.
• Homework will be due next class.
• Homework will generally not be collected (unless you won’t do it and I will be forced to deduct points for homework not done).
• You will learn only by practicing. Discussing your work with another student (after you both do it) is beneficial.
• Many of the answers are in the back. I will distribute some answers. Check your work. Don’t fool yourself!!! Exams don’t have answers in the back.

Last modified: Aug 17, 2009 -- Eva Cogan