CS 70 Discrete Mathematics and Probability TheorySummer 2011 Kamil HW 1Due Wednesday, June 22, 4:59pmYou may work in groups of up to 4 people (no larger!). Please read the group collaboration policies on thecourse website at http://www.cs.berkeley.edu/~kamil/cs70/ before beginning group work.You must write up the solution set entirely on your own. You must never look at any other students’ solutions(not even a draft), nor share your own solutions (not even a draft).Please put your answer to each problem on its own sheet of paper. Label each sheet of paper with yourname, class account (cs70-??), student ID, section number (101 or 102), the assignment number, the problemnumber, and “CS70–Summer 2011.” Turn in your homework in the boxes labeled “CS70” on the 2nd floorof Soda Hall. Submit each problem separately in its appropriate box (i.e., your answer to question i goesinto CS 70 drop box i). Failure to follow these instructions may cost you points, or cause you to receive nocredit at all.You don’t need to explain your answer to any of the questions on HW1. Note that this homework is dueat 4:59pm on Wednesday.1. (43 pts.) Getting Started(a) You get an automatic 8 points for following directions (e.g., labelling every sheet of paper with yourname and section, turning them in to the right box).(b) What has four wheels and flies?The answer is found on the Piazzza forum for CS 70. Look for the message from Amir Kamil titled“The answer to question 1b,” and write down the answer you find there.(Why are we having you do this? The Piazzza forum is the best way to get clarifications on homeworks,ask for help with topics from lecture that are confusing, etc. We want you to be familiar with how toaccess the Piazzza forum.)(c) What’s brown and sticky?You can find the answer by logging into your class account and executing the following command:more ∼cs70/q1cYou can find instructions on how to login to your class account on Piazzza.(d) When are the midterm and final exams for CS70 this summer? You can find the answer on the coursewebsite.(e) What is the name of your TA? What is the name of the other TA?(f) Two CS 70 students Alice and Bob decide to work in a group. They collaborate to figure out howto solve every question on the homework. Then, they split up the questions: Alice writes down theanswers they came up with for questions 1 and 2, Bob writes down the answers they came up with forquestions 3 and 4, and then they swap these papers and use them to finish their writeups. Under the CS70 collaboration policy, is this OK, assuming they worked together on figuring out how to solve eachquestion?CS 70, Summer 2011, HW 1 12. (27 pts.) ImplicationsWhich of the following implications is true?(a) If 3 +4 = 5 then 32+ 42= 52.(b) If 3 +4 = 7 then 32+ 42= 52.(c) If 3 +4 = 5 then 32+ 42= 72.(d) If 3 +4 = 7 then 32+ 42= 72.(e) If any of this semester’s CS 70 students are award-winning violinists, then 1 + 1 = 2.(f) If Los Angeles is the state capital of California, then the trillionth digit of π is 7.In part 6, π = 3.14159 . . . denotes the ratio of the circumference of a circle to its diameter.3. (30 pts.) Practice with quantifiersWhich of the following propositions is true? (N = {0, 1, 2, . . .} denotes the set of natural numbers.)(a) (∀x ∈ N)(x2< 9) =⇒ (∀x ∈ N)(x2< 10).(b) (∀x ∈ N)(x2< 10) =⇒ (∀x ∈ N)(x2< 9).(c) (∀x ∈ N)(x2< 9 =⇒ x2< 10).(d) (∀x ∈ N)(x2< 10 =⇒ x2< 9).(e) (∀x ∈ N)(∃y ∈ N)(x2< y).(f) (∃y ∈ N)(∀x ∈ N)(x2< y).(g) (∀x ∈ N)(∃y ∈ N)(x2< y =⇒ x < y).(h) (∃y ∈ N)(∀x ∈ N)(x2< y =⇒ x < y).(i) (∀x ∈ N)(∃y ∈ N)(x < y =⇒ x2< y).(j) (∃y ∈ N)(∀x ∈ N)(x < y =⇒ x2< y).CS 70, Summer 2011, HW 1
View Full Document