Problem Set 1

\dbox{{\bf Deliverable:} Submit your responses as a single PDF file on the collab site before {\bf 6:29pm} on {\bf Friday, 2 September}. The PDF you submit can be a scanned handwritten file (please check the scan is readable), or a typeset PDF file (e.g., generated by LaTeX or Word).}

Deliverable: Submit your responses as a single PDF file on the collab site before 6:29pm on Friday, 2 September. The PDF you submit can be a scanned handwritten file (please check the scan is readable), or a typeset PDF file (e.g., generated by LaTeX or Word).

Collaboration Policy - Read Carefully

For this assignment, you may work in groups of one to three students, so long as all members of a group were born at least 100 kilometers apart. (That is, if you work in a group of 3, no two of you may have been born within 100 km of each other.) If you work with teammates, you should submit one assignment that represents your collective best work with all of your names and UVA ids on it. Everyone on a team should understand everything you turn in for the assignment well enough to be able to produce it completely on your own. You are encouraged to use the #teaming channel to find suitable teammates.

You may discuss the assignment with anyone you want and get help from others, so long as it is help in the spirit of learning how to do things yourself not getting answers you don’t understand.

Remember to follow the course pledge you read and signed at the beginning of the semester. For this assignment, you may consult any outside resources you want, including books, papers, web sites and people. You may consult an outside person (e.g., another friend who is a CS major but is not in this class) who is not a member of the course staff, but that person cannot type anything in for you and all work must remain your own and outside sources should never give you specific answers to problem set questions. If you use resources other than the class materials, lectures and course staff, you should document this clearly on your submission.

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.

Download PDF for Problems.

Your response should be submitted as a single PDF file using collab: submission link

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.

$\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}$

Proofs

Prove rigorously that if $x + y$ is even and $x$ is odd, $y$ must be odd. (For this proof, you should be more rigorous than will be expected on most proofs in cs2102, showing all of the steps and justifying each step, similar to the level of rigor from the proof in Class 2.)
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.)