Project II

Requirements

Essay. You’ll choose one of the four project topics outlined in the Project Options section of this document.

Your submission will be an essay discussing your solution or approach to the tasks outlined in the topic

description. Each topic has unique requirements, but all submissions must meet the following criteria.

(1) Your submission must be in the form of a report. It must be written using complete and readable

sentences. It may help to read your paper out loud to identify where you have grammar mistakes or

run-on sentences. If you would like to have someone else help you proof-read and edit your paper, you are

welcome to sign up for a peer tutor at the Wolak Learning Center (https://snhu.mywconline.com/)

(2) Your paper must be 2-10 pages. It can be double-spaced, but if you use a cover page or bibliography,

they do not count in the page count.

(3) Your paper must be typed, but any mathematics included can be written by hand within the appropriate

portion of your paper.

(4) If you write an algorithm or a runnable function to help you answer any of the questions posed in

your project, please include it. Use your best judgment about whether your code/algorithm should be

included in the body of your paper or as an appendix. Regardless of where it is included, you should

provide a detailed explanation of the steps in the algorithm or the lines of code in the function.

(5) You may use knowledge from your other classes without citation. However, if you use any sources outside

of your own knowledge, make sure that you cite them in a bibliography. Rule of thumb: if you open up

a book or a webpage while writing the paper, you should put it in the bibliography.

(6) You may not just look up solutions to these project problems.

Project Topic Options

You have the following project options, with more details on the following pages. You can find how they

relate to our course content in the parentheses following the topic title.

A) You Can Count! (Advanced Counting Techniques)

B) Algorithmic Complexity in Understanding DNA Replication (Run-Time Complexity and “Big-O” Notation)

C) A Game of Bridge (Probability and Simulation)

D) A Prisoners’ Dilemma (Probability and Simulation)

You should choose a project topic that is interesting to you. Don’t look for the “easiest” of the four topics

– rather, choose the one that you would most enjoy working on. Having solutions to the questions posed

in your project topic is preferable, but the most important component of the project is the discussion you

provide around your approach to solutions.

1

1) You Can Count!

We spent a few weeks in our course covering some techniques for counting. We saw that counting is not

as simple as your elementary school teachers made it seem – in fact, counting can be quite complex and

difficult! You’ll explore some even more advanced counting techniques in this project. This project includes

the following requirements.

i) Read Section 2.5 of Applied Combinatorics by Mitch Keller and Tom Trotter.

a) Provide your own synopsis of the section, including how it extends our ability to count beyond those

applications we considered in our class discussions.

b) Provide detailed discussions and solutions of problems 15, 16, and 24 from the Chapter Exercises.

ii) Read Section 8.1 and Section 8.2 of Applied Combinatorics by Mitch Keller and Tom Trotter.

a) Provide your own synopsis of the section, including how it extends our ability to count beyond those

applications we considered in our class discussions.

b) Provide detailed discussions and solutions of problems 5 and 10 from the Chapter Exercises.

Topic Expectations

A complete submission for this topic will include solutions to all five of the problems mentioned in the topic

description above. Solutions alone, however, are not enough to earn full credit for the assignment. The

quality of your synopses of the required readings as well as your discussions around the solutions to the

problems is of primary importance.

A submission including well-explained and well-documented solutions to Chapter 2 problems 15, 16 (a and

b), and 24 as well as Chapter 8 problem 5, will have completed enough of the project to earn a B. Submissions

going further will earn higher scores.

2

2) Algorithmic Complexity in Understanding DNA Replication

In this project you’ll consider an application from Bioinformatics. The goal will be to count the frequency of

a substring within a section of a genome. This project provides a foundation for finding the DNA replication

origin within a genome. For this project, you’ll work with the Vibrio cholerae genome, which you can obtain

here.

i) Build a function or describe an algorithm which will count the frequency of each nucleotide (A: adenine,

C: cytosine, G: guanine, T: thymine) in the Vibrio cholerae genome. What is the run-time complexity

of your algorithm?

ii) Bioinformaticists have found that the subsequence ATGATCAAG signals to DNA polymerase that DNA

replication should begin. DNA polymerase is a protein structure that controls DNA replication. Edit

your function or algorithm from part i) to count the frequency of ATGATCAAG in the Vibrio cholerae

genome. What is the run-time complexity of your new algorithm?

iii) Bioinformaticists are often interested in frequent substrings within a genome that occur with high

frequency in a particular region. Update your function to count the frequency of ATGATCAAG within

a sliding window of 300 nucleotides along the Vibrio cholerae genome. Your function should return two

items – the maximum number of times ATGATCAAG occurs within the Vibrio cholerae genome inside

of the 300-nucleotide window and the starting index of the window. Be sure to clearly indicate whether

