Instructions:

●  Homework  is  due on  Tuesday  at  11:59pm  ET/Boston.   Homeworks received up to  24 hours  late (11:59pm ET on Wednesday) will be penalized 5 percent.  Homeworks received up to 48 hours late (11:59pm ET on Thursday) will be penalized 10 percent.  NO  assignment will be accepted after 48 hours.

●  We expect that you will study with friends and fellow students and you are welcome to verbally discuss the problems openly.  However, your solution writeup should be the product of your own mind and expressed in your own words. The TAs and I will be available to answer specific questions or address speific points of confusion but we will not verify your answers prior to submission.

●  Assignments should be typed using Word or LateX, or hand-written  neatly.   When submitting to gradescope be sure to indicate the page containing your answer to each problem, so that the TAs don’t have to search for your solution.

●  To  get full  credit,  explain  your solution  and show  each  step  of the  solution process!   Simply writing down a correct answer will receive little or no credit.   We don’t need your scratch work or draft solutions, only your final solution explaining your step-by-step reasoning.  Recommendation:  try to imagine you need to explain your solution to someone not in this class.

●  If you think the TA made a clerical error in grading your assignment, you may submit a regrade request on Gradescope within 1 week of the publication of the grades.  After 1 week of publication, ALL GRADES ARE FINAL.

Problem 1 [25 (8, 8, 9)]:  Ride the MBTA.

i. The worcester line makes 10 inbound trips, 4 of which are express and 6 are local.  In how many ways can we order the trips as a sequence of either express or local trips. For example, LLEELLEELL is one possibility.

ii. A train engine is to be connected with either 3, 4, or 5 passenger cars chosen from 7 available passenger cars. Assuming the passenger cars are all numbered, and that the same cars linked together in a different sequence constitutes a different train, how many possible trains could we form?

iii. Suppose an inbound train starts at station 1 and ends at station 10.  The local train makes all 8 intermediate stops at stations 2 through 9.  An express train is any inbound train that makes no more than 3 intermediate stops.  (The starting and ending station do not count.) How many different valid express train trips are possible?

Problem 2 [25 pts (6, 6, 6, 7)]:  DNA - The code of life.

The human genome is a double helix containing some 3 billion nucleotide base pairs.   For purposes of discussion we can imagine DNA as a long string of four letters (A,T,G,C) corresponding to the four nucleotides (Adenine, Thymine, Guanine, and Cytosine).

i. How many DNA sequences of length 12 are possible?  Note:  DNA sequences have a defi- nite direction or orientation, so reversing the sequence produces a different DNA sequence. (Molecular biologists refer to one end as the 3’ end and the other as the 5’ end.)

ii. How many DNA sequences of length 12 are possible if no nucleotide ever repeats? By ”repeat” we mean that the nucleotide occurs at least twice in a row (AA, CC, GG, TT).

iii. How many DNA sequences have at least one repeating nucleotide somewhere along the se- quence?

iv. Human genes may be fragmented into multiple exons  as shown in the figure below.  In fact the exons of two genes may even be interleaved. Gene A has 3 exons and gene B has 4 exons. In how many ways can the exons of gene A and B be ordered (including interleavings of the two genes) while maintaining the relative sequence of gene A’s exons and gene B’s exons? That is, exon A1 is always before exon A2 is always before exon A3 and so on.