# CMSC 250 - Discrete Structures

Class:

Discussions (MW):

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.

## Schedule

### Exam Dates:

• Midterm #1: Tuesday, October 3rd, in Lecture.
• Midterm #2: Tuesday, November 7th, in Lecture.
• Final Exam: Friday, December 15th, 4:00 - 6:00 PM, Location: BRB 1101, IRB 0318, CSI 1122

### Lectures (Tentative)

Week Starting Tuesday Thursday
08/29 Course Intro

Introduction to the course; What is logic?; statements; disjunction, conjunction, negation; interpretations; truth tables; logical equivalence
Logical equivalencies; conditional and biconditional connectives;
09/04 Conditional equivalence contd., biconditional connectives;inverse, converse, contrapositive; "sufficient" and "necessary" conditions; arguments 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
09/11 Predicates and domains, Universal and Existential quantifiers negating statements, empty domains Practice translating English to Predicate Logic; free vs. bound variables; interpretations; rules of inference; closure; Why number theory?; basic definitions,
09/18 Introduction to proofs; direct; contrapositive; contrapositive;contradiction; Equivalence proofs
09/25 constructive proofs; proofs by exhaustion/cases; proving implications (directly and via contrapositive); proving equivalence Midterm Review
10/02 Midterm I Applying Universal Generalization; More proof examples; Notation for divisibility; Fundamental Theorem of Arithmetic , Applications of the Fundamental Theorem
10/09 Modular Congruence, Modular Arithmetic Theorem Proof by contradiction; "famous" proofs; Modular Congruence, Modular Arithmetic Theorem Quotient-Remainder Theorem, floor and ceiling proofs, review of sequences, summations, and products
10/16 Introduction to induction; induction proofs with congruences; induction proofs with summations Induction with inequalities, recurrences, etc.; Introduction to strong induction.
10/23 More examples of strong induction / Constructive Induction Constructive induction /
Set Theory definitions (cardinality, subset, union, intersection, compliment, difference, Venn diagrams, tuples, cartesian product, power set, etc.)
10/30 Proving subset relationships; Proving set equality; Properties of sets; Venn diagrams for finding counterexamples; Proofs with powersets; Intro to Combinatorics (Multiplication rule, permutations) Midterm II Review
11/06 Midterm II r-permutations; probability
11/13 Probability Contd.
11/20 Thanksgiving break
04/27 More pratice with counting and probability,
multi-sets, probability trees;
Functions; domain, co-domain, range; injection,
surjection, bijection; inverse image, inverse function;
12/04 Cardinality, countability
Pigeonhole principle
Pigeonhole principle contd.,
binary relations, reflexive, symmetric , transitive

## Staff

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

Office: IRB 2224
Office Hours:

### Teaching Assistants

Dhruva Sahrawat dhruva7 at umd.edu 0201
Roksana Khanom rkhanom at umd.edu 0202
Sean Michael McLeish smcleish at umd.edu 0203
Elias Prieto eprieto at umd.edu 0204
Nengneng Yu ynn1999 at umd.edu 0205
Jacob Langille jlangill at umd.edu 0206
Zain Ahmed Zarger zzarger at umd.edu 0206
Siyuan Peng peng2000 at umd.edu 0207
Zora Che zche at umd.edu 0208
Geonsun Lee gsunlee at umd.edu

## Office Hours

### Teaching Assistants

Day
Office hours (IRB 1266 Open Area)
Monday Dhruva: 9:00 - 11:00 AM
Roksana: 11:00 AM - 12:00 PM
Yu: 12:00 - 1:00 PM
Roksana / Jacob: 1:00 - 2:00 PM
Yu: 4:00 - 5:00 PM
Tuesday Zora: 9:20 AM - 1:20 PM,
Elias: 1:30 - 2:30 PM
Siyuan: 2:00 - 3:00 PM,
Wednesday Dhruva: 9:00 - 11:00 AM,
Yu / Siyuan: 12:00 - 1:00 PM
Jacob: 1:00 - 2:00 PM
Geonsun: 1:00 - 2:00 PM
Zain: 2:00 - 4:00 PM
Yu: 4:00 - 5:00 PM
Thursday Geonsun: 11:00 AM - 12:00 PM
Elias: 12:30 - 1:30 PM
Sean: 1:00 - 2:00 PM
Sean / Siyuan: 2:00 - 3:00 PM
Friday Sean: 9:00 - 11:00 AM
Roksana: 12:00 - 2:00 PM
Siyuan: 1:00 - 2:00 PM

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.

## Class Resources

Handouts

Online Course Tools
• ELMS - 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.

## Assignments

Homework Due Date*
Homework 1 Thursday Sep. 14, 2023
Homework 2 Monday Sep. 25, 2023
Homework 3 Friday Oct. 13, 2023

*All homeworks/assignments are due at 11:59 PM on the due date.