Problem Set 1
Collaboration Policy - Read Carefully
Remember to follow the course pledge you read and signed at the beginning of the semester. For this assignment, you may discuss the problems and work on solutions with anyone you want (including other students in this class), but you must write your own solutions and understand and be able to explain all work you submit on your own. To confirm your own understanding, after discussing the problems with others, you should attempt to write your solutions on your own without consulting any notes from group work sessions. If you get stuck, you may visit notes from the group work sessions, but should make sure you understand things well enough to produce it on your own. You may also use any external resources you want, with the exception of solutions and comments from last year’s offering of this course. Since the staff and students benefit from being able to both reuse problems from previous years, and from being able to provide detailed solutions to students, it is important that students do not abuse these materials even if it is easy to find them. Using solutions from last year’s course would be detrimental to your learning in this course, and is considered an honor violation.
If you use resources other than the class materials, lectures and course staff, you should document this and mention it clearly on your submission. For everyone other than the course staff you work with, you should credit them clearly on your assignment, and should find out something interesting about their family history (you shouldn’t include this in your submission, though, especially if they share something private with you).
You are strongly encouraged to start early and take advantage of the scheduled office hours for this course.
Preparation
This problem set focuses on Chapter 1 of the MCS book, and Class 1 and Class 2.
Directions
Solve all the problems on the next page. For full credit, your answers should be correct, clear, well-written, and convincing.
Proofs and Certification
The introduction for the MCS book states,
“Proofs also play a growing role in computer science; they are used to certify that software and hardware will always behave correctly, something that no amount of testing can do.”
The statement suggests “no amount of testing can certify software will always behave correctly”. Is this claim valid or invalid? Support your answer with a short justification.
The statement suggests “proofs can certify that software will always behave correctly”. Argue that this is not a correct statement.
Inference Rules
For each candidate rule below, state whether or not the rule is sound. Support your answer with a convincing proof. The variables $P$, $Q$, and $R$ are Boolean propositions (either true or false).
$\infer{R}{P \implies Q, Q \implies R}$
$\infer{P}{(NOT(NOT(P)))}$
$\infer{Q \implies P}{P \implies Q}$
$\infer{NOT(Q) \implies P}{P}$
$\infer{Q \implies NOT(P)}{P \implies NOT(P)}$
Proofs
The proof that $\sqrt{2}$ is irrational (Theorem 1.8.1) in the book includes relies on this implication: $d^2$ is a multiple of two implies $d$ is a multiple of 2. Prove that this is a valid implication to a skeptical reader.
Problem 1.4 (parts a, b, and c) from the MCS book.
Prove that for any non-negative real numbers, $x$ and $y$, if $xy = n$ then the minimum of $x$ and $y$ is not greater than $\sqrt{n}$. (Hint: prove by contradiction.)