CS 242, Section 002  Sonoma State University  Fall, 2021 
Discrete Structures for Computer Science


Instructor: Henry M. Walker
Lecturer, Sonoma State University 
Submissions are to be submitted on paper, with one submission from each assigned pair of students, unless a student has explicit (written) permission from the instructor.
Both partners should collaborate on every problem, and both names should be at the top of the first page. Since this is a collaborative effort, both partners should agree that the work represents their agreement in the correctness of the answers, and the same grade will be recorded for each assignment.
Problems for each section (each bullet item in the assignment) should begin on a new page, and problems within a section should be in numeric order.
If a problem requires the writing of a Python program, then the submission should include a printout of the code, a listing of appropriate test runs, and a statement regarding how the test runs provide sufficient evidence to conclude the program works properly.
Each problem from Rosen's text should be identified with its section number and problem number. Each problem written out as a separate bullet point should be identified in a phrase or sentence, so it is clear which question is being answered.
When a problem asks for a conclusion, the solution must include both a statement of the conclusion and an argument justifying that conclusion.
Answers should be placed in Section and problem order, so the first page (more if needed) should give answers for the problems in the first assignment bullet. Answers for subsequent bullets should be in the order of the bullets on the Assignment sheet.
Although the rules of this course allow the use of sources beyond the discussions of a student pair, any outside references (e.g., from the textbook, from Web sources, from discussions with others, etc.) must be fully cited.
Use mathematical induction to prove that, given x > 0, (1 + x)^{n} ≥ 1 + nx for all n ≥ 0.
Consider the following questions related to a database involving a course schedule and courses.
+++++++  courseScheduleID  courseID  day  startTime  endTime  room  +++++++  1  1  MWF  1:50  4:00  Sal 1035   3  2  MWF  8:00  10:10  Sal 1035   5  7  MWF  12:40  1:40  Sal 1030 
Also the following courses table contains information about several hypothetical courses.
+++++  courseID  number  title  credits  +++++  1  141  Intro. to Prog.  1.00   2  199  PHP, MySQL, Web Applications  1.00   3  241  Data Structures  1.00   5  451  Topics in Computer Science  1.00   7  496  Senior Seminar in CS II  0.50 
SELECT * FROM courses JOIN courseSchedule;
SELECT * FROM courses JOIN courseSchedule on courses.courseID = courseSchedule.courseID ;
SELECT * FROM courses JOIN courseSchedule on courses.courseID = courseSchedule.courseID where courseSchedule.courseScheduleID = 3;
The table should show all relevant rows, including entries for all relevant fields in the table.
Challenging Problem: (for extra credit) The following claims to prove that all ice cream flavors are equally tasty. Since the result is clearly false, identify the specific error in this argument. (For example, at what step does this argument fail and why.)
Induction Hypothesis: Let P(n) be the predicate
if {IC_{1}, IC_{2}, IC_{3}, ...,
IC_{n}} is any set of ice cream flavors. Then each of
the flavors in the set are equally tasty.
For conveience in notation, we will use an equal sign (=) to
indicate flavors are equally tasty.
IC_{1} = IC_{2} = IC_{3} = ... = IC_{n}
Proof by Induction on n.
Base case: When n = 1,
Let {IC_{1}} be any set with 1 flavor of ice cream. Then, only 1 flavor is represented, so all flavors in the set are qually tasty.Inductive case: Assume P(n) and prove P(n+1).
Set S = {IC_{1}, IC_{2}, IC_{3}, ... IC_{n}, IC_{n+1}}
be any set of n+1 flavors of ice cream. Now consider
subsets
IC_{1} = IC_{2} = IC_{3} = ... = IC_{n} = IC_{n+1} This proves P(n+1). 
create July 22, 2021 revised September 15/20, 2021 

For more information, please contact Henry M. Walker at walker@cs.grinnell.edu. 