you are using indexing beginning from 0 or 1. What is the run-time complexity of this algorithm? Can

you find an algorithm that is O(n)?

In addition to covering the tasks outlined above, your paper must achieve the following:

a) Give a basic introduction to DNA replication. You may find some helpful information in lessons 1.1 and

1.2 here.

b) Provide detailed discussions of what your algorithms solving each task above are doing and why your

algorithm achieves what the task requests.

Topic Expectations

A complete submission for this topic will provide algorithms to address parts i) – iii) outlined above. It is

expected that your submission also details the run-time complexity of the algorithms you propose to achieve

each of the objectives. In part iii), it is expected that you will discuss what it would mean to reduce your

algorithm to O(n). A submission which does not include an O(n) solution to part iii) will still be considered

complete. Submissions including a basic introduction to DNA replication, completing tasks i) and ii), and

providing a detailed discussion of the algorithms used in those parts will have completed enough of the

project to earn a B. Submissions going further will earn higher scores.

3

3) A Game of Bridge

You’ll analyse a bridge-crossing game. Various scenarios will be considered. In each scenario, the game is

as follows. All players begin at one end of the bridge, with the goal of getting all the way to the other side.

The bridge consists of glass panes, each of which will turn red or green when stepped on. If a player stops

on a pane and it turns red, that player is out. All lit panes remain lit for the entirety of the game (so later

players have an advantage).

Players will cross the bridge one at a time, in a predetermined order. You may also assume that the glass

panes are large enough that players may not jump over segments of the bridge. That is, in the picture below,

the players begin from the left side of the bridge and each player must step on one of the two panes in each

column in an attempt to reach the right hand side of the bridge.

Analyse the game by finding the expected number of players reaching the opposite end of the bridge safely

(without stepping on a red glass pane) in each of the following scenarios.

i) The bridge contains 2 glass panes in each segment and there are 18 segments to cross the entire bridge.

That is, the bridge is like the one in the image above, but it contains 18 columns rather than just four.

Each segment contains one pane that will light green and one pane that will light red.

ii) The bridge contains 3 glass panes in each segment and there are 18 segments to cross the entire bridge.

Each segment contains two panes that will light green and one pane that will light red.

iii) The bridge contains 3 glass panes in each segment and there are 18 segments to cross the entire bridge.

Each segment contains two panes that will light red and one that will light green.

Topic Expectations

A complete submission for this topic will address all parts i) – iii) presented above. Students opting for

a simulation approach are expected to obtain solutions to all three parts. Students adopting a purely

mathematical approach may make significantly less progress.

A submission including a correct, well-explained, and well-documented solution to part i) will earn a B.

Submissions going further will earn higher scores.

4

4) A Prisoners’ Dilemma

You are locked in a tower of a Medieval castle with three fellow captives (i.e., there are four captured persons

in total), each in an isolated cell with no opportunity to communicate.

The guards have decided to give you all a single chance for immediate release. They invite you and your

three fellow captives to partake in a game of chance. Provide your analysis of the best strategy under the

following individual game scenarios. Given your strategy, what is the probability of escaping the tower?

In your analysis, please remember that you may not consult with your fellow captives (not even prior to the

game commencing), nor will they be able to communicate with one another, and you will not be able to

learn the choice made or result obtained by any of the captives participating before you.

i) Each captive will be given a fair die, which they can either decide to roll or simply return to the guards

without rolling. If the sum of the rolls is at least 11, then you will all be released without question, but

if the total of the rolls is less than 11, you will all remain imprisoned in the castle tower for the rest of

your days.

ii) Each captive will be given a fair coin, which they then can either decide to flip or simply return to the

guards without flipping. If all flipped coins come up tails, you will all be released without question, but

if any of the flipped coins show heads, or if none of you flip the coin, you will all remain imprisoned in

the castle tower for the rest of your days.

iii) Each captive will be given a fair die, which each captive can either decide to roll or simply return to the

guards without rolling. If all rolls result in an odd number of pips facing upwards, then you will all be

released without question, but if any single roll turns up an even number, or if none of you choose to

roll, you will all remain imprisoned in the castle tower for the rest of your days.

The only tools you and your fellow prisoners have to aid you are random number generators, which will give

each prisoner a random number, uniformly and independently chosen between zero and one. These random

number generators may be a helpful tool in making individual decisions about whether to play or pass.

Topic Expectations

A complete submission for this topic will address all parts i) – iii) presented above. That is, a complete

solution should discuss all three parts of the problem, including any differences that make one part more

challenging than another. A submission including well-explained and well-documented solutions to parts i)

and ii) will have completed enough of the project to earn a B. Submissions going further will earn higher

scores.

5