CSE 312 – Problem Set 1

Instructions

For each problem, you must briefly explain/justify how you obtained your answer, as correct answers without an explanation will not receive full credit. Writing the explanation is an important part of the learning process. Moreover, in the event of an incorrect answer, we can still try to give you partial credit based on the explanation you provide. A higher number of mathematical symbols in your solution will not make your solution more precise or “better” – what is important is that the logical flow is complete and can be followed by the graders. Relying exclusively on mathematical symbols in fact often make the solution less readable. Avoid expressions such as “it easy to see” and “clearly” – just explain these steps.

Use section solutions as a model for what your solutions should look like.

Unless a problem states otherwise, you should leave your answer in terms of factorials, combinations, etc., for instance \(26^7\) or \(26!/7!\) or \(26 \cdot \binom {26}{7}\) are all good forms for final answers. Also, you may find the following short note (by Francis E. Su at Harvey Mudd) helpful.

Submission: There are four gradescope "assignments" for this problem set:

a)

You will do an “online assignment” on gradescope for problem 1. See link in problem below.

b)

You will do an “online assignment” on gradescope for problem 2. See link in problem below.

c)

You must upload a pdf of your written solutions to Gradescope under “PSet 1 [Written]”. The use of LaTeX is highly recommended. We have provided a LaTeX template that you can use as a starting point. You may want to work through the LaTeX lesson on Ed to prepare for writing up your solutions. (Note that if you want to hand-write your solutions, you’ll need to scan them. We will not grade work that we are unable to read, so please write neatly if you handwrite.)

Remember to “select pages” to identify which problem is on which page as part of your gradescope upload. Please put each numbered problem on its own page of the pdf (this will make selecting pages easier when you submit), and ensure that your pdfs are oriented correctly (e.g. not upside-down or sideways).

d)

Your code will be submitted under “PSet 1 [Coding]” as files called cse312_pset1_vars.py, cse312_pset1_loops.py, cse312_pset1_lists.py, cse312_pset1_functions.py, and
cse312_pset1_classes.py.

Due Date: This assignment is due at 11:59 PM Wednesday April 8.

Collaboration: Please read the full collaboration policy on the syllabus. If you work with others (and you may), you must still write up your solution independently and name all of your collaborators somewhere on your assignment. In addition, please indicate which problems you used the 312 Learning Assistant on.

Late policy. You have a total of six late days during the quarter, but can only use up to three late days on any one problem set. Please plan ahead, as we will not be willing to add any additional late days except in absolute, verifiable emergencies.

1  Syllabus and Course Integrity Commitment (5 points)

Read the Syllabus, especially the collaboration and AI policy, late policy, and the policy on exam conflicts. If you have questions, please ask them on Ed!

Then fill in the commitment on Gradescope. Full points on this problem is a requirement for passing this course.

2  Mathematical Background [10 points]

Complete the mathematical background problems located in Problem 2 on gradescope. The material in those problems are things we expect you learned in prior courses (especially calculus courses). We’ll do similar computations as part of bigger problems later in the quarter. If there are any topics you aren’t comfortable with, you should carve some time out to review over the next few weeks.

3  Film Festival Volunteers (10 points)

Fourteen people volunteer at a film festival: 5 critics and 9 general volunteers.

a)

(3 points) How many ways are there to choose 4 volunteers to staff a screening room?

b)

(3 points) How many ways are there to assign 4 distinct roles (usher, ticket scanner, projection assistant, and crowd manager) from the 14 volunteers?

c)

(4 points) How many such role assignments are there if at least one critic must be among the four selected volunteers?

4  DNA codes (16 points)

A DNA code is a string of length 4 formed from the alphabet \(\{A,C,G,T\}\).

a)

(3 points) How many DNA codes are there in total?

b)

(3 points) How many DNA codes contain only \(A\) and \(T\)?

c)

(4 points) How many DNA codes contain exactly two \(G\)’s?

d)

