Reference no: EM132681097

COMP10002 Foundations of Algorithms Assignment - School of Computing and Information Systems - The University of Melbourne, Australia

Learning Outcomes - In this project, you will demonstrate your understanding of dynamic memory and linked data structures (Chapter 10), and extend your skills in terms of program design, testing, and debugging. You will also learn about Robotic Process Automation (RPA) for executing routine clerical tasks in organizations, and implement simple mechanisms for checking candidate routines in a given trace of executed activities.

Robotic Process Automation -

RPA is an emerging technology that allows organizations to automate repetitive clerical work by executing software scripts (RPA scripts) that support executions of sequences of fine-grained interactions with Web and desktop 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 common approach to eliciting RPA scripts nowadays is through observing workers or in-terviews, which is time-consuming. Alistair and Artem would like to start a business, called A&A RPA, which will offer a new product to the market. This product will aim to automate the process of identifying routines, i.e., sequences of interactions with User Interfaces of informa-tion systems that lead to the same effect. For example, in the context of Figure 1, a routine is a procedure for transferring data from a row in sub-figure (a) to the Web form in sub-figure (b) and clicking the "Save" button. As the first step, we developed a tool that records a trace of consecutiveactions, where an action captures information about user interaction with an infor-mation system. Examples of actions include se-lecting a cell in a spreadsheet, copying the content of a cell, and clicking a button in a Web form. An action is characterized by apreconditionandeffect, 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) may be that variablesFirstNameEntered, LastNameEntered, and CountryOfRresidenceEnteredare all set to true, and variable InternationalStudentSelectedis set to false. The effect of this example action may be that variable NewStudentEntryCreatedis 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 acandidate routine, both specified as sequences of actions with preconditions and effects, identifies all sub-sequences of actions in the trace that gen-erate the same cumulative effect as the candidate routine. Candidate routines that lead to identifying many such sub-sequences can be recommended for implementing in RPA scripts. Note that the identified sub-sequences may, in general, be different as, for example, a user may be transferring content from the spreadsheet cells to the form 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.

Stage 0 - Reading and Analyzing Input Data

The first version of your program should read the input fromstdin, ensure that the input trace is valid, and print out some basic information so that you can be sure you have read the inputs correctly. Avalidtrace is composed of actions that occur in states that satisfy their preconditions; otherwise, the trace isinvalid. The required output from this stage generated fortest0.txtfile shown above is the summary shown below on the left.

The 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 are3, 5, andvalid, respectively, for input filetest0.txt.

This information should be followed by a delimiter line, followed by the detailed specification of the trace given as a table of ASCII characters. The columns in this table refer to variables, while rows specify states and executed actions. A state is encoded as a sequence of '0' and '1' characters, where '0' indicates that the corresponding variable (specified in the column header) is set to false and '1' indicates that the variable is set to true. The first printed state, denoted by character '>' in the left-most column, specifies the initial state. Each subsequent line prints the next executed action, followed by the sequence of zeros and ones that encodes the state one achieves after executing the action. For instance, the execution of actionXin the example input trace flips the values of variablesbandfin the initial state.

If the input trace is invalid, your program should report the corresponding status of the trace and print its valid prefix. For example, if line 9 in filetest0.txtis changed from "fpq:b:U::pq" to "fpq:b:U:b:pq" to obtain filetest1.txt, then your program should produce the output shown above on the right. In this case, the second occurrence of action Ucannot take place as its precondition requires that variablebis set to false. However,bis set to true after the execution of the first four actions of the trace.

All inputs will follow the format specified in the Input Data section. No input action will specify that a variable is equal (or should be set) to true and false simultaneously, e.g., "a:a:X:b:b". Also, no input action will set a value of a variable as in the precondition, e.g., "a:b:Y:a:b". Your program will not be tested on erroneous inputs. Refer to the input files distributed with this specification for the exact formatting of inputs.

Stage 1 - Check Basic Routines

Extend your program from Stage 0 to perform a basic check of a candidate routine by identifying all trace sub-sequences that produce the same effect. All of the Stage 0 output should be retained. If the input proceeds with a 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, discover and print non-overlapping sub-sequences of consecutive actions of the trace that produce the same cumulative effect as the candidate routine. Proceed from left to right in the trace. Once theshortestsub-sequence with the desired 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 filetest0.txt, candidate routine VUgenerates the cumulative effect of setting variablesp andqto false. First, action Vsetspandqto true. Next, action Uupdates them to be false. Hence, would input filetest0.txtbe modified to contain a single character '#' at line 12 and string "VU" at line 13 to encode a candidate routine followed by the new line character, Stage 1 output should proceed by printing these lines:

Candidate routine: VU

1: VU

3: VU

Here, the first line specifies the candidate routine and the two subsequent lines refer to two sub-sequences that start at positions 1 and 3 of the input trace (counting positions from zero); trace positions are printed using the formatting 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 output should be separated from the previous output by the delimiter line composed of '-' characters, refer to Stage 0 specification above for examples of using the delimiter line. Consider input filetest2.txtlisted below.

The Stage 1 output for input filetest2.txtis shown below on the left. Indeed, both sequences of actions Dand ABhave the cumulative effect of setting variablesx, y, and zto true, and are therefore identified. Sub-sequences with smaller start positions should be printed first.

Stage 2 - Check Advanced Routines

Extend your program from Stage 1 to perform further checks for the input candidate routines. All of the output from Stages 0 and 1 should be retained. If your input after Stage 1 continues with a single character line of '#', process subsequent input lines with candidate routines (one routine per line). This time, an identified sub-sequence of actions in the input trace should be allowed to modify the values of variables not set by the candidate routine. However, in this case, once all the actions of the identified sub-sequence are executed, the values of such variables must be set to the values they had before executing the sub-sequence. Note that this knowledge of variable values can be obtained from the preconditions of the trace actions. For example, the sub-sequence of actionsACGHEin the trace of input filetest2.txtsets values of variables i, j, x, y, and z. Note that, to execute, action Grequires thatiandjare both set to false, and sets them to true.

However, next, actionHsets them to false, which are their original values at the start of the sub-sequence. Hence, the cumulative effect of executing ACGHEis the same as that one of executing DorAB, i.e., setting x, y, and z to true. The complete output of Stage 2 for input file test2.txtis proposed on the right of the listings presented in the specification of Stage 1. If your program concludes with Stage 2, at the end, it should output this line:

==THE END===============================

Attachment:- Foundations of Algorithms Assignment File.rar