CSC 3002 (Solved) Assignment 4

Problem 1 (Exercise 8.16)

If you search the web for fractal designs, you will find many intricate wonders beyond the Koch snowflake illustrated in this chapter. H-fractal, in which the repeated pattern is shaped like an elongated letter H in which the horizontal bar and vertical lines on the sides have the same length. Thus, the order-0 H-fractal looks like this:










To create the order-1 fractal, all you do is add four new H-fractals each one half of the original size at each open end of the order-0 fractal, like this:












To create the order-2 fractal, all you have to do is add even smaller H-fractals (again half the size of the fractal to which they connect) to each of the open endpoints. This process gives rise to the following order-2 fractal:

















Write a recursive function

drawHFractal (GWindow & gw ,  double x ,  double y ,  double s i z e ,    int  o r d e r ) ;

where x and y are the coordinates of the center of the H-fractal, size species the width and the height, and order indicates the order of the fractal. As an example, the main program

int main ( )    {

GWindow gw ;

double xc = gw . getWidth ( )  /  2 ;

double yc = gw . g e t H e i g h t ( )  /  2 ;

drawHFractal (gw ,  xc ,  yc ,    1 0 0 ,    3 ) ;

return 0 ;

}

would draw an order-3 H-fractal at the center of the graphics window, like this:





















Requirments:

Please finish the fileHFractal.cpp according to the fileHFractal.h.


Problem 2 (Exercise 9.6)

In chess, a knight moves in an L-shaped pattern: two squares in one direction horizontally or vertically, and then one square at right angles to that motion. For example, the white knight in the upper right side of the following diagram can move to any of the eight squares marked with an x:




















The mobility of a knight decreases near the edge of the board, as illustrated by the black knight in the corner, which can reach only the two squares marked with an ⃝.
It turns out that a knight can visit all 64 squares on a chessboard without ever moving to the same square twice. A path for the knight that moves through all the squares without repeating a square is called a knights tour. One such tour is shown in the following diagram, in which the numbers in the squares indicate the order in which they were visited:






















Write a program that uses backtracking recursion to find a knights tour.

Requirments:

Please finish the fileKnightsTour.cpp according to the fileKnightsTour.h.
Problem 3 (Exercise 11.7)

Rewrite the implementation of the merge sort algorithm from Figure 10-3 (shown as follows) so that it sorts an array rather than a vector.


As in the reimplementation of the selection sort algorithm on page 499 (shown as follows),

void s o r t ( int  a r r a y [ ] ,
int
n )  {
{
for  ( int  l h = 0 ;
l h
< n ;
l h++)

int rh = l h ;




for  ( int  i = l h
+
1 ;  i
< n ;
i ++) {
i f  ( a r r a y [ i ] < a r r a y [ rh ] )  rh = i ;
}




swap ( a r r a y [ l h ] ,
a r r a y [ rh ] ) ;

}




}





your function should use the prototype

void s o r t ( int  a r r a y [ ] ,  int n )

Requirments:

Please finish the fileMergeSort.cpp according to the fileMergeSort.h.


Problem 4 (Exercise 13.12)

Implement the EditorBuffer class using the strategy described in the section entitled ”Doubly linked lists” (Page 606). Be sure to test your implementation as thoroughly as you can. In partic-ular, make sure that you can move the cursor in both directions across parts of the buffer where you have recently made insertions and deletions. Simple testing results are shown as follows.


In this implementation, the ends of the linked list are joined to form a ring, with the dummy cell at both the beginning and the end. This representation makes it possible to implement the moveCursorToEnd method in constant time, and reduces the number of special cases in the code. The constructor is already given. Methods need to be implemented:

    • The destructor that delete all cells;

    • Methods move the cursor;

    • A insertCharacter method that inserts one character into the buffer on the cursor;

    • A deleteCharacter method that deletes one character after the cursor;

    • A getText method that returns the content in buffer;

    • A getCursor method that returns the index of the cursor.

Implement the EditorBuffer class using this representation (which is, in fact, the design strat-egy used in many editors today). Make sure that your program continues to have the same compu-tational efficiency as the two-stack implementation in the text and that the buffer space expands dynamically as needed.

Requirments:

Please finish the filebuffer.cpp according to the filebuffer.h.


Requirements for Assignment

We have provided a project named as AS4 ID.pro. Firstly, please replace the ID with your student ID in both .pro file and the project folder name. (e.g. if your student ID is 123456, hereby the file should be named asAS4 123456),


You should finish all .cpp files except theassignment4.cpp and SimpleTextEditor.cpp according to the problem requirements. You are not allowed to modify any .h files. The resources and test files are provided under res folder such as hello.cpp and TheWonderfulO.txt. You can use them with relative path directly after you compile the whole project. Finally, pack your whole project files into a single .zip file, and submit the .zip file via BB system.

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 BB.

Please refer to the BB system for the assignment deadline. For each day of late submission, you will obtain late penalty in the assignment marks.

Reminder: Please switch your input language to English before interacting in Stanford console.

Or, you will get no response.