CS242 – Spring 2021 – Assignment
homework | Algorithm | java代写 | assignment作业 – 这是一个关于Algorithm的题目, 主要考察了关于Algorithm的内容,是一个比较经典的题目, 是有一定代表意义的Algorithm/java等代写方向, 该题目是值得借鉴的assignment代写的题目
Collaboration policy: The goal of assignment is to give you practice in mastering the course material. Consequently, you are encouraged to collabo- rate with others. In fact, students who form study groups generally do better on exams than do students who work alone. If you do work in a study group, however, you owe it to yourself and your group to be prepared for your study- group meeting. Specifically, you should spend at least 3045 minutes trying to solve each problem beforehand. If your study group is unable to solve a problem, it is your responsibility to get help from the instructor before the assignment is due. For this assignment, you can form a team of up to three members. Each team must write up each problem solution and/or code any programming assignment without external assistance, even if you collaborate with others outside your team for discussions. You are asked to identify your collabo- rators outside your team. If you did not work with anyone outside your team, you must write Collaborators: none. If you obtain a solution through research (e.g., on the web), acknowledge your source, but write up the solution in your own words. It is a violation of this policy to submit a problem solution that any member of the team cannot orally explain to the instructor.No other student or team may use your solutions; this includes your writing, code, tests, documentation, etc. It is
a violation of this policy to permit anyone other than the instructor and yourself read-access to the location where you keep your solutions.
Submission Guidelines: Your team has to submit your work on Black- board (no email) by the due date. Only one submission per team is nec- essary. For each class in the programming assignments you must use the header template provided in Blackboard. Make sure that you identify your team members in the header, and any collaborators outside your team, if none, write none. Your code must follow the java formatting standards posted in Blackboard. Format will also be part of your grade. To complete the submission, you have to upload two files to Blackboard: your source file and your class file. Your answers to questions that do not require coding must be included in the remarks section of the header. The submission will not be accepted in any other format.
Style and Correctness: Keep in mind that your goal is to communicate. Full credit will be given only to the correct solution which is described clearly. Convoluted and obtuse descriptions might receive low marks, even when they are correct. Also, aim for concise solutions, as it will save you time spent on write-ups, and also help you conceptualize the key idea of the problem.
Assignment #3 Grading Rubric
Coding:
Program
characteristic
Program feature
Credit
possible
Design
30%
Algorithm 30%
Functionality
30%
Program runs
without errors
20%
Correct result given 10%
Input
15%
User friendly,
typos, spacing
10%
Values read in
correctly
5%
Output
15%
Output provided 10%
Proper spelling,
spacing, user friendly
5%
Format
10%
Comments, name 5%
Indentation 5%
TOTAL 100%
Non-coding: Embedded in questions.
1(15) 2(40) 3(15) 4(15) 5(15) TOTAL(100) EC
Assignment: As you know at this point, Dynamic Programming is a powerful technique that explores all possible cases to obtain a solution, yet achieves an exponen- tial improvement in running time when compared with a simpler brute-force approach. A well-known example of Dynamic Programming usage is Text Justification, where we are given an array of words and a page width and we have to decide how to split the text so that it looks nice after justifying against margins. The purpose of this homework is to compare experimentally the result obtained justifying text with a greedy algorithm (as used by MS Word) against doing the same using LATEX rules and Dynamic Programming. Specifically, your assignment is the following.
- (15 points) Implement a badness method that, given a widthas a number of characters, an arrayW[0… n1] of strings, and two indices iandjsuch that 0in1 and 1jn, computes the following function used by LATEX.
badness(W, i, j, ) =
{
(`(W, i, j))^3 if`(W, i, j)0,
otherwise.
Where `(W, i, j) is the total length in characters of the words from
indexito j1 in the arrayW, taking into account that one space
must be left in between each pair of consecutive words.
- (40 points) Implement a split method that, given as parameters the widthand the arrayW, returns a listLof the indices of the array where each line should start to minimize the aggregated badness (i.e. the sum of the badness of all lines in such split). The Dynamic Pro- gramming pseudocode to compute the minimum aggregated badness seen in class follows in Algorithms 1 and 2.
- (15 points) Implement a justify method that, given as parameters the width, the array of wordsW, and the list of breakpointsL, creates a text file, call it for instancejust.txt, justified accordingly. That is, for each line, your code should spread the words evenly in the width ofcharacters. Hint: a line starting at indexiand ending at index j1 hasjiwords. So, the`(W, i, j) space characters have to be distributed roughly evenly among theji1 separations of words.
Algorithm 1:Minimum Badness
input :an arrayW[0... n1] ofnstrings and an integer.
output:an array with the indices ofW where the next line of each
suffix ofW should start to obtain the minimum aggregated
badness.
1 memo[0… n]new array of integers 2 linebreaksmemo[0… n]new array of integers 3 fori= 0tondo memo[i] 1 4 Memoized Minimum Badness(W, 0 , memo, linebreaksmemo, ) 5 returnlinebreaksmemo
- (15 points) Implement a main method that prompts the user to enter a number of wordsnand a page widthas a number of characters. Then, create the arrayW[0… n1] of strings and fill it with random strings. The length of each string should be chosen at random in the range [1,15]. Notice that, to the extent to evaluate the result of justification, the actual characters used are irrelevant. For instance, you could choose all the characters to be the same, as in aaaaaaaaaaa. (If you prefer to use real text, read the words from an input file or the web.) Then, your main method should call the method split to obtain the list of breakpointsL, and subsequently call the method justify passingW, , andLas parameters. Finally, output the arrayW to a second text file in a single line, call it for instanceunjust.txt.
- (15 points) Evaluation: Compare the result ofjust.txtwithunjust.txt opening the latter in MS Word and justifying the text. How do they look? Can you evaluate if MS Word is using a greedy approach? Play with the maximum word length of 15 as needed.
Algorithm 2:Memoized Minimum Badness input :an arrayW[0… n1] ofnstrings, an integeriin the range [0, n], an arraymemo[0… n] of integers, an array linebreaksmemo[0… n] of integers, and an integer. output:minimum aggregated badness of the suffix [i,n-1] ofW. 1 ifmemo[i] 0 then returnmemo[i] 2 ifi=nthen 3 memo[i] 0 4 linebreaksmemo[i]n 5 else 6 min 7 indexof min 0 8 forj=i+ 1tondo 9 tempbadness(W, i, j, ) 10 temptemp+ Memoized Minimum Badness(W, j, memo, linebreaksmemo, )
11 iftemp < minthen 12 mintemp 13 indexof minj
14 memo[i]min 15 linebreaksmemo[i]indexof min
16 returnmemo[i]