back to Home Page

Update page--Discrete Structures-Fall 2025 Welcome!
Here you will see info about what we did in class, upcoming exams, solutions for past exams, etc.,
CHECK AT LEAST ONCE A WEEK!!

COURSE PAGE WITH SYLLABUS, GRADING SCHEME ETC

Notes and exams from fall 2017.

TUTORING SCHEDULE





NOTE: We will have a quiz on Nov 24 (monday of thanksgiving week).
MIDTERM TEST II FRIDAY NOV 7 ; REVIEW Wednesday Nov 5
Covering 2.5, 3.1, 3.2, 3.3, 3.4, 6.1, 6.2, 6.3 strong induction, functions, relations, counting methods including permutations and combbinations.
STUDY CLASS NOTES, CLASSWORK NOTES, QUIZ SOLUTIONS, PRACTICE PROBLEMS POSTED HERE EVERYDAY
For strong induction do problems 1,2,3 in 2.5 and the problems in the notes.

ALSO: FALL 2017 Test I Solutions, only 7.
FALL 2017 Test II Solutions, 1,2,3.
FALL 2017 Test III Solutions, only 4 and 5.
Fall 2017 test 3 review, only 7, 8, 9, 10

Tutoring schedule posted above.

11/3/2025 Monday
Today we talked about generalized permutations and combinations.
Notes and Classwork from today on generalized permutations and combinations.
Please also read the sections on permutations and combinations in these notes.
Please try these problems on generalized permutations and combinations. (From 8th edition ; Make sure you are doing same kind of problems as in notes above).
6.3: 1, 4, 7, 10, 17, 18, 21, 39, 42, 45, 48.

11/1/2025 Saturday
Pleae read quiz solutions.
QUIZ VII Version 1 PROBLEMS.
QUIZ VII Version 1 Solutions.
QUIZ VII Version 2 PROBLEMS.
QUIZ VII Version 2 Solutions.

10/29/2025 Wednesday
QUIZ 7 friday, Oct 31 on counting methods and permutations and combinations (6.1 and 6.2 in 8th ed).
Today we talked about permutations and combinations.
Notes and Classwork from today on permutations and combinations.
Please also read the sections on permutations and combinations in these notes.
Please try these problems on permutations and combinations. (From 8th edition ; Make sure you are doing same kind of problems as in notes above).
6.2: 1, 4, 7, 10, 30, 60, 63, 65, 68.

10/27/2025 Monday
QUIZ 7 friday, Oct 31 on counting methods and permutations and combinations (6.1 and 6.2 in 8th ed).
Today we talked about counting methods and number of ways to do things.
Notes and Classwork from today on number of ways to do things.
Please try these problems on number of ways to do things. (From 8th edition ; Make sure you are doing same kind of problems as in notes above).
6.1: 1, 7, 10, 13, 19, 37 to 43, 70, 73, 99.

10/22/2025 Wednesday
Pleae read quiz solutions.
QUIZ VI Version 1 PROBLEMS.
QUIZ VI Version 1 Solutions.
QUIZ VI Version 2 PROBLEMS.
QUIZ VI Version 2 Solutions.

10/20/2025 Monday
QUIZ 6 wednesday, Oct 22 on sequences and strings (3.2 in 8th ed) equivalence relations and equivalence classes (3.4 in 8th ed).
Today we talked about sequences and how to write sums of sequences. We also reviewed equivalence classes.
Please also read about strings from textbook (3.2 in 8th ed).
Please read these notes on sequences.
Please read about equivalence classes and partitions in these notes on relations and functions.
Classwork from today.
Please try these problems in addition to ones from monday. (From 8th edition ; Make sure you are doing same kind of problems as in notes above).
3.2: 45, 50, 53, 55, 111, 138, 146.

10/18/2025 Saturday
QUIZ 6 wednesday, Oct 22 on sequences and strings (3.2 in 8th ed) equivalence relations and equivalence classes (3.4 in 8th ed).

Yesterday we talked about equivalence relations and equivalence classes.
Please read Notes on Relations (same as for Proofs class).

Please try these problems. (From 8th edition ; Make sure you are doing same kind of problems as in notes above).
3.4: 4, 7, 10, 11, 14, 20, 32 (worked out in notes), 43.

10/15/2025 Wednesday
Pleae read quiz solutions.
QUIZ V Version 1 PROBLEMS.
QUIZ V Version 1 Solutions.
QUIZ V Version 2 PROBLEMS.
QUIZ V Version 2 Solutions.

