Assignment 4: Algorithms and Runtime Complexity

Textbook Exercises

Note that all numbered exercises are from Rosen's Discrete Mathematics and Its Applications, Eighth Edition. If an exercise has multiple parts (e.g., a, b, c, d, etc.), you must complete all of them unless we list specific parts, in which case you only need to complete the listed ones.

Section 3.2

Exercises (2), (8), (12), (14), (22), (26), (34)

Section 3.3

Exercises (2), (4), (16), (18), (20), (42)


Your work must be typed up and uploaded to Blackboard as a PDF by the due date. Please note that hand-drawn diagrams, tables, etc., are not permitted.


Each exercise is graded on a 4-point scale, according to the following rubric:

4 Correct answer with (if needed) a concise, adequate explanation.
3 Correct answer with an incomplete or partially incorrect explanation.
2 Correct answer without (if needed) accompanying explanation, or an incorrect answer with a plausible explanation.
1 Incorrect answer without an explanation, or with a nonsensical explanation
0 Not attempted

If an exercise consists of multiple parts, its point value is the average of all parts graded using the same rubric (rounded to the nearest integer).