MATH/EECS 1028: Discrete Math for Engineers

Assignment 5
Due Date: Wednesday, July 30, 2025, before 23:59
Instructions:
Important Reminders
• You must do this assignment individually.
• The assignment must be each individual's own work. While
consultations with the instructor, tutor, and among students are part of
the learning process and are encouraged, nevertheless, at the end of all
these consultations, each student will have to produce an individual
solution/report rather than a copy (full or partial) of somebody else's
report.
• You can submit your solution for this assignment through eClass any time
before 23:59 on Wednesday (July 30, 2025). Your last submission will
overwrite the previous ones, and only the last submission will be graded.
• The deadline is strict with no excuses: you receive 0 for not making your
electronic submission in time. Emailing your solutions to the instructors
or TAs will not be acceptable.
• As you recall, the concept of late assignments does not exist in this
course.
• To submit your solution, you need to use the York eClass. Submission must
be a SINGLE pdf standalone file to eClass.
• The maximum file size is 10MB.
• Ensure your answers to the given questions in this assignment are clearly
written
• The assignment can be handwritten or typed. It MUST be legible.
• Your handwriting significantly affects how your work is understood
and evaluated. If an answer is not clear or difficult to read, it can be
challenging to be graded accurately.
• You will receive a zero if your solution is not organized and
hard to read by TAs.

Page 1 of 4
 MATH/EECS 1028: Discrete Math for Engineers
Assignment 5
Due Date: Wednesday, July 30, 2025, before 23:59
• Your answers should be precise and concise. Points may be deducted for
long, rambling arguments.
Marking will be done on a continuum using the following criteria per
question:
• 0% = Does not meet criterion or completely wrong answer (i.e., your
answer contains major errors)
- For example, you did not answer the question or provide an
insufficient/short answer to the question.
• 50% = Demonstrates moderate skill in meeting the criterion of the
correct answer
- For example, you answered the question and leveraged course
content in the answer.
• 100%= Demonstrates mastery of the course content, and your answers
reflect a deep understanding of the course content.
- For example, you answered the question, leveraged the course
content in your answer, and provided a complete and correct
answer.
• You must develop and submit a complete and correct solution for this
assignment. Hence, you must take a reasonable amount of time to verify
and review your solution for this assignment in different ways.

Academic Honesty
• Students are expected to read the Senate Policy on Academic Honesty. See
also the EECS Department Academic Honesty Guidelines.
• All Assignments are to be completed individually: no group work is
allowed. Do not discuss solutions with anyone other than the instructor or
the TAs. Do not copy or look at specific solutions from the net. If you are
repeating the course, you are not allowed to submit your own solution
developed in previous terms or for other purposes. You should start from
scratch and follow the instructions.

Page 2 of 4
 MATH/EECS 1028: Discrete Math for Engineers
Assignment 5
Due Date: Wednesday, July 30, 2025, before 23:59
Question 1. (10 Marks) In a secure system, users must create passwords for their accounts. The
passwords must follow the following rules:
• The password length must be between 4 and 6 characters, inclusive.
• Each character in the password can be a lowercase letter (a-z), a digit (0-9), or one of
the special characters {!, @, #, $, %, ^, &, *}.
• Each password must contain at least the following:
o One lowercase letter
o One digit
o One special character from the set {!, @, #, $, %, ^, &, *}.
Determine the total number of valid passwords that can be generated under these rules.

Question 2. (10 Marks) In a group of 𝑛𝑛 words, at least four words must start with the same
letter. What is the smallest value of 𝑛𝑛 that guarantees this property?

Question 3. (10 Marks) How many 8-bit strings consist of exactly four consecutive 0s or four
consecutive 1s?

Question 4. (16 Marks) For each of the following relations on the set of all real numbers,
determine whether it is reflexive, symmetric, antisymmetric, or transitive. Here 𝑥𝑥𝑥𝑥𝑥𝑥 if and
only if:
(a) 𝑥𝑥 + 2𝑦𝑦 = 0
(b) 𝑥𝑥 = 2𝑦𝑦
(c) 𝑥𝑥 − 𝑦𝑦 is a rational number
(d) 𝑥𝑥𝑥𝑥 = 0
(e) 𝑥𝑥𝑥𝑥 ≥ 0
(f) 𝑥𝑥 = 1 or 𝑦𝑦 = 1
(g) 𝑥𝑥 is a multiple of 𝑦𝑦
(h) 𝑥𝑥𝑥𝑥 = 1

Question 5. (14 Marks) Determine the matrix which represents the transitive closures of the
following relations on the set {𝑎𝑎, 𝑏𝑏, 𝑐𝑐, 𝑑𝑑, 𝑒𝑒}
(a) {(𝑏𝑏, 𝑐𝑐), (𝑏𝑏, 𝑒𝑒), (𝑐𝑐, 𝑒𝑒), (𝑑𝑑, 𝑎𝑎), (𝑒𝑒, 𝑏𝑏), (𝑒𝑒, 𝑐𝑐)}
(b) {(𝑎𝑎, 𝑏𝑏), (𝑎𝑎, 𝑐𝑐), (𝑎𝑎, 𝑒𝑒), (𝑏𝑏, 𝑎𝑎), (𝑏𝑏, 𝑐𝑐), (𝑐𝑐, 𝑎𝑎), (𝑐𝑐, 𝑏𝑏), (𝑑𝑑, 𝑎𝑎), (𝑒𝑒, 𝑑𝑑)}

Page 3 of 4
 MATH/EECS 1028: Discrete Math for Engineers
Assignment 5
Due Date: Wednesday, July 30, 2025, before 23:59
Question 6. (16 Marks) List all possible relations on the set {0,1} and determine which of these
relations are
(a) reflexive
(b) symmetric
(c) antisymmetric
(d) transitive

Question 7. (14 Marks) Give the equivalence classes of the relation

Question 8. (10 Marks) Are the relations represented by the following matrices equivalence
relations?

1 0 1 0
0 1 0 1
(a) � �
1 0 1 0
0 1 0 1

1 1 1 0
1 1 1 0
(b) � �
1 1 1 0
0 0 0 1

Page 4 of 4