10/10/2025 Friday
QUIZ 5 wednesday, Oct 15 on relations, functions and reflexivity etc.
Today we talked about inverse functions and reflexivity, symmetry, antisymmetry and transitivity.
Please read about functions in these notes on relations and functions.
Classwork from today.
Please try these problems in addition to ones from previous days. (From 8th edition ; Make sure you are doing same kind of problems as in notes above).
3.3: 24, 27, 30, 33, 35.

10/9/2025 Thursday
QUIZ 5 wednesday, Oct 15 on relations, functions and reflexivity etc.,
Yesterday we started with functions.
Please read about functions in these notes on relations and functions.
Please try these problems in addition to ones from previous days. (From 8th edition ; Make sure you are doing same kind of problems as in notes above).
3.1: 8, 11, 17, 20, 29, 30, 43, 46.

10/7/2025 Tuesday
Pleae read quiz solutions.
QUIZ IV Version 1 PROBLEMS.
QUIZ IV Version 1 Solutions.
QUIZ IV Version 2 PROBLEMS.
QUIZ IV Version 2 Solutions.

10/5/2025 Sunday
QUIZ IV MONDAY 10/6, on strong induction.

Friday we did more problems on proofs by strong induction, and talked about Egyptian fractions.
Notes on Proof by induction (Updated! Try some of the exercises in it!)
Practice problems:
Show using regular induction that, if you add the first n Fibonacci numbers, you get one less than the n+2-th Fibonacci number.
For example, 1+1+2+3 = 7, and 7 = 8-1.

For your information: The postage stamp problem is also known as the Coin problem or the Chicken McNugget problem.
Here is a Wikipedia article about it.
FACT: If the positive integers x and y have no common factors, all numbers bigger than xy-x-y (but not xy-x-y itself!) can be expressed using x and y.

Here is nice write-up by Nam Nguyen of Williams College on Egyptian fractions.
It contains the proof that the "greedy algorithm" for writing Egyptian fractions works.
Can you tell where he uses strong induction? Actually, he avoids it. How?

10/1/2025 Wednesday
QUIZ IV NEXT MONDAY.

Today we discussed proofs by strong induction.
Notes on Proof by induction from 2020 (Try some of the exercises in it!)
Practice problems:
Show using regular induction that, if you add the first n Fibonacci numbers, you get one less than the n+2-th Fibonacci number.
For example, 1+1+2+3 = 7, and 7 = 8-1.


9/29/2025 Monday
QUIZ IV NEXT MONDAY.

Today we did more exercises on proofs by induction.
Please go over the notes and the classwork and try the problems mentioned below:
Classwork on proofs by induction.
Notes on Proof by induction from 2019 (Try some of the exercises in it!)
Practice problems:
2.4: 2, 4, 13, 22, 28, 30.

9/27/2025 Saturday
Pleae read midterm exam solutions.
MIDTERM I Version 1 PROBLEMS.
MIDTERM I Version 1 Solutions.
MIDTERM I Version 2 PROBLEMS.
MIDTERM I Version 2 Solutions.

MIDTERM TEST I FRIDAY SEP 26 ; ALL OF CHAPTERS 1 & 2 (BOTH 7TH & 8TH ED) EXCEPT 2.3 and 2.5 (resolution proofs and strong induction)
STUDY CLASS NOTES, CLASSWORK NOTES, QUIZ SOLUTIONS, PRACTICE PROBLEMS POSTED HERE EVERYDAY
ALSO: FALL 2017 Test I Solutions, all except 7
Fall 04 Test I (all except 4b and 5)
Fall 06 Test I (all except 7)

9/22/2025 Monday
Tutoring schedule posted above.
Today we did proofs by cases and by induction.
Please go over the notes and the classwork and try the problems mentioned below:
Classwork on proofs by cases and induction.
Notes on Proofs from 2017
Notes on Proof by induction from 2019
Notes on Proof by cases and direct proofs from 2019
Practice problems:
2.2 : 26, 27, 42, 46.
2.4: 2, 4, 13, 22.

9/17/2025 Wednesday
Pleae read quiz solutions.
QUIZ III Version 1 PROBLEMS.
QUIZ III Version 1 Solutions.
QUIZ III Version 2 PROBLEMS.
QUIZ III Version 2 Solutions.

9/15/2025 Friday
Midterm exam coming up on Sep 26. Details soon.
QUIZ 3 WED, on nested quantifiers and proofs.

Today we did more exercises on proofs.
Please go over the notes and the classwork and try the problems in the classwork:
Notes on Proofs from 2017
Classwork on proofs by contrapositive etc (Updated, Reload).
Practice problems: 2.1 : 10, 13, 16, 18, 21, 24.

