CMSC 250
Discrete Structures

05/06/15   The final exam will be on Saturday 5/16 at 4:00PM. Please arrive at 3:50PM. The location depends on your section; please see the table below for your final exam location.

Sections Exam Room
0101, 0102, 0103, 0104 HJP 0226
0201, 0202, 0203 MMH 1400
0301, 0302, 0303, 0304 PHY 1412

04/29/15   Homework #9 has been posted. This will be the last homework. This assignment is not short and it is not obvious how to solve some of the problems, so please get started right away.

04/27/15   An error was found in one of the solutions for HW #8. For problem #4c, the co-domain was listed as R+, but it should have been R≥ 0

04/27/15   Fawzi's usual Tuesday office hour will be canceled tomorrow (4/28) due to an unavoidable conflict.

04/23/15   Midterm #2 has been graded. The median score was 81. (Students who took the exam with DSS will not see a score yet.)

04/22/15   Solutions to Homework #8 have been posted.

04/21/15   Please don't forget that the second midterm is on Thursday 4/23. Be sure to arrive on time!

04/20/15   Regarding the solutions to HW #7: There was an error in the solution to #2d, which has now been corrected.

04/17/15   Solutions to HW #7 have been posted.

04/15/15   Students in section 0202: There was a miscommunication between the TAs, so you missed out on the quiz that was supposed to be given on Wednesday. You'll be getting an alternate quiz on Monday 4/20.

04/15/15   Homework #8 has been posted.

04/10/15   Solutions to HW #6 have been posted.

04/08/15   Homework #7 has been posted.

04/04/15   Solutions to homework #5A and #5B have been posted.

04/01/15   Homework #6 has been posted.

03/30/15   Please staple homework #5A and homework #5B together before handing them in on Wednesday. We are grading them together as a single homework assignment.

03/24/15   Fawzi's Friday office hours are changing for the rest of the semester. From this point on my office hours will be Friday 12:00PM-1:00PM, Friday 3:00PM-4:00PM, and Tuesday 5:00PM-6:00PM

03/24/15   Homework #5B has been posted.

03/24/15   Tomorrow's quiz will NOT involve induction -- I may have said something today in class that might lead you to think that induction is on this quiz, but it will not be on a quiz until the following week.

03/13/15   The first part of homework #5 has been posted. (The rest will be posted after Spring Break.) Even though this assignment is not due for a long time, it would be wise to work on it as soon as possible, while the ideas are still fresh in your mind.

03/10/15   The midterms have been graded! The median score was 77. The exams will be returned tomorrow (Wednesday) and your TA will go over the solutions.

03/05/15   Due to the snow day, the midterm exam will be held during the lecture on Tuesday, 3/10. The exam will cover the same topics mentioned previously -- it's the same exam, just on a later date.

03/05/15   Solutions to HW #4 have been posted.

02/25/15   Solutions to HW #3 have been posted.

02/25/15   Homework #4 has been posted.

02/20/15   Solutions to homework #2 have been posted.

02/18/15   HW #3: Minor correction on #3a: The domain for n was originally N, but has been corrected to N+.

02/18/15   Homework #3 has been posted.

02/16/15   Solutions to HW #1 have been posted on the class webpage, but you will need a password (that you don't know) to access them. The password will be announced in class.

02/13/15   Please be sure to staple your homework pages together, as specified in the instructions. In the future we will be deducting 5 points from homeworks that are submitted with unstapled pages.

02/13/15   Clarification on HW#2: On problem #5, please do not list separate domains for x and y. For each part, you should specify a finite domain (for x and y) and an infinite domain (for x and y). Similarly, on question #6, when specifying an interpretation please give just one domain for all of the variables. If this is not clear, please drop by TA office hours.

02/11/15   Homework #2 has been posted.

02/04/15   We will use the C.S. Department's grades server for posting grades on assignments. If you are unable to login, let me know.

02/01/15   Homework #1 has been posted. (See the "Assignments" tab.) Please don't attempt the last two questions until after Tuesday's lecture.

01/22/15   Classes officially begin on Monday 1/26, but our discussion session that day is cancelled. Please be sure to attend the first lecture on Tuesday 1/27 and all subsequent class sessions.

01/22/15   All students in this course are required to attend the class (both lecture and discussion) for which they are officially registered. This policy will be strictly enforced.

01/22/15   Welcome to CMSC 250 for the Spring 2015 Semester. Important announcements will appear here as the semester goes on. Be sure to look every day.

Welcome to CMSC 250. This course covers fundamental mathematical concepts related to computer science, including propositional logic, first-order logic, methods of proof, elementary number theory (including sequences, and induction), set theory with finite and infinite sets, functions, relations, introductory counting and probability theory, and an introduction to graph theory. Emphasis will be on mathematical rigor and the development of sound and elegant formal proofs.

Fawzi Emad