(6 points) How many DNA codes contain at least one \(A\) and at least one \(T\)?

5  The Problem of Grandma Gertrude (10 points)

Grandma Gertrude has hoarded \(s\) neon scratchy sweaters, \(d\) terrifying porcelain dolls, and \(f\) petrified fruitcakes. Conveniently, she has exactly \(s + d + f\) deeply unenthusiastic grandchildren. (The grandchildren are distinguishable, but the horrifying gifts of the same variety are not distinguishable.) Gertrude wants to force exactly one "gift" upon each grandchild. Let \(W\) be the set of all ways in which she can ruin their holidays.

a)

(6 points) The story outlines two different ways Gertrude could assign the gifts, which results in a combinatorial identity.

• Method 1: She could first determine which poor souls get the petrified fruitcakes. Then, she could decide who among her remaining grandchildren has earned a terrifying porcelain doll. The rest get sweaters.
• Method 2: She could first decide which grandchildren will suffer her "homemade horrors" (the sweaters and the fruitcakes) and then, from among those unlucky few, determine who truly merits a scratchy neon sweater. The rest of the homemade horror recipients get fruitcakes, and the remaining grandchildren get dolls.

Translate both methods into mathematical expressions using binomial coefficients to show the two formulas for \(|W|\). In other words, write down the equation that is being proved using a combinatorial argument.

b)

(4 points) Suppose Gertrude decides to make things even more personal. She embroiders a unique passive-aggressive message on each sweater, names each porcelain doll, and adds different questionable ingredients to each fruitcake. Now, all \(s\) sweaters, \(d\) dolls, and \(f\) fruitcakes are completely distinguishable from one another. How many distinct ways can she distribute the gifts now?

6  Card Selection (15 points)

a)

(3 points) How many ways are there to choose 7 cards from a standard 52-card deck?

b)

(4 points) How many 7-card hands contain at least one heart?

c)

(8 points) How many 7-card hands contain at least one card from each suit?

7  Walking on a Grid (12 points)

Consider paths on an integer grid that start at \((0,0)\) in which every step increments one coordinate by 1 and leaves the other coordinate unchanged.

a)

(3 points) How many such paths are there to \((20,30)\)?

b)

(3 points) How many such paths to \((20,30)\) pass through the point \((5,10)\)?

c)

(6 points) How many such paths to \((20,30)\) pass through \((5,10)\) but do not pass through \((10,15)\)?

8  Using the Binomial Theorem (12 points)

a)

(3 points) What is the coefficient of \(x^4\) in \((1+x)^6\)?

b)

(4 points) What is the coefficient of \(x^3y^2\) in \((x+2y)^5\)?

c)

(5 points) Use the binomial theorem to prove that \[\sum _{k=0}^{n} \binom {n}{k} 2^k = 3^n.\]

9  A gentle introduction to Python (15 points)

a)

(10 points) Read the Pset 1 Python Tutorial and Coding Exercises lesson on Edstem and follow the directions to complete the 5 coding exercises. Then submit all required files to Pset 1 [Coding] on Gradescope. You may resubmit to Gradescope as many times as you like. We do not have any hidden tests for this assignment; whatever score you see on Gradescope on your last submission will be your final score.

b)

(5 points) Read the Edstem lesson on Python’s numpy library and write the reflection described below (be sure to finish part (a) before moving to this part). You do not need to complete the coding exercises for this part (but you might find them to be nice extra practice); you do have to do the reflection below. The goal of this part is to see some more advanced python features that will definitely be useful in the future, but you won’t need to use frequently for this course.
After reading the lesson, write a reflection on what you felt was the most confusing numpy function and/or class to you and why. If nothing is confusing, explain which function and/or class is the most interesting to you. We will grade based on completion and effort (since this response can’t be “correct” or “incorrect”). We expect most responses will be 2-4 sentences. Include your reflections in the pdf you upload to Gradescope with the other problems on this assignment.