9/12/2025 Friday
Midterm exam coming up on Sep 26. Details soon.
Today we did more exercises on nested quantifiers and started talking about proofs.
Please go over the notes and the classwork and try the problems in the classwork:
Notes on Proofs from 2017
Notes on quantifiers.
Classwork on nested quantifiers and proofs (Updated, Reload).
Practice problems: 2.1 : 10, 13, 16, 18, 21, 24.

9/10/2025 Wednesday
Tutoring schedule posted above. Midterm exam coming up on Sep 26. Details soon.
Today we went over nested quantifiers.
Please go over the notes and the classwork and try the problems in the classwork:
Notes on quantifiers.
Classwork on nested quantifiers.

9/8/2025 Monday
Pleae read quiz solutions.
QUIZ II Version 1 PROBLEMS.
QUIZ II Version 1 Solutions.
QUIZ II Version 2 PROBLEMS.
QUIZ II Version 2 Solutions.

9/3/2025 Wednesday
Tutoring schedule posted above.
QUIZ MONDAY 9/8 on 1.3, 1.4, 1.5 (converse, contrapositive, arguments, counterexample, quantifiers)

Today we went over arguments and quantifiers.
Please go over the notes and try the problems below:
Notes on quantifiers.
Notes on set theory and logic (Updated, please reload!).
Exercises we did in class today.
Try problems 39, 43, 49, 50, 55, 76 in section 1.5.

9/3/2025 Wednesday
Today we went over converse and contrapositive and arguments.
Please go over the notes and try the problems below:
Notes on set theory and logic (Updated, please reload!).
Try problems 15, 18 and 30 from 1.4.
Also, check the following statement for validity. Justify your answer:
Either a number is not prime or it is equal to 1.
The number is not equal to 1.
Therefore it is a prime number.


8/31/2025 Sunday.
On friday we went over quiz and talked about converse and contrapositive.
Please go over the notes and try the problems below:
Notes on set theory and logic (Updated, please reload!).
Try problems 39 and 42 from 1.3.
Also, write the following statement, its converse, and its contrapositive both in symbols and in words:
If you run 10 laps daily, your health will improve.

8/28/2025
Pleae read quiz solutions.
QUIZ I Version 1 PROBLEMS.
QUIZ I Version 1 Solutions.
QUIZ I Version 2 PROBLEMS.
QUIZ I Version 2 Solutions.

8/25/2025
QUIZ 1 WEDNESDAY 8/27 ON WHAT WE COVER UNTIL THEN.

Today we started talking about logical statements and DeMorgan's laws of logic. They are all mentioned either in the notes or in the classwork linked below.
Notes on set theory and logic (Updated, please reload!).
Please read section 1 of the textbook on basic notions of sets and do the following exercises:

(mostly the ones marked in blue ; the exercises are about logical operations and symbolic notation) :
1.2: 16, 20, 23, 37, 56, 59.
1.3: 73, 76.

8/22/2025
QUIZ 1 WEDNESDAY 8/27 ON WHAT WE COVER UNTIL THEN.

Today we went over some exercises in set theory. They are all mentioned either in the notes or in the classwork linked below.
Notes on set theory and logic (Updated, please reload!).
Exercises we did in class today.
Please read section 1 of the textbook on basic notions of sets and do the following exercises:

(mostly the ones marked in blue ; the exercises are about set operations such as union, intersection, etc.,) :
1.1: 1, 4, 7, 10, 13, 16, 17, 23, 35, 47, 61-65, 68, 93.

8/20/2025
Today we introduced logic and set theory. We talked about Russell's paradox, how Euclid's parallel lines postulate (that they never intersect) could not be proved and became an an axiom, and basic set theory.
Notes from class today on set theory and logic .
Please read section 1 of the textbook on basic notions of sets and do as many exercises as you can.

(Optional) Extra reading related to class:
Here is a How Russell's paradox means there is no set contining all sets
Note on Russell's paradox from 2017.
This note contains its definition, history, and an example using web search principles.

Terry Tao's talk on machine learning and mathematical proofs.

The Dunning-Kruger effect which is about people not knowing what they don't know.

8/18/2025
Today we only introduced each other and talked about class. Please go to Canvas and upload unofficial transcript under Quiz 0.
Read the notes from first class of 2017 if you can.


Started 8/13/2025
Notes from first class of Fall 2017 below.
WARNING: What we do this semester will be substantially different from Fall 2017. I will point out where they are different.

Notes from first class of fall 2017.
Please read the following to get started on the course:
Note on Russell's paradox
This note contains its definition, history, an example using web search principles, and the Barber of Seville example. I compiled it from various web-sites