Programming Paradigms Assignment 1

CSC3002: Introduction to Computer Science
Programming Paradigms
Assignment 1
Assignment description:
This assignment will be worth 10% of the final grade.
You should write your code for each question in a .cpp and .h file (please name it
using the question name, e.g. q1.cpp). Please pack all your .cpp and .h files into a
single .zip file, name it using your student ID (e.g. if your student ID is 123456, then
the file should be named as 123456.zip), and then submit the .zip file via Moodle.
You should create an empty project in QT and start your programing.
Please note that, the teaching assistant may ask you to explain the meaning of your
program, to ensure that the codes are indeed written by yourself. Please also note
that we may check whether your program is too similar to your fellow students’ code
using Moodle.
This assignment is due on 24:00PM, 15 October(Sunday). For each day of late
submission, you will lose 10% of your mark in this assignment. If you submit more
than three days later than the deadline, you will receive zero in this assignment.
Question 1:
Heads. . . .
Heads. . . .
Heads. . . .
A weaker man might be moved to re-examine his faith, if in nothing else at least in the law of
probability.
—Tom Stoppard, Rosencrantz and Guildenstern Are Dead, 1967
Write a program that simulates flipping a coin repeatedly and continues until three consecutive
heads are tossed. At that point, your program should display the total number of coin flips that
were made. The following is one possible sample run of the program:
Question 2:
There is no gene for the human spirit.
—Tagline for the 1997 film GATTACA
The genetic code for all living organisms is carried in its DNA—a molecule with the remarkable
capacity to replicate its own structure. The DNA molecule itself consists of a long strand of
chemical bases wound together with a similar strand in a double helix. DNA’s ability to
replicate comes from the fact that its four constituent bases—adenosine, cytosine, guanine,
and thymine—combine with each other only in the following ways:
• Cytosine on one strand links only with guanine on the other, and vice versa.
• Adenosine links only with thymine, and vice versa.
Biologists abbreviate the names of the bases by writing only the initial letter: A, C, G, or T.
Inside the cell, a DNA strand acts as a template to which other DNA strands can attach
themselves. As an example, suppose that you have the following DNA strand, in which
the position of each base has been numbered as it would be in a C++ string:
Your mission in this exercise is to determine where a shorter DNA strand can attach itself to
the longer one. If, for example, you were trying to find a match for the strand
the rules for DNA dictate that this strand can bind to the longer one only at position 1:
By contrast, the strand
matches at either position 2 or position
7. Write a function
int findDNAMatch (string s1, string s2, int start = 0);
that returns the first position at which the DNA strand s1 can attach to the strand s2. As in the
find method for the string class, the optional start parameter indicates the index position at
which the search should start. If there is no match, findDNAMatch should return –1.
Question 3:
Some files use tab characters to align data into columns. Doing so, however, can cause
problems for applications that are unable to work directly with tabs. For these applications, it is
useful to have access to a program that replaces tabs in an input file with the number of spaces
required to reach the next tab stop. In programming, tab stops are usually set at every eight
columns. For example, suppose that the input file contains a line of the form
where the symbol represents the space taken up by a tab, which differs depending on its
position in the line. If the tab stops are set every eight spaces, the first tab character must be
replaced by five spaces and the second tab character by three.
Write a program that copies an input file to an output file, replacing all tab characters by the
appropriate number of spaces.
Question 4:
And the first one now
Will later be last
For the times they are a-changin’.
—Bob Dylan, “The Times They Are a-Changin’,” 1963
Following the inspiration from Bob Dylan’s song (which is itself inspired by Matthew 19:30), write
a function
void reverseQueue(Queue<string & queue);
that reverses the elements in the queue. Remember that you have no access to the internal
representation of the queue and must therefore come up with an algorithm—presumably
involving other structures—that accomplishes the task.
Question 5:
Write a program that checks whether the bracketing operators (parentheses, brackets, and curly
braces) in a string are properly matched. As an example of proper matching, consider the string
{ s = 2 * (a[2] + 3); x = (1 + (2)); }
If you go through the string carefully, you discover that all the bracketing operators are correctly
nested, with each open parenthesis matched by a close parenthesis, each open bracket
matched by a close bracket, and so on. On the other hand, the following strings are all
unbalanced for the reasons indicated:
(([]) The line is missing a close parenthesis.
)( The close parenthesis comes before the open parenthesis.
{(}) The bracketing operators are improperly nested.