CMSC 250 - Discrete Structures

Class:

Discussions:

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.

Class Announcements

• 05/02/2019
• Hw 9 posted.

• 04/25/2019
• Hw 8 posted.

• 04/18/2019
• Hw 7 posted.

• 04/05/2019
• Hw 6 posted.

• 03/28/2019
• Hw 5 posted.

• 03/15/2019
• Hw 4 posted.

• 03/06/2019
• Hw 3 posted.

• 02/13/2019
• Hw 2 posted.

• 02/02/2019
• Hw 1 posted.

• 1/21/2019
• This is the class webpage for CMSC250, sections 020X only. Please check here often (at least once a day) for important class announcements.

Schedule

Exam Dates:

• Midterm #1: Thursday, February 28th, in Lecture.
• Midterm #2: Thursday, April 11th, in Lecture.
• Final Exam: Saturday, May 18th, 4:00 - 6:00 PM, Location: IRB 0324

Lectures (Tentative)

Week Starting Tuesday Thursday
01/29 Course Intro

Introduction to the course; What is logic?; statements; disjunction, conjunction, negation; interpretations; truth tables; logical equivalence

Introduction
Lec01-Examples
Logical equivalencies; conditional connectives; "sufficient" and "necessary" conditions;

Lec02
Lec02-Examples
02/05 biconditional connectives; inverse, converse, contrapositive; arguments Checking validity of arguments via truth table; rules of inference; proving arguments;

Lec03
Lec03-Examples
logic gates; circuits; translating truth tables into statements; translating statements into circuits; building an "addition" circuit

Lec04
Lec04-Examples
02/12 Predicates and domains, Universal and Existential quantifiers, negating statements, Practice translating English to Predicate Logic;

Lec05
Lec05-Examples
truth and falsity of predicates; empty domains, interpretations; translations; negations; rules for negations;

Lec06
Lec06-Examples
02/19 rules of inference; closure; Why number theory?; basic definitions, Introduction to proofs; direct proofs; contrapositive proof;

Lec07
contrapositive proof More examples; proving implications (directly and via contrapositive); proving equivalence Proof by contradiction;

Lec08
Lec08-Examples
02/26 Review

Lec09-Review
Lec09-Examples
Midterm I
03/05 Proofs of Equivalence; constructive proofs;proofs by exhaustion; Proofs by cases; Constructive proofs of existence;

Lec10
Lec10-Examples
Proofs by Universal generalization, divisibility, Fundamental Theorem of Arithmetic, Applications of the Fundamental Theorem,

Lec11
Lec11-Examples
03/12 Modular Congruence, Modular Arithmetic Theorem, Quotient-Remainder Theorem, floor and ceiling proofs, Introduction to sequences.

Lec12
Lec12-Examples
Review of sequences, summations, and products; Introduction to induction;

Lec13
03/19 Spring Break
03/26 Induction proofs with congruences; induction proofs with summations

Lec14
Lec14-Examples
Induction with inequalities, recurrences, etc.; Introduction to strong induction, Examples of strong induction.

Lec15
Lec15-Examples
04/02 More examples of strong induction, Introduction to Constructive induction

Lec16
Lec16-Examples
Constructive Induction examples; Introduction to set theory; definitions (cardinality, subset, etc.)

Lec17
Lec17-Examples
04/09 Review

Lec18-review
Lec18-review-Examples
Midterm II
04/16 Set Definitions Contd. (union, intersection, compliment, difference, Venn diagrams, tuples, cartesian product, power set, etc.) Proving subset relationships; Proving set equality; Properties of sets; Venn diagrams for finding counterexamples

Lec19
Lec19-Examples
proofs with rule sheet for set equality; Venn diagrams for counter examples; Proofs with powersets; partitions; Intro to Combinatorics; Multiplication Rule; permutations

Lec20
Lec20-Examples
Lec21
04/23 r-permutations, combinations, Introduction to discrete probability
Lec22a (P(n,r) and n choose r)
Lec22b (discrete probability)
Joint Probability, Indpendent events; Disjoint events; multiplication rule; probabilities with compliments; addition rule; inclusion/exclusion rule; decision trees;
Lec23
04/30 multi-sets, probability tree,pigeonhole principle.
Lec24
Lec24-examples
pigeonhole principle
Functions; domain, co-domain, range; injection, surjection, bijection; inverse image, inverse function; composition of functions;
Lec25
Lec25-examples
05/07 Cardinality of infinite sets, countable, uncountable
Lec26
Lec26-examples
Relations: binary, ternary, unary, n-ary. Properties of binary relations;
Lec27
Lec27-examples
05/14 Equivalence relations,partial order relations; total relations and total order relations
Lec28
Lec28-examples

Staff

Instructor: Mohammad Nayeem Teli (nayeem at cs.umd.edu)

Office: 1351 AV Williams
Office Hours: TuTh 1:00 - 2:00 PM

Teaching Assistants

Name Email Responsibilities
Seyed Esmaeili esmaeili@cs.umd.edu Discussion Lead (0202/0203)
Anthony Ostuni anthonyjostuni@gmail.com Discussion Lead (0201)

TA Office Hours

All TA office hours take place in room 1124 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.

Time MON TUE WED THU FRI
9:00 - 10:00
10:00 - 11:00 Seyed Dantong Hamed
11:00 - 12:00 Seyed Dantong
12:00 - 1:00 Hamed Seyed Hamed
1:00 - 2:00 Hamed Dantong Seyed Anthony
2:00 - 3:00 Jue Dantong Jue Anthony
3:00 - 4:00 Jason
4:00 - 5:00 Jason
5:00 - 6:00

Class Resources

Handouts

Online Course Tools
• Grades Server - This is where you go to see grades on assignments and to get your class account information.
• Gradescope - This is where you submit yout homeworks and receive feedback.

Homeworks

Homework Due Date
Homework 1 11:59 PM, Tuesday, February 12, 2019
Homework 2 11:59 PM, Wednesday, February 20, 2019
Homework 3 11:59 PM, Wednesday, March 13, 2019
Homework 4 11:59 PM, Thursday, March 28, 2019
Homework 5 (pdf,tex) 11:59 PM, Thursday, April 04, 2019
Homework 6 (pdf,tex) 11:59 PM, Thursday, April 18, 2019
Homework 7 (pdf,tex) 11:59 PM, Thursday, April 25, 2019
Homework 8 11:59 PM, Thursday, May 2, 2019
Homework 9 11:59 PM, Thursday, May 9, 2019