Lab 6: Using Python with MySQL and Microsoft SQL Server This assignment practices developing Java code that uses JDBC to connect to a MySQL database. Customer (CustomerId, CustomerName) Employee (EmployeeId, EmployeeName, Salary, SupervisorId) Product(ProductId, ProductName, ListPrice) Orders (OrderId, OrderDate, CustomerId, EmployeeId, Total) OrderedProduct (OrderId, ProductId, Quantity, Price) Initial Steps Download the starter code Python file and the test file Python file. There is also a DDL script to create the database. Use VSCode to edit the code files. You will need to install the Python extension to execute. Write the code to complete the methods in OrderDB.py (look for TODO items). The Python test library is called unittest. To add it to your project in VSCode, click on the test (beaker) icon, then click on the Configure Tests blue button. VSCode will ask for the test library. Respond with unittest and indicate the test files will have the format Test*.py.
Assignment 5 – Converting ER/UML Diagrams into the Relational Model Build a pet daycare database that tracks information on owners and their pets when they stay at a pet daycare. There are three components: On Canvas submit a single document that contains a screenshot of the UML design (part 1), the subclass info (part 2), and the conversion to the relational model (part 3). If you used PrairieLearn, make sure the screenshot shows the user name of one student in your group and the mark received. Question Description The project will build an online store like Amazon.com selling whatever products you want. The first step is to develop a database design and convert that design into SQL DDL. Description: A Customer is identified by an auto-increment id. Other attributes include first name, last name, email, phone number, street address, city, province/state, postal code, and country. A Customer also has a user id (unique) and password. The store sells products. A Product has an auto-increment id, name, price, image URL (string), image (BLOB), and description. A product has a category. A category has one or more Products. A Category has an auto-increment id and name. Deliverables
Lab 4: Building ER diagrams using an UML modeling tool This lab designs ER diagrams in UML notation. The AutoER auto-grading software on PrairieLearn is used to design and mark your UML diagrams. It is also valuable to learn how to use commercial UML design software such as Astah. Note: Astah no longer has a free community version. Request a student license or use the 30-day trial. drawio is an online drawing tool that can also be used but it does not have as good support for database modeling in UML. AutoER PrairieLearn link: https://plcanary.ok.ubc.ca/pl/course_instance/6/assessment/145 When using PrairieLearn, for each question please submit a screenshot showing your answer and the marking. Make sure the screenshot shows your name. Construct a database design in UML for a stock market tracking database. Data types are not needed. The database tracks companies, where a company has a name and is identified by its ticker symbol. Each company participates in a particular industry. An industry has an identifying name and also a description. Stock market analysts cover stocks and produce recommendations. Analysts are distinguished from each other by the name of their firm and their name. Analysts also have an accuracy rating that measures the accuracy of their recommendations. Each recommendation is from a particular analyst on a certain company. A recommendation includes a predicted price in the next 12 months and a rating for the stock (buy, hold, sell). Construct a database design in UML for a question databank. Data types are not needed. A course is identified by its course number and has a course name and year. A question is used in a course offering to test student knowledge. A question is identified by its questionId and also contains a questionName, questionText, and questionAnswer.
customer(cid: integer, cname: string, address: string, city: string, state: string) product(pid: integer, pname: string, price: currency, inventory: integer) shipment(sid: integer, cid: integer, shipdate: DateTime) shippedproduct(sid: integer, pid: integer, amount: integer) 1. Return the customer name and address as one field called fullAddress that consists of the address, city, state. Only show customers in ‘IA’ or ‘BC’ that have a valid address. Order by customer name ascending. Hint: You will need the concat function in MySQL or the concatenate operator (||) if using PrairieLearn. Output: +—————–+————————————-+ | cname | fullAddress | +—————–+– ———————————–+ | Aiden Adams | 324 2A Street, Kelowna, BC | | Beth Rosebud | 1 First Street, Muscatine, IA | | David Denter | 23456 Main Street, Vernon, BC | | Elish Elias | 3445 Hwy 97 North, Iowa City, IA | +—————–+————————————-+ Output: +—–+———————+—–+——–+ | sid | shipdate | pid | amount | +—–+———————+– 1. Find all customers that have an ‘R’ or ‘T’ in their name and have a state of ‘MI’ or ‘IA’. Order by customer name descending. Output: +—–+—————–+———————+———–+——-+ | cid | cname | address | city | state | +—–+—————–+———————+———–+——-+ | 8 | Shannon Rose | NULL | Wyandotte | MI | | 2 | Joe Smithsonian | 245 Straight Street | Iowa City | IA | | 9 | Beth Rosebud | 1 First Street | Muscatine | IA | +—–+—————–+———————+———–+——-+ 1. Return a list of the unique product id and names that have shipped before with an amount less than 5. Order by product id descending. Output: +—–+————————-+ | pid | pname | +—–+————————-+ | 10 | Textbook | | 9 | Sports Car | | 8 | Table | | 7 | Deluxe Sweet Collection | | 4 | Chocolate Bar | | 3 | Teddy Bear | | 2 | Wooden Chair | | 1 | Swiss Chocolate | +—–+————————-+ 1. For each state, return the number of customers in that state and the number of shipments for customers in that state. Hint: Note: Count customers in a state even if they do not have any shipments. Output: +——-+————–+————–+ | state | numCustomers | numShipments | +——-+————–+—— ——–+ | BC | 4 | 7 | | CA | 2 | 6 | | IA | 3 | 5 | | AB | 1 | 2 | +——-+————–+————–+ Output: Chair | 499.95 | +——-+——+————–+———–+ Output: +—–+—————–+———————-+——————–+——————-+ | pid | pname | numberOfTimesShipped | totalAmountShipped | totalValueShipped | +—–+—————–+———————+——————–+——————-+ | 10 | Textbook | 3 | 6 | 1500.00 | | 2 | Wooden Chair | 6 | 38 | 3799.62 | | 8 | Table | 3 | 38 | 113.62 | | 1 | Swiss Chocolate | 7 | 44 | 1451.56 | +—–+—————– +———————-+——————–+——————-+ 1. Return pairs of customers (only show a pair once) that have been shipped the same product. Return the number of times the pair of customers have been shipped the same product (numShippedProducts). Order by numShippedProducts descending, then first customer name ascending, and second customer name ascending. Note: If product 1 is in two shipments for customer 4 and two shipments for customer 15, that counts as 4 (2 x 2). We are not eliminating any duplicates when counting in this question. Show customer pairs that have 5 or more times that they have been shipped the same product. Output: +—–+—————–+—–+—————–+—————-+ | cid | cname | cid | cname | numSameShipped | +—–+—————–+—–+—————–+—————-+ | 4 | Russell Johnson | 15 | Elish Elias | 7 | | 4 | Russell Johnson | 6 | Scott Charles | 7 | | 2 | Joe Smithsonian | 4 | Russell Johnson | 6 | | 2 | Joe Smithsonian | 6 | Scott Charles | 5 | | 6 | Scott Charles | 15 | Elish Elias | 5 | +– —+—————–+—–+—————–+—————-+ 1. Return a complete list of all customers (cid, cname), the total number of shipments, and total shipped value (amount*price) that they have been shipped. Return the bottom five customers by total shipped value. Output: +—–+—————–+————–+——————-+ | cid | cname | numShipments | totalShippedValue | +—–+—————–+————–+——————-+ | 1 | Fred Smith | 0 | NULL | | 5 | John Doe | 0 | NULL | | 14 | David Denter | 0 | NULL | | 7 | Robert Dean | 1 | 72.49 | | 3 | Steve Stevenson | 1 | 164.95 | +—–+—————–+————–+——————-+ Output: +—–+—————–+————–+ | pid | pname | numShipments | +—–+—————–+————-+ | 1 | Swiss Chocolate | 8 | | 2 | Wooden Chair | 8 | | 4 | Chocolate Bar | 6 | | 10 | Textbook | 5 | +—-+—————–+————–+
This assignment practices SQL DDL. Write the SQL DDL to create the following 5 tables describing cooking: Recipe, Ingredient, Author, Cook, Requires. Make sure that every table has a primary key. An Author table where each author is identified by an integer id and has a name (up to 30 characters). An Ingredient table where each ingredient has an id of exactly 5 characters and a name (up to 30 characters). A Recipe table where each recipe is identified by a field called id that is an integer. Other attributes include name (string up to 40 characters), authorId (integer), and directions (string up to 255 characters). Make all foreign keys set to null on delete and no action (generate error) on update. A Requires table that stores what ingredients are needed in a recipe. This table has a recipe id, ingredient id, and amount (floating point number). Make all foreign keys set to cascade on both update and delete. Write the SQL DDL to perform the following modifications to the database created in Question 1. Insert the following records into the appropriate tables. Author (1,’Joe Smith’) (2,’Fred Funk’) Ingredient (‘BUTTR’,’Butter’) (‘FLOUR’,’Flour’) (‘MILK’,’Milk’) (‘EGGS’,’Eggs’) (‘SUGAR’,’Sugar’) Recipe (100,’Cookies’,1,’Mix butter, flour, milk, eggs, and sugar. Then hope for the best.’) (200,’Bread’,2,’Knead flour with milk and eggs. Bake at 450F or until brown.’) Requires You figure it out based on both recipes (choose your own amount). Cook 1. Change the name of the ingredient with id ‘MILK’ to ‘Skim Milk’. 2. Increase the amount of all required ingredients used with recipe 100 by 2. 1. Delete all recipes written by ‘Fred Funk’. How many rows are deleted when this statement is run? (1 mark) Note: In addition to testing when the foreign key is ON CASCADE, also recommend you try the DELETE when the foreign key on Recipe is either SET NULL or NO ACTION to see the difference. 2. Delete all ingredients required for recipe 200 with an amount greater than 2. Submission
Note: Use of Internet sources including Google, Stack Overflow, ChatGPT, and GitHub Copilot are ALLOWED but must be documented as part of the project deliverables. Include URLs to any sources or AI conversations used. It is NOT allowed to use code from other current or past students. Students receiving 90% or above on the labs 7, 8, and 10 (combined) will receive a digital badge. Make sure to include your email addresses on your documentation submission if you want to receive a digital badge. Development Stream Details: 1. Get inspired for your store and the products it sells by reviewing some of the best past projects. You should sell different products than the sample products provided in lab 7. 2. Submit documentation with your walkthrough on Canvas. Submit a zip file of all your code on Canvas as well. 3. Make sure your documentation contains the URL for your site as well as user ids and passwords. 4. List of features with points must be included when submitting your documentation. 5. Your web site should ideally run on a public cloud server. Analysis Stream Details: 1. Submit report document, Excel file, and any other files in a zip on Canvas. 2. Make sure your documentation contains any Internet sources used. 3. List of features with points must be included when submitting your documentation.
Lab 1: Querying using Relational Algebra RelaX – Online Relational Algebra Tool RelaX is an online relational algebra tool that we will use for the assignments. It allows entering relational algebra expressions and executing them to get results. The data set can be loaded from a GitHub Gist including the Bookstore data set GIST: 367f41bb51110ef3c84bb5f906f2fb87 used for sample relational algebra queries in this lab, and the Shipment database GIST: 585ee1836abb142a461d137e12dd14a3 used in the lab questions.Given the following relational schema, write queries in relational algebra to answer the English questions using the online relational algebra tool. The database definition is available as a Shipment database GIST: 585ee1836abb142a461d137e12dd14a3. The database is also available as an DDL file. Customer(cid: integer, cname: string, address: string, city: string, state: string) Product(pid: integer, pname: string, price: currency, inventory: integer) ShippedProduct(sid: integer, pid: integer, amount: integer) 1. Return the product id and amount for each ShippedProduct where the amount was less than or equal to 5 or greater than 30. Expected output:2. Return the shipment id, product id, shipped amount, product name, and inventory for products that have any past shipment amount more than the current inventory. Expected output:4. Return the product name, current inventory, shipment amount, and customer state where the product had a shipment of an amount at least 30% of its current inventory and the customer state was either ‘CA’ or ‘IA’. Expected output:5. Return a list of products (id, name, price) where the product has not been in any shipments or the product price is greater than $5 and has been shipped to a customer in ‘NJ’. Expected output:Note: Order does not matter for the output.
Project 2 involves writing an analysis of the results that you obtained in first project. You are to submit a paper that discusses the results of your analysis. Your paper should include the following items: • A brief introduction of the sorting algorithm that you have selected and how the two versions of the algorithm compare including: o High-level pseudocode for the sorting algorithms o A Big-Θ analysis of the two versions of the algorithm o An explanation of your approach to avoiding the problems associated with JVM warm-up o A discussion of the critical operation that you chose to count with an explanation of why you selected it • An analysis of the results of your study, which should include: o graph of critical operations for both algorithms and one for the execution times o a comparison of the performance of the two versions of the algorithm o a comparison of the critical operation results and the actual execution time measurements o a discussion of the significance of the coefficient of variance results and how it reflects the data sensitivity of your algorithm o how your results compare to your Big-Θ analysis • A conclusion that summarizes the important observations of your study If for any reason, it was necessary to revise the program you submitted in project 1, the revised source code should also be included along with the paper. Grading Rubric Criteria Meets Does Not Meet 100 points 0 pointsIntroduction 35 points 0 pointsContains a brief description of the sorting algorithm together with highlevel pseudocode for the algorithm (10) Does not contain a brief description of the sorting algorithm together with high-level pseudocode for the algorithm (0) Contains a correct Big-Θ analysis of the algorithm (10) Does not contain a correct Big-Θ analysis of the algorithm (0) Contains an explanation of your approach to avoiding the problems associated with JVM warm-up (10) Does not contain an explanation of your approach to avoiding the problems associated with JVM warmup (0) Contains a discussion of the critical operation that you chose to count with an explanation of why you selected it (5) Does not contain a discussion of the critical operation that you chose to count with an explanation of why you selected it (0) Analysis 50 points 0 pointsContains a graph of critical operations and one for the execution times (20) Does not contain a graph of critical operations and one for the execution times (10) Contains a comparison of the performance of the two versions of the algorithm (5) Does not contain a comparison of the performance of the two versions of the algorithm (0) Contains a comparison of the critical operation results and the actual execution time measurements (10) Does not contain a comparison of the critical operation results and the actual execution time measurements (0) Contains a discussion of the significance of the coefficient of variation results and how it reflects the data sensitivity of your algorithm (5) Does not contain a discussion of the significance of the coefficient of variation results and how it reflects the data sensitivity of your algorithm (0) Contains a discussion of how your results compare to your Big-Θ analysis (10) Does not contain a discussion of how your results compare to your Big-Θ analysis (0) Conclusion 15 points 0 pointsContains a conclusion that summarizes the important observations of your study (20) Does not contain a conclusion that summarizes the important observations of your study (0)
You must identify some critical operation to count that reflects the overall performance and modify each version so that it counts that operation. In addition to counting critical operations you must measure the actual run time in nanoseconds. In addition, you should examine the result of each call to verify that the data has been properly sorted to verify the correctness of the algorithm. If the array is not sorted, an exception should be thrown. It should also randomly generate data to pass to the sorting methods. It should produce 50 data sets for each value of n, the size of the data set and average the result of those 50 runs. The exact same data must be used for the iterative and the recursive algorithms. It should also create 10 different sizes of data sets. Choose sizes that will clearly demonstrate the trend as n becomes large. Be sure that the data set sizes are evenly spaced so this data can be used to generate graphs in project 2 This project should consist of two separate programs. The first of those programs should perform the benchmarking described above and generate two data files, one containing the results from the iterative algorithm and the one containing the results of the recursive algorithm. The benchmarking program must be written to conform to the following design:The output files should contain 10 lines that correspond to the 10 data set sizes. The first value on each line should be the data set size followed by 50 pairs of values. Each pair represents the critical element count and the time in nanoseconds for each of the 50 runs of that data set size. The second program should produce the report. It should allow the user to select the input file using JFileChooser. The report should contain one line for each data set size and five columns and should be displayed using a JTable. The first column should contain the data set size the second the average of the critical counts for the 50 runs and the third the coefficient of variance of those 50 values expressed as a percentage. The fourth and fifth column should contain similar data for the times. The coefficient of variance of the critical operation counts and time measurement for the 50 runs of each data set size provide a way to gauge the data sensitivity of the algorithm. Criteria Meets Does Not Meet 100 points 0 pointsDesign 20 points 0 pointsImplemented the required design (20) Did not implement the required design (0) Input 20 points 0 points Shown below is an example of how the report should look:You must research the issue of JVM warm-up necessary for properly benchmarking Java programs and ensure that your code performs the necessary warm-up so the time measurements are accurate. Grading RubricCreated 10 different sizes of data sets (10) Did not create 10 different sizes of data sets (0) Produced 50 data sets for each value of n (10) Did not produce 50 data sets for each value of n (0) Sorting Algorithm Benchmark Calculations 35 points 0 pointsCorrectly averaged the count and time results of the 50 data sets (10) Did not correctly average the count and time results of the 50 data sets Calculated the coefficient of variance of the critical operation counts and time measurement (5) Did not calculate the coefficient of variance of the critical operation counts and time measurement (0) Included correct sorting algorithm and code to verify data was properly sorted (10) Did not Include correct sorting algorithm and code to verify data was properly sorted (0) Performed the necessary warm-up so the time measurements were accurate (10) Did not perform the necessary warmup so the time measurements were accurate (0) Output 25 points 0 pointsOutput all the required data (15) Did not output all the required data (0) Output displayed in the required format (10) Output not displayed in the required format (0)
1. Using Warshall’s algorithm, compute the reflexive-transitive closure of the relation below. Show the matrix after the reflexive closure and then after each pass of the outermost for loop that computes the transitive closure. 0 0 0 0 1 1 0 0 0 00 0 1 1 0 0 0 1 0 0 1 0 1 0 1] 2. Using the matrix in the previous problem show the final result of executing Floyd’s algorithm on that matrix to produce a matrix containing path lengths. 3. Show the graph that corresponds to the matrix in the first problem assuming the rows and columns correspond to the vertices a, b, c, d and e. Show its condensation graph, renaming its vertices. Determine any topological order of that graph and create an adjacency matrix with the vertices ordered in that topological order. Finally compute the reflexive-transitive closure of that matrix. What characteristic of that matrix indicates that it defines a total order? 4. Using Floyd’s algorithm, compute the distance matrix for the weight directed graph defined by the following matrix: 0 4 5 2 0 3 3 [ ] 2 0 −2 −4 0 Show the intermediate matrices after each iteration of the outermost loop. Grading Rubric Problem Meets Does Not Meet Problem 1 10 points 0 pointsShowed the correct matrix after the reflexive closure (2) Did not show the correct matrix after the reflexive closure (0) Showed the correct matrices after each pass of the outermost for loop that computes the transitive closure (8) Did not show the correct matrices after each pass of the outermost for loop that computes the transitive closure (0)Problem 2 10 points 0 pointsShowed the correct final result of executing Floyd’s algorithm on that matrix to produce a matrix containing path lengths (10) Did not show the correct final result of executing Floyd’s algorithm on that matrix to produce a matrix containing path lengths (0) Problem 3 10 points 0 pointsShowed the correct graph that corresponds to the matrix in the first problem assuming vertices a, b, c, d and e (1) Did not show the correct graph that corresponds to the matrix in the first problem assuming vertices a, b, c, d and e (0) Showed its correct condensation graph, renaming its vertices (2) Did not show its correct condensation graph, renaming its vertices (0) Determined a correct topological order of that graph (2) Did not determine a correct topological order of that graph (0) Created a correct adjacency matrix with the vertices ordered in that topological order (1) Did not create a correct adjacency matrix with the vertices ordered in that topological order (0) Correctly computed the reflexivetransitive closure of that matrix (2) Did not correctly compute the reflexive-transitive closure of that matrix (0) Correctly explained what characteristic of that matrix indicates that it defines a total order (2) Did not correctly explain what characteristic of that matrix indicates that it defines a total order (0) Problem 4 10 points 0 pointsShowed the correct intermediate matrices after each iteration of the outermost loop using Floyd’s algorithm (7) Did not show the correct intermediate matrices after each iteration of the outermost loop using Floyd’s algorithm (0) Showed the correct final matrix after executing Floyd’s algorithm (3) Did not show the correct final matrix after executing Floyd’s algorithm (0)
Consider the following directed graph for each of the problems:1. Perform a breadth-first search on the graph assuming that the vertices and adjacency lists are listed in alphabetical order. Show the breadth-first search tree that is generated.2. Perform a depth-first search on the graph assuming that the vertices and adjacency lists are listed in alphabetical order. Classify each edge as tree, forward, back or cross edge. Label each vertex with its start and finish time.3. Remove all the back edges from the graph so it becomes a DAG. Perform a depth-first search recording the start and finish times. Using those finish times, provide the topological order that is produced. Provide one breadth-first topological order for that graph.4. Determine the strongly connected components of the graph using the algorithm provided in the sample problems. Show the final depth-first search of the transpose graph labeled with its start and finish times. Identify the strongly connected components based on that search.Grading Rubric Problem Meets Does Not Meet Problem 1 10 points 0 pointsBreadth-first search was done correctly assuming alphabetical vertex and adjacency lists (5) Breadth-first search was not done correctly assuming alphabetical vertex and adjacency lists (0) Tree provided is a correct breadth-first search tree (5) Tree provided is not a correct breadthfirst search tree (0) Problem 2 10 points 0 pointsPerformed a correct depth-first search (3) Did not perform a correct depth-first search (0) Tree edges correctly labeled (1) Tree edges not correctly labeled (0) Back edges correctly labeled (1) Back edges not correctly labeled (0) Forward edges correctly labeled (1) Forward edges not correctly labeled (0) Cross edges correctly labeled (1) Cross edges not correctly labeled (0) Provided correct start and finish times (3) Did not provide correct start and finish times (0) Problem 3 10 points 0 pointsCorrectly transformed the graph into a DAG (2) Did not correctly transform the graph into a DAG (0) Provided correct start and finish times (3) Did not provide correct start and finish times (0) Provided correct topological order from finish times (3) Did not provide correct topological order from finish times (0) Provided correct breadth-first topological order (2) Did not provide correct breadth-first topological order (0) Problem 4 10 points 0 pointsCorrectly transposed graph (2) Did not correctly transpose graph (0) Provided correct start and finish times (4) Did not provide correct start and finish times (0) Provided correct strongly connected components (2) Did not provide correct strongly connected components (0)
1. Execute Prim’s minimum spanning tree algorithm by hand on the graph below showing how the data structures evolve specifically indicating when the distance from a fringe vertex to the tree is updated. Clearly indicate which edges become part of the minimum spanning tree and in which order. Start at vertex A.2. Execute Kruskal’s algorithm on the weighted tree shown below. Assume that edges of equal weight will be in the priority queue in alphabetical order. Clearly show what happens each time an edge is removed from the priority queue and how the dynamic equivalence relation changes on each step and show the final minimum spanning tree that is generated.3. Give an example of a weighted graph for which the minimum spanning tree is unique. Indicate what the minimum spanning tree is for that graph. Give another example of a weighted graph that has more than one minimum spanning tree. Show two different minimum spanning trees for that graph. What determines whether a graph has more than one minimum spanning tree? 4. Given the following adjacency lists (with edge weights in parentheses) for a directed graph: A: B(5), C(3), D(1) B: C(1), D(3) C: B(3), D(7), E(1) D: A(6), C(3) E: F(5) F: D(3), A(4) Execute Dijkstra’s shortest-path algorithm by hand on this graph, showing how the data structures evolve, with A as the starting vertex. Clearly indicate which edges become part of the shortest path and in which order.Grading Rubric Problem Meets Does Not Meet Problem 1 10 points 0 pointsIndicated when the distance from a fringe vertex to the tree was updated (3) Did not indicate when the distance from a fringe vertex to the tree was updated (0) Indicated which edges became part of the minimum spanning tree and in which order (3) Did not indicate which edges became part of the minimum spanning tree and in which order (0) Provided the correct final minimum spanning tree (4) Did not provide the correct final minimum spanning tree (0) Problem 2 10 points 0 pointsShowed what happened each time an edge was removed from the priority queue (3) Did not show what happened each time an edge was removed from the priority queue (0) Showed how the dynamic equivalence relation changed on each step (3) Did not show how the dynamic equivalence relation changed on each step (0) Provided the correct final minimum spanning tree (4) Did not provide the correct final minimum spanning tree (0) Problem 3 10 points 0 pointsProvided a correct example of a weighted graph for which the minimum spanning tree is unique (2) Did not provide a correct example of a weighted graph for which the minimum spanning tree is unique (0) Provided the correct unique minimum spanning tree for that graph (2) Did not provide the correct unique minimum spanning tree for that graph (0) Provided a correct example of a weighted graph that has more than one minimum spanning tree (2) Did not provide a correct example of a weighted graph that has more than one minimum spanning tree (0) Provided two correct distinct minimum spanning trees for that graph (2) Did not provide two correct distinct minimum spanning trees for that graph (0) Correctly explained what determines whether a graph has more than one minimum spanning tree (2) Did not correctly explain what determines whether a graph has more than one minimum spanning tree (0)Problem 4 10 points 0 pointsClearly indicated which edges became part of the shortest path and in which order (5) Did not clearly indicate which edges became part of the shortest path and in which order (0) Provided correct final shortest path tree (5) Did not provide correct final shortest path tree (0)
The fourth project involves modifying the semantic analyzer for the attached compiler by adding checks for semantic errors. The static semantic rules of this language are the following: Variables and parameter names have local scope. The scope rules require that all names be declared and prohibit duplicate names within the same scope. The type correspondence rules are as follows: • Boolean expressions cannot be used with arithmetic or relational operators. • Arithmetic expressions cannot be used with logical operators. • Reductions can only contain numeric types. • Only integer operands can be used with the remainder operator. • The two statements in an if statement must match in type. No coercion is performed. • All the statements in a case statement must match in type. No coercion is performed. • The type of the if expression must be Boolean. • The type of the case expression must be Integer • A narrowing variable initialization or function return occurs when a real value is being forced into integer. Widening is permitted. • Boolean types cannot be mixed with numeric types in variable initializations or function returns. Type coercion from an integer to a real type is performed within arithmetic expressions. You must make the following semantic checks. Those highlighted in yellow are already performed by the code that you have been provided, although you are must make minor modifications to account for the addition of real types and the need to perform type coercion and to handle the additional arithmetic and logical operators. • Using Boolean Expressions with Arithmetic Operator • Using Boolean Expressions with Relational Operator • Using Arithmetic Expressions with Logical Operator • Reductions containing nonnumeric types • Remainder Operator Requires Integer Operands • If-Then Type Mismatch • Case Types Mismatch • If Condition Not Boolean • Case Expression Not Integer • Narrowing Variable Initialization • Variable Initialization Mismatch • Undeclared Variable • Duplicate Variable • Narrowing Function Return This project requires modification to the bison input file, so that it defines the additional semantic checks necessary to produce these errors and addition of functions to the library of type checking functions already provided in types.cc. You must also make some modifications to the functions provided. You need to add a check to the checkAssignment function for mismatched types in the case that Boolean and numeric types are mixed. You need to also add code to the checkArithmetic function to coerce integers to reals when the types are mixed and the error message must be modified to indicate that numeric rather than only integer types are permitted. The provided code includes a template class Symbols that defines the symbol table. It already includes a check for undeclared identifiers. You need to add a check for duplicate identifiers. Like the lexical and syntax errors, the compiler should display the semantic errors in the compilation listing, after the line in which they occur. An example of compilation listing output containing semantic errors is shown below: 1 — Test of Multiple Semantic Errors 2 3 function test a: integer returns integer; 4 b: integer is 5 if a + 5 then 6 2; 7 else 8 5; 9 endif; Semantic Error, If Expression Must Be Boolean 10 c: real is 9.8 – 2 + 8; 11 d: boolean is 7 = f; Semantic Error, Undeclared f 12 begin 13 case b is 14 when 1 => 4.5 + c; 15 when 2 => b; Semantic Error, Case Types Mismatch 16 others => c; 17 endcase; 18 end;Lexical Errors 0 Syntax Errors 0 Semantic Errors 3You are to submit two files. 1. The first is a .zip file that contains all the source code for the project. The .zip file should contain the flex input file, which should be a .l file, the bison file, which should be a .y file, all .cc and .h files and a makefile that builds the project. 2. The second is a Word document (PDF or RTF is also acceptable) that contains the documentation for the project, which should include the following: a. A discussion of how you approached the project b. A test plan that includes test cases that you have created indicating what aspects of the program each one is testing and a screen shot of your compiler run on that test case c. A discussion of lessons learned from the project and any improvements that could be made Grading Rubric Criteria Meets Does Not Meet Functionality 70 points 0 pointsGenerates semantic error when a remainder operator has non-integer operands (10) Does not generate semantic error when a remainder operator has noninteger operands (0) Generates semantic error when if and then types don’t match (10) Does not generate semantic error when if and then types don’t match (0) Generates semantic error when case types don’t match (10) Does not generate semantic error when case types don’t match (0) Generates semantic error when if condition is not Boolean (10) Does not generates semantic error when if condition is not Boolean (0) Generates semantic error when case expression is not integer (10) Does not generate semantic error when case expression is not integer (0) Generates semantic error on narrowing initialization (10) Does not generate semantic error on narrowing initialization (0) Generates semantic error for duplicate variables (10) Does not generate semantic error for duplicate variables (0) Test Cases 15 points 0 pointsIncludes test cases that test all type checking errors (10) Does not Include test cases that test all type checking errors (0) Includes test cases that test all symbol table errors (3) Does not include test cases that test all symbol table errors (0) Includes test case with multiple errors (2) Does not include test case with multiple errors (0) Documentation 15 points 0 pointsDiscussion of approach included (5) Discussion of approach not included (0) Lessons learned included (5) Lessons learned not included (0)
The third project involves modifying the attached interpreter so that it interprets programs for the complete language. When the program is run on the command line, the parameters to the function should be supplied as command line arguments. For example, for the following function header of a program in the file text.txt: function main a: integer, b: integer returns integer; One would execute the program as follows: $ ./compile < test.txt 2 4 In this case, the parameter a would be initialized to 2 and the parameter b to 4. An example of a program execution is shown below: $ ./compile < test.txt 2 41 function main a: integer, b: integer returns integer; 2 c: integer is 3 if a > b then 4 a rem b; 5 else 6 a ** 2; 7 endif; 8 begin 9 case a is 10 when 1 => c; 11 when 2 => (a + b / 2 – 4) * 3; 12 others => 4; 13 endcase; 14 end;Compiled SuccessfullyResult = 0 After the compilation listing is output, the value of the expression which comprises the body of the function should be displayed as shown above. The existing code evaluates some of the arithmetic, relational and logical operators together with the reduction statement and integer literals only. You are to add the necessary code to include all of the following: • Real and Boolean literals • All additional arithmetic operators • All additional relational and logical operators • Both if and case statements • Functions with multiple variables • Functions with parameters This project requires modification to the bison input file, so that it defines the additional the necessary computations for the above added features. You will need to add functions to the library of evaluation functions already provided in values.cc. You must also make some modifications to the functions already provided. You are to submit two files. 1. The first is a .zip file that contains all the source code for the project. The .zip file should contain the flex input file, which should be a .l file, the bison file, which should be a .y file, all .cc and .h files and a makefile that builds the project. 2. The second is a Word document (PDF or RTF is also acceptable) that contains the documentation for the project, which should include the following: a. A discussion of how you approached the project b. A test plan that includes test cases that you have created indicating what aspects of the program each one is testing and a screen shot of your compiler run on that test case c. A discussion of lessons learned from the project and any improvements that could be made Grading Rubric Criteria Meets Does Not Meet Functionality 70 points 0 pointsFunctions with real and Boolean literals evaluated correctly (5) Functions with real and Boolean literals not evaluated correctly (0) Subtraction and division operators evaluated correctly (5) Subtraction and division operators not evaluated correctly (0) Remainder operator evaluated correctly (5) Remainder operator not evaluated correctly (0) Exponentiation operator evaluated correctly (5) Exponentiation operator not evaluated correctly (0) Additional relational operators evaluated correctly (5) Additional relational operators not evaluated correctly (0) Additional logical operators evaluated correctly (5) Additional logical operators not evaluated correctly (0) if conditional expressions evaluated correctly (10) if conditional expressions not evaluated correctly (0) case conditional expressions evaluated correctly (10) case conditional expressions not evaluated correctly (0) Functions with multiple variables evaluated correctly (10) Functions with multiple variables not evaluated correctly (0) Functions with parameters evaluated correctly (10) Functions with parameters not evaluated correctly (0) Test Cases 15 points 0 pointsIncludes test cases that test real and Boolean literals (3) Does not Include test cases that test real and Boolean literals (3) Includes test cases that test all arithmetic operators (3) Does not include test cases that test all arithmetic operators (0) Includes test cases that test all relational and logical operators (3) Does not include test cases that test all relational and logical operators (0) Includes test cases that test both conditional expressions (3) Does not include test cases that test both conditional expressions (0) Includes test cases with variables and parameters (3) Does not include test cases with variables and parameters (0) Documentation 15 points 0 pointsDiscussion of approach included (5) Discussion of approach not included (0) Lessons learned included (5) Lessons learned not included (0)
The second project involves modifying the syntactic analyzer for the attached compiler by adding to the existing grammar. The full grammar of the language is shown below. The highlighted portions of the grammar show what you must either modify or add to the existing grammar. function: function_header {variable} body function_header: FUNCTION IDENTIFIER [parameters] RETURNS type ; variable: IDENTIFIER : type IS statement parameters: parameter {, parameter} parameter: IDENTIFIER : type type: INTEGER | REAL | BOOLEAN body: BEGIN statement END ; statement: expression ; | REDUCE operator {statement} ENDREDUCE ; | IF expression THEN statement ELSE statement ENDIF ; | CASE expression IS {case} OTHERS ARROW statement ENDCASE ; operator: ADDOP | MULOP case: WHEN INT_LITERAL ARROW statement expression: ( expression ) | expression binary_operator expression | NOTOP expression | INT_LITERAL | REAL_LITERAL | BOOL_LITERAL | IDENTIFIER binary_operator: ADDOP | MULOP | REMOP | EXPOP | RELOP | ANDOP | OROP In the above grammar, the red symbols are nonterminals, the blue symbols are terminals and the black punctuation are EBNF metasymbols. The braces denote repetition 0 or more times and the brackets denote optional. Your parser should be able to correctly parse any syntactically correct program without any problem. You must modify the syntactic analyzer to detect and recover from additional syntax errors using the semicolon as the synchronization token. To accomplish detecting additional errors an error production must be added to the function header, another to the variable declaration and a final one to the when clause of the case statement. Your bison input file should not produce any shift/reduce or reduce/reduce errors. Eliminating them can be difficult so the best strategy is not introduce any. That is best achieved by making small incremental additions to the grammar and ensuring that no addition introduces any such errors. An example of compilation listing output containing syntax errors is shown below: 1 — Multiple errors 2 3 function main a integer returns real; Syntax Error, Unexpected INTEGER, expecting ‘:’ 4 b: integer is * 2; Syntax Error, Unexpected MULOP 5 c: real is 6.0; 6 begin 7 if a > c then 8 b 3.0; Syntax Error, Unexpected REAL_LITERAL, expecting ‘;’ 9 else 10 b = 4.; 11 endif; 12 ; Syntax Error, Unexpected ‘;’, expecting ENDLexical Errors 0 Syntax Errors 4 Semantic Errors 0 You are to submit two files. • The first is a .zip file that contains all the source code for the project. The .zip file should contain the flex input file, which should be a .l file, the bison file, which should be a .y file, all .cc and .h files and a makefile that builds the project. • The second is a Word document (PDF or RTF is also acceptable) that contains the documentation for the project, which should include the following: a. A discussion of how you approached the project b. A test plan that includes test cases that you have created indicating what aspects of the program each one is testing and a screen shot of your compiler run on that test case c. A discussion of lessons learned from the project and any improvements that could be made Grading Rubric Criteria Meets Does Not Meet Functionality 70 points 0 pointsParses all syntactically correct programs (25) Does not parse all syntactically correct programs (0) Productions correctly implement precedence and associativity (10) Productions do not correctly implement precedence and associativity (0) Grammar contains no shift/reduce or reduce/reduce errors (5) Grammar contains shift/reduce or reduce/reduce errors (0) Detects and recovers from all programs with single syntax errors (20) Does not detect and recover from errors in the function header (0) Detects and recovers from a program with multiple syntax errors (10) Does not detect and recover from multiple errors (0) Test Cases 15 points 0 pointsIncludes test cases that test all grammar productions (6) Does not include test cases that test all grammar productions (0) Includes test cases that test errors in all productions (6) Does not include test cases that test errors in all productions (0) Includes test case with multiple errors (3) Does not include test case with multiple errors (0) Documentation 15 points 0 pointsDiscussion of approach included (5) Discussion of approach not included (0) Lessons learned included (5) Lessons learned not included (0)
The first project involves modifying the attached lexical analyzer and the compilation listing generator code. You need to make the following modifications to the lexical analyzer, scanner.l: 1. A new token ARROW should be added for the two character punctuation symbol =>. 2. The following reserved words should be added: case, else, endcase, endif, if, others, real, then, whenEach reserved words should be a separate token. The token name should be the same as the lexeme, but in all upper case. 3. Two additional logical operators should be added. The lexeme for the first should be or and its token should be OROP. The second logical operator added should be not and its token should be NOTOP. 4. Five relational operators should be added. They are =, /=, >, >= and 6 and 8 = 5 * (7 – 4); 6 end;Compiled Successfully Here is the required output for a program that contains more than one lexical error on the same line: 1 — Function with two lexical errors 2 3 function test2 returns integer; 4 begin 5 7 $ 2 ^ (2 + 4); Lexical Error, Invalid Character $ Lexical Error, Invalid Character ^ 6 end;Lexical Errors 2 Syntax Errors 0 Semantic Errors 0 You are to submit two files. 1. The first is a .zip file that contains all the source code for the project. The .zip file should contain the flex input file, which should be a .l file, all .cc and .h files and a makefile that builds the project. 2. The second is a Word document (PDF or RTF is also acceptable) that contains the documentation for the project, which should include the following: a. A discussion of how you approached the project b. A test plan that includes test cases that you have created indicating what aspects of the program each one is testing and a screen shot of your compiler run on that test case c. A discussion of lessons learned from the project and any improvements that could be made Grading Rubric Criteria Meets Does Not Meet Functionality 70 points 0 pointsDefines new comment lexeme (5) Does not define new comment lexeme (0) Correctly modifies identifier definition to include underscores (5) Does not correctly modify identifier definition to include underscores (0) Adds real and Boolean tokens (5) Does not add real and Boolean tokens (0) Defines additional logical operators (5) Does not define additional logical operators (0) Defines additional relational operators (5) Does not define additional relational operators (0) Defines additional arithmetic operators (5) Does not define additional arithmetic operators (0) Defines additional reserved words and arrow symbol(5) Does not define additional reserved words and arrow symbol (0) Adds new tokens to the token header file (5) Does not add new tokens to the token header file (0) Implements modifications to display multiple errors on the same line (15) Does not implement modifications to display multiple errors on the same line (0) Implements modifications to count and display each type of compilation error (15) Does not Implement modifications to count and display each type of compilation error (0) Test Cases 15 points 0 pointsIncludes test case containing all lexemes (5) Does not include test case containing all lexemes (0) Includes test case with multiple errors on one line (5) Does not include test case with multiple errors on one line (0) Includes test case with no errors (5) Does not include test case with no errors (0) Documentation 15 points 0 pointsDiscussion of approach included (5) Discussion of approach not included (0) Lessons learned included (5) Lessons learned not included (0)
Write a Java, C# or C/C++ program (the choice is yours) for file/directory processing according to the following rules. The program requested for this project must have a text menu like this:0 – Exit 1 – Select directory 2 – List directory content (first level) 3 – List directory content (all levels) 4 – Delete file 5 – Display file (hexadecimal view) 6 – Encrypt file (XOR with password) 7 – Decrypt file (XOR with password) Select option:The menu is displayed and the user must select an option (a number between 0 and 7). The action corresponding to the selection is performed, then the menu is displayed again and the user can choose another option. This cycle is repeated until the user selects 0, which exits the loop and ends the program.The options are:0 – Exit This options ends the program1 – Select directory The user is prompted for a directory [absolute] name. This is the first options that must be selected by the user. All the options below are working on the directory selected here. After performing several operations on the selected directory, the user can select another directory and work with it.2 – List directory content (first level) This option displays the content of the selected directory on the screen. All the files and subdirectories from the first level must be displayed (files and directories should be listed separately). If no directory was selected an error message must be displayed.3 – List directory content (all levels) This option displays the content of the selected directory on the screen. All the files and subdirectories from the first and subsequent levels must be displayed (files and directories should be listed separately). If no directory was selected an error message must be displayed.4 – Delete file This option prompts the user for a filename and deletes that file from the selected directory. If no directory was selected an error message must be displayed. If the directory does not contain the file specified by the user, an error message must be displayed. The filename does not include any path, it’s just the name of the file.5 – Display file (hexadecimal view) This option prompts the user for a filename (from the selected directory) and displays the content of that file on the screen, in hexadecimal view. If no directory was selected an error message must be displayed. If the directory does not contain the file specified by the user, an error message must be displayed. The filename does not include any path, it’s just the name of the file. Note 1: The hexadecimal view displays each byte of the file in hexadecimal; it should look something like this, but simpler:Note2: The ASCII representation, the Current Offset and the Value Preview are NOT required; also there is no window, no graphics, no colors, just black and white text display. Being a text only display, you are required to display ONLY the Data Offset and the Hexadecimal Representation.6 – Encrypt file (XOR with password) passwordpasswordpasswordpasswordpasswordpasswordpass this is the file content that we need to encrypt nowchiphertext is obtained here by XORing byte to byteNote1: the user must be prompted for the filename of the encrypted file (containing the ciphertext) as well, otherwise we would need to overwrite the initial file. Note2: If no directory was selected an error message must be displayed. If the directory does not contain either of the files specified by the user, an error message must be displayed. The filenames do not include any path.7 – Decrypt file (XOR with password) passwordpasswordpasswordpasswordpasswordpasswordpass chiphertext is here …this is the file content that we had initiallyNote1: the user must be prompted for the filename of the decrypted file as well, otherwise we would need to overwrite the initial file. Note3: If no directory was selected an error message must be displayed. If the directory does not contain either of the files specified by the user, an error message must be displayed. The filenames do not include any path.Testing: 1. You should use this file as the test file for Display, Encryption and Decryption. 2. For encryption, use the following password “Qwertyuiop[123$4$567]” 3. After encrypting this file with the above password, you obtain an encrypted file of the same length; after decrypting that file with the same password you should obtain an exact replica of this file, and this must be reflected in the Report document by appropriate screenshots showing the content of the files involved in these operations.Deliverables: 1. Source code (zipped) 2. A Report showing the program performing each of the 7 actions correctly (use screenshots), plus screenshots showing the error reporting situations.
Demand paging problems (page replacement algorithms):1. For the following reference string apply the FIFO page replacement algorithm.– Option 1 – according to Week 6 – Textbook Readings: Reference string 2 4 5 6 1 5 3 4 5 2 3 6 5 3 4 7 3 5 6 Physical frame 0 2 2 2 2 Physical frame 1 4 4 4 Physical frame 2 5 5 Physical frame 3 6 Page faults F F F F Victim frames OR – Option 2 – according to Week 6 – Module Readings Reference string 2 4 5 6 1 5 3 4 5 2 3 6 5 3 4 7 3 5 6 Physical frame 0 2 4 5 6 Physical frame 1 2 4 5 Physical frame 2 2 4 Physical frame 3 2 Page faults F F F F Victim frames2. For the following reference string apply the OPT page replacement algorithm. Reference string 2 4 5 6 1 5 3 4 5 2 3 6 5 3 4 7 3 5 6 Physical frame 0 2 2 2 2 Physical frame 1 4 4 4 Physical frame 2 5 5 Physical frame 3 6 Page faults F F F F Victim frames3. For the following reference string apply the LRU page replacement algorithm. Reference string 2 4 5 6 1 5 3 4 5 2 3 6 5 3 4 7 3 5 6 Physical frame 0 2 2 2 2 Physical frame 1 4 4 4 Physical frame 2 5 5 Physical frame 3 6 Page faults F F F F Victim frames4. For the following reference string apply the LFU page replacement algorithm. Reference string 2 4 5 6 1 5 3 4 5 2 3 6 5 3 4 7 3 5 6 Physical frame 0 2 2 2 2 Physical frame 1 4 4 4 Physical frame 2 5 5 Physical frame 3 6 Page faults F F F F Victim frames