Optional Textbook

There is no required textbook for this course and no assignments will refer to a textbook.

For students who like having a textbook as a secondary source of explanations and for practice problems, we recommend "Discrete Mathematics with Applications" by Susanna S. Epp. The book is currently in its 4th edition, but the 2nd or 3rd editions are fine for this course. There are many vendors selling this book online for reasonable prices.

Used books can be very economical, so you might want to find a used copy. You may also find electronic versions of the textbook for less money than a printed copy -- these are fine as well.

Below are links to some of the vendors carrying this book; there are many others, and you may find lower prices from other sources -- shop around. (We are not endorsing any particular sellers.)

Homeworks and Quizzes

There will be numerous homework assignments throughout the semester. The assignments will be posted online, but you are expected to write out your solutions on paper and hand them in at the beginning of class on the designated due date. Write neatly! If your solutions are not legible you will not receive credit for the assignment. Homework assignments are individual work; you may ask questions of us during office hours but may not work with other students on these assignments. Late homeworks will not be accepted.

Quizzes will not be announced, but you can expect them regularly (nearly every week) during your discussion section.

All students must attend the discussion session for which they are registered; any homework or quiz that is handed in during the wrong section will not be graded.

Course Grades

Final grades will be computed according the following weights.

15% Homeworks
15% Quizzes
20% Midterm #1
20% Midterm #2
30% Final Exam

Laptops, Cellphones, and Other Devices

Use of electronic devices (laptops, tablets, cell phones, etc.) will not be permitted during class, unless the student has an accommodation from the Disability Support Services Unit specifically recommending the use of such a device. Students are expected to take notes during class with pencil and paper.

Class Announcements

You are responsible for reading the class announcements that are posted on this webpage. Please check them often (at least once a day). Important information about the course (e.g., deadlines, assignment updates, etc.) will be posted in this section.

Excused Absences
  1. Any student who needs to be excused for an absence from a single class session , due to a medically necessitated absence shall:
    • Make a reasonable attempt to inform the instructor of his/her illness prior to the class. If you are going to miss an in-class assignment (including quizzes or handing in a homework) then we expect to hear from you (either email or a telephone message) before the class session begins. You should contact the instructor, not one of the TAs.
    • Upon returning to the class, present their instructor (not the TA) with a self-signed note attesting to the date of their illness. The note must contain an acknowledgment by the student that the information provided is true and correct. Providing false information to University officials is prohibited under Part 9(h) of the Code of Student Conduct (V-1.00(B) University of Maryland Code of Student Conduct) and will result in disciplinary action.
    • This self-documentation may not be used for the Major Scheduled Grading Events as defined below and it may only be used for 1 class meeting during the course.

  2. Any student who needs to be excused for more than one absence, or for a "Major Scheduled Grading Event", must provide written documentation of the illness from the Health Center or from an outside health care provider. This documentation must verify dates of treatment and indicate the timeframe that the student was unable to meet academic responsibilities. The documentation should be given to the instructor, not the TA. We will not accept a "self-signed" note for "major scheduled grading events", as defined below, nor for multiple absences. The note must be signed by a health care professional.

    The Major Scheduled Grading Events for this course include:
    • Midterm #1
    • Midterm #2
    • Final Exam

Academic Honesty
All assignments/exams must be done individually. Please visit the webpage of the Student Honor Council for a detailed explanation of what constitutes academic dishonesty. Note that it includes not only cheating, fabrication, and plagiarism, but also includes helping other students commit acts of academic dishonesty by allowing them to obtain copies of your work.

Cases of academic dishonesty will be dealt with harshly. Each such case will be referred to the University's Office of Judicial Programs. If the student is found to be responsible of academic dishonesty, the typical sanction results in a special grade "XF", indicating that the course was failed due to academic dishonesty. More serious instances can result in expulsion from the university. If you have any doubt as to whether an act of yours might constitute academic dishonesty, please contact your instructor.

