Math 21:640:237:01 (Discrete Structures)
Math 21:640:237:01 (Discrete Structures)
Professor Feighn
UPDATED: December 7, 2017
OFFICE HOURS: Tuesday, 2:003:00PM and Thursday, 8:459:45AM,
or by appointment, in Smith 318
OFFICE PHONE: 9733535335
EMAIL: feighn@rutgers.edu
CLASS TIMES: 11:30AM12:50PM, Tuesday and Thursday in Engelhard 215
COURSE DESCRIPTION: Sets, relations, functions, graphs, trees, formal expressions, mathematical induction, and some algebraic structures; applications to probability and computer science and enumerative problems in combinatorial analysis. This course covers the fundamental abstract algebraic structures and concepts most often employed in computer science and probability and statistics. The ideas involved are simple, but elegant and useful and the course aims to convey some of the beauty of mathematics as well as its utility. The course integrates theory and practical applications.
PREREQUISITE: 21:640:119 (Basic Calculus), or 21:640:135 (Calculus I), or 21:640:155 (Honors Calculus I).
NOTE: Discrete Structures is required for CS majors. It NOT required for CS minors or IS majors, who can take 21:198:251 Computer Organization instead. Also, Discrete Structures does not count for credit for the math major. Math majors should take 21:640:238 (Foundations) instead.
TEXTBOOK:
Discrete Mathematics (8th Edition) by Johnsonbaugh
GRADING:

2 midterms 20% each:
 Test 1: Thursday, October 5
 Test 2: Thursday, November 9

quizzes 20% total

final exam 40% total
 3PM6PM, Friday, December 15, Engelhard 215
DEPARTMENT WEB SITE: http://www.ncas.rutgers.edu/math
DEFINITIONS: You will be responsible for the definitions of important terms introduced in this course. A partial list can be found here.
THIS COURSE COVERS THE FOLLOWING CHAPTERS AND SECTIONS (subject to change):

CHAPTER 1: Sets and Logic
 1.1 Sets
 9/5: 5, 12, 30, 31, 45, 65, 84, 8792, 93
 1.2 Propositions
 9/7: 13, 21, 23, 28, 32, 38, 46, 5055,
 1.3 Conditional Propositions and Logical Equivalence
 9/7: 5, 15, 21, 28, 37, 52, 54, 64
 1.4 Arguments and Rules of Inference
 9/12: 5, 10, 15, 20, 25, 27, 30
 1.5 Quantifiers
 9/12: 6, 10, 29, 34, 44, 54, 59 quiz 1
 1.6 Nested Quantifiers
 9/17: 4, 5, 6, 23, 29, 36, 46, 54, 66

CHAPTER 2: Proofs

2.1 Proofs and Counterexamples

2.2 More Proof Methods
 9/21: 1, 7, 8, 9, 29, 32, 48

2.4 Mathematical Induction

2.5 Strong Induction

CHAPTER 3: Functions

3.1 Functions
 10/12: 813, 17, 23, 31, 43, 46, 49, 51

3.2 Sequences and Strings
 10/17: 2, 12, 16, 25, 32, 36, 45, 57, 117, 138

3.3 Relations
 10/19: 3, 6, 11, 13, 18, 19, 28, 30, 32, 34, 40, 44, 46, 52 (Note: In 2434, consider only the properties reflexive, symmetric, and transitive.)
quiz 3

3.4 Equivalence Relations
 10/24: 1, 3, 5, 11, 13, 17, 19, 23, 24, 25, 27
quiz 4

3.5 Matrices of Relations
 10/31: 1, 4, 8, 12 (reflexive, symmetric, transitive only), 13, 15, 17

CHAPTER 4: Algorithms

4.1 Introduction

4.2 Examples

4.3 Analysis of Algorithms
 11/16: 1, 5, 10, 12, 14, 15, 18, 21, 24, 25

4.4 Recursive Algorithms
 11/21: 1, 3, 8, 9, 11, 13

CHAPTER 7: Recurrence Relations

7.1 Introduction
 11/28: 1, 13, 14, 15, 16, 25, 30, 52 quiz 6

7.2 Solving Recurrence Relations

7.3 Analysis of Algorithms
 12/7: 2, 12, 19, 40, 41, 42, 51, 52, 53, 54

CHAPTER 6: Counting Methods (lightly covered)

6.1 Basics

6.2 Permutations and Combinations

6.3 Generalized Permutations and Combinations

6.4 Algorithms

6.5 Introduction to Discrete Probability

6.6 Discrete Probability

6.8 Pigeonhole Principle

CHAPTER 5: Number Theory (if time permits)

CHAPTERS 8, 9: Trees and Graphs (if time permits)