MATH 211 Syllabus, Fall 2011

AMERICAN UNIVERSITY OF BEIRUT Faculty of Arts and Sciences - Mathematics Department Fall 2011-2012 Syllabus Check moodle for any updates • Basic Information: Course Number: Math 211 Course Title: Discrete Mathematics Class Meetings: M W F, 9:00 - 9:50 in Bliss 203 Solving sessions: section 2 Bliss 105 F 12:00 - 12:50 section 1 Bliss 205 F 2:00 - 2:50 section 3 Nicely 412 F 4:00 - 4:50 section 4 Nicely 412 F 5:00 - 5:50 Instructor: Sara Abu Diab, e-mail: sara.abu-diab@aub.edu.lb or sa88@aub.edu.lb, website: http://people.aub.edu.lb/∼ sa88 Office Hours: Tues., Thurs. 8:15 - 9:15 and Wed. 8:00 - 9:00 or by appointment in Bliss 112 (entrance through Bliss 110) extension 4279 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • Course Resources: Required Textbook: Kenneth H. Rosen, Discrete Mathematics and its Applications, 6 th edition, McGraw Hill 2007. There will be exercises to be solved assigned from this book. The book also has a companion website with online exercises and assessments which will be available through moodle. Additional References: K. Ross and C. Wright, Discrete Mathematics, Prentice Hall Other resources will be available through moodle. • Course Overview and Objectives: 1. Logical reasoning, sets, truth tables, functions and relations; mathematical induction, recursion, counting; recurrence relations; basic algorithms and analysis of complexity; graphs and trees; strings and languages. This course is equivalent to CMPS 211. (Source: AUB catalogue) 2. At the end of this course, students should have the: - Ability to identify sets and handle standard set operations: complement, union, intersection, difference and symmetric difference - Knowledge of the concept of functions between sets: domain, co-domain, range, inverse im- ages, onto, one to one, bijection, inverse function, composition of functions and inverse of the composition 1 - Experience in using the floor and ceiling functions from real numbers to integers - Fluent ability in the use of propositional calculus: ”negation,” ”or,” ”and,” ”imply,” ”bi- condition,” ”exclusive or,” propositional equivalences and rules of inference - Ability to express symbolically a given problem using propositions, predicates and quantifiers and to obtain conclusions using logical equivalences and rules of inferences - Adequate understanding of relations between sets and the ability to distinguish between func- tions and relations - Understanding the basic elements of number theory: Euclidean division, prime numbers and prime number decomposition, greatest common divisors, and least common multipliers - Ability to use various methods of proofs on the basis of logical equivalences: direct; indirect; contradiction; counter-examples as applied to specific examples in the theory of numbers, such as the infinite cardinality of the prime numbers set; Mersenne prime numbers; and the square root test - Understanding of equivalence classes, in particular through the use of congruences on the set of integers - Ability to identify partially ordered sets on integers - Ability to develop appropriate proofs by using mathematical induction as a fundamental tool to validate a property P(n) on the set of integers - Ability to define a recursive structure such as the factorial function, a string of characters and operations on strings (length and concatenation in particular) - Ability to solve linear recurrence relations of first and second order, in particular Fibonacci equation. - Understanding the basics of counting methods, in particular the multiplication and addition rules, permutations and combinations, and the simple and generalized pigeonhole principles - Adequate understanding of the concept of growth of functions in light of their use to ana- lyze complexity of simple algorithms such as computations of basic statistical data, arithmetic operations on arrays and binary searches on ordered lists - Adequate understanding of the concept of basic discrete sets, such as graphs, trees and strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . • Course grading criteria: The maximum of the following two distributions will be considered: Distribution 1: 25% Quiz I, 25% Quiz II, 50% Final Exam Distribution 2: 25% Quiz I, 25% Quiz II, 10% Coursework, 40% Final Exam * Coursework denotes homework, drop quizzes, projects, presentations,... if available - Previous exams and any other material deemed beneficial will be provided through moodle. - One makeup of quizzes missed for a valid medical excuse will be given during the last week of classes including the topics in both quizzes. Make ups of the final exam are subject to the approval of the dean’s office. • Other course policies and remarks: – Classes are not a rehearsal of particular notes or of chapters in the book. They are a medium for positive interaction and transmission of skills. Your ’active’ attendance is proportional to your ’good’ performance. In case you miss a class, please note that you are required to compensate for it and to be informed about any announcements made during your absence. 2 – Attendance will be recorded at the beginning of each session. – You should never hesitate to ask questions, give your input and comments, and participate in the progress and development of this course in an orderly manner. – You are expected to be aware of and to respect AUB’s policies. You may want to glance over the following: ⋄ Read the student code of conduct that is applied at AUB if you have not already done so. Some important parts are those dealing with cheating, plagiarism, and class behavior. ⋄ AUB is an equal opportunity employer and educator. Students with learning, physical, or psychological disabilities are provided with the necessary care upon request. AUB is committed to appreciate and foster diversity among its staff, faculty, and students. AUB is also committed to accommodate a multi-cultural environment that promotes tolerance, respect, in addition to academic and intellectual maturity. – Some ideas may be implemented to help you enjoy the course and study well for it. (work- sheets, self assessments, optional workshops, optional projects, readings, discussion sessions, guest lecturers...) – The course will also be on moodle. Relevant exercises, additional resources and review sheets will be available in due time. Have a nice semester. 3