Course Evaluations
Your participation in the evaluation of courses through CourseEvalUM is a responsibility you hold as a student member of our academic community. Your feedback is confidential and important to the improvement of teaching and learning at the University as well as to the tenure and promotion process. Please go directly to the website ( to complete your evaluations. By completing all of your evaluations each semester, you will have the privilege of accessing online, at Testudo, the evaluation reports for the thousands of courses for which 70% or more students submitted their evaluations.

Disability Support Services
Any student eligible for and requesting reasonable academic accommodations due to a disability is requested to provide, to the instructor in office hours, a letter of accommodation from the Office of Disability Support Services (DSS) within the first two weeks of the semester. If special accommodations are to be given for any exam, then the student is also required to schedule the exam and provide to the instructor (before/after class) the form that specifies the scheduled time and date of the requested accommodation. This form must be provided at least four days before the exam. Please note that the time/date of the scheduled exam must overlap with the time/date of the regular in-class exam. You may not schedule the exam at an alternate time or date.
Exam Dates:

Lecture content:
Week 1
Introduction to the course; What is logic?; statements; disjunction, conjunction, negation; interpretations; truth tables; logical equivalence
Lecture Slides
Logical equivalencies; conditional and biconditional connectives; inverse, converse, contrapositive; "sufficient" and "necessary" conditions; arguments
Lecture Slides
Week 2
Checking validity of arguments via truth table; rules of inference; proving arguments; logic gates; circuits; translating truth tables into statements; translating statements into circuits; building an "addition" circuit
Lecture Slides
Predicates and domains, Universal and Existential quantifiers, negating statements, empty domains
Lecture Slides
Week 3
Practice translating English to Predicate Logic; free vs. bound variables; interpretations; rules of inference; closure; Why number theory?; basic definitions
Lecture Slides
Introduction to proofs; constructive proofs; proofs by exhaustion/cases; applying Universal Generalization; styles of proof
Lecture Slides
Week 4
snow More examples; Notation for divisibility; proving implications (directly and via contrapositive); proving equivalence
Lecture Slides
Week 5
Proof by contradiction; "famous" proofs; Fundamental Theorem of Arithmetic
Lecture Slides
Applications of the Fundamental Theorem, Modular Congruence, Modular Arithmetic Theorem
Lecture Slides
Week 6
Quotient-Remainder Theorem, floor and ceiling proofs, review of sequences, summations, and products
Lecture Slides
Week 7
Midterm #1 Introduction to induction; induction proofs with congruences; induction proofs with summations
Lecture Slides
Week 8
Spring Break Spring Break
Week 9
Induction with inequalities, recurrences, etc.; Introduction to strong induction.
Lecture Slides
More examples of strong induction.
Lecture Slides
Week 10
Constructive induction; Set Theory definitions (cardinality, subset, union, intersection, compliment, difference, Venn diagrams, tuples, cartesian product, power set, etc.)
Lecture Slides
Proving subset relationships; Proving set equality; Properties of sets; Venn diagrams for finding counterexamples
Lecture Slides
Week 11
noPower.png Proofs with powersets; partitions; Intro to probability; Multiplication Rule
Lecture Slides
Week 12
Functions; domain, co-domain, range; injection, surjection, bijection; inverse image, inverse function; composition of functions; pigeon hole principle.
Lecture Slides
Generalized pigeon hole principle; using funcions to compare cardinalities; cardinalities of infinite sets; countable vs. uncountable
Lecture Slides
Week 13
Indpendent events; multiplication rule; probabilities with compliments; addition rule; inclusion/exclusion rule; decision trees; probability trees
Lecture Slides
Midterm #2
Week 14
Counting techniques: permutations, combinations, tuples, multi-sets, etc.
Lecture Slides
More pratice with counting and probability
Lecture Slides
Week 15
Relations: binary, ternary, unary, n-ary. Properties of binary relations.
Lecture Slides
Equivalence relations; partial order relations; total relations and total order relations
Lecture Slides
Week 16
[No class this day]

Fawzi Emad
Office: 1201 A.V. Williams
Office Hours: Friday 12:00PM-1:00PM and 3:00PM-4:00PM, Tues 5:00PM-6:00PM

Teaching Assistants
 EmailOffice Hours
Karthik Abinav (See table below)
Aditya Acharya (See table below)
Noam Auslander (See table below)
Brian Brubach (See table below)
Huijing Gong (See table below)
Mahyar Najibikohnebshari (See table below)
Xing Niu (See table below)
Alex Stepanov (See table below)
Adam Sterling (See table below)
Yogarshi Vyas (See table below)

TA Office Hours Schedule

All TA office hours take place in room 1112 A.V. Williams. Please note that a TA may need to leave 5 minutes before the end of the hour in order to go to his/her class. Please be understanding of their schedules.

9:00   Yogarshi   Yogarshi Aditya
10:00 Karthik Karthik Xing Karthik Aditya
11:00 Karthik Noam Aditya Noam  
12:00 Brian   Brian    
1:00 Huijing Alex Brian Alex Mahyar
2:00 Mahyar Xing Mahyar Huijing Huijing
3:00 Yogarshi Xing   Xing Noam
4:00         Noam
Examples from Lecture
Course Tools

Assignment Due date Solutions
Homework #1 Wednesday 02/11 Solutions
Homework #2 Wednesday 02/18 Solutions
Homework #3 Wednesday 02/25 Solutions
Homework #4 Wednesday 03/04 Solutions
Homework #5A Wednesday 04/01 Solutions
Homework #5B Wednesday 04/01 Solutions
Homework #6 Wednesday 04/08 Solutions
Homework #7 Wednesday 04/15 Solutions
Homework #8 Wednesday 04/22 Solutions
Homework #9 Wednesday 05/06 Solutions