Introduction to Computer Science Programming Paradigms Assignment 2

1
CSC3002: Introduction to Computer Science Programming Paradigms
Assignment 2
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 your whole project 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 23:59PM, 20 November (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.
Reminders:
Marks will be given on the style of your coding. Please write comments and make your
variable name meaningful.
2
1. For certain applications, it is useful to be able to generate a series of names that form a sequential
pattern. For example, if you were writing a program to number figures in a paper, having some
mechanism to return the sequence of strings "Figure 1", "Figure 2", "Figure 3", and so on,
would be very handy. However, you might also need to label points in a geometric diagram, in
which case you would want a similar but independent set of labels for points such as "P0", "P1",
"P2", and so forth. If you think about this problem more generally, the tool you need is a label
generator that allows the client to define arbitrary sequences of labels, each of which consists of a
prefix string ("Figure " or "P" for the examples in the preceding paragraph) coupled with an
integer used as a sequence number. Because the client may want different sequences to be active
simultaneously, it makes sense to define the label generator as a LabelGenerator class. To
initialize a new generator, the client provides the prefix string and the initial index as arguments to
the LabelGenerator constructor. Once the generator has been created, the client can return new
labels in the sequence by calling nextLabel on the LabelGenerator.
As an illustration of how the interface works, the main program shown in Figure 6-14 produces the
following sample run:
Write the files labelgen.h and labelgen.cpp to support this class.
3
a b c d e f g
2. In theory, the recursive backtracking strategy described in this chapter should be sufficient to solve
most puzzles that involve performing a sequence of moves looking for some solution. In practice,
however, some of those puzzles are too complex to solve in a reasonable amount of time. One
puzzle that is just at the limit of what recursive backtracking can accomplish without using some
additional cleverness is the peg solitaire puzzle, which dates from the 17th century. Peg solitaire is
usually played on a board that looks like this:
The black dots in the diagram are pegs, which fill the board except for the center hole. On a turn,
you are allowed to jump over and remove a peg, as illustrated in the following diagram, in which
the colored peg jumps into the vacant center hole and the peg in the middle is removed:
The object of the game is to perform a series of jumps that leaves only one peg in the center hole.
Write a program to solve this puzzle.
1
2
3
4
5
6
7
4
3. Write a program that generates a table comparing the performance of two algorithms—linear and
binary search—when used to find a randomly chosen integer key in a sorted Vector<int. The
linear search algorithm simply goes through each element of the vector in turn until it finds the
desired one or determines that the key does not appear. The binary search algorithm, which is
implemented for string vectors in Figure 7-5, uses a divide-and-conquer strategy by checking the
middle element of the vector and then deciding which half of the remaining elements to search.
The table you generate in this problem, should calculate the number of comparisons made against
elements of the vector. To ensure that the results are not completely random, your program should
average the results over several independent trials. A sample run of the program might look like
this:
5
4. Rewrite the implementation of the merge sort algorithm from Figure 10-3 so that it sorts an array
rather than a vector. Your function should use the prototype
void sort(int array[], int n)
6
5. Even though programmers tend to think of strings as relatively simple entities, their
implementation turns out to involve the full range of techniques you have seen in this chapter. In
this exercise, your mission is to define a class called MyString that approximates the behavior of
the string class from the Standard C++ libraries. Your class should export the following methods:
• A constructor MyString(str) that creates a MyString object from a C++ string.
• A destructor that frees any heap storage allocated by the MyString.
• A toString() method that converts a MyString to a C++ string.
• A method length() that returns the number of characters in the string.
• A method substr(start, n) that returns a substring of the current string object. As in the
library version of the string class, the substring should begin at the index position start and
continue for n characters or through the end of the string, whichever comes first. The parameter n
should be optional; if it is missing, the substring should always extend through the end of the
original string.
• A redefinition of the operator + that concatenates two MyString objects. It also makes sense to
overload the operator += so that it appends a character or a string to the end of an existing one.
• A redefinition of the operator << so that MyString objects can be written to output streams.
• A redefinition of the bracket-selection operator so that str[i] returns by reference the character
at index position i in str. As an improvement over the string class in the C++ libraries, your
implementation of the bracket operator should call error if the index is outside the bounds of the
string.
• A redefinition of the relational operators ==, !=, <, <=, , and = that compare strings
lexicographically.
• A redefinition of the assignment operator and the copy constructor for the MyString class so
that any copying operations make a deep copy that creates a new character array.
Your code should work directly with your underlying representation and should make no calls to any of
the methods in the C++ string class. Your interface and implementation should also be const correct
so that both clients and the C++ compiler know exactly what methods can change the value of the string.