WebGL 3D Project Overview In this project you will create a unique 3D animated scene composed of WebGL graphic components. The scene should include animation, lighting, textures, frame buffers and multiple objects. Requirements: 1. Using WebGL create a unique 3D animated scene. The scene has the following specifications: a. Size: minimum 640×480 b. Includes at least 10 different objects. c. Uses multiple lighting effects on different materials d. Uses multiple textures e. Includes radio buttons, slider bars or other widgets to turn on or off certain components of the animation. f. Uses frame buffers to organize the memory resources that are needed to render the scene.2. Use WebGL 3. All JavaScript source code should be written using Google JavaScript style guide.( http://google.github.io/styleguide/jsguide.html) 4. Prepare, conduct and document a test plan verifying your application is working as expected. This plan should include a test matrix listing each method you tested, how you tested it, and the results of testing Deliverables: 1. All JavaScript source code used for this project. Code should adhere to the Google Javascript style guide.Grading guidelines: Attribute Meets Design 20 points Methods used to isolate functionality (10 points)Code is efficient without sacrificing readability and understanding. (5 points) Code can easily be used and maintained. (5 points) Functionality 50 points Creates a unique 3D animated scene. (10 points) 1Size is at least 640×480. (5 points)Includes at least 10 different objects. (5 points)Uses multiple lighting effects on different materials. (5 points)Uses multiple textures. (5 points)Includes radio buttons, slider bars or other widgets to turn on or off certain components of the animation. (10 points)Uses frame buffers to organize the memory resources that are needed to render the scene. (5 points)Uses WebGL (5 points)Testing 10 points Prepares, conducts and documents a test plan verifying the application is functioning properly. (10 points)Documentation and deliverables 20 points Submits all JavaScript source code used for this project. (5 points)Code adheres to the Google JavaScript style guide. (5 points)Submits Word or PDF file demonstrating with clearly labeled screen captures and associated well-written descriptions, the successful execution of your 3D Three.js scene. (5 points)2
Overview In the project you will use Java Inheritance to create a series of related classes with a “Shape” theme. Before completing this exercise, be sure to review and try the Java class and inheritance examples and materials found in this free Safari resource: https://learning.oreilly.com/library/view/java-the-complete/9781260440249/ You should focus on Chapters 6, 7 and 8. If you have previously signed up for the Safari account you don’t need to sign-up again. Just use this link: https://learning.oreilly.com/accounts/login/?next=/library/view/temporary-access/ If you have not previously requested a Safari account follow the details on this page to sign-up for your Safari Account: https://libguides.umuc.edu/safari You’ll need to sign in using your UMGC student email account. Once you sign in, you’ll have immediate access to the content, and you’ll shortly receive an e-mail from Safari prompting you to set up a password and complete your account creation (recommended). Students: Your UMUC e-mail account is your username + @student.umuc.edu (example: [email protected]). Note: Be sure to review is-a and has-a class relationships prior to starting this exercise as well. Assignment Details Design, implement and test a Java class Inheritance hierarchy that would satisfy the following is-a and has-a relationships: • A Shape is an object • A TwoDimensionalShape is a Shape • A ThreeDimensionalShape is a Shape • A Circle is a TwoDimensionalShape • A Square is a TwoDimensionalShape • A Triangle is a TwoDimensionalShape • A Rectangle is a TwoDimensionalShape • A Sphere is a ThreeDimensionalShape • A Cube is a ThreeDimensionalShape • A Cone is a ThreeDimensionalShape • A Cylinder is a ThreeDimensionalShape • A Torus is a ThreeDimensionalShape • A Shape has a NumberofDimensions • A TwoDimensionalShape has an area • A ThreeDimensionalShape has a volume Note you should fill in additional methods and variables that make sense for each of the classes. Also some assumptions about shape types is appropriate and should be documented in the code and documents submitted. For example, type of triangle … The following represents a possible menu session for a user: *********Welcome to the Java OO Shapes Program ********** Select from the menu below: 1. Construct a Circle 2. Construct a Rectangle 3. Construct a Square 4. Construct a Triangle 5. Construct a Sphere 6. Construct a Cube 7. Construct a Cone 8. Construct a Cylinder 9. Construct a Torus 10. Exit the program 2 You have selected a Rectangle What is the length? 4 What is the Width? 9.5 The area of the Rectangle is 38. Would you like to continue? (Y or N) 3 Sorry I do not understand. Enter Y or N Y Select from the menu below: 1. Construct a Circle 2. Construct a Rectangle 3. Construct a Square 4. Construct a Triangle 5. Construct a Sphere 6. Construct a Cube 7. Construct a Cone 8. Construct a Cylinder 9. Construct a Torus 10. Exit the program 10 Thanks for using the program. Today is Nov 11 at 1:40 PM.Submission Requirements: 1. Submit all of your Java source files (each class should be in a separate .java file). These files should be zipped and submitted with the documentation. 2. UML class diagram showing the type of the class relationships. 3. Developer’s guide describing how to compile and execute the program. The guide should include a comprehensive test plan that includes evidence of testing each component of the menu with screen captures and descriptions supporting each test. Documentation includes Lessons learned. Grading Rubric: Attribute Meets Design 20 points Designs a Java class Inheritance hierarchy that would satisfy the following isa and has-a relationships: • A Shape is an object • A TwoDimensionalShape is a Shape • A ThreeDimensionalShape is a Shape • A Circle is a TwoDimensionalShape • A Square is a TwoDimensionalShape • A Triangle is a TwoDimensionalShape • A Rectangle is a TwoDimensionalShape • A Sphere is a ThreeDimensionalShape • A Cube is a ThreeDimensionalShape• A Cone is a ThreeDimensionalShape • A Cylinder is a ThreeDimensionalShape • A Torus is a ThreeDimensionalShape • A Shape has a NumberofDimensions • A TwoDimensionalShape has an area • A ThreeDimensionalShape has a volume Functionality 40 points Contains no coding errors.Contains no compile warnings. Creates a command line driven menu that allows a user to construct each of the TwoDimensional and ThreeDimensional Shape subclasses.The menu should continue to loop prompting for a specific class and then prompt for appropriate input parameters. The values returned should be the volume or area as appropriate to the shape.Error checks should be in developed to make sure appropriate menu items and types of data were input and prompt the user to enter to correct data.Test Data 20 points Tests the application using multiple and varied test cases.Documentation and submission 20 pointsSubmission includes Java source code files, Data files used to test your program, Configuration files used.Documentation includes a UML class diagram showing the type of the class relationships.Documentation includes a user’s Guide describing of how to set up and run your application.Documentation includes a test plan with sample input and expected results, test data and results and screen snapshots of some of your test cases.Documentation includes Lessons learned.Documentation is in an acceptable format. Document is well-organized. The font size should be 12 point. The page margins should be one inch. The paragraphs should be double spaced. All figures, tables, equations, and references should be properly labeled and formatted using APA style. The document should contain minimal spelling and grammatical errors.
1. (20 pts) For the following program, explain the interesting elements related to threads. Focus on explaining the output of the program. 1 public class TaskThreadDemo { 2 public static void main (String args []) { 3 String [] sa = {“a”, “X”, “+”, “.”}; 4 for (String s: sa) { 5 Runnable ps = new PrintChar (s, 200); 6 Thread ts = new Thread (ps, s); 7 ts.start (); 8 } // end for each character 9 } // end main 10 } // end class TaskThreadDemo 11 12 class PrintChar implements Runnable { 13 String ch; 14 int times; 15 16 public PrintChar (String c, int n) { 17 ch = c; 18 times = n; 19 } // end constructor 20 21 public void run () { 22 for (int i = 0; i < times; i++) { 23 System.out.print (ch); 24 } // end for loop 25 } // end method run 26 } // end class PrintChar 2. (20 pts) What is changed if the method called on line 7, start(), is replaced with run()? Explain (of course). Focus on explaining the output of the program. 3. (20 pts) What is changed if the method Thread.yield() is added between lines 23 and 24? Explain. Focus on explaining the output of the program. 4. (20 pts) Modify the above program so that the Thread.sleep method is called after each character has been printed causing it to sleep for 500 milliseconds. Describe how that modification has altered the output and explain why the change had the effect that you described. 5. (20 pts) Modify the above program so that the Thread.sleep method is called after each thread is created in the main method causing it to sleep for 500 milliseconds. Describe how that modification has altered the output and explain why the change had the effect that you described.1Grading Rubric: Attribute Meets Does not meet Problem 1 20 points Explains the interesting elements related to threads. Focuses on explaining the output of the program. 0 points Does not explain the interesting elements related to threads. Does not focus on explaining the output of the program. Problem 2 20 points Explains what is changed if the method called on line 7, start(), is replaced with run().Focuses on explaining the output of the program. 0 points Does not explain what is changed if the method called on line 7, start(), is replaced with run(). Does not focus on explaining the output of the program. Problem 3 20 points Explains what is changed if the method Thread.yield() is added between lines 23 and 24. Focuses on explaining the output of the program. 0 points Does not explain what is changed if the method Thread.yield() is added between lines 23 and 24. Does not focus on explaining the output of the program. Problem 4 20 points Explains how the output is changed if the Thread.sleep method is called after each character has been printed. 0 points Does not explain how the output is changed if the Thread.sleep method is called after each character has been printed. Problem 5 20 points Explains how the output is changed if the Thread.sleep method is called after each thread is created in the main method. 0 points Does not explain how the output is changed if the Thread.sleep method is called after each thread is created in the main method.2
a. What is wrong with everybody doing the following – other than that the philosophers never get up from the table? 1. think for a while 2. get left chopstick 3. get right chopstick 4. eat for a while 5. return left chopstick 6. return right chopstick 7. return to 1 b. How can the above be fixed to avoid deadlocks? c. Is your solution starvation free? Literally!8. (10 pts) Describe the environment in which a wait () call is legal?
Sample code has been provided that implements a basic implementation of Divide and Conquer for Matrix Multiplication. You should use this code as your base (copy+paste) into your own function that implements Strassen’s method explained in Week 5 slides.Your assignment is to implement Strassen’s algorithm for Matrix Multiplication. Submit a python file with a function ”strassens(A,B)” that can be called and tested.Submission Instructions Please submit a single python file (.py) with a function defined as described blow. If you would like to include any of your own test code, please include at bottom using: if __name__ == “__main__”: This allows the class to be imported for grading/testing without executing your tests. Also, please refrain from including print statements in your submission. Please name the file: Strassens.pyYour submission should contain the following function definition: def strassens(A, B): “”” Uses Strassen’s method for matrix multiplication to return the product of the two provided Matrices A and B. :param A: the first matrix to multiply. Implemented as a np.array :param B: The second matrix to multiply. Implemented as a np.array :return: The product of A and B “””Description of the provided code The file MatrixMult Starter.py contains two basic methods. def recursive_matrix_mult(A, B): “”” Recursively multiplies sub matrices of A and B :param a: The first Matrix A implemented as a np.array :param b: The second Matrix B implemented as a np.array :return: The product of a and b “”” def basic_smoke_test(): “”” Calls recursive_matrix_mult and throws AssertionException if calculations are not performed as expected. “””
The sample code provided for RedBlackTrees in lecture uses recursion to perform the insert() function. Your assignment is to implement the same functionality, but without the use of recursion. To do so effectively, you should maintain a parent pointer in your nodes, so that you may traverse back up the tree. Maintaining a parent requires an update to the provide rotate right() and rotate left() methods as well, as parents will have changed during the rotation. If you successfully manage parents in the rotation functions, and set the parent correctly when inserting the new node into the base of the tree, you should then be able to traverse back up the tree using curr = curr.parent and assess the current node for the left rotation, right rotation and color flip scenarios until curr.parent is None (you’re at the root).Description of the methods provided for the student for in the assignment. The RedBlackBST class provided for this assignment includes the following methods for reference and testing. These can be optionally omitted from the submission if desired, but will not impact results if left in. def insert_r(self, key, value): “”” A functioning recursive implementation of insert. Does not update or maintain parent links for nodes. It is used for student reference and testing. It will not be included as part of grading, and can be optionally omitted from the submission. “”” def _put(self, node, key, value): “”” The recursive protected method used by insert_r to insert nodes recursively into the data structure. It is used for student reference and testing. It will not be included as part of grading, and can be optionally omitted from the submission. “”” def _rotate_left_r(self, node):“”” A functioning left rotation that is used by insert_r and _put methods. It does NOT maintain links to parent nodes and will thus not work as is for the iterative implementation. This should be used for student reference and testing. It will not be included as part of grading, and can be optionally omitted from the submission. “”” def _rotate_right_r(self, node):“”” A functioning right rotation that is used by insert_r and _put methods. It does NOT maintain links to parent nodes and will thus not work as is for the iterative implementation. This should be used for student reference and testing. It will not be included as part of grading, and can be optionally omitted from the submission. “”” The RedBlackBST class provided for this assignment includes the following subclass that can be used as is for the solution or rewritten by the student if desired. class RedBlackNode:“”” This subclass comes prepared with a standard constructor and support for a parent link. The RedBlackBST class provided for this assignment includes the following methods that can be used as isHomework 1: Red-Black BSTs TCSS503: Analysis and Problem Solving for Software Engineers for the solution or rewritten by the student if desired. def _flip_colors(self, node): “”” The same method that works for the recursive implementation also works as is for the iterative implementation.””” def search(self, key): “”” Regardless of the insert implementation, the search method is the same. This can be used as is for testing.””” def _node_search(self, key): “”” Supports search(). returns the RedBlackNode object that contains the provided key.””” def _right_is_red(self, node): “”” Explanation in provided file. “”” def _left_is_red(self, node): “”” Explanation in provided file. “”” def _left_left_is_red(self, node): “”” Explanation in provided file. “”” The Starter Code file includes the following function that can be used to test the implementation of the RedBlackPST.insert i() method. Note that a successful test doesn’t guarantee a perfect score. There are additional smoke tests that will be run, including ”search” on an empty tree that should be verified by the student. def test_bst(bst): “”” Runs a few basic tests of the bst provided. “”” Finally, below is the list of stub methods that have been included in the sample file for you to complete as a student. These methods MUST be included with the same signature in the submission for automated tests to function. def insert_i(self, key, value): “”” Should produce the same results as insert_r but done so in an iterative, not recursive manner. The traversal down to insert, and the bubble up of rotations and flips should be contained within this method. “”” def _rotate_left_i(self, node): “”” Rotation left that includes the maintenance of parent links. “”” def _rotate_right_i(self, node): “”” Rotation right that includes the maintenance of parent links. “””Homework 1: Red-Black BSTs TCSS503: Analysis and Problem Solving for Software Engineers One final hint: When rotating, the new root node needs to be set as the original parent’s .left node or .right node depending on whether the original child is smaller or larger than the parent. For example: 5 / 2(n) 6 / 1(x) / 0 n (node) and x are the variable names used in _rotate_left and _rotate_right Assume the links between 2-1 and 1-0 are both red links. We would want to rotate right(n). When doing so, the resulting structure will look like this: 5 / 1(x) 6 / 0 2(n) This means that x.parent should be set to 5, but also that 5.left must be set to x. Do so using something akin to: “if n.parent.left is n then n.parent.left = x else n.parent.right = x”
Question 1. (10 points) Suppose someone gives you a polynomial time algorithm for deciding the 3-SAT problem (yes/no answer to whether there exists a satisfying assignment for the 3-CNF expression). Show how to use this algorithm to compute a satisfying assignment in polynomial time. Question 2. (10 points) Exercise 22 from Chapter 8, page 517 of the textbook. Question 3. (10 points) Exercise 5, Chapter 8, p. 506. (For the reduction, you should use one of the problems we have already shown to be NP-complete in class.) Question 4. (10 points) (10 points for answering (no right or wrong answers!)) (a) Which topics did you enjoy learning about the most and why? (b) Name one or more topic(s) that you found easy to understand. (c) Name one or more topic(s) that you found difficult to understand.
Question 1. (10 points) Exercise 1 from Chapter 6, pages 312-313 of the textbook. Question 2. (10 points) Suppose you visit a country where the coins are of denominations d1, d2, . . . , dn and you wish to make change for value v. Provide an efficient dynamic programming algorithm for calculating the minimum number of coins required to make change for value v. For example, if the coin denominations are 1, 2, 5, and 7, then you would need at least 2 coins (i.e., 5, 5) to make change for value 10. You may assume that the coin denominations are such that it is possible to make exact change for any value. Question 3. (10 points) Suppose that you run a fast-food restaurant business and wish to open a series of restaurants along a highway. There are n possible locations along the highway where you could open your restaurants, and these n locations are at distances of m1, m2, . . . , mn miles, in increasing order, from the starting point of the highway. The expected profit from opening a restaurant at location i is pi , where pi > 0 and 1 ≤ i ≤ n. Give an efficient algorithm to compute your maximum expected total profit, subject to the following two constraints: (i) You can open at most one restaurant at each location, and (ii) any two restaurants must be at least k miles apart along the highway, where k is a positive integer. Question 4. (10 points) Exercise 5 from Chapter 6, pages 316-317 of the textbook. Question 5. (10 points) Exercise 11 from Chapter 6, page 323 of the textbook.
Question 1. (10 points) An array A[1 . . . n] is said to have a majority element if more than half of its entries are the same. Suppose you are given array A[1 . . . n] of n objects. These objects are not necessarily from some ordered domain, and so there can be no comparisons of the form “is A[i] > A[j]?”. (The objects may be GIF files, for example.) However, you can answer questions of the form “is A[i] = A[j]?” in constant time. Give an O(n lg n)-time algorithm to determine if the array A has a majority element. Question 2. (10 points) Suppose we have k sorted arrays, each with n elements. We we want to merge these k arrays into a single sorted array with kn elements. (a) One way to solve this problem is to use the merge procedure of merge-sort to first merge the first two arrays, then merge in the third array, and then the fourth array, and so on until all k arrays have been merged. What is the time complexity of this algorithm in terms of n and k? (b) Use divide and conquer to give a more efficient solution for this problem. Question 3. (10 points) Solve the following recurrences and give a Θ bound for each . You may use either the recursion tree technique or the master theorem to solve these recurrences. You may also assume that T(1) is Θ(1) in each case. a) T(n) = 2T(n/2) + n 4 . b) T(n) = T(7n/10) + n. c) T(n) = 16T(n/4) + n 2 d) T(n) = T(n − 1) + 2 Question 4. (10 points) Suppose you are given an infinite array A[·] in which the first n cells contain integers in sorted order and all the remaining cells are filled with ∞. You have not been given the value of n. Describe a O(log n)-time algorithm that takes as input an integer x and finds a position in the array containing x, if such a position exists. Question 5. (10 points) Exercise 2 from Chapter 5, pages 246 of the textbook.
Question 1. (10 points) Recall the coin changing problem and the cashier’s algorithm we studied in class. Suppose we are given coin denominations that are powers of some number c, i.e., the denominations are c 0 , c1 , . . . , ck for some positive integers c > 1 and k ≥ 1. Prove that the cashier’s algorithm will always yield an optimal solution when given such coin denominations. (You do not need to restate cashier’s algorithm here and do not need to analyze its time complexity.) Question 2. (10 points) Exercise 2 from Chapter 4, page 189 of the textbook. Question 3. (10 points) Exercise 3 from Chapter 4, pages 189-190 of the textbook. Question 4. (10 points) Exercise 6 from Chapter 4, page 191 of the textbook. Question 5. (10 points) Given an edge-weighted digraph G = (V, E) with positive edge-lengths and two nodes u, v ∈ V , provide a polynomial-time algorithm to determine if there is a unique (i.e., only one) shortest path from u to v in G.
Question 1. (10 points) Exercise 2 from Chapter 3, page 107 of the textbook. You may assume that the input graph is given to you as an adjacency list. Question 2. (10 points) Exercise 7 from Chapter 3, pages 108-109 of the textbook. Question 3. (10 points) Consider the pseudocode for BFS given in the slides of Lecture 6. How would the running time of this algorithm change if the input graph is represented as an adjacency matrix? Justify your answer. Question 4. (10 points) Suppose we have three containers whose sizes are 10, 7, and 4 gallons, respectively. The 7-gallon and 4-gallon containers start out full of water, while the 10-gallon container starts out empty. We are allowed one type of operation: pouring the contents of one container into another, stopping only when the source container is empty or the destination container is full. We would like to figure out if there is a sequence of such operations that leaves exactly 2 gallons in the 7- or 4-gallon container. Show how to model this problem as a graph problem: give a precise definition of the graph involved and state the specific question about this graph that needs to be answered to solve the original problem. Justify your answer. (Hint: You may think of possible container configurations as vertices). Question 5. (10 points) Exercise 12 from Chapter 3, page 112 of the textbook. (Hint: you may use vertices to represent dates, i.e., (unknown) birth and death dates for each person.)
Question 1. (10 points) Consider the following simple algorithm for sorting an input array A[1 . . . n] of n numbers. The algorithm first finds the smallest element of A and exchanges it with the element in A[1]. Then it finds the second-smallest element of A and exchanges it with A[2]. The algorithm continues in this manner for the first n − 1 elements of A (i.e., continues for n − 1 iterations). (i) Provide pseudocode for this algorithm. You do not need to prove correctness of this algorithm. (ii) Give the worst case running time for this algorithm in Θ notation and justify your answer.Question 2. (10 points) Suppose we want to compute the value x y , where x and y are positive integers with m and n bits, respectively. One way to solve the problem is to perform y − 1 multiplications by x. Can you give a more efficient algorithm that uses only O(n) multiplication steps?Question 3. (10 points) Given a positive real number c, show that the function g(n) = 1 + c + c 2 + . . . + c n is (i) Θ(1) if c < 1, (ii) Θ(n) if c = 1, and (iii) Θ(c n ) if c > 1.Question 4. (10 points) Exercise 6 from Chapter 2, pages 68-69 of the textbook.
Part 1. (100 points) Guess My Number – Socket. In this lab, we implement another version of Guess My Number game, using the Internet sockets! After completing the assignment, you can set up the online game at home and invite your parents, siblings, or guests to play! (and show off how much you know about binary search!) The game is the same as described in Labs 6 and 8. In this problem, it is more natural to call the two people in the game S and C. S is on the server side and knows the random number. C is a client that connects to the server and uses binary search to guess the number. The server listens on TCP port 3119. Clients connect to the port when they want to play the game. Once a connection is established, the server creates a thread S to play game with the client C. Multiple clients can play the game simultaneously. The protocol is as follows. 1. After a client is connected, S first tells C the largest possible value. 2. C makes a guess (picking an integer in the range) and tells S the guess. 3. S checks if the guess is correct and informs C the result. The result is 0 if the guess is correct, 1 if the guess is smaller, or -1 if the guess is larger. If the guess is correct, S also sends a final message to C and then exits. 4. If the guess is not correct, C adjusts the range, based on the feedback from S, and goes to Step 2. 5. If the guess is correct, C prints the final message to stdout and exits. The communications between S and C are line based. Each line must end with a new line character. Integers are converted to strings of decimal digits (with an optional negative sign) before being written to the socket. Converting integers between native binary format and decimal strings can be done by functions like snprintf(), sscanf(), atoi(), or strtol() (BTW, do NOT use sprintf()!). Read the manual to learn how to use these functions. For example, the following function call converts integer n to a string in buf of sz bytes. Make sure buf is large enough. Although we do not have a lot of surprises when printing an integer, it is a good practice to check the return value! rv = snprintf(buf, sz, “%d ”, n); // check rv The protocol is straightforward. One line is transmitted for each message. Note that S sends a single line at the end when the guess is correct: “0” (without newline) followed by the final message. If we use recv_lines(), the client will receive both the zero and the final message in one call. Once the client receives the final message, it will need to print the received 0 on a separate line (just like when the client prints out the other responses, 1 and -1), and print the final message on the second line. Search for TODO in the starter code (server.c and client.c) to find the places where code is to be completed. The steps are similar to what we have done in previous labs. We should work on the server first. We can revise the client from the demo program s2.toupper to have a program to talk to the server manually. We can also use commands like nc, if they are available, to test the server. 1 $ nc localhost 3119 $ seq 1000 | nc localhost 3119 The output of the client is similar but different from the program in previous labs. The client prints a “connecting to” message once the connection is made. Also, it prints the responses from the server. A sample session is as follows. $ ./client localhost client: connecting to 127.0.0.1 1000 My guess: 500 -1 My guess: 250 1 My guess: 375 -1 My guess: 312 -1 My guess: 281 1 My guess: 296 0 It took you 6 attempt(s) to guess the number 296. This will be the last guess my number program. We promise! Happy coding! 2
Part 1. (100 points) Guess My Number – MT. In this lab, we implement the Guess My Number game again, using threads! The game is the same as described in Lab 6, and we still call the two people in the game C and P. C generates a random number and P uses a binary search to guess the number. In the multithreading version, C and P are threads. Although they share the memory space, P is honest and does not peek at the answer. No cheating! In this problem, thread C and thread P use a shared structure (thread_arg_t) to exchange information. Of course, they need a mutex and condition variables to coordinate. In the starter code, the structure already has one mutex and two condition variables. The status field indicates the status of the shared data. Let us recap the protocol between C and P. 1. C first tells P the largest possible value. 2. P makes a guess (picking an integer in the range) and tells C the guess. 3. C checks if the guess is correct and informs P of the result. The result is 0 if the guess is correct, 1 if the guess is smaller, or -1 if the guess is larger. If the guess is correct, C also copies a final message to the shared structure and then exits. 4. If the guess is not correct, P adjusts the range, based on the feedback from C, and goes to Step 2. 5. If the guess is correct, P prints the final message to stdout and exits. Thread P uses a binary search to minimize the number of the guesses. guess_my_number() in the starter code demonstrates the process. The tasks in this problem are to complete the starter code so the main thread creates two threads, C and P, that play the game by exchanging information through the shared structure thread_arg_t. Search for TODO in the starter code to find the places where code is to be completed. The detailed steps are described in the comments. Below are some requirements and suggestions on the implementation. • Thread C uses local variable gmn to maintain the game state and calls provided functions to operate on it. The thread does not access fields in the structure directly. • There are many ways to synchronize the two threads in this problem. Let us use one mutex and two condition variables. We want to practice for more complicated programs! After solving the problem with two condition variables, you can experiment with other methods. The program guess-my-number takes optional arguments from the command line. An argument can be one of the following. • A positive integer. It will be used as the seed for generating pseudorandom numbers. If no seed is specified on the command line, a default value is used. • demo. Call the demo function and exit. It helps us to test our implementation using two threads. The output of the program should be the same as in the demo mode, as well as the output from the program in Lab 6. 1 $ ./guess-my-number demo 12345 My guess: 500 My guess: 750 My guess: 875 My guess: 938 My guess: 969 My guess: 985 My guess: 993 My guess: 997 My guess: 999 My guess: 1000 It took you 10 attempt(s) to guess the number 1000. 2
Part 1. Matrix addition (100 Points). An implementation of matrix ADT (abstract data type) is given in matrix.c. The API (application programming interface) functions that operates on the matrices are listed in matrix.h. One of the functions, addMatrix(), performs matrix addition, which is implemented in matrix.c. In this lab, we implement addMatrix thread() in madd.c.The function performs matrix addition with two threads. It has the same interface as addMatrix(), but performs matrix addition with two threads. We only need to change madd.c. test-madd.c is provided to test our implementation. The program takes the number of rows and columns from the command line, fills two matrices with random numbers, and compares the result of addMatrix() and addMatrix thread(). If no argument is specified, the program works on matrices of size 6 × 6. In addition, if a command line option -t is present, test-madd prints the time (in seconds) spent on matrix additions, using the average of calls.Here are some sample sessions of running test-madd. In the second session, the program call the functions 20 times to collect timing information. time1 is the average time on addMatrix() and time2 is the average time on addMatrix thread(). The numbers are likely to change in different runs. $./test-madd Good work! $./test-madd 1000 2000 -t20 Good work! num_runs=20 time1=0.0107 time2=0.0058 speedup=1.8545 Debugging. gdb supports multithreading.Run your code in gdb until it stops at a breakpoint or appears to stop making progress. If threads are not making progress, interrupt the execution with Ctrl-C to get to the gdb prompt. Here are some commonly used thread commands. • info threads See what threads are running. • thread n Switch to thread n, where n is a thread number. • thread apply [threadno] [all] args Apply commands to one or more threads.
Part 1. (100 points) Guess My Number. In the Guess My Number game, two people, C and P, agree upon a range of integer values. One person, C, picks a random integer within the range. The other person, P, tries to guess the number. For each guess P makes, C tells P if the guess is correct, too large, or too small. P then makes another guess based on the feedback. This process repeats until P has guessed the correct number. P tries to minimize the number of guesses.In this problem, we will use two processes, a parent process and a child process, to simulate the game. The parent process plays person P, and the child process plays person C. The child process generates a random number between 1 and MAX VALUE (defined as 1000), inclusively, for the parent process to guess. The parent process and the child process use two pipes for two-way communications.The process works as follows. 1. The child process tells the parent process the largest possible value. 2. The parent process makes a guess (picking an integer in the range) and sends it to the child process. 3. The child process checks if the guess is correct and sends the result to the parent process. The result is 0 if the guess is correct, 1 if the guess is smaller, or -1 if the guess is larger. If the guess is correct, the child process also sends a final message and then exits. The final message includes the number of attempts the parent has made to guess the correct number.4. If the guess is not correct, the parent process adjusts the range, based on the feedback from the child process, and goes to Step 2. 5. If the guess is correct, the parent receives the final message from the child process and prints it to stdout.The parent process uses a binary search to minimize the number of the guesses (over many games). guess_my_number() in the starter code demonstrates the process. It prints the guesses the parent process makes and the final message from the child process. The function does not involve multiple processes or pipes.The task in this problem is to complete the starter code so the parent process and child process can play the game by communicating through pipes. Search TODO in the starter code to find the places where work needs to be done. The detailed steps are described in comments. Most of the steps are operations on pipes, e.g., reading from or writing to a pipe. Below are some requirements and suggestions on the implementation.• Integers are stored in variables of type int. An integer is written to the pipe as 4 (sizeof(int)) bytes in a binary format. • The final message is transmitted as a sequence of ASCII characters. It ends with a new line character. The parent does not assume the message has a specific length. Therefore, it has to read characters until it finds a new line character. The child does not send a NULL character to the pipe to indicate the end of the sequence of characters (that is, the sequence is not a string).• The child process calls functions to operate on gmn. It does not access fields in the structure directly. • Put commonly used operations, e.g., writing an integer to a pipe, in functions. • If read() or write() fails, call die() to exit.The program guess-my-number takes optional arguments from the command line. An argument can be one of the following. • A positive integer. It will be used as the seed for generating pseudorandom numbers. If no seed is specified on the command line, a default value is used.• demo. Call the demo function and exit. It helps us to test our implementation using two processes. The following are two sessions of running the program. The first session calls the demo function. The second session is from our implementation using two processes. ./guess-my-number demo 3000 My guess: 500 My guess: 250 My guess: 375 My guess: 312 My guess: 281 My guess: 265 My guess: 273 My guess: 277 My guess: 279 My guess: 280 It took you 10 attempt(s) to guess the number 280. $ ./guess-my-number 3000 My guess: 500 My guess: 250 My guess: 375 My guess: 312 My guess: 281 My guess: 265 My guess: 273 My guess: 277 My guess: 279 My guess: 280 It took you 10 attempt(s) to guess the number 280.
Part 1. (100 points) run2 should use the fork and exec functions to run two commands specified on the command line. The arguments passed to run2 are stored in the array argv. The first executable is argv[1] and it takes one, and only one, argument, which is in argv[2]. The second executable is argv[3], and the rest of arguments, if any, are arguments to argv[3]. In the following example, the two commands are cat Makefile and ls a b. $ ./run2 cat Makefile ls a b There are multiple functions in the exec family of functions, which behave in slightly different ways. You should use execlp to run the first command, and execvp to run the second command. You should read the manpage for exec, and understand why these variants are sensible choices here. If any functions like fork() fail, report the error using perror() and exit from the process. The parameter to perror() is the function name followed by parentheses, as in the following examples. perror(“fork()”); perror(“execlp()”); For each child process successfully created, the parent process waits for the child process to exit and prints out the exit status of the child process using the following format string: “exited=%d exitstatus=%d ” The first number is from WIFEXITED, and the second is from WEXITSTATUS. Study the demo code or the manuals to learn WIFEXITED and WEXITSTATUS. Below are some examples of using run2. You may have more creative ways to use the program. $ ./run2 vi run2.c make $ ./run2 touch run2.c make run2 $ ./run2 echo 1 ./run2 echo 2 ./run2 echo 3 ls *
Part 1. Delete node. The linked list example we have studied in lecture maintains a singly linked list of integers. The program can append and prepend integers to the list. Type help in the program to see a list of commands. Note that if the number to be added is already on the list, the program prints the information about the node that stores the number and does not add the number twice. The list is displayed every time an integer is processed. Currently, the program does not support the delete function. Complete the function delete node() in linkedlist.c so that the program can delete an integer from the list. The prototype of the function is: node * delete_node(node * head, int v); head is a pointer to the head node and v is the integer to be removed. The function returns the pointer to the head node of the new list, which could be the same as head. If v is not on the list, the function prints a message using the following function call: error_message(ERR_NOTFOUND). Below is an example session using the delete feature. $ ./linkedlist-main 1 2 3 4 5 6 7 8 9 [1, ] [1, 2, ] [1, 2, 3, ] [1, 2, 3, 4, ] [1, 2, 3, 4, 5, ] [1, 2, 3, 4, 5, 6, ] [1, 2, 3, 4, 5, 6, 7, ] [1, 2, 3, 4, 5, 6, 7, 8, ] [1, 2, 3, 4, 5, 6, 7, 8, 9, ] d5 [1, 2, 3, 4, 6, 7, 8, 9, ] d3 [1, 2, 4, 6, 7, 8, 9, ] d3 linkedlist: The number is not on the list. [1, 2, 4, 6, 7, 8, 9, ] 1 Part 2. List reversal. In this exercise, we implement another function reverse_list() in linkedlist.c. The prototype of the function is: node * reverse_list(node * head); The function receives head as its sole argument, a pointer to the head node of the linked list. Assume the list is acyclic. The function must change the next fields of each node so that the nodes end up linked in reverse order. The function must return the address of the new head node (originally last in the list). You may use additional functions and local variables besides those already included in the starter code, but cannot change the values stored in the nodes or dynamically allocate new nodes. You can use either a loop or recursion. Below is an example session using the reversal feature. $ ./linkedlist-main 1 2 3 4 5 6 7 8 9 [1, ] [1, 2, ] [1, 2, 3, ] [1, 2, 3, 4, ] [1, 2, 3, 4, 5, ] [1, 2, 3, 4, 5, 6, ] [1, 2, 3, 4, 5, 6, 7, ] [1, 2, 3, 4, 5, 6, 7, 8, ] [1, 2, 3, 4, 5, 6, 7, 8, 9, ] r [9, 8, 7, 6, 5, 4, 3, 2, 1, ] r [1, 2, 3, 4, 5, 6, 7, 8, 9, ] 2
