## Homework 1 (due 4/9) CSC 202

We covered most of Sections 1.1, 1.2, 1.3 (no implication yet), and the first part of Section 1.4; for next time, please read through sections 1.3, 1.4 and 1.5, we will talk about those next time. The lecture notes for the second class should be available before Monday. Our topic will be databases and set theory. For this, and the next homeworks, I suggest you install the H2 Database Engine (the appendix has some information on installation.)

See the class links page for links on puzzles, etc.(to class I brought Tangoes, a two-player version of Tangram, the pencil-case puzzle, and some wire-puzzles).

Submission: you can submit the homework to me either by hardcopy in class or email it to me.

Style: Please type up your homework (drawings by hand are ok, but text should be typed). Write up your solutions in full sentences.

1. [SQL Queries, 25pt] For each SQL query, please submit your SQL and a printout of the resulting table.

1. [5pt] List all Chicago students that started before 2002.
2. [10pt] Find all students that are neither in Computer Graphics nor Computer Science.
3. [10pt] List all Computer Science and Information Systems students that are not from Chicago.

2. [Propositional Logic, 5pt] Using truth-tables, prove that Peirce's law is a tautology:

((p -> q) -> p) -> p

The truth-table for implication, ->, is the following:

3. [Binary operators, 10pt] Construct the truth-table for "p and q have opposite truth-values" and find an equivalent formula using only p, q, and any of the logical operations (and, or, not).

4. [SQL, multiple tables, 15pt] The following queries require multiple tables, remember to include the conditions equating foreign and primary keys.

1. [5pt] List all members (by lastname, firstname and SID) of HerCTI.
2. [10pt] List all graduate students enrolled in an undergraduate course, where an undergraduate course is a course whose course number is less than 420.

5. [Extra Credit] (due to Martin Gardner) Multiple choice question: assuming at least one of the following statements is true, which one is it? Why?

• Exactly one of these statements is true.
• Exactly two of these statements are true.
• Exactly three of these statements are true.
• Exactly four of these statements are true.
• Exactly five of these statements are true.

6. [Extra Credit] (classic interview question)

You have a bucket of jelly beans. Some are red, some are blue, and some green. With your eyes closed, pick out 2 of a like color. How many do you have to grab to be sure you have 2 of the same?

7. [Extra Credit] If you find any typos and mistakes in the lecture notes, please let me know.

Marcus Schaefer
Last updated: April 3rd, 2007.