” 写作comp10002程序、 辅导Systems编程语言、web/HTML编程 写作School of Computing and Information Systemscomp10002 Foundations of AlgorithmsSemester 2, 2020Assignment 2Learning OutcomesIn this project, you will demonstrate your understanding of dynamic memory and linked data structures (Chapter10), and extend your skills in terms of program design, testing, and debugging. You will also learn aboutRobotic Process Automation (RPA) for executing routine clerical tasks in organizations, and implement simplemechanisms for checking candidate routines in a given trace of executed activities.Robotic Process AutomationRPA is an emerging technology that allows organizations to automate repetitive clerical work by executingsoftware scripts (RPA scripts) that support executions of sequences of fine-grained interactions with Web anddesktop applications. An example of such repetitive clerical work is transferring data across information systems,for instance, from a spreadsheet into a Web form (refer to Figure 1).(a) Student records spreadsheet (b) New Record creation formFigure 1: Extract of spreadsheet with student data that needsto be transferred to a Web form; httpss://bit.ly/2SPet3u.A common approach to eliciting RPA scriptsnowadays is through observing workers or interviews,which is time-consuming. Alistairand Artem would like to start a business, calledAA RPA, which will offer a new product to themarket. This product will aim to automate theprocess of identifying routines, i.e., sequencesof interactions with User Interfaces of informationsystems that lead to the same effect. Forexample, in the context of Figure 1, a routineis a procedure for transferring data from a rowin sub-figure (a) to the Web form in sub-figure(b) and clicking the Save button. As the firststep, we developed a tool that records a traceof consecutive actions, where an action capturesinformation about user interaction with an informationsystem. Examples of actions include selectinga cell in a spreadsheet, copying the content of a cell, and clicking a button in a Web form. An action ischaracterized by a precondition and effect, each captured as a collection of Boolean variables.For example, the precondition of clicking the Save button action in the Web form in Figure 1(b) maybe that variables FirstNameEntered, LastNameEntered, and CountryOfRresidenceEntered are all set totrue, and variable InternationalStudentSelected is set to false. The effect of this example action may bethat variable NewStudentEntryCreated is set to true, and all the precondition variables are set to false.As the next step, we would like to develop a tool that given a trace and a candidate routine, both specified assequences of actions with preconditions and effects, identifies all sub-sequences of actions in the trace that generatethe same cumulative effect as the candidate routine. Candidate routines that lead to identifying many suchsub-sequences can be recommended for implementing in RPA scripts. Note that the identified sub-sequencesmay, in general, be different as, for example, a user may be transferring content from the spreadsheet cells to theform in different orders for different students (first name then last name, or vice versa).Your task is to implement a tool for checking candidate routines.Input DataYour program should read input from stdin. The input starts by listing names of Boolean variables, one perline, that must be set to true in the initial state, where the initial state is defined by values of all the Booleanvariables before a trace gets executed. All the other variables must be set to false in the initial state. An input line1with a single character # denotes the end of input of the initial state. The lines that follow define actions, oneaction per line. Each action is defined as a quintuple. The first two elements of an action list its precondition,i.e., variables that must be set to true and false to enable the action. The third element is the name of the action.The last two elements of an action specify its effect, i.e., variables that are set to be true and false after the actionis executed. Another input line with a single character # denotes the end of the action definition section of theinput. The subsequent input characters encode a trace, each referring to the name of the action executed in thecorresponding position of the trace. All the lines of the input, except the last line, are not empty. The followingfile test0.txt defines the initial state, three actions, and a trace executed from the initial state (the numbers initalics show line numbers and are not part of the input file).Boolean variables are denoted by characters a, b, . . . , z (lower-case Latin alphabet letters), while actionnames are referred to as A, B, . . . , Z (upper-case Latin alphabet letters). Hence, the above input specifies theinitial state in which variables a, b, x, y, and z are set to true, while variables c, d, . . . , w are set to false. Theinput trace consists of five actions, see line 11. From the initial state, the trace commences by executing action X,followed by an execution of action V, followed by action U, followed by another occurrence of V, and concludesby another occurrence of action U. Actions U, V, and X are defined at lines 79 of the input. The five componentsof each action are delimited using the colon character :. For example, the action defined at line 7 of the inputhas name X. This action can occur in a state where variables a and b are set to true, and variable c is set to false.Once this action is executed, variables c and f are set to true, while variable b is set to false.Stage 0 Reading and Analyzing Input Data (8/20 marks)The first version of your program should read the input from stdin, ensure that the input trace is valid, and printout some basic information so that you can be sure you have read the inputs correctly. A valid trace is composedof actions that occur in states that satisfy their preconditions; otherwise, the trace is invalid. The required outputfrom this stage generated for test0.txt file shown above is the summary shown below on the left.mac: ass2-soln test0.txt==STAGE 0===============================Number of distinct actions: 3Length of the input trace: 5Trace status: valid—————————————-abcdefghijklmnopqrstuvwxyz 11000000000000000000000111X 10100100000000000000000111V 10100100000000011000000111U 10100100000000000000000111V 10100100000000011000000111U 10100100000000000000000111mac: ass2-soln test1.txt==STAGE 0===============================Number of distinct actions: 3Length of the input trace: 5Trace status: invalid—————————————-abcdefghijklmnopqrstuvwxyz 11000000000000000000000111X 10100100000000000000000111V 10100100000000011000000111U 11100100000000000000000111V 11100100000000011000000111The basic information printed by your program should specify the number of distinct actions, length of the trace,and the status of the trace read from the input, which are 3, 5, and valid, respectively, for input file test0.txt.This information should be followed by a delimiter line, followed by the detailed specification of the trace givenas a table of ASCII characters. The columns in this table refer to variables, while rows specify states and executedactions. A state is encoded as a sequence of 0 and 1 characters, where 0 indicates that the correspondingvariable (specified in the column header) is set to false and 1 indicates that the variable is set to true. The firstprinted state, denoted by character in the left-most column, specifies the initial state. Each subsequent lineprints the next executed action, followed by the sequence of zeros and ones that encodes the state one achievesafter executing the action. For instance, the execution of action X in the example input trace flips the values ofvariables b and f in the initial state.If the input trace is invalid, your program should report the corresponding status of the trace and print itsvalid prefix. For example, if line 9 in file test0.txt is changed from fpq:b:U::pq to fpq:b:U:b:pq toobtain file test1.txt, then your program should produce the output shown above on the right. In this case,the second occurrence of action U cannot take place as its precondition requires that variable b is set to false.However, b is set to true after the execution of the first four actions of the trace.2All inputs will follow the format specified in the Input Data section. No input action will specify that avariable is equal (or should be set) to true and false simultaneously, e.g., a:a:X:b:b. Also, no input actionwill set a value of a variable as in the precondition, e.g., a:b:Y:a:b. Your program will not be tested onerroneous inputs. Refer to the input files distributed with this specification for the exact formatting of inputs.Stage 1 Check Basic Routines (16/20 marks)Extend your program from Stage 0 to perform a basic check of a candidate routine by identifying all trace subsequencesthat produce the same effect. All of the Stage 0 output should be retained. If the input proceeds witha line with a single character #, your program should generate Stage 1 output, which starts with this line:==STAGE 1===============================For each subsequent input line containing a candidate routine specified as a sequence of action names, discoverand print non-overlapping sub-sequences of consecutive actions of the trace that produce the same cumulativeeffect as the candidate routine. Proceed from left to right in the trace. Once the shortest sub-sequence with thedesired effect is identified, record it and restart searching from the next position in the trace.The cumulative effect of a routine or sequence of actions is determined as all the values (true and false)set to the Boolean variables as effects of the actions executed in the order they appear in the routine/sequence.Considering input file test0.txt, candidate routine VU generates the cumulative effect of setting variables pand q to false. First, action V sets p and q to true. Next, action U updates them to be false. Hence, would inputfile test0.txt be modified to contain a single character # at line 12 and string VU at line 13 to encode acandidate routine followed by the new line character, Stage 1 output should proceed by printing these lines:Candidate routine: VU1: VU3: VUHere, the first line specifies the candidate routine and the two subsequent lines refer to two sub-sequences thatstart at positions 1 and 3 of the input trace (counting positions from zero); trace positions are printed using theformatting string %5d. These two sub-sequences generate the same cumulative effect as the candidate routine.Each subsequent input line with a candidate routine should be processed in the same way, and its outputshould be separated from the previous output by the delimiter line composed of – characters, refer to Stage 0specification above for examples of using the delimiter line. Consider input file test2.txt listed below.The Stage 1 output for input file test2.txt is shown below on the left. Indeed, both sequences of actions D andAB have the cumulative effect of setting variables x, y, and z to true, and are therefore identified. Sub-sequenceswith smaller start positions should be printed first.==STAGE 1===============================Candidate routine: AB0: D2: AB—————————————-Candidate routine: D0: D2: AB==STAGE 2===============================Candidate routine: D0: D2: AB5: ACGHE—————————————-Candidate routine: AB0: D2: AB5: ACGHE==THE END===============================Stage 2 Check Advanced Routines (20/20 marks)Extend your program from Stage 1 to perform further checks for the input candidate routines. All of the outputfrom Stages 0 and 1 should be retained. If your input after Stage 1 continues with a single character lineof #, process subsequent input lines with candidate routines (one routine per line). This time, an identifiedsub-sequence of actions in the input trace should be allowed to modify the values of variables not set by thecandidate routine. However, in this case, once all the actions of the identified sub-sequence are executed, the3values of such variables must be set to the values they had before executing the sub-sequence. Note that thisknowledge of variable values can be obtained from the preconditions of the trace actions.For example, the sub-sequence of actions ACGHE in the trace of input file test2.txt sets values of variablesi, j, x, y, and z. Note that, to execute, action G requires that i and j are both set to false, and sets them to true.However, next, action H sets them to false, which are their original values at the start of the sub-sequence. Hence,the cumulative effect of executing ACGHE is the same as that one of executing D or AB, i.e., setting x, y, and z totrue. The complete output of Stage 2 for input file test2.txt is proposed on the right of the listings presentedin the specification of Stage 1. If your program concludes with Stage 2, at the end, it should output this line:==THE END===============================Important…The outputs generated by your program should be exactly the same as the sample outputs for the correspondinginputs. You should not assume the maximal allowed lengths for the input trace and candidate routines and, thus,use malloc and linked lists to store them. Regardless of the algorithmic techniques you will employ in thisassignment, your program should run under 1 second on each sample input.Boring But Important…This project is worth 20% of your final mark, and is due at 11:00pm on Friday 30 October.Submissions that are made after that deadline will incur penalty marks at the rate of two marks per day orpart day late. Students seeking extensions for medical or other outside my control reasons should emailammoffat@unimelb.edu.au as soon as possible after those circumstances arise. If you attend a GP or otherhealth care service as a result of illness, be sure to take a Health Professional Report (HPR) form with you (getit from the Special Consideration section of the Student Portal), you will need this form to be filled out if yourillness develops in to something that later requires a Special Consideration application to be lodged. You shouldscan the HPR form and send it with any non-Special Consideration assignment extension requests.A rubric explaining the marking expectations is provided on the FAQ page. You need to submit your programfor assessment; detailed instructions on how to do that will be posted on the FAQ page once submissions areopened. Submission will not be done via the LMS or grok, and you will instead use a software system knownas submit. You can (and should) use submit both early and often to get used to the way it works, and alsoto check that your program compiles correctly on our test system, which has some different characteristics to thelab machines. Failure to follow this simple advice is highly likely to result in tears. Only the last submission thatyou make before the deadline will be marked. Marks and a sample solution will be available on the LMS twoweeks after submissions close.Academic Honesty: You may discuss your work during your workshop, and with others in the class, but whatgets typed into your program must be individual work, not copied from anyone else. So, do not give hard copy orsoft copy of your work to anyone else; do not lend your Uni backup memory stick to others for any reasonat all; and do not ask others to give you their programs just so that I can take a look and get some ideas, Iwont copy, honest. The best way to help your friends in this regard is to say a very firm no if they ask to seeyour program, pointing out that your no, and their acceptance of that decision, are the only way to preserveyour friendship. See httpss://academicintegrity.unimelb.edu.au for more information. Note also thatsolicitation of solutions via posts to online forums, whether or not there is payment involved, is also AcademicMisconduct. In the past students have had their enrolment terminated for such behavior.The FAQ page contains a link to a program skeleton that includes an Authorship Declaration that you mustsign and include at the top of your submitted program. Marks will be deducted (see the rubric linked fromthe FAQ page) if you do not include the declaration, or do not sign it, or do not comply with its expectations.A sophisticated program that undertakes deep structural analysis of C code identifying regions of similaritywill be run over all submissions. Students whose programs are identified as containing significant overlapswill have substantial mark penalties applied, or be referred to the Student Center for possible disciplinaryaction, without further warning.Nor should you post your code to any public location (github, codeshare.io, etc) while the assignment isactive or prior to the release of the assignment marks.如有需要，请加QQ：99515681 或邮箱：99515681@qq.com
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
