Assessed Coursework MA407 Algorithms and Computation due: Monday 10 February 2020 at 14:00 Instructions The tasks on the following pages describe your assessed coursework, which constitutes 25% of the final mark for this course. It is due on Monday 10 February 2020 at 14:00 (start of week 4 of Lent Term 2020). The tasks ask you to complete up to 4 Java files in plain text format. Make sure that your files compile on LSE computers, without the loading of any external Java packages. Submit the two files Graph.java and Tree.java, plus up to two additional files with further public classes that you may need, on the Moodle page for MA407 under the submission link in the Assessed Coursework section. Make sure that each of your files contains your candidate number (not your student number; see below). Please submit only a single final version of your files. Otherwise you risk that the wrong submission will be marked. The deadline is sharp. Late work carries an automatic penalty of 5 deducted marks (out of 100) for every 24 hours that the coursework is late. Submission of answers to this coursework is mandatory. Without any submission your mark for this course is incomplete, and you may not be eligible for the award of a degree. The work should be yours only. Plagiarism is considered an assessment offence at the LSE and is, as an instance of academic misconduct, taken very seriously. In a case of suspected plagia- rism, the Department will act according to the School’s Regulations on Assessment Offences— Plagiarism. So only submit work that is solely your own. This also means that for developing your solutions you are not allowed to collaborate with other students or to ask other persons for help. The contents of your work must remain anonymous, so do not write your name or student number in any of the program files. Instead, identify your work with your candidate number. Please insert your candidate number as a comment in the first line in each of your files. You can find your candidate number on ‘LSE for You’. Coursework MA407 Your task is to extend by various methods the data structure of a binary search tree from week 7. The main aim is to nicely draw the tree, as in the following example: 5 10 8 6 3 4 2 7 9 1000 are inserted 1000 9 7 6 8 10 42 3 5 Let the program be called Tree.java, which when started with java Tree 5 10 8 6 3 4 2 7 9 1000 could produce the following text output to create the above diagram, as we will explain: \documentclass[a4paper,11pt]{article} %%%%%%%%%%%% start of LaTeX file \usepackage{mathpazo} \usepackage{tikz} \usetikzlibrary{shapes} \oddsidemargin -0.54cm \textwidth 17.0cm \textheight 24cm \topmargin -1.3cm \parindent 0pt \parskip 1ex \pagestyle{empty} \begin{document} %%%%%%%%%%%% end of LaTeX preamble, start of text \medskip\hrule\medskip 5 10 8 6 3 4 2 7 9 1000 are inserted \begin{tikzpicture}[scale=0.600] \draw [help lines, color=green] (1,-10) grid (10,-2); % creates help grid \draw [thick] (10,-6) node[draw, rounded rectangle] (A) {1000}; \draw [thick] (8,-8) node[draw, rounded rectangle] (B) {9}; \draw [thick] (6,-10) node[draw, rounded rectangle] (C) {7}; \draw [thick] (5,-8) node[draw, rounded rectangle] (D) {6}; \draw [thick] (7,-6) node[draw, rounded rectangle] (E) {8}; \draw [thick] (9,-4) node[draw, rounded rectangle] (F) {10}; \draw [thick] (3,-6) node[draw, rounded rectangle] (A6) {4}; \draw [thick] (1,-6) node[draw, rounded rectangle] (CC6) {2}; \draw [thick] (2,-4) node[draw, rounded rectangle] (4_4) {3}; \draw [thick] (4,-2) node[draw, rounded rectangle] (abc) {5}; \draw [->, thick] (F) to (A); \draw [->, thick] (E) to (B); \draw [->, thick] (D) to (C); \draw [->, thick] (E) to (D); \draw [->, thick] (F) to (E); \draw [->, thick] (abc) to (F); \draw [->, thick] (4_4) to (A6); \draw [->, thick] (4_4) to (CC6); \draw [->, thick] (abc) to (4_4); \end{tikzpicture} \medskip\hrule\medskip \end{document} %%%%%%%%%%%% end of text and of LaTeX file 2 Generating a LaTeX file from Java by re-directing the standard output The text above (also on Moodle as test-latex.tex ) is a program in LaTeX, which is a type- setting program for mathematical text that you will be using for writing an MSc thesis (if this is part of your degree course). Your Java program will produce such a LaTeX file. In a LaTeX file, anything from the % character onwards until the end of the line is ignored, so % starts a comment just like // does in a Java program. The first line above is therefore equivalent to \documentclass[a4paper,11pt]{article} and would be printed with the Java command System.out.println(“\\documentclass[a4paper,11pt]{article}”); where the double backslash \\ is needed because a single backslash introduces a special character (as in \n for “new line”) where the special character is here the backslash itself. The Java methods System.out.print() and System.out.println() print to standard output. When you start your program, you should re-direct the standard output to a file, for example named a.tex, with the re-direct symbol > as in java Tree 5 10 8 6 3 4 2 7 9 1000 > a.tex which will then send its output to the file a.tex. This file could be named in any way, such as myoutput.tex, but should end in .tex to show that it is a LaTeX file. A redirection such as java Tree 3 1 2 4 > a.tex normally requires that you start the Java program from the command line (it may also work in the “Interactions Pane” of DrJava). Get a command line to work for you, which is the terminal program on Mac computers and either the cmd prompt or an environment such as cygwin (which you have to install) on Windows com- puters. You have to make sure to be in the correct directory (i.e., folder) which contains your Java file and compiled Java class. Starting programs from the command line is old-fashioned but reliable and fast. You should learn the minimal things about it for this coursework. On the command line, you typically can access previous commands with the up-arrow key so that you do not have to type them again. From the command line, you should also have access to the LaTeX program that translates your LaTeX file to a pdf file (again, do not use a LaTeX development environment for this because you will not edit the .tex file here, only view it and generate it automatically). The command pdflatex a.tex will compile your file a.tex into a file called a.pdf which contains the generated pdf file, assuming your LaTeX file contains no errors. You can then view your pdf file with a pdf viewer, such as Acrobat Reader, or a web browser such as Chrome. This is done by clicking on the pdf file in your folder (on some systems, from the command line with acroread a.pdf). When you generate the .tex and .pdf file again with java and pdflatex, you have to re-load it in your pdf viewer; some pdf readers automatically re-load the pdf file when it has changed. In summary, a typical program execution is java Tree 3 1 2 4 > a.tex pdflatex a.tex and then look at a.pdf with your pdf viewer. Structure of a LaTeX file and tikz commands Copy the following minimal LaTeX file into a file such as a.tex; you can also generate it with the program Minimal_latex.java which is on Moodle. Then compile a.tex with pdflatex 3 to see the single sentence “Hello, this is my text” on a page with a page number 1 at the bottom in the resulting pdf file: \documentclass{article} \begin{document} Hello, this is my text \end{document} In general, anything before \begin{document} (see the larger introductory example on page 2) contains general information such as the layout of a page and a number of LaTeX packages. This is called the LaTeX preamble which is the header for your LaTeX file (and which you should generate with a Java method dedicated to producing it). Similarly, the terminal line of your text should contain the line \end{document} (again generated with a separate Java method). Any text between \begin{document} and \end{document} represents normal text or special LaTeX commands that will appear, formatted, on your pdf pages. Line breaks in your text will considered just as blanks, so if you want to start a new paragraph you
should type a blank line as in the introductory example on page 2 above. The three LaTeX commands \medskip\hrule\medskip generate a bit of vertical space, a hor- izontal rule that goes across the full text width of the page (in the above file defined to be 17 centimetres), and another vertical space (omit \medskip to see the effect). We use the special tikz LaTeX “environment” to draw graphs, shown above between the lines \begin{tikzpicture} and \end{tikzpicture} . This environment uses an implicit grid of coordinates, with standard grid size 1 cm. With \begin{tikzpicture}[scale=0.600] it is changed to 0.6 cm for the length of a grid square. Above we see a number of \draw commands that end in a semicolon “;” and that are convenient to start on separate lines. The tikz com- mand \draw [help lines, color=green] (1,-10) grid (10,-2); draws a green grid be- tween the coordinate pairs (1,−10) and (10,−2). Coordinates can have floating-point values but we will only use integers. The coordinates are only relative to each other. The command \draw [thick] (10,-6) node[draw, rounded rectangle] (A) {1000}; draws at position (10,−6) a text, here “1000”, surrounded by a rounded rectangle (with thick lines), and gives it a label, here (A) . This label (between parentheses) has to identify the shape (here the rounded rectangle) uniquely; the label could also be the pair of coordinates itself, such as (10,-6) instead of (A) . These labels are then used to draw arrows between the rounded rectangles as in the command \draw [->, thick] (F) to (A); where in this case both shapes (F) and (A) have to be defined earlier in the LaTeX file because otherwise pdflatex would interrupt with an error such as ! Package pgf Error: No shape named F is known. (In that case you should continue the LaTeX compilation by typing q to terminate it; then pdflatex may or may not produce a pdf file from what it has seen so far.) Hence, when you draw a graph via tikz commands with nodes and directed edges (as you are asked to below) make sure you define the nodes before the edges. Apart from drawing a graph as a tikz figure, you can also print normal text. Remember to create a blank line to start a new paragraph. In addition, you can type out error messages as LaTeX comments, as in % Error: unknown end node (1,1) of edge which will be ignored in the LaTeX compilation (anywhere, including in or before the preamble) but give useful information because they are visible in the LaTeX file. 4 Your coursework For the following questions (a)–(g), the percentage of marks assigned to the individual answers are listed with each question, and are for (a) 35%, (b) 5% (bonus question), (c) 20%, (d) 20%, (e) 15%, (f) 10%, (g) 5% (bonus question). The two bonus questions (b) and (g) give 5% of marks each and are added to your marks, but the total will not exceed 100%, which you can also achieve by answering the remaining questions perfectly. Please write elegant and straightforward code, without needless case distinctions, and appro- priate separate methods for conceptually separate tasks, and take care of borderline cases (for example, empty input). Clarity and readability of your program is part of the assessment cri- teria. Write appropriate (concise) comments. If you want to add any special features to your program (not required), or if you can only give partial answers to some questions, document this so we can take notice. (a) The Graph class (35% of marks) Create a Java program Graph.java with a public class Graph which allows creating a graph that is then output as a LaTeX file as described above. It should have the following public methods: addNode Add a node to the graph, given by a pair of integer coordinates, together with a label string (such as “1000” in the example above). If the same coordinate pair is given again, update the label (so do not store the same node twice). The coordi- nates can be positive or negative but should in absolute value not be larger than an integer constant maxcoordinate , which you should set to 100 at a central place. Reject nodes where a coordinate exceeds this value with a LaTeX comment (on its own output line) as in % coordinate 190 in node (50,190) too large addEdge Add a directed edge to the graph, given by the two pairs of integer coordinates of the endpoints of the edge. These nodes have to be present already; if not, reject them with a suitable LaTeX comment. clear Empty the node and edge list. outheader Output the header of the LaTeX file, i.e., the preamble up to \begin{document} outfooter Output the footer of the LaTeX file, here the single line \end{document} . You could prefix it with \medskip\hrule if you like the resulting output better. outgraph Output the graph as a tikz figure as described, with a blank line before and after, and including a green grid at the beginning. (There may be several such figures in a single LaTeX file, hence the separate outheader and outfooter methods.) outgrid Output a grid between the smallest and largest coordinates that occur, in turn computed by a separate method. main This standard static method will only be used to test the Graph methods. Invoked with java Graph x1 y1 x2 y2 · · · xn yn , it should create a path with edges (x1, y1) → (x2, y2), . . . , (xn−1, yn−1) → (xn, yn) from the sequence of pairs of co- ordinates given on the command line. The labels of the nodes are the numbers 1, . . . , n (possibly overwritten when a node is used twice). For example, java Graph 0 0 2 0 2 2 4 0 2 -2 java Graph 0 0 2 0 2 2 4 0 2 -2 0 0 5 java Graph 1 1 3 4 10 200 3 2 5 4 (re-directed to a .tex file) generate, respectively, the graphs 5 4 3 21 5 4 3 26 5 4 2 1 As computed by the outgrid method, in the first two graphs the lower left corner is (0,−2), and in the third graph it is (1, 1). (b) Grid adjustment in the Graph class (5% bonus marks) Consider the \textwidth 17cm statement in the sample LaTeX file on page 2. This means that the text is printed on a width of 17 centimetres. An A4 sheet is 21 cm wide, so with equal margins (which we aim for) each margin is 2 cm wide. The standard left margin in LaTeX is 1 inch or 2.54 cm, so the additional margin (called \oddsidemargin above) should be -0.54cm as it is stated there to get a 2cm margin. • Add a Java constant textwidth for the text width in centimetres which can be changed centrally, and from which the LaTeX layout parameters \textwidth and \oddsidemargin are correctly output. • The standard grid size of 0.6 cm works well, but if the graph is too wide (as measured be- tween the difference of smallest and largest horizontal coordinate) then it will go into or beyond the right margin. If the graph is too wide, adjust the grid size in the [scale=0.600] parameter depending on the textwidth, but not below 0.3, say, because otherwise the graph will look too dense. Hint: When you print the scale or the textwidth, which is a double number in Java, use the System.out.printf() method. Suppose the double number is a=0.42857142857. Then System.out.printf(“%.3f”, a) will print it with three digits after the decimal point as 0.429. You can also add further text to the formatting string: e.g., the output [scale=0.429] is created with System.out.printf(“[scale=%.3f]”, a) . (c) Creating the binary search tree as a data structure (20% of marks) As discussed in week 7, the Java program BinarySearchTree.java (on Moodle) describes a binary search tree. Re-name it as Tree.java and remove the comments before and after the program that describes the class. Also delete any methods that you won’t need. • The main method should read in the command-line arguments as integers and insert them into the tree. Print the numbers as they have been input to standard output (see the example below). • Write a printsorted method that prints the numbers in ascending order to standard output. Hint: Use a straightforward recursion. • Write a method avgdepth that computes the average depth (= level) of the nodes. The root has level 0. Output the number of stored keys as well. In the introductory example on page 2, the output is average depth: 2.000, size
10 6 Altogether, these outputs for the introductory example from page 2 should be 5 10 8 6 3 4 2 7 9 1000 are inserted in sorted order: 2 3 4 5 6 7 8 9 10 1000 average depth: 2.000, size 10 where the blank lines are for LaTeX so they appear on separate lines in the pdf file. (d) Draw the binary tree using the Graph class (20% of marks) As part of Tree.java, write a method that draws a nice picture of the generated binary search tree as a LaTeX file. It should use the Graph class from (b) and its methods. The text that you have output in part (c) should come before the graph picture as text in the LaTeX file and later pdf file. The initial example on page 2 shows you good choices of the coordinates for placing the nodes. The coordinates can be nicely computed with a recursive method applied to the tree, where a (recursively defined) width method is useful to count the children in a subtree, and it is useful to know whether that is a left or right subtree, to determine the position of the node relative to the parent node. You may possibly use as a feature the behaviour of addEdge to not draw an edge if an endpoint is missing (but then should explain where you use this). The input to the program should be the command-line arguments as numbers to be inserted into the tree, like java Tree 5 10 8 6 3 4 2 7 9 1000 to generate the picture on page 2. (e) Generating a random permutation for tree elements (15% of marks) For this part (e) and later (f) and (g), we will use a different interpretation of the command-line arguments if there are at most three of them (because binary trees with up to three elements are not very interesting anyway). Namely, the possible calls will be • java Tree -1 (the first number is negative), which tests the generation of a random permu- tation, see below; • java Tree n where n ≥ 0, which generates a random permutation of the numbers 1, . . . , n , and inserts them into the tree and displays it as before; • java Tree n d , which generates n random numbers to be inserted, and subsequently re- places d further numbers; • java Tree n d r , which repeats this r times and prints a table with r columns to compare the resulting average tree depths, in bonus question (g). This question (e) asks the following: As part of the Tree class, write a method declared as int[] randomperm(int n) that generates an array whose n entries form a random permuta- tion a1, a2, . . . , an of the numbers 1, 2, . . . , n (the array size and array indices should follow the usual Java convention, with indices starting at 0). This method should use at most n calls to the method Math.random which generates a double number between 0.0 and 1.0 (exclusive). Hint: In each step, select the next element of the permutation randomly from a suitably represented set of numbers, and delete that number from the set. Write a randomtest method that is used if the first command-line argument to java Tree is 7 a negative integer. It should output, say, 20 random permutations for n = 3 to see if your randomperm method does not accidentally avoid certain permutations. In addition, argue with some text (as comment in your code) why your randomperm method is correct. When called with java Tree n , your program should with randomperm generate a random permutation a1, a2, . . . , an and insert these numbers into the tree, and display it as before as if you had typed the numbers explicitly. A sample output is shown in part (f) below. If there is no command-line argument, do the same with default n = 20. (f) Alternating random deletions and insertions (10% of marks) When the program is started with java Tree n d, let d = n if d > n. Then, generate a random permutation a1, a2, . . . , an, . . . , an+d, of {1, 2, . . . , n + d}, which are the numbers to be inserted into the tree. However, only the first n of these numbers a1, a2, . . . , an are to be inserted at the beginning. This is what the program should do first. Then, compute and output the average depth of the tree nodes, and draw the tree. (So far, the program does nothing new.) Next, compute another random permutation q1, q2, . . . , qn of {1, 2, . . . , n}. The first d of these numbers, q1, q2, . . . , qd, are the indices of the numbers to be deleted. The program should now proceed, for each i = 1, 2, . . . , d, to first (i) delete aqi from the tree, and then (ii) insert an+i into the tree. So these are d alternate delete/insert operations applied to random elements in the tree. If d = n, then all n numbers a1, a2, . . . , an are thereby replaced by the second set of n numbers an+1, an+2, . . . , a2n. After these d alternate delete/insert operations (which should be printed), give the new aver- age depth of the tree nodes, and draw the tree again. The following is an example when started with java Tree 20 3. First, it creates the following text output (as part of the LaTeX file, after the preamble): 10 4 13 19 22 18 2 3 1 21 17 12 14 11 6 8 15 23 9 7 are inserted in sorted order: 1 2 3 4 6 7 8 9 10 11 12 13 14 15 17 18 19 21 22 23 average depth: 2.950, size 20 This means that it generates the search tree from 20 random numbers (out of 23, where the numbers 5, 16, and 20 are missing as can be seen from the sorted output). Then it nicely draws the tree, as follows. The subsequently described deletions and insertions mean that first 3 is deleted, then 16 inserted, then 13 deleted, then 5 inserted, then 17 deleted, then 20 inserted. 8 2321 22 15 14 17 18 19 11 12 13 97 8 6 31 2 4 10 — alternate delete/insert: — 3 13 17 are deleted 16 5 20 are newly inserted in sorted order: 1 2 4 5 6 7 8 9 10 11 12 14 15 16 18 19 20 21 22 23 new average depth: 2.900, size 20 23 20 21 22 16 15 18 19 11 12 14 97 85 6 1 2 4 10 (g) Testing of alternate deletions/insertions (5% bonus marks) The effect of alternate deletions and insertions into a binary search tree is not well understood theoretically. In this question, interpret three command-line parameters as in java Tree n d r as follows, with n and d as in (f). The third parameter r is a number of repetitions (so if it is missing as in (f), let r = 1). If r > 1, draw the tree only at the first iteration (or omit the tree drawing altogether). Then your program should display a nice table, which after java Tree 40 20 10 could look like 9 Old depth: 5.38 5.60 4.35 4.83 5.03 4.78 6.13 4.10 4.38 5.28 New depth: 5.05 4.95 4.13 4.58 4.53 4.60 6.10 4.15 4.43 5.50 which in LaTeX is \begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|} \hline Old depth:& 5.38& 5.60& 4.35& 4.83& 5.03& 4.78& 6.13& 4.10& 4.38& 5.28\\ \hline New depth:& 5.05& 4.95& 4.13& 4.58& 4.53& 4.60& 6.10& 4.15& 4.43& 5.50\\ \hline \end{tabular} A specific tree would only be drawn for 4 or more numbers given on the command line. You can still draw trees with n = 0, 1, 2, 3 elements, by generating them randomly with java Tree n . To repeat, correct answers to the two bonus questions (b) and (g) give 5% of marks each and are added to your marks. However, the total will not exceed 100%, which you can also achieve by answering the remaining questions perfectly. We hope you enjoy this project! END of assessed coursework for 2019/20 Good luck! 10
