Problem 1. (Points: 10) Suppose a job ji is given by two numbers di and pi , where di is the deadline and pi is the penalty. The length of each job is equal to 1 minute.All n such jobs are to be scheduled, but only one job can run at any given time. If job ji does not complete before its deadline di , its penalty pi should be paid. Design a greedy algorithm to find a schedule which minimizes the sum of penalties and prove its optimality.Problem 2. (Points: 20) A thief enters a store and sees a set I of n items, I = {a1, a2, · · · , an}. Each item has an associated weight wi and value vi . Ideally, the thief would like to steal everything in order to gain maximum benefit. However, there is only so much he can carry. The thief has a knapsack with capacity C. The thief now has to determine which items to steal so that their total weight does not exceed C and their total value is maximum.1. Suppose the items are such that a fraction of an item can be taken, i.e. the thief can take some part of an item (for example, 0.4wi of ai) and leave the remaining part. This is called the Fractional Knapsack Problem. Let A ⊂ I be the subset of items that the thief steals. Devise an O(n log n) greedy algorithm to find the subset A such that P ai∈A wi < C and P ai∈A vi is maximum.2. Suppose items can be taken as a whole, i.e. the thief can only take or leave an item; he can not take a fraction of an item. This is called the Binary Knapsack Problem. Does your greedy algorithm for the fractional version of the problem (previous question) still find an optimal solution? Justify your answer.Problem 3. (Points: 20) Coins of a set of denominations (values) are available to a cashier who needs to provide change for a given amount V , such that the number of coins returned in exchange for V is minimum. We assume an infinite supply of each denomination.1. Given the denomination set {1, 5, 10}, devise a greedy algorithm to find the minimum number of coins, that can be exchanged for V . 2. Is your greedy algorithm optimal for any given set of denominations? Justify.Problem 4. (Points: 10) The counting sums problem is to count the number of ways a number can be written as the sum of two or more positive integers. For example, we can write 6 as the sum of two or more positive integers in the following ways 5 + 1 = 6 4 + 2 = 6 4 + 1 + 1 = 6 3 + 3 = 6 3 + 2 + 1 = 6 3 + 1 + 1 + 1 = 6 2 + 2 + 2 = 6 2 + 1 + 1 + 2 = 6 2 + 1 + 1 + 1 + 1 = 6 1 + 1 + 1 + 1 + 1 + 1 = 6 Using a dynamic programming approach, write an algorithm to determine the number of ways 100 can be written as the sum of two or more positive integers.Problem 5. (Points: 10) Consider the coin change problem: Coins of a set of denominations (values) are available to a cashier who needs to provide change for a given amount V , such that the number of coins returned in exchange for V is minimum. We assume an infinite supply of each denomination.Devise a dynamic programming algorithm which, given a set of denominations D = {d1, · · · , dk} and value V , produces the optimal result for the coin change problem. Briefly argue about the optimal substructure property of the problem.
Problem 1. (Points: 15) Suppose you are choosing between the following 3 algorithms: • Algorithm A solves the problem of size n by dividing it into 8 subproblems of size n/4, recursively solving each subproblem, and then combining the solutions in linear time.• Algorithm B solves the problem of size n by recursively solving two subproblems of size n − 1 and then combining the solutions in constant time • Algorithm C solves the problem of size n by dividing it into nine subproblems of size n/3, recursively solving each subproblem, and then combining the solutions in O(n 2 ) time. What are the running times of each algorithm and which would you choose and why?Problem 2. (Points: 10) Assume that n = 2k for some positive integer k. Using induction prove that if T(n) is given as follows, then T(n) = n log n. T(n) = 2 if n = 2 2T n 2 + n if n > 2Problem 3. (Points: 20) Assume you have an array A[1..n] of n elements. A majority element of A is any element occurring in more than n/2 positions (so if n = 6 or n = 7, any majority element will occur in at least 4 positions). Assume that elements cannot be ordered or sorted, but can be compared for equality. (You might think of the elements as chips, and there is a tester that can be used to determine whether or not two chips are identical.)Design an efficient divide and conquer algorithm to find a majority element in A (or determine that no majority element exists). Aim for an algorithm that does O(n log n) equality comparisons between the elements. A more difficult O(n) algorithm is possible, but may be difficult to find.Problem 4. (Points: 20) Given a binary string S of type{1 m0 n}, devise an algorithm that finds the number of zeroes in O(log k) time. Let m + n = kProblem 5. (Points: 20) [K-way Merge] Suppose you have k sorted arrays A1, A2, …Ak each with n elements. You want to combine them into a single sorted array of size kn.One way to do this would be to use the merge operation we discussed in class. First merge arrays A1, A2 then merge the result with A3 and so on • Figure out how many steps this algorithm would take. • Design a better algorithm for this problem.Problem 6. (Points: 20) [Fibonacci Numbers] Given below is a recursive algorithm for finding the nth Fibonacci number Algorithm 1 : function fib(n) if n == 0 or n == 1 then return 1 else return fib(n-1) + fib(n-2)• Analyze the running time of this algorithm • A lot of computation seems to be repeated over and over in this algorithm. For example f ib(4) would compute f ib(3) and f ib(2) and then the called f ib(3) would also compute f ib(2). Is there a way we could avoid computing the same thing over and over again while still using a recursive approach?Problem 7. (Points: 30) Given the following recurrence relations, find the running time (in big-O notation) using the recursion tree method and the Master Theorem. • T(n) = 8T n 2 + Θ(n 2 ) if n ≥ 2 1 else • T(n) = 3T n 4 + n log n if n ≥ 2 1 else • T(n) = 2T n 4 + √ n if n ≥ 2 1 elseProblem 8. (Points: 20) A bank confiscates n bank cards suspecting them to be involved in fraud. Each card corresponds to a unique account but an account can have many cards corresponding to it. Therefore, two bank cards are equivalent if they belong to the same account. The bank has a testing machine for finding out if two cards are equivalent.They want to know that among the collection of n cards, are there more than n/2 cards that are equivalent. The only operation that the machine can do is to select two cards and tests them for equivalence. You are required to come up with a solution to this using only O(n log n) invocations of the testing machine.Problem 9. (Points: 20) Prove the correctness of the following algorithm for incrementing natural numbers. Analyze the algorithm to find out how many times is line 3 executed in the worst case.Algorithm 2 : Increment Natural Numbers function increment(x) . Returns x + 1 if x mod 2 == 1 then return 2 × increment(b x 2 c) else return x + 1Problem 10. (Points: 20) Prove the correctness of the following recursive algorithm for the multiplication of two natural numbers is correct, ∀ integer constants ≥ 2. Analyze this algorithm to find out how many times line 5 executed in the worst case.Algorithm 3 : Multiply Two Numbers function multiply(x,y) . Returns product xy if y == 0 then return 0 else return multiply(cx, by/cc) + x(y mod c)
Problem 1. (20 points) Suppose that you have been hired by the CS Department to prepare the course offering schedule of CS courses for the next 5 years. You are given the following scheduling constraints:1. All CS courses are offered in regular semester only, i.e., in Fall semester or in Spring semester. No CS course is offered in the summer semester. 2. Due to shortage of faculty, same course cannot be offered in both Fall and Spring. A course is offered either in Fall semester or in Spring semester but not in both semesters.3. All CS courses, except CS100, have one or more prerequisites. CS100 does not have any prerequisite. Any given course and its prerequisite course(s) cannot be offered in the same semester. We refer to a pair of courses (ci , cj ) as conflicting courses if ci is a prerequisite of cj .Note that the conflict relation is not a transitive relation. For example CS100 is a prerequisite of CS200 and CS200 is a prerequisite of CS300. However, CS100 and CS300 are not conflicting courses because CS100 is not a direct prerequisite of CS300.Suppose that there are n CS courses and r pair of conflicting courses. Give an O(n+r) time algorithm that returns a feasible course offering schedule, including all n courses subject to the above constraints. Your algorithm should return “FALSE” if no feasible schedule existsProblem 2. (10 points) Explain how a vertex u of a directed graph can end up in a depth-first tree containing only u, even though u has both incoming and outgoing edges in G.Problem 3. (10 points) Consider a directed graph G = (V, E), where V = {a, b, c, d, e, f, g, h}, and E = {(a, e),(a, h),(b, c),(b, d),(c, d),(d, a),(d, e),(e, f),(f, h),(g, f),(h, e),(h, g)} Find the strong components of G.Problem 4. (10 points) Consider a directed graph G = (V, E), where V = {a, b, c, d, e, f}, and E = {(a, b),(a, d),(b, c),(c, f),(d, e),(e, f)} How many topological orderings does G have? Write all possible topological orderings.Problem 5. (10 points) The topological ordering algorithm discussed in class repeatedly finds a node with no incoming edges and deletes it. This will eventually produce a topological ordering, provided that the input graph is a DAG.Extend the topological ordering algorithm so that, given any arbitrary directed graph G, it outputs one of the two things: (a) a topological ordering, thus establishing that G is a DAG; or (b) a cycle in G, thus establishing that G is not a DAG. The running time of your algorithm should be O(m + n) for a directed graph with n nodes and m edges.
Problem 1. (10 points) Gale and Shapely published their paper on the Stable Matching Problem in 1962; but a version of their algorithm had already been in use for ten years by the National Resident Matching Program, for the problem of assigning medical residents to hospitals.Basically, the situation wa the following. There were m hospitals, each with a certain number of available positions for hiring residents. There were n medical students graduating in a given year, each interested in joining one of the hospitals. Each hospital had a ranking of the students in order of preference, and each student had a ranking of the hospitals in order of preference. We will assume that there were more students graduating than were slots available in the m hospitals.The interest, naturally, was in finding a way of assigning each student to at most one hospital, in such a way that all available positions in all hospitals were filled. (Since we are assuming a surplus of students, there would be some students who do not get assigned to any hospital.)We say that an assignment of students is stable if neither of the following situations arise. 1. First type of instability: There are students s and s 0 and a hospital h, so that • s assigned to h, and • s 0 is assigned to no hospital, and • h prefers s 0 to s.2. Second type of instability: There are students s and s 0 and hospitals h and h 0 , so that • s assigned to h, and • s 0 is assigned h 0 , and • h prefers s 0 to s, and • s 0 prefers h to h 0 ,So, we basically have the Stable Matching Problem, except that (i) hospitals generally want more than one resident, and (ii) there is a surplus of medical students. Show that there is always a stable assignment of students to hospitals, and give an algorithm to find one.Problem 2. (18 points)Suppose you have algorithms with the six running times listed below. (Assume these ar the exact number of operations performed as a function of the input size n.) Suppose you have a computed that can perform 1010 operations per second, and you need to compute a result in at most an hour of computation.For each of the algorithms, what is the largest input size n for which you would be able to get the result within an hour? a) n 2 b) n 3 c) 100n 2 d) nlogn e) 2 n f) 2 2 n Problem 3. (5 points) Show that 2 n+1 is O(2n )Problem 4. (15 points, 3 points for each case) In each case below, demonstrate whether the given expression is true or false.You need to provide proper reason to receive credit. a) 5n 3 ∈ O(n 3 ) b) 100n 2 ∈ O(n 4 ) c) log n 2 ∈ O(log n) d) (n 2 + 7n − 10)3 ∈ O(n 6 ) e) √ n ∈ O((log n) 3 )Problem 5. (18 points, 2 points for each row) In each row of the following table, write whether f = O(g), or f = Ω(g), or both i.e. f = Θ(g) 2 f(n) g(n) Your Answer 100 17 10200 n − 10200 n 2 log 300 n log n n 100 2 n n log n n − 100 √ n log n n 1.01 n + 100 2 log n log(n 2 ) log(n 2 ) (log n) 2Problem 6. (18 points) Order the following functions of n from the smallest to largest complexity. If two have the same complexity put them in one line next to each other. n log n, (n − 5)(n), 10 log 300, n + 7 log(n 2 ), 2 n , 10n 2 + 15n, 17, 15n 3 + n log n, 3n 8 n6 10200, n2 log 300, 2 log10 10200, n2 + 7 log(n 2 ), 3 n 2 , n2 + √ n, n2 log n, n4 + n 2 + n 2 log n, n4Problem 7. [Complexity Classes] (18 points, 2 points for each function) Order the following functions of n from the smallest to largest complexity and also identify the complexity class for each. If two have the same complexity put them in one line next to each other. Briefly explain next to each line why these functions are in the same complexity class. 10200, n2 log 300, 2 log10 10200, n2 + 7 log(n 2 ), 3 n 2 , n2 + √ n, n2 log n, n4 + n 2 + n 2 log n, n4Problem 8. (24 points, 3 points for each part) Let f(n) and g(n) by asymptotically positive functions. Prove or disprove each of the following conjectures. 1. f(n) = O(g(n)) implies g(n) = O(f(n)). 2. f(n) + g(n) = Θ(max(f(n), g(n))). 3. f(n) = O(g(n)) implies lg(f(n)) = O(lg(g(n))), where lg(g(n)) ≥ 1 and f(n) ≥ 1 for all sufficiently large n. 4. f(n) = O(g(n)) implies 2 f(n) = O(2g(n) ). 5. f(n) = O((f(n))2 ). 6. f(n) = O(g(n)) implies g(n) = Ω(f(n)). 7. f(n) = Θ(f(n/2)). 8. f(n) + Ω(f(n)) = Θ(f(n)).Problem 9. (24 points – 5 + 5 + 14) Consider the following basic problem. You are given an array A consisting of n integers A[1], A[2], . . . A[n]. You would like to output a two-dimensional n − by − n array B in which B[i, j] (for i < j) contains the sum of array enries A[i] through A[j] – that is, the sum A[1] + A[2], + · · · + A[n]. (The value of array entry B[i, j] is left unspecified whenever i ≥ j, so it does not matter what is output for these values.)Following is a simple algorithm to solve this problem. Algorithm 1 : Summing array entries for i = 1 to n − 1 do for j = i + 1 to n do B[i, j] ← Pj k=i A[k] return B1. For some function f that you should choose, give a bound of the form O(f(n)) on the running time of this algorithm on an input of size n (i.e., a bound on the number of operations performed by the algorithm)2. For this same function f, show the running time of the algorithm on an input of size n is also Ω(f(n)). (This shows an asymptoticaly tight bound of Θ(f(n)) on the running time.3. Although the algorithm given above is the most natural way to solve the problem – after all, it just iterates through the relevant entries of the array B, filling in a value for each – it contains some highly unnecessary sources of inefficiency. Give a different algorith to solve this problem, with an asymptotically better running time. In other words, you should design an algorithm with running time O(g(n)), where limn→∞ g(n)/f(n) = 0.
Task(s): Question 1: For this task, you are required to take the name of the file as input from the user and then read it (marks will be deducted if you don’t take the name of the file as input). (20 marks)• The txt file contains push & pop operations. You need to read the file line by line and identify the given data structures i.e., Stack, Queue, Priority Queue (min & max) or you can identify it as insufficient information or illegal action depending on the information in the file.• The first line of your txt file will always be an integer that shows how many lines you are required to read from first line to that specific line in the file to determine the data-structure. The sample txt file is attached for your help• For example, if there is a 6 in the first line, you must read the next 6 lines and based on that you must identify the data structure. Please look at the examples given below • If there is a non-digit character in it, you need to deal with its ASCII-value. For example, if there is push(’A’), you need to check if there is pop(65) as ASCII-value of ’A is 65• If the line count is greater than number of remaining lines of code in the txt file then your code must not crash in that case as well. Please look at the last example given below for this taskQuestion 2: Write a O(n) boolean function named checkpalindrome that checks whether a given singly linked-list is palindrome or not. The arguments of the function will be a linked-list of integers. (4 marks)Question 3: Write a O(n) function named rotate that takes a number n and and a singly linked-list in its arguments. Your function will rotate the given linked-list by n times and return it. (6 marks)Question 4: Write a O(n) function named reverse that reverses a stack using recursion. The arguments of the function will be a stack containing strings. Your function will return a reversed stack (5 marks)Question 5: SWAPI: The Star Wars API. SWAPI is a data source which contains all the data from the Star Wars canon universe! You can familiarise yourself with the API here. (20 marks) Given 2 strings, the name, and the entity to which the name belongs, you are required to write a program that uses the API and displays their complete information.For example: If the entity is a “film” and the name of the film is “A New Hope” then you need to return the details of the film which has that specific name. You must also return the name of the characters (along with their species), planets, vehicles, and starships involved in the movie. Similarly, this needs to be done for other entities, which can be a starship, a person, a vehicle, or any of the species.You’re required to use promises and your code must not crash in case of an input that is incorrect (and if any of the API returns an error). For calling the API’s, you will be using axios, which is a promise-based HTTP client for browsers and node js. You can read further on axios here.Example: Entity: film Name: A New Hope Output: Title: A New Hope Director: George Lucas Producer: Gary Kurtz, Rick McCallum Release-date: 1977-05-25 Characters: (only typing out the first 2, but there is a total of 18 ) 1. Luke Skywalker 2. C-3PO The following planets where the movie was shooted at: 1. Tatoonie 2. Alderaan 3. Yavin IV The following starships were used in the movie: 1. CR90 corvette 2. Star Destroyer 3. Sentinel-class landing craft 4. Death Star 5. Millennium Falcon 6. Y-wing 7. X-wing 8. TIE Advanced x1 The following vehicles were used in the movie: 1. Sand Crawler 2. T-16 Skyhopper 3. X-34 Landspeeder 4. TIE/LN starfighter Different species involved in the movie: 1. Human 2. Droid 3. Wookie 4. Rodian 5. HuttQuestion 6: Sameer and Ahmed want to hire a team of ”k” software engineers from ”n” candidates such that the performance of the team is maximized.You are given two integers ”n” and ”k” and two integer arrays ”speed” and ”efficiency” both of length ”n”. There are ”n” engineers numbered from ”1” to ”n”. speed[i] and efficiency[i] represent the speed and efficiency of the ith engineer respectively. Write a function named maxPerformance that chooses ”k” engineers from ”n” candidates to form a team with the maximum performance and returns the maximum performance.The performance of a team is the sum of their engineers’ speeds multiplied by the minimum efficiency among their engineers. The function will take following parameters (k n speed effeciency) (10 marks)Question 7: Is Node really single-threaded? Through this question we will try to learn the threading structure of Node. “pbkdf2” https://nodejs.org/api/crypto.html is a bult-in function that computes a hash, and it is a long running operation, which is expected of a hash function. We are going to use this function and do some experiments. Import this function from the crypto module, call it and measure the time it takes to complete the execution.a) Use the “pbkdf2” function and observe whether or not node is single threaded. Observe the results and comment on what do you think about the default number of threads in Nodejs. (5 Marks)b) Add “process.env.UV THREADPOOL SIZE = 8” at the start of your code and now repeat the above experiment. Comment on your observations. (5 Marks)c) Add “process.env.UV THREADPOOL SIZE = 8” at the start of your code. Call the pbkdf2 and measure the time, keep on adding the function calls one by one and you will observe that the average running time starts increasing, although that we have increased the thread pool size. What do you think is the cause of this? Comment on your observations. (5 Marks)d) Explore the Node’s git repo https://github.com/nodejs/node. What is v8? What is Libuv? And what is the role of these two in Node. (Hint: find the ”pbkdf2” function in the repo and explore it) (5 Marks) Code in separate files for each question and write the comments inside the file.Question 8: You’re working at a tech company, and you’ve been assigned a task to reduce the storage costs on the servers by compressing the large codebase of their website without changing the repository structure. (15 marks)You’re required to make function that essentially takes a source directory path and a target directory path as arguments. The target folder will be empty initially. Your job is to compress all the files in the source folder and store them in the target directory in a recursive fashion (the target folder will have the same hierarchy of the subdirectories as in the source folder). You’re only allowed to use the JavaScript’ ‘fs’ module (only the asynchronous functions of it) for all tasks except compressing; you may use any library/module for it.You’re also required to make the promised versions of the read and write functions, and not use them directly.
Question 1 [50]: Given a (singly) linked list with head node root, write a function to split the linked list into k consecutive linked list “parts”. The length of each part should be as equal as possible: no two parts should have a size differing by more than 1.This may lead to some parts being null. The parts should be in the order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal parts occurring later. Return a List of List Nodes representing the linked list parts that are formed. Examples 1->2->3->4, k = 5 // 5 equal parts [ [1], [2], [3], [4], null ] Input: root = [1, 2, 3], k = 5 Output: [[1],[2],[3],[],[]] Explanation: The input and each element of the output are ListNodes, not arrays. For example, the input root has root.val = 1, root.next.val = 2, root.next.next.val = 3, and root.next.next.next = null.The first element output[0] has output[0].val = 1, output[0].next = null. The last element output[4] is null, but it’s string representation as a ListNode is []. Input: root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3 Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]] Explanation: The input has been split into consecutive parts with size difference at most 1, and earlier parts are a larger size than the later parts.The function prototype will be something like splitListToParts(ListNode* root, int k), however, it’s not necessary to use this. Marks distribution: Code works on all inputs: 50 marks Code works on some but not all inputs: 25 marks Works on no input: 0 marksQuestion 2 [50]: In this question, you will implement a music playlist using a recursive singly linked list. You need to edit the pa4.cpp file provided in the assignment for this question, don’t forget to rename it according to the naming convention before submitting. The node will be a struct called ‘Node’ which has 3 variables: 1. Song_title 2. Id 3. Pointer to Node next Your playlist will be a linked list of these nodes. You will need to write functions to: 1. Insert a song at the end (recursive definition) [5] 2. Insert a song after a specific song (iterative definition) [5] 3. Delete a song (from the end) (recursive definition) [5]4. Display the playlist (recursive definition) [5] 5. Find the min id of the songs in the playlist (recursive definition) [10] 6. Determine the length of the playlist (recursive definition)[5] 7. Search for a song in the playlist (search by song title, search by song id) (recursive definition) [5] 8. Delete the playlist (recursive definition)[10] You must implement the functions iteratively or recursively as mentioned above and in the driver code. You are not allowed to make changes to the function definitions.Make the appropriate prompts to the user for entering the details of the songs where required and also to determine whether the user wants to search for a song by its title or its id. In the main function, you will create a menu that will allow the user to avail of any of these functionalities and will continue doing so until the user desires to stop. Ensure that your program makes the appropriate checks where required so that your program never crashes unexpectedly.
Question 1 [50]: Board-Game scenario: Consider a board game (Board: 2D Dynamic Array/ 2D Vector (m x n)). The player starts the game at the top left corner of the board. While he ends the game at the bottom right corner. The board elements are either marked with 0 or 1. During the game, if any cell of the board is marked with zero, the player can’t go to that cell. The player can only move to the board cell if the cell is marked with 1. Moreover, the player can only move to the consecutive right or down cell. You need to find if there is any possibility for the player to reach the bottom right corner of the board. Note: Top left cell always contains 1.The required functions for this question are: 1. You need to implement the function inputBoard which inputs the board from the user in the 2D Dynamic Array / 2D Vector. The number of rows does not necessarily have to be equal to the number of columns. [5]2. You need to implement another function findPossibility. This takes the board as input and states if there is any possibility for the player to reach the end of the board. [45] Works for no input, max marks possible = 10, based on code If only works for some input, max marks possible = 30 Works for all inputs correctly = 45The prototype of function for 2D dynamic array should look something like this: bool findPossibility(bool** board, int row, int col); Sample Input and Output: Input Example: arr[][] = { {1, 1, 1, 0, 1}, {0, 1, 1, 0, 0}, {1, 1, 1, 0, 1}, {0, 1, 1, 1, 1}, {1, 1, 0, 1, 1} } Output: True Input Example: arr[][] = { {1, 1, 1, 0, 1}, {0, 1, 1, 0, 0}, {1, 1, 1, 0, 1}, {0, 1, 0, 1, 1}, {1, 1, 0, 1, 1}, {0, 0, 0, 0, 1} } Output: FalseQuestion 2 [100 marks]: In this next task, you will need to implement a program using class inheritance: There will be one class named ‘Clock’ with attributes: [5] 1. Minutes 2. Hour 3. Meridiem (will store ‘AM’ or ‘PM’)And methods: 1. display_time() [5] You are also required to make the default and parameterized constructors along with getters and setters. Another class, ‘Clock_angle’ will inherit Clock publicly and contains the following variables and member functions: [5]Attributes: 1. Angle Methods: 1. calculate_clock_angle() 2. display_time() [20] Make the default and parameterized constructors and setter and getters Note: Both display_time functions will have the same prototype, but their functionality will be different. The display_time() function of class ‘Clock’ will display the time as ‘hh: mm’ while in clock_angle it will display the time in 24hr format ‘XXXX hrs’ Calculate_clock_angle(): [35]This function will determine the size of the angle between the hour and minute hands of the clock object.It will also take an argument: ‘minutes_elapsed’ and calculate the angle between the clock hour hand and the new minutes. New minutes = clock minutes + minutes_elapsed (You may assume for simplicity that minutes_elapsed will range from 0 to 60. Make sure to deal with the corner cases accordingly then)The function should print both the above-mentioned angles to the console and return the difference of clock-hour-clock-minutes angle subtracted from new_minutes-clock-hour angle.Note: Assume all angles are positive and consider the smaller of the two possible angles between the hands. For E.g., if the hour = 9 and minutes = 0, the angles between the two hands are 90 degrees and 270 degrees, but you will only consider the 90-degree angle.In the main function Make a pointer to the clock class and an object of clock_angle and make the pointer of the base clock class point to the clock_angle object and use the pointer to call the necessary functions where possible. [10]You are required to prompt the user for the time, which will be entered as “hhmm” (i.e., 12-hour format). You must do all error handling to ensure that a valid time is entered. [10] E.g 1234 is valid 2314 is not valid 959 is valid 1060 is valid, but you need to interpret it as 1100 Keep prompting the user for a valid input if an invalid time is entered And then prompt for ‘AM or PM’After entering the time, display the time in 12-hour format then in 24-hour format and then call calculate_clock_angle() which would print the 2 angles (make sure to include prompts to specify which angle between which hands is being printed) and then print the returned angle difference Correct output [10]Sample output: If input = 900, AM and angle parameter in calculate_clock_angle() = 15 Time in 12-hour format: 9:00 AM Time in 24-hour format: 0900 hrs The angle between clock hour and clock minute: 90 degrees The angle between clock hour and minutes elapsed: 180 degrees Angle difference: 90 degreesMarks Distribution details: 1. If any constructor or setter or getter missing, award 0/5 marks for either class structure 2. If 24-hour display_time() works for values and not for other, award 10/20 marks 3. Calculate_Clock_angle() a. If larger angles considered instead of smaller ones, max marks = 20 (with everything else correct) b. If some angles correct and some wrong, award 20/35 c. If no angles correct, max marks = 10/35 d. If all angles correct, award 35/35 4. If pointer for base class not used with inherited object, 0/10 5. Validation of inputs: a. If all inputs correctly validated, 10/10 b. If 60 minutes not handled, 5/10 c. If some invalid input regarded valid or vice versa, 5/10 6. Output format: a. If description for values missing, 5/10 b. One item missing, 5/10 c. Two or more items missing from output, 0/10
In this question, you will have to implement fractions as a class and perform operations on them using operator overloading. Create a class Fractions with private member variables [2] ● int numerator ● int denominator Implement the following: ● Default constructor (choose the fraction appropriately) [3] ● Parameterized constructor [5] Fractions(int n, int d)Note: ALL RESULTS OF COMPUTATIONS SHOULD HAVE THE FRACTION IN REDUCED FORM. ( if the result is 4/6, it should be displayed as ⅔ where needed); Other member functions to include using operator overloading are. The operator to overload is mentioned in parentheses: ● Addition of two fractions returning the sum of the fractions (+) [10] ● Subtraction of two fractions returning the difference of the fractions (-) [10]Note: For the above-mentioned functions, you may find it helpful to make a function for calculating the LCM, but it is not mandatory ● Check if two fractions are equal and return whether they are equal or not. (==)Note: The implementation should cater for equivalent fractions and return them as true [5] ● Increment the fraction (+) (fraction + 1) [5] Note: You will have two overloaded (+) functions that will have different definitions and so will be used differently. Hint: it will be defined how Sir did it in class. ● Decrement the fraction (–) (fraction – 1) [5] ● Multiply two fractions and return the result (*) [5] ● Divide two fractions and return the result (/) [5] Note: Keep in mind that division of fractions is really just multiplication with a fraction’s reciprocal ● Check whether the current fraction is greater than the other (>) [10] ● All input of fractions should be using the (>>) operator [5]● All display of fractions should be with the ( frac2 returns falseInitialize a 2-D char array. Both size (rows and columns) and input of characters into array will be done by the user. Part A – Initialization [15]: You are required to save a number of rows, and an array to save a number of columns of sizes equal to the number of rows. The user will enter a number of columns for each row at run time.That could be of variable size. For example: D D N M A V V V J H E E E B P K L D D V A C R F P Y R X O H H H G Part B – Remove duplicates [10] Now you have to compress this 2-D array. By removing characters that occur more than once consecutively (in rows), remove them and place a ‘&’ in their place. For example: D & N M A V & & J H E & & B P K L D & V A C R F P Y R X O H & & GPart C – Reinitialization [20] Need to reinitialize arrays such that after compressing each array there is no additional extra space allocated. For instance: D N M A V J H E B P K L D V A C R F P Y R X O H G Hint to resize array: create temp array, delete current array, point to temp array Part D – Deallocation and Testing[10] Properly Deallocate the 2D dynamic array and implement a main function to testYou have to design a program for a newly admitted Chief Police Officer (CPO) of a police station. This program will help the CPO to gather data on the prisoners in the prison. You have to store the following variables for each prisoner in a class Prisoner: 1. Name 2. Age 3. Blood Group 4. Crime 5. Date of Entry (DD-MM-YYYY format) 6. Duration of Sentence 7. Tentative Release Date 8. Prison-cell number a. Assume every prisoner has a unique prison-cell number. b. Prison-cell numbers start with 0. c. As every prisoner has a unique prison cell number, you should use this variable for indexing different prisoners for addition/removal. Only the CPO should be able to access prisoner data and must be able to keep track of the behaviour of the prisoners depending on their recent behaviour in prison. For this, you need another member variable for the Prisoner class named ‘behaviour’. The CPO can increase or decrease the sentence period of any prisoner depending on behaviour. The types of behaviour are: 9. Behaviour a. Very Bad: +5 years, 3 months, and 20 days b. Bad: +2.5 years, 9 months, and 15 days c. Average: No change d. Good: -6 months, and 20 days e. Very Good: -1 Year and 3 months Note: (+) denotes increase in sentence period, (-) denotes a decrease in sentence period. In cases where the dates suggest that the prisoner has served his/her full sentence, s(he) should be automatically removed from the prison data. The default value for behaviour should be Average. Make another class, Prison, which would store all the data of the prisoners in a dynamic array of type Prisoner.The CPO should also be able to: 1. Initialize the prisoner data of the number of prisoners present in the prison on his first day as CPO. [10 – Proper Dynamic Allocation] 2. Add a prisoner using the overloaded (++) operator. Keep in mind that a new prisoner can be added only to a prison cell that is not occupied by any other prisoner. [10] 3. Remove a prisoner manually using the (–) operator. [10] Hint for 2. And 3.: You can implement this functionality by making a new temporary dynamic array with a new size, delete the current array, and point to the temporary array.4. Remove a prisoner automatically if the release date has crossed (using behaviour functionality) [15] 5. Edit the information of a prisoner (in the case where the CPO tries to edit the cell number of a particular prisoner to a cell number which is already occupied, the CPO should be given the option to swap cell numbers or enter another cell number that is not occupied) [5] 6. Make deep copies of the data using the overloaded copy constructor and the overloaded assignment operator (=) [10] 7. Sort the details of all prisoners in ascending order by their release date using the insertion sort algorithm. [10] a. Here’s a short video on insertion sort to get you started: https://www.youtube.com/watch?v=JU767SDMDvA&ab_channel=MichaelSambol 8. View all prisoners’ details using the overloaded (
Question 1 [25]: A. Write a swap () function that only takes pointers to two integer variables as parameters and swaps the values in those variables using the pointers without creating any extra variables. The swapped values are displayed fromthe main(). [5]B. Write a program that will take a char array as an input, and it reverses the positionsof the char elements in the array. You are not allowed to make a newarray. Usethebracket notation of arrays for this question eg: arr[j + k]. [5]Example: Input: [ ‘C’, ‘S’, ‘2’, ‘0’, ‘0’] Output: [‘0’, ‘0’, ‘2’, ‘S’, ‘C’]C. Write a program that will ask the user to enter a two integer arrays of variablesize(this means that the user can tell the program the size of each array), and thencomputes the intersection and union of those arrays. Note: the arrays can be of different lengths and the intersection/union shouldhaveunique elements in sorted order. Use pointer notation of arrays for this question. Eg: *(arr+1) [10]Output Example: Enter size of array 1: 2 Element 0, array 1: 10 Element 1, array 1: 9 Enter size of array 2: 5 Element 0, array 2: 9 Element 1, array 2: 8 Element 2, array 2: 3 Element 3, array 2: 3 Element 4, array 2: 10 Union: {3, 8, 9 ,10} Intersection: {9, 10}D. Write a function named searchInsertPos () that takes in three arguments: a sortedarray, size of the array, and an integer number. It should return the position wherethe integer value is found. In case the number does not exist in that array it shouldreturn the index where it should have been if it were present in this sorted array. Usepointer notation of arrays for this question. [5]Question 2 [25]: A. Write a function isPalindromeDelete () that will take a string containing only alphanumeric characters that are in lowercase (if you think your logic requires youtouse more than one argument, please go ahead). Your task is to see if the stringbecomes a palindrome if only one character is removed from anywhere in thestring.[12]Example: Input: “pop”, Output: true Input: “pops”, Output: true Input: “acde”, Output: false Input: “”, Output: trueB. In this task you will implement a function targetSum (). Argument: a sorted integer array, size of the array, and a target integer value. You have to find all combinationsof two elements in the sorted array which sum up to the target value. When found, add the combinations into an array, and print the array. In the case where thereismore than one combination, you may use the number 999 as a separator for thetwoor more combinations in the output array. Note: You are not allowed to use morethan one loop. Use pointer notation of arrays to do this question. [13] Input: [2, 4, 6, 9, 11], target = 11Output: [2, 9] Input: [-10, 10, 10, 20, 30, 40], target = 20 Output: [-10, 30, 999, 10, 10] Input: [-1, 4, 6, 9, 10], target = 0 Output: []Question 3 [95]: In this task, you will implement a restaurant system using structs (using the dot notation). There is a single person managing a new restaurant and several potential customers will come to the restaurant.Initially, there will be a main menu displayed on the console to enter either of the twomodes: customer or owner. Main Menu [3]: Press 1 for customer mode Press 2 for owner mode Press 3 to exit programIf customer is selected, the following options should be available for the customers[2]: Press 1 for new customer Press 2 for current customerThe details of what the above selections would do is specified below: 1. New customer The customer is prompted to enter their name (assume every person at the restaurant has a different name) [2] The customer is asked to select a seat position to be seated and after successful seating, the customer menu is displayed. The criteria for successful seating is statedbelow [3] Select seat [2+2+2+2+2]:o There is a single row of 10 seats available, each empty seat depictedwithan‘o’ o The customer will select the numbered seat they wish to sit at, and theoccupied seat will then turn ‘x’ (the size of the seats array will remain thesame)o A customer may mistakenly try to sit in an already occupied seat andyoushould make sure that isn’t possible. (report the exact probleme.g. Error: seat taken, choose another seat) o You should also make sure that whatever seat the customer chooses isn’t tothe immediate left or immediate right of an occupied seat, keeping in viewsocial distancing rules. o The customer should be asked to select a different seat until a successful seating is done2. Current customer (already seated) they enter their name and if the named person is present in any of the seats, thecustomer menu is displayed, otherwise an error is displayed to show this personisnot currently at the restaurant [3] Customer Menu [2] Press 1 to View food menu Press 2 to Place order Press 3 to View order Press 4 to Pay bill Press 5 to Leave Press 6 to Return to Main menuThe details of what should happen when any of the options are selected are explained as follows: 1. View food menu [10]: This will simply display the current menu of the restaurant in the followingformat: (Serial no Dish name Price) Hint: There should be an array of struct defined for menu items. There can beat most 10 items on the menu. This would be the same for both owner and customer. At initialization, the menu should have 4 items already (of your choice) (Thisis to allow space for adding more food items later)2. Place order [10]: The customer will place their order by entering the serial number of thefoodwhich will place the order (food item name) on the list for the owner toviewaswell. For simplicity’s sake, assume every customer only orders one item3. View order [5]: This will display the name of the item of food ordered by the customer4. Pay bill [8 + 2]: If a person selects to pay the bill, the person’s order is removed fromthelist of current orders kept by the restaurant and the customer is regarded as being served by the restaurant and the amount of thebill isadded to the earnings of the restaurant. Make sure that a person is not able to pay if their order was empty5. Leave [5]: A customer must only be able to leave if they have no amount due Their seat should be vacated after they leave Menu 1. Apple Pie $ 11.00 2. French Fries $8.00 3. Lasagna $24.00 4. Chop suey $15.00If owner mode is selected from the Main Menu, the following owner menu should bedisplayed on the console: Owner Menu [3] Press 1 to Update food menu Press 2 to View food menu Press 3 to View number of customers served Press 4 to View orders received (names of food items) Press 5 to Amount earned Press 6 to Offer discount Press 7 to Return to Main menuThe details of what should happen when any of the options are selected are explainedasfollows: a. Update food menu [10]: The owner would like to make the small café bigger so they would liketoaddmore food items to the menu but does not intend to get rid of anyitemonce added on the menu card. The popularity of a dish may warrant changing its price so there shouldbeanoption to adjust the price of any item on the menu individually. These two options should be displayed to the owner to select fromb. View number of customers served [2]: This should simply display the total number of customers servedc. Orders received [5]: The orders of customers who have not paid for their food yet are displayed Assume there are no more than 10 orders maded. Amount earned [5]: This should display the total earnings the owner has made at the restaurante. Offer Discount [5]: The owner would enter the percentage amount to offer discount whichwouldapply to all items on the restaurant menu.
In this homework, you will finetune the SAM model to segment the tumor area fromthe MRI images of brasins. As shown in Fig.1, there are many MRI images of brain and their masks of tumor as groundtruth. Segment Anything Model (SAM) is a large model that can be used for image segmentation. But in this task, we need to fine-tune the model in specific areas of braintumor segmentation. This homework will be implemented on the GPU server we provided. Figure 1: The MRI of brain and its mask1.2 Provided File List The provided files for this homework including: 0-The code for SAM: https://github.com/facebookresearch/segment-anything 1-SAM: The code for SAM fine-tune 2-MRI dataset: The MRI dataset 3-HW3_Assignment.pdf: The introduction and description of homework 3. 4-Report Template: A template for report. 1.3 Submission File List H3_code: Put the whole code you edited in one fold. HW3report.pdf: Report for homework 3.There are three types of sparse prompts: points, boxes, and text. In task 1, You need to prompt the model in boxes. The boxes are the envelope of the maskes, and you can also write the code yourself to generate the boxes. You can find the code to prompt the model in box in the code for SAM fine-tune. You need to finetune the model on training dataset, and validate it on testing dataset.Figure 2: The prompt encoder of SAM You should calculate the IOU to show the results of your tasks. You need to write codes to calculate the IOU of the masks we provided and your model predicted. IOU(Intersection over Union) is used to compare the similarity between the predicted output of the model and the real ground truth. The calculation formula for IOU of two areas A and B is as follows: IOU = S(A ∩ B) S(A ∪ B) Figure 3: The IOUWhere S(A∩B) means the the area of A∩B，and S(A∪B) means the the area of A∪B.There are three types of sparse prompts: points, boxes, and text. In task 2, You need to prompt the model in points. Points are generated by masks. Just one point should be generated for each image. You need to write the code yourself to generate the points. You can also find the code to prompt the model in points in the code for SAM fine-tune. You need to finetune the model on training dataset, and validate it on testing dataset. You also need to calculate IOU to showyour result.4 Code and Report Code: Before editing your code, you need to use the following commands to configure the environment on the GPU server we provided: conda install numpy conda install pandas conda install scikit-image conda install tqdm pip install ipykernel –upgrade pip install torch==2.0.1 torchvision==0.15.2 torchaudio==2.0.2 –index-url https://download.pytorch.org/whl/cu118 conda install matplotlib conda install monaiFor the task, you need to use pre_grey_rgb2D.py to preprocess your dataset. Then you need to edit finetune_and_inference_tutorial_2D_dataset.ipynb to fine-tune the SAMmodel. You canfollow the tips in code annotation.Report: Summarize the process and results of the homework, including but not limited to: The description of the implementation of SAM. The formulation and implementation of the prompt of SAM. The comparison between points and box of prompt. The description, formulation and implementation of your algorithm to improve IOU.5 Discussion and Question You are encouraged to discuss your ideas, and ask and answer questions about homework 3. Anew post for this assignment “Homework 3 Discussion” is opened in the Discussion Forumon Canvas. If you encounter any difficulty with the assignment, try to post your problemfor help. The classmates and the course staff will try to reply.6 Submission Instructions 1.Zip your whole edited code and your report file HW3report.pdf to a zip file named as HW3_GoupID.zip for a group. Write the GroupID in the name of zip file and all the names and student IDs on the cover of the report, and submit it on the team leader’s account. 2.Upload the file to “Homework 3: Segmentation” on Canvas.
In this assignment, you will implement Reinforcement Learning agents to find a safe path to the goal in a grid-shaped maze. The agent will learn by trail and error from interactions with the environment and finally acquire a policy to get as high as possible scores in the game.Suppose a 12×4 grid-shaped maze in Fig. 1. The bottom left corner is the starting point, and the bottom right corner is the exit. You can move upward, downward, leftward, and rightward in each step. You will stay in place if you try to move outside the maze. You are asked to reach the goal through the safe region and avoid falling into the cliff. Reaching the exit terminates the current episode, while falling into the cliff gives a reward -100 and return to the starting point. Every step of the agent is given a living cost (-1).Figure 1: The cliff-walking environment The state space and action space are briefly described as follows: State: st is an integer, which represents the current coordinate (x, y) of the agent. Action: at ∈ {0, 1, 2, 3}, where four integers represent four moving directions respectively.1.2 Implement Sarsa and Q-Learning You are asked to implement agents based on Sarsa and Q-Learning algorithms. Please implement the agents in agent.py and complete the training process in cliff_walk_sarsa.py and cliff_walk_qlearning.py respectively. An agent with a random policy is provided in the code. You can learn how to interact with the environment through the demo and then write your own code. Hint: Take cliff_walk_sarsa.py as an example:• Line 27: more parameters need to be utilized to construct the agent, such as learning rate, reward decay γ, ε value, and ε-decay schema. • Line 47: the agent needs to be provided with some experience for learning.Hint: In agent.py: • You need to implement ε-greedy with ε value decay in the choose_action function. • Functions given in the template need to be completed. You can also add other utility functions as you wish in the agent classes.Hint: You should keep a balance between exploration and exploitation by tuning ε value carefully. In the early stage of the training, exploration should be encouraged to get familiar with the environment. With the advancement of training, exploration may be reduced for the convergence of the policy.1.3 Result Visualization and Analysis Result Visualization: You are required to visualize the training process and the final result according to the following requirements: 1. Plot the episode reward during the training process. 2. Plot the ε value during the training process. 3. Visualize the final paths found by the intelligent agents after training.Result Analysis: You are required to analyze the learning process based on the experiment results according to the following requirements: 1. Analyze the learning process of Sarsa and Q-learning respectively; 2. You may find that there exists a little difference between the paths found by Sarsa and Q-learning. Please describe the difference in the report and analyze the reason in detail.In this part, you will implement a DQN agent to control a lunar lander. You are asked to read and running the given code to train your intelligent lander agent. The performance of the agent may not be satisfactory and you have to tune it to get higher scores.2.1 Game Description Figure 2: The lunar lander environment in this assignment This task is a classic rocket trajectory optimization problem. As shown in Fig. 2, you are required to control the the space-ship and land between the flags smoothly.In this assignment, you are required to train a DQN agent in “LunarLander-v2” gym environment. The definitions of state and action are given as follows: State(Array): The state st is an 8-dimensional vector: the coordinates of the lander in x & y, its linear velocities in x & y, its angle, its angular velocity, and two booleans that represent whether each leg is in contact with the ground or not.Action(Integer): There are four discrete actions available: do nothing, fire left orientation engine, fire main engine, and fire right orientation engine. More details of this gym environment is given in the documents of gym1 . However, information given in this file is sufficient for this assignment.2.2 Read and Analyze the Deep Q-Network Implementation In this section, a complete DQN implementation dqn.py is given for the lunar lander task. You are required to read the code and understand the DQN training process. You are required to write comments in the code to point out the function or your understanding of each part of the code. Please fill in every “““comments: ””” (cf. dqn.py) with your understanding of the code.2.3 Train and Tune the Agent In this section, you are required to train the DQN agent. Please show your training process (such as learning curve of episode return) and the training result (such as the game video of the final model) in the report. The performance of the given code may be not satisfying. You need to tune the agent to get higher scores within 500000 time-steps or make the learning process more efficient.Here are some possible ways to improve the performance: • (Requested) Tuning the hyper-parameters of the agent, especially gamma value, epsilon value, and epsilon decay schema. • Tuning the structure of the Q network. • Utilize multiple continuous frames of the game instead of one frame each time. • Other ideas.2.4 Improve DQN Agent DQN is not a perfect DRL method. There exists some drawbacks of DQN, hence various improvements are proposed. In this section, you are required to choose one drawback, learn the corresponding improvements, and write your understanding in the report.3 Installation You can follow the tutorial in this section to install the environment on Linux or Windows, and we strongly recommend you to use Linux system.3.1 Install Anaconda Open the address https://www.anaconda.com/distribution/ and download the installer of Python 3.x version(3.8 recommended) for your system. 1https://www.gymlibrary.dev/environments/box2d/lunar_lander/3.2 Install Required Environment After installing anaconda, open a Linux terminal and create an environment for Gym: conda create python=3.8 – -name gymThen activate the environment conda activate gym Install gym and some dependencies pip install gym==0.25.2 pip install gym[box2d] pip install stable-baselines3==1.2.0 pip install tensorboard Install pytorch: Please follow the instructions given on the pytorch website2 .4 Code, Demo Video, and Report Code: You can edit the code between “##### START CODING HERE #####” and “##### END CODING HERE #####”. Please DON’T modify other parts of the code. Demo Video: Videos (optional) should be in .mp4 format and a 10MB max for a single file . You can compress/speed up the videos. We recommend reocrding videos utilizing gym wrappers: “env = gym.wrappers.RecordVideo(env, ’./video’)”. More information is given in the gym docs3 . All the videos should be put into a folder called videos. Report: Summarize the process and results of the homework.5 Discussion and Question You are encouraged to discuss your ideas, ask and answer questions about this homework. If you encounter any difficulty with the assignment, try to post your problem on Canvas for help. The classmates and the course staff will try to reply.6 Submission instructions 1. Zip all your program files, experiment result, and report file HW2_report.pdf to a file named as HW2_ID_name.zip. 2. Upload the file to the homework 2 page on the Canvas. 2https://pytorch.org/get-started/locally/ 3https://www.gymlibrary.dev/api/wrappers/
In this homework, you will develop a path-planning framework for a service robot in a room using A* algorithm. The task scenario is shown in Fig. 1. The 2D global map is given. You are required to design and implement the path planning algorithm according to the following task requirements. Figure 1: Path planning of a service robot.1.2 Provided File List The provided files for this homework including: • 1-HW1 Assignment.pdf: The introduction and description of homework 1. • 2-Report Template: A latex template for the report. • 3-map: A 2D map in numpy array format. • 4-Example.py: An example code of path planning for homework 1. • 5-Task 1.py: The code for basic A* algorithm to be completed. • 6-Task 2.py: The code for improved A* algorithm to be completed. • 7-Task 3.py: The code for self-driving planning algorithm to be completed.1.3 Submission File List • Task 1.py: The completed code for A* algorithm. • Task 2.py: The completed code for improved A* algorithm. • Task 3.py: The completed code for self-driving planning algorithm. • HW1 report.pdf: Report for homework 1.In this task, you need to implement the basic A* algorithm. The robot’s starting position, target position, and global map are all known. You can control the robot to move forward, backward, left, and right. To implement the A* algorithm, the 120m×120m world map is discretized into a grid map, where a grid indicates a 1.0m×1.0m block in the world. The coordinate system of the grid map is defined in Fig. 2. The start position of the robot is indicated as (xs, ys), and the goal position is indicated as (xg, yg). Figure 2: Coordinate system of the world.Although the A* algorithm can theoretically plan an optimal (or shortest) path, you may find that the path planned by the A* algorithm in Section 2 may not be good enough, such as frequent turns and close distance to the obstacles. Hence in this section, you will implement an improved A* algorithm to improve the performance of the A* planner. Specifically, you are asked to formulate and incorporate the following factors into the A* algorithm:• Possibility of moving towards upper left, upper right, bottom left, bottom right, shown as Fig. 3(a); • Consider the distance between the robot and the obstacle to avoid possible collisions. For example, the path shown in Fig. 3(b) is too close to the obstacles; • Adding the cost of steering to reduce unnecessary turns in the path as shown in Fig. 3(c). 2 (a) (b) (c) Figure 3: Some factors to consider for improving A* algorithm.Due to the discretization of the map, the paths obtained by the methods in Section 2 and 3 are not smooth. However, smoothness is usually required to guarantee the comfort and energy efficiency of self-driving cars.In this section, you are asked to improve the smoothness of the path. The following are four possible methods to solve this task. The first two trajectory smoothing methods are relatively simple, which are easy to implement and complete this task. The latter two methods are more practical in real applications, which require you to build a car model, thus is relatively more complex. We recommend you to read the relevant papers if you decide to solve this task with the latter two methods.• Polynomial interpolation[1]; • B´ezier curve[2]; • Hybrid A* algorithm[3]; • Lattice planner[4]; Above all, you can choose any one of these methods. Besides, your own ideas are also encouraged.Please provide a detailed description of your solution in the homework report. (a) (b) Figure 4: Smoothness of the path.5 Code and Report Code: You can edit your code between “### START CODE HERE ###” and “### END CODE HERE ###”. Please DO NOT revise other parts of the code. The code block to be completed is described below.### START CODE HERE ### # This code block is optional . You can define your utility function and class in this block if necessary . ### END CODE HERE ### def A_star ( world_map , start_pos , goal_pos ): “”” Given map of the world , start position of the robot and the position of the goal , plan a path from start position to the goal using A* algorithm . Arguments : world_map — A 120 * 120 array indicating map , where 0 indicating traversable and 1 indicating obstacles . start_pos — A 2D vector indicating the start position of the robot . goal_pos — A 2D vector indicating the position of the goal . Return : path — A N*2 array representing the planned path by A* algorithm . “”” def Improved_A_star ( world_map , start_pos , goal_pos ): “”” Given map of the world , start position of the robot and the position of the goal , plan a path from start position to the goal using improved A* algorithm . Arguments : world_map — A 120 * 120 array indicating map , where 0 indicating traversable and 1 indicating obstacles . start_pos — A 2D vector indicating the start position of the robot . goal_pos — A 2D vector indicating the position of the goal . Return : path — A N*2 array representing the planned path by improved A* algorithm . “”” def Self_driving_path_planner ( world_map , start_pos , goal_pos ): “”” Given map of the world , start position of the robot and the position of the goal , plan a path from start position to the goal .Arguments : world_map — A 120 * 120 array indicating map , where 0 indicating traversable and 1 indicating obstacles . start_pos — A 2D vector indicating the start position of the robot . goal_pos — A 2D vector indicating the position of the goal . Return : path — A N*2 array representing the planned path . “””Report: Writing in English. Summarize the process and results of the homework, including but not limited to: • The description, formulation, and implementation of A* and improved A*. • The comparison between A* and improved A* algorithm, such as computational time, safety, optimality, etc.• The description, formulation and implementation of your algorithm to improve the smoothness of the path. • The figures of paths planned in each task are required to be given in the report.6 Discussion and Question You are encouraged to discuss your ideas, and ask and answer questions about homework 1. A new post for this assignment “Homework 1 Discussion” is opened in the Discussion Forum on Canvas. If you encounter any difficulty with the assignment, try to post your problem for help. The classmates and the course staff will try to reply.7 Submission Instructions 1. Zip your python code files Task 1.py, Task 2.py, Task 3.py and the report file HW1 report.pdf to a zip file named as HW1 Name ID.zip for individually. 2. Upload the file to “Homework 1: Search Algorithm” on Canvas.References [1] “Basics of polynomial interpolation,” https://www.baeldung.com/cs/polynomial-interpolation. [2] “B´ezier curve,” https://en.wikipedia.org/wiki/B%C3%A9zier curve. [3] D. Dolgov, S. Thrun, M. Montemerlo, and J. Diebel, “Practical search techniques in path planning for autonomous driving,” Ann Arbor, vol. 1001, no. 48105, pp. 18–80, 2008. [4] M. Werling, J. Ziegler, S. Kammel, and S. Thrun, “Optimal trajectory generation for dynamic street scenarios in a frenet frame,” in 2010 IEEE international conference on robotics and automation. IEEE, 2010, pp. 987–993.
Answer the following questions: 1. Present in detail the characterization of bivariate extreme value distributions with unit Fréchet margins. 2. What are the properties of the dependence function? 3. Write the formula for extreme value copula and give at least three examples of parametric bivariate extreme value copulas. How can one check that a given copula is an extreme value copula?4. Explain in detail how one can construct a bivariate extreme value distribution with arbitrary univariate extreme value margins? 5. Derive the formula for Pickand’s estimator of the dependence function.Getting started with the computational part: If you plan to carry out the assignment on your own computer, you need to download and install R from http://www.r-project.org.If you want to carry out the assignment in the computer room MH:230, you just need to start one of the PCs first. Then choose the latest version of R from the Start menu.In this assignment you need to use evd, SimCop, copula and mgpd packages. It is strongly recommended that you download the corresponding PDF files of the manuals from cran.r-project.org to use as a reference in the assignment. Type library(evd), library(SimCop), library(copula) and library(mgpd) to load the packages to your R-session.These packages are installed in all computers in the computer room MH:230. If you use your own laptop you need to install the packages yourself; see the help page for install.packages for more information.In all exercises below you will plot several datasets. Note that you can use mfrow to collect any number of the plots in one single figure.1. In the package evd nine parametric bivariate extreme value models have been implemented. Study each family and specify which parameter(s) stand for strength of dependence in each family. If the model is asymmetric specify also which parameter stands for asymmetry. Note that the parametrization of some families in evd package (as you can see in the help page for bvevd in the evd manual which you can download from cran.r-project.org) is different from the course literature and lecture notes (see e.g. the logistic model).2. Choose one symmetric and one asymmetric family and generate 200 observations from each model using the package evd. In order to check your answer to the previous part, in each case simulate for a couple of different values of parameters in the model and make a scatter plot of the data. Does the dependence parameter have the expected effect on the dependence of simulated data?For each pair of the simulated sample calculate the empirical values of Pearson’s correlation ρ, Kendall’s τ and Spearman’s ρS.3. In the package SimCop nine parametric bivariate and multivariate copulas have been implemented. Download the reference manual SimCop.pdf and study each family and specify which parameter(s) stand for strength of dependence in each family. If the model is asymmetric specify also which parameter stands for asymmetry.4. Generate 200 observations from the bivariate asymmetric logistic extreme value copula for different combinations of the parameters and plot the results. For each plot comment on the effect of changing the copula parameters on the dependence structure of the model.Check the help documents for GenerateRV.CopApprox and NewBEVAsyLogisticCopula to see examples of how these functions can be used to generate random observations from copulas. You do not need to use Metropolis-Hastings algorithm (MH) argument) in your simulations. See also the help document for plot.CopApprox. Note that by default the plot function for the class CopApprox creates interactive plots but by setting the type=öriginal” you can create the traditional 2-dimensional plots.This part of the assignment is concerned with the annual maximum sea-level in Fremantle and Portpirie in Australia. The datasets ”fremantle.R” and ”portpirie.R” can be downloaded from the following locations • The page Datasets in R under the Pages in the homepage of the course in Canvas, • http://www.maths.lth.se/matstat/kurser/fmsn15masm23/datasetsR.html.Note that these datasets should be loaded to R using source command. 1. Find out for which years the maximum sea level is available in each location.2. Create a data frame which contains data for those years for which maximum sea level is available in both locations. One way of doing this is to use the function merge in R. See the help file of the function for details.3. Create a scatter plot of maximum sea level in both locations. 4. Choose at least two parametric models (one symmetric and one asymmetric) and fit the models to the dataset. In both cases use full maximum likelihood (FML) and inference for margins (IFM) methods to estimates the parameters. Compare your results.5. Choose at least one non-parametric model and fit it to the dataset. Use both parametric and empirical transformation of margins to estimate the dependence function (see the argument epmar to abvnonpar). Plot both estimates and compare them. 6. Suppose X and Y stand for the annual maximum sea level in Fremantle and Portpirie, respectively. Estimate the probabilities • P((X, Y ) > (1.7, 4.2)), • P((X, Y ) > (1.8, 4.4)), and • P((X, Y ) 6< (1.478, 3.850)) based on both parametric and non-parametric fits above. The values in the last probability above are the 30%-quantiles of the sea levels in the dataset. Compare them also with the empirical estimates of the probabilities.Remarks: For parametric models you can use pbvevd and pgev to calculate the distribution function of bivariate and univariate extreme value distributions, respectively. There is no such functions if the dependence function is estimated by a non-parametric method. In this case one needs to use the following relationship as it was shown in ”Exercises 2”: G(x, y) = G∗((1 + γ1 x−µ1 σ1 ) 1 γ1 + ,(1 + γ2 y−µ2 σ2 ) 1 γ2 + ) where G∗(x, y) = e −( 1 x + 1 y )A( x x+y ) . The function abvnonpar can be used to find the value of dependence function in a specific point.7. With the same notation as in previous question estimate P((X, Y ) < (1.95, 4.8)|(X, Y ) 6< (1.478, 3.850)). 8. Plot both parametric and non-parametric estimates for upper quantile curves of bivariate extreme value distributions fitted above for p = 0.75, 0.90, 0.95 (see the help page for the function plot.bvevd).9. The Fremantle dataset was also analyzed in the ”Computer Assignment 3” of the course on univariate extreme values. It was noted that there seems to be a trend in Fremantle sealevel data which might be explained by including ”Year” and ”SOI” (South Oscillation Index) as linear trend in the location parameter. Fit the same parametric models as above but include ”Year” and ”SOI” as covariates for Fremantle sealevel in the model (see nsloc1 and nsloc2 arguments in the help file for fbvevd).Recall also that in order to avoid numerical difficulties in optimization you need to normalize ”Year” to [−1, 1]. Use log-likelihood ratio test to verify if any of these have significant effect on the fit. The functions deviance, logLik and anova can also be used to compare nested models in R.As the package copula provides some extra functions such as goodness of fit tests for fitting different copulas there are some advantages in using this package even for exrtreme value analysis. On the other hand there are only five families of extreme value copulas included in this package (see the help file for evCopula)1. Fit parametric models “huslerReiss” , ”gumbel” and “galambos” implemented in the copula package to the dataset using FML method. Compare your results with the corresponding models in the evd package (“hr”, ”log” and “neglog” models) to make sure that the estimated parameters are the same. What is the difference in parametrization of ”logistic” model in these two packages?2. Use the Inference For Margins (IFM) method based on GEV margins and Canonical Maximul Likelihood (CML) method without specifying the marginal distributions and fit the models to the dataset.3. Use the function gofEVCopula for goodness-of-fit tests for parametric bivariate extremevalue copulas which you have fitted to the dataset above.4. Use the function An.biv and find non-parametric estimators of the dependence function according to Pickands and CFG method. Plot the estimates in a figure.5. Suppose X and Y stand for the annual maximum sea level in Fremantle and Portpirie, respectively. Estimate the probabilities • P((X, Y ) > (1.7, 4.2)), • P((X, Y ) > (1.8, 4.4)), and • P((X, Y ) 6< (1.478, 3.850)) based on both parametric and non-parametric fits above. The conditional values in the last probability above are the 30%-quantiles of the sea levels in the dataset. Compare them also with the empirical estimates of the probabilities. You have done this part in the previous exercise as well using evd package. Compare your results.6. With the same notation as in previous question estimate P((X, Y ) < (1.95, 4.8)|(X, Y ) 6< (1.478, 3.850)).One advantage of using SimCop package is that we can create a copula model based on nonparametric smoothing splines estimate of the dependence function. This can be done by using NonparEstDepFct and SplineFitDepFct functions. Start with reading the help files for these functions. In particular check the examples which demonstrate how the functions can be used.1. Find the Pickand’s estimator of the dependence function for the annual maximum sea level dataset you have analyzed above. Plot the estimates for two cases corresponding to setting convex.hull to TRUE or FALSE. 2. Find the estimate of dependence function using cubic smoothing splines. As input use the non-parametric estimator of dependence function with the argument convex.hull = FALSE. Plot the resulting estimate.3. Create a copula for the smoothing spline fit using the function NewBEVSplineCopula. Find an approximation to the copula by using the function GetApprox and plot the corresponding copula.4. Suppose we want to estimate the same probabilities as in the previous exercises by using simulated observations from the smoothing splines copulas. Generate 1000 observations from the smoothing splines copula and estimate the following probabilities:(a) P((X, Y ) > (1.7, 4.2)), (b) P((X, Y ) > (1.8, 4.4)), (c) P((X, Y ) 6< (1.478, 3.850)), and (d) P((X, Y ) < (1.95, 4.8)|(X, Y ) 6< (1.478, 3.850)). Compare the results with your answers to the corresponding probabilities in exercises 3 and 4.In this exercise the same dataset on sea level will be analyzed by using peaks over threshold method. As discussed in the course there are at least two ways of defining exceedances in higher dimensions. In the first definition a distribution is fitted to the observations {(x, y)|(x, y) > (ux, uy)} where ux and uy are suitable thresholds for each margin. Second definition aims to fit a distribution to {(x, y)|(x, y) 6< (ux, uy)} where (ux, uy) is defined as before.These distributions will be called Type I and Type II bivariate generalized Pareto distributions (BGPD), respectively. Type I BGPD The function fbvpot in package evd fits a Type I model by maximizing the censored likelihood as given in e.g. Section 8.3.1 of Coles (2001) which is attached.1. Calculate the 30%-quantiles of the sea levels in both locations. Use these values as thresholds for the margins in the analysis below. 2. Choose at least two parametric models (one symmetric and one asymmetric) and fit a Type I BGPD to the dataset above the thresholds.3. Plot upper quantile curves of the distributions fitted above for p = 0.75, 0.9, 0.95. (see the help page for the function plot.bvpot). Compare these quantile curves with what you have plotted in part 8 of exercise 2. Do they agree?4. Calculate P((X, Y ) < (1.95, 4.8)|(X, Y ) 6< (1.478, 3.850)) based on your parametric models.Remarks: Note that you need to transform (X, Y ) to (X, e Ye) according to the theory which has been discussed in the course (see also attached pages from Coles book). Read also Details section in the help page for bvevd on page 14 of evd manual to check which parametrization has been used for each model and how they can be transformed to an arbitrary bivariate extreme value distribution with GEV margins.5. Note that if the shape parameter in GPD is negative then the distribution has finite right end point σ/|γ|. It is important to take this into consideration when you transform the margins to unit Frechét distribution. As an example calculate P((X, Y ) < (2, 5)|(X, Y ) 6< (1.478, 3.850)).Type II BGPD Type II bivariate generalized Pareto distributions can be fitted by using the package mgpd. The main function is fbgpd. As an extra help on how to use the functions in this package you can download and use the file ”bgpdExampleRun.R” from the following locations• The page Datasets in R under the Pages in the homepage of the course in Canvas, • http://www.maths.lth.se/matstat/kurser/fmsn15masm23/datasetsR.html.1. Choose at least two parametric models (one symmetric and one asymmetric) and fit a Type II BGPD to the exceedances over the same thresholds as for the Type I BGPD above.Note that the estimation is based on a complicated likelihood function and therefore it is strongly dependent on good start values. One way of finding suitable start values for a model is to use estimates from a simpler model (e.g. Logistic model) as a starting point. Further, if you get an error in R such as “invalid NA contour values”it means that the density for some points has become not available”. In this case you should try to change x and y vectors in the bgpdExampleRun.R.2. Calculate P((X, Y ) < (1.95, 4.8)|(X, Y ) 6< (1.478, 3.850)). Compare the result with your answer to question 4d in exercise 3 and question 4 in type I BGPD.3. Plot estimates of prediction regions for p = 0.75, 0.9, 0.95 based on parametric models you have fitted to the dataset. Compare your results with your answer to the same question for the Type I BGPD above and comment on any differences you see.Finishing Off: When you’ve finished, close down R by typing q(). Choose ‘Save’ when prompted as to whether you want to retain your workspace. 154 8. Multivariate Extremes 0 ‘” “! g ] “! E ” ~ “‘: “! 5 10 50 100 500 1000 Retum PeriOd (Years) FIGURE 8.5. Comparison of return level plot for Z = min{M.,, (My- 2.5)} in logistic model analysis of Fremantle and Port Pirie annual maximum sea-level series with a= 0, 0.25, 0.5, 0.75 and 1, respectively. Lowest curve corresponds to a= 1; highest to a= 0.excess model and point process model can be obtained. In this section we give a brief description of both techniques. 8.3.1 Bivariate Threshold Excess Model In Chapter 4 we derived as a class of approximations to the tail of an arbitrary distribution function F the family G(x) = 1 – ( { 1 + e(x; u)} -1/e, X > u. (8.18)This means there are parameters (,a and e such that, for a large enough threshold u, F(x) ~ G(x) on x > u. Our aim now is to obtain a bivariate version of (8.18), i.e. a family with which to approximate an arbitrary joint distribution F(x, y) on regions of the form x > ux, y > uy, for large enough Ux and Uy.Suppose (x1, Yl), … , (xn, Yn) are independent realizations of a random variable (X, Y) with joint distribution function F. For suitable thresholds Ux and uy, the marginal distributions ofF each have an approximation of the form (8.18), with respective parameter sets ((x,ax,ex) and ((y,ay,ey)·8.3 Alternative Representations 155 The transformations (8.19) and (8.20) induce a variable (X, Y) whose distribution function F has margins that are approximately standard Frechet for X> Uz andY> uy. By (8.5), for large n, _ {- }1/n F(x, y) = Fn(x, y) ~ [exp { -V(xfn,yfn)}]11n = exp{-V(x,y)}, because of the homogeneity property of V. Finally, since F(x, y) = F(x, y), it follows that F(x,y) ~ G(x,y) = exp{-V(x,y)}, x > ux,Y > uy, (8.21) with x andy defined in terms of x andy by (8.19) and (8.20). This assumes that the thresholds Ux and uy are large enough to justify the limit (8.5) as an approximation. We discuss this point further in Section 8.4.Inference for this model is complicated by the fact that a bivariate pair may exceed a specified threshold in just one of its components. Let Ro,o = (-oo,ux) x (-oo,uy),Rt,o = [ux,oo) x (-oo,uy), Ro,t = (-oo,ux) x [uy,oo),Rt,l = [ux,oo) x [uy,oo), so that, for example, a point (x, y) E R1,o if the x-component exceeds the threshold ux, but the y-component is below uy. For points in R1,1, model (8.21) applies, and the density ofF gives the appropriate likelihood component. On the other regions, since F is not applicable, it is necessary to censor the likelihood component. For example, suppose that (x, y) E R1,o.Then since x > Uz, but y < uy, there is information in the data concerning the marginal x-component, but not the y-component. Hence, the likelihood contribution for such a point is Pr{X = x, Y $ uy} = !’. aFI uX (x,uy} as this is the only information in the datum concerning F. Applying similar considerations in the other regions, we obtain the likelihood function n L(8; (xt,Yt), … , (xn,Yn)) =IT 1/J(B; (xi,yi)), (8.22) i=l 156 8. Multivariate Extremes where (} denotes the parameters of F and ‘ljJ(O; (x,y)) = if (x,y) E R1,1, if (x, y) E R1,o, if (x,y) E Ro,1, if (x, y) E Ro,o, with each term being derived from the joint tail approximation (8.21).Maximizing the log-likelihood leads to estimates and sta~dard errors for the parameters of F in the usual way. As with the componentwise block maxima model, the inference can be simplified by carrying out the marginal estimation, followed by transformations (8.19) and (8.20), as a preliminary step. In this case, likelihood (8.22) is a function only of the dependence parameters contained in the model for V.An alternative method, if there is a natural structure variable Z = ¢(X, Y), is to apply univariate threshold techniques to the series Zi = ¢(xi,Yi)· This approach now makes more sense, since the Zi are functions of concurrent events. In terms of statistical efficiency, however, there are still good reasons to prefer the multivariate model.8.3.2 Point Process Model The point process characterization, summarized by the following theorem, includes an interpretation of the function H in (8.6). Theorem 8.2 Let (xl,Yl),(x2,Y2) … be a sequence of independent bivariate observations from a distribution with standard Frechet margins that satisfies the convergence for componentwise maxima Pr{M;,n $ x,M;,n $ y}-+ G(x,y).Let { N n} be a sequence of point processes defined by Then, Nn = {(n- 1xl,n-1 y1), … ,(n-1xn,n-1yn)}. d Nn –t N (8.23) on regions bounded from the origin (0, 0), where N is a non-homogeneous Poisson process on (O,oo) x (O,oo). Moreover, letting r=x+y the intensity function of N is X and w=–, x+y ‘( ) _ 2dH(w) “‘r,w – 2 , r where H is related to G through (8.5) and (8.6). (8.24) (8.25) 0
Answer the following questions: 1. What are the properties of Archimedean copulas and their generators? 2. Write the bivariate ditribution functions for Frank, Clayton, Gumbel and AMH copulas.3. Find Laplace transform of a random variable which is distribute as Gamma(a,b) (the density is given in (71) in collection of formulas). Set shape parameter a = 1/θ and rate parameter b = 1. Explain how this result is related to Archimedean copulas and nd the corresponding copula in the bivariate case.4. Suppose X is a d-dimensional random vector. Explain how multivariate normal and multivariate t distributions are de ned.5. Explain how the dependency measures Pearson’s correlation ρ, Kendall’s τ and Spearman’s ρS are de ned. What is the relationship between Pearson’s correlation and two other dependency measures?Getting started with the computational part: If you plan to carry out the assignment on your own computer, you need to download and install R from http://www.r-project.org.If you want to carry out the assignment in the computer room MH:230, you just need to start one of the PCs rst. Then choose the latest version of R from the Start menu.In this assignment you need to use package copula. It is strongly recommended that you download the corresponding PDF le of the manual (copula.pdf) from cran.r-project.org to use as a reference in the assignment. Type library(copula) to load the package to your R-session. The package is also installed in all computers in the computer room MH:230. If you use your own laptop you need to install package yourself; see the help page for install.packages for more information.In exercises 2, 4 and 5 below you will generate observations from dierent distributions. As you will be using the simulated values in other parts of this assignment you should save each simulated dataset in an object for later use.In all the exercises below you will plot several datasets. Note that you can use mfrow to collect any number of the plots in one single gure. In each part you need to estimate dierent measures of dependence and compare them by their theoretical values. Note that for elliptical copulas τ = 2 π arcsin(ρ) and ρS = 6 π arcsin(ρ/2). Moreover, for Archimedean copulas the relationship between the parameter of copula and Kendall’s τ can be found in the attached table. Finally note that Spearman’s ρS can be calculated as the correlation between the ranks of the observations.1. Generate 500 observations from a 3-dimensional normal copula with an exchangeable covariance matrix with variance 1 and correlation 0.4. Plot the scatter plot of the simulated observations.For each pair of the simulated sample calculate the empirical values of Pearson’s correlation ρ, Kendall’s τ and Spearman’s ρS. Do the estimates agree with the theoretical values? In addition, calculate the ranks of the observations and verify that the Spearman’s ρS can be calculated as the correlation between the ranks of the observations.2. Generate 500 observations from a bivariate t copula with 8 degrees of freedom, an exchangeable characteristic matrix with diagonal 1 and o-diagonal values θ = −0.4, 0, 0.4 (use one value of θ in each simulation). Plot the scatter plot for each dataset and comment on dependence between observations and parameter θ.For the simulated sample calculate the empirical values of Pearson’s correlation ρ, Kendall’s τ and Spearman’s ρS. Do the estimates agree with the theoretical values?3. Generate 500 observations from a 3-dimensional Frank copula with parameter 3. For each pair of the simulated sample calculate the empirical values of Pearson’s correlation ρ, Kendall’s τ and Spearman’s ρS. Do the estimates of Kendall’s τ agree with its theoretical value?4. Use your results in Exercise 1 part 3 above and write a function which generates random observations from the corresponding copula. The function should be able to generate any number of observations in an arbitrary dimension for a given θ. In addition, it should not contain any for(), while() or similar commands for one by one iteration. Include your function in your report. Generate 500 observations from this copula in 3-dimensional case with parameters θ = 0.5, 1, 5, 50.5. Suppose X is random variable uniformly distributed in the interval [−1, 1]. Let Y = T(X) = arctanh(X) and Z = −T(X) = − arctanh(X). Is function T(x) increasing? Why? Generate 1000 observations from X and plot the corresponding functions for Y and Z. Calculate Spearman’s ρ, Kendall’s τ and Pearson’s correlation for the simulated pairs (xi , yi) and (xi , zi). Compare the results and comment on whether all three dependence measures produce reasonable results.For two simulated dataset from bivariate t in part 2 of Exercise 2 above plot the simulated values and the corresponding pdf and cdf of each copula. Comment on the plots. Note that you can use mfrow to collect all of the plots in one single gure.In this exercise we will compare four dierent copulas. Simulate 2000 observations from four bivariate copulas as the following: the Gaussian copula with parameter ρ = 0.7; the Gumbel copula with parameter θ = 2; the Clayton copula with parameter θ = 2.2; the t copula with parameters df = 4 and ρ = 0.71. You will need to use the simulated samples in the second part of this exercise so make sure you to save all the samples in R. Use par(mfrow=c(2,2)) and plot all the simulated samples in one single plot. Comment on any dierences you see between copulas.Use quantile transformation and transform all the simulated samples to bivariate distributions with standard normal margins. Make a similar plot as above for the simulated bivariate observations. Note that the parameters of the copulas have been chosen so that all of these distributions have a linear correlation that is roughly 70%. Do you see any dierences in the dependence structure of the simulated observations despite the fact that all the simulated samples have the same margins with the same linear correlations? Comment on the results.In each of the following parts calculate both the linear and Spearman’s correlation for each dataset. Theoretically rank correlation should not be aected by change of the margins. At least in one case below calculate both linear and rank correlation for the copula and corresponding bivariate distribution with arbitrary margins and show that the rank correlation does not depend on the marginal distribution.1. Generate 500 observations from a 2-dimensional distribution with normal copula (parameter 0.75) and N(0, 2) and exp(2) margins. 2. Generate 500 observations from a 2-dimensional distribution with Gumbel copula (parameter 2) and exp(4) and exp(2) margins.For each simulated dataset above plot the simulated values. Plot also contour plots of pdf of the corresponding distributions. Note that you can use mfrow to collect all of the plots in one single gure.A collection of measurements were taken from a representative sample of new cars in 1993. Because some of the variables are measured at an ordinal scale, Spearman’s ρ is more appropriate than Correlation for measuring monotonic association.The dataset cardata.txt can be downloaded from the following locations The page Datasets in R under the Pages in the homepage of the course in Canvas, http://www.maths.lth.se/matstat/kurser/fmsn15masm23/datasetsR.html. 1. Read the data to R (use read.csv() function) and plot a scatterplot matrix of the data by uding pairs function in R.2. calculate Spearman’s ρ corresponding to the scatterplot matrix. 3. Does your results suggest that vehicles with higher horsepower are more costly? higher fuel economy (MPGcity) meant lower prices in 1993?4. Can you suggest a formal test to answer the same quesions above? Hint: You can use help.search or RSiteSearch to search the help system for key words or phrases.Consider a portfolio of 2 risks X1 and X2. Let the risks represent potential losses in dependent lines of business for an insurance company and let u1 and u2 be some thresholds. Suppose the insurer seeks reinsurance for the situation that both losses exceed their thresholds. In this case these losses will be paid in full by the re-insurer. In the following we will analyze the problem from the re-insurer’s point of view so their loss is when both thresholds are exceeded.Based on historical data we can assume that Xi ∼ Lognormal(0, 1), i = 1, 2. Further we assume that τ (X1, X2) = 0.5 and we take both thresholds ui , i = 1, 2 equal to 0.95-quantile of each marginal distribution. Answer the following questions based on each of the following assumptions for the joint distribution: Gaussian copula t-copula with 2 degrees of freedom Gumbel copula.1. Calculate probability that both losses exceed their thresholds. Computer Assignment 2, FMSN65/MASM33 5 2. Calculate the ratio of the payout probabilities for the reinsurance company for each pair of copulas.3. How do the ratios change if we increase the threshold to the 0.99-quantile of each margin? 4. Use simulation to estimate expected value of loss for the reinsurance company corresponding to the both choices of thresholds above. 5. Compare also the upper tail dependence for the copulas and comment on the practical consequences of your results.In this exercise we will use copulas to analyze an insurance dataset on indemnity claims. Figure 1 shows observations on 1500 liability claims for an insurance company. The indemnity payment (Loss) and the allocated loss adjustment expense (ALAE) are recorded in USD for each claim.Here, ALAE are types of insurance company expenses that are speci cally attributable to the settlement of individual claims such as lawyers’ fees and claims investigation expenses. The dataset insuranceData.txt can be downloaded from the following locations The page Datasets in R under the Pages in the homepage of the course in Canvas, http://www.maths.lth.se/matstat/kurser/fmsn15masm23/datasetsR.html.Loss ALAE 10 100 1000 10000 1e+05 1e+06 1e+07 10 100 1000 10000 1e+05 1e+06 1e−04 0.001 0.01 0.1 1 10 100 1e−04 0.001 0.01 0.1 1 10 Figur 1: Scatterplot of ALAE verses Loss: The bottom and left axes represent the original data (log-scale). In the analysis we scale the data so that one unit corresponds to 100 000 USD. The corresponding rescaled axes are in the top and right side of the gure.1. Read the data to R (use read.table(“insuranceData.txt”,header=T) function) and plot a gure similar to Figure 1. 6 Computer Assignment 2, FMSN65/MASM33 2. Calculate the correlation between Loss and ALAE.3. Fit a bivariate distribution to the dataset by using copulas. For general optimization you can use the function optim() in R. Note that you need to pass the dataset as a matrix to optim() otherwise it will not produce any results (see the function as.matrix())). In addition, the package fitdistrplus can be used to estimate parameters for several univariate distributions.Note that you need to provide the details of your calculations here. Speci cally, you have to present the details of the univariate distributions you have tried for each margin and justify your nal choice of the marginal distributions by providing suitable checks or goodness of ts plots. The same applies to the choice of copula. You should also use dierent estimation methods (FML, IFM and CML) in tting the models.Suppose a reinsurer considers selling reinsurance to this company. As a simple model assume they agree on a policy with limit L for the reinsurer and retention R for the insurance company.To formulate this policy in mathematical terms let X1 and X2 denote the Loss and ALAE, respectively. Assuming a proportional sharing of expenses, the above policy means that the reinsurer’s payment, RP(X1, X2), can be expressed as the following: RP(X1, X2) = 0 if X1 < R X1 − R + X1−R X1 X2 if R ≤ X1 < L L − R + L−R L X2 if X1 ≥ LSuppose the reinsurer wants to estimate E[RP(X1, X2)] using simulations. 1. Use the tted distribution above and estimate E[RP(X1, X2)] for all combinations of L = 10 000, 500 000, 1 000 000 and R/L = 0, 0.25, 0.75, 0.95.2. Suppose one makes an unrealistic assumption that Loss and ALAE are independent. Calculate the corresponding values of E[RP(X1, X2)] for the same combinations of L and R as in the previous part. In which cases the reinsurance premium is under- or overvalued?Finishing O: When you’ve nished, close down R by typing q(). Choose `Save’ when prompted as to whether you want to retain your workspace. Tail Dependence 3-30 Copula τ λU λL Gauss 2 π arcsinρ 0 for ρ < 1 0 for ρ < 1 −1 ≤ τ ≤ 1 1 for ρ = 1 1 for ρ = 1 tν 2 π arcsinρ 2tν+1 q(ν+1)(1−ρ) 1+ρ λU −1 ≤ τ ≤ 1 −1 ≤ ρS ≤ 1 Gumbel 1 − 1 θ 2 − 2 1 θ 0 0 ≤ τ ≤ 1 Clayton θ θ+2 0 2− 1 θ 0 ≤ τ ≤ 1 Frank 1 − 4 θ {1 − D1(θ)} 0 0 Dk (x) = k x k Rx 0 t k e t−1 dt −1 ≤ τ ≤ 1 Table 5: Kendall’s τ and TDCs for various selected copulae. MSR
In this assignment, you will work with your group to implement Q-learning for the multi-arm bandit and frozen lake environments. You may discuss the homework with other groups, but do not take any written record from these discussions. Also, do not copy any source code from the Web. Your submission must be your own.1. Coding (4.0 points): Your task is to implement two reinforcement learning algorithms: Multi-armed Bandits (in src/multi_armed_bandits.py) Q-Learning (in src/q_learning.py)Note that while these reinforcement learning methods inherently depend on randomization, we provide a src/random.py package that will randomize things in the same way for all students.Please use src.random anywhere that you might have otherwise used np.random. Your goal is to pass the test suite (contained in tests/). You can test your code by running pytest tests/test_bandit.py and pytest tests/test_q_learning.py. Once the tests are passed, you will use your code to answer FRQ 2 and 3.2. Bandits vs. Q-Learning (2.0 points): a. Run python -m q2.py; it will create three plots: 2a_SlotMachines_Comparison.png, 2a_FrozenLake_Comparison.png, and 2a_SlipperyFrozenLake_Comparison.png. Please read about the FrozenLake environment (https://gymnasium.farama.org/environments/toy_text/frozen_lake/) . Each plot will show a comparison of your MultiArmedBandit and QLearning models on the named environment (e.g., SlotMachines). Include those plots here. For each plot, provide a onesentence description of the most notable trend. Pay attention to the scale on the y-axis.b. In which of the above plots does Q-Learning appear to receive higher rewards on average than MultiArmedBandit? Provide an explanation for why that happens, based on your understanding of Q-Learning.c. Following b.: in the environment(s) where MultiArmedBandit was the worse model, is there any way you could change your choice of hyperparameters so that MultiArmedBandit would perform as well as Q-Learning? Why or why not?d. In which of the above plots does MultiArmedBandit appear to receive higher rewards on average than Q-Learning? Provide an explanation for why that happens, based on your understanding of MultiArmedBandit.e. Following d.: in the environment(s) where Q-Learning was the worse model, is there any way you could change your choice of hyperparameters so that QLearning would perform as well as MultiArmedBandit? Why or why not?3. Exploration vs. Exploitation (2.0 points): a. Look at the code in q3.py and run python -m q3.py and include the plot it creates (free_response/3a_g0.9_a0.2.png) as your answer to this part. In your own words, describe what this code is doing.b. Using the above plot, describe what you notice. What seems to be the “best” value of epsilon? What explains this result?c. The above plot trains agents for 50,000 timesteps each. Suppose we instead trained them for 500,000 or 5,000,000 timesteps. How would you expect the trends to change or remain the same for each of the three values of epsilon? Give a one-sentence explanation for each value.d. When people use reinforcement learning in practice, it can be difficult to choose epsilon and other hyperparameters. Instead of trying three options like we did above, suppose we tried 30 or 300 different choices. What might be the danger of choosing epsilon this way if we wanted to use our agent in a new domain?4. Tic-Tac-Toe (2.0 points): Suppose we want to train a Reinforcement Learning agent to play the game of Tic-Tac-Toe (see https://en.wikipedia.org/wiki/Tic-tac-toe), and need to construct an environment with states and actions. Assume our agent will simply choose actions based on the current state of the game, rather than trying to guess what the opponent will do next.a. What should be the states and actions within the Tic-Tac-Toe Reinforcement Learning environment? Don’t try to list them all, just describe how the rules of the game define what states and actions are possible. How does the current state of the game affect the actions you can take?b. Design a reward function for teaching a Reinforcement Learning agent to play optimally in the Tic-Tac-Toe environment. Your reward function should specify a reward value for each of the 3 possible ways that a game can end (win, loss, or draw) as well as a single reward value for actions that do not result in the end of the game (e.g., your starting move). Explain your choices.c. Suppose you were playing a more complicated game with a larger board, and you want the agent to learn to win as fast as possible. How might you change your reward function to encourage speed?5. Fair ML in the Real World (3.0 points): Read Joy Buolamwini and Timnit Gebru, 2018. “Gender shades: Intersectional accuracy disparities in commercial gender classification.” Conference on fairness, accountability and transparency, then use it to help answer the following questions (see https://proceedings.mlr.press/v81/buolamwini18a/buolamwini18a.pdf).a. Buolamwini and Gebru use PPV and FPR as metrics to measure fairness. Find the definition of these in the paper, then look up the corresponding definition for NPV and FNR (these appear in the slides). Assuming you were applying for a loan and you know a ML classifier is deciding whether to grant it to you: would you rather have that decision made by a system with a high FPR or a high FNR? Why? Provide a detailed justification.b. Assuming you were applying for a loan and you know a ML classifier is deciding whether to grant it to you: would you rather have that decision made by a system with a high PPV or a high NPV? Why? Provide a detailed justification.c. What recommendations do Buolamwini and Gebru make regarding accountability and transparency of ML systems? How does this relate to specific metrics such as PPV or FPR?d. What is intersectional about the analysis conducted by the authors? What does that analysis show?e. In Section 4.7, the authors say that their “findings … do not appear to be confounded by the quality of sensor readings.” What do they mean by “confounded” in this context? Why is it important to the thesis of this paper to check whether their findings are confounded?Submission Instructions Turn in your homework as a single zip file, in Canvas. Specifically: 1. Create a single pdf file hw4.pdf with the answers to the questions above and summaries of your results. 2. Create a single ZIP file containing: o hw4.pdf o All of your .py code files 3. Turn the zip file in under Homework #4 in Canvas. Good luck, and have fun!
In this assignment, you will work with your project group to implement decision trees. You may discuss the homework with other groups, but do not take any written record from the discussions. Also, do not copy any source code from the Web or use code generated by AI.The algorithm you should implement is the same as that given in the decision tree lecture slides (slide 4-5, the “ID3” algorithm). We have written code to read in the data for you (parse.py). It represents each example as a dictionary, with attributes stored as key:value pairs. The target output is stored as an attribute with the key “Class”.Guidelines You should use Information Gain for choosing which attribute to split on. You must handle missing attributes, but exactly how is up to you. You must implement some kind of pruning, but exactly how is up to you. You must adhere to the signature in the ID3.py file. In particular, you must implement the four given methods as described in that file. You can and should define additional methods in ID3.py, and additional fields in the Node class. You do not need to handle numeric attributes, but your code should work for categorical attributes with an arbitrary number of attribute values. Do not import any modules from outside the Python standard library. If you need other modules to produce e.g. graphs, write that code in a separate source file. (4.0 points) Complete the decision tree code. You should use Python 3.6 or later. Implement the four methods in ID3.py, adding new methods as necessary. You will also need to change node.py. We have included a few tests in unit_tests.py that you can run individually, to check your methods. Further, we have also included a file mini_auto_grader.py that gives you an idea of the kinds of tests we will run to grade your methods.NOTE: that depending on how you implement pruning, it’s possible (albeit unlikely) that the pruning test will not pass even if your implementation is acceptable. We will test you code on an unseen dataset with random training, validation and test sets. The tennis.data dataset is also provided to help you debug your code on a much smaller and simpler dataset. Create a PDF document with the answers to the following questions (try to keep you responses to a few sentences or a single paragraph for each question): 1. (0.25 points) Did you alter the Node data structure? If so, how and why? 2. (0.25 points) How did you handle missing attributes, and why did you choose this strategy?3. (0.5 points) How did you perform pruning, and why did you choose this strategy? 4. (2.0 points) Now you will try your learner on the house_votes_84.data, and plot learning curves. Specifically, you should experiment under two settings: with pruning, and without pruning. Use training set sizes ranging between 10 and 300 examples. For each training size you choose, perform 100 random runs, for each run testing on all examples not used for training (see testPruningOnHouseData from unit_tests.py for one example of this). Plot the average accuracy of the 100 runs as one point on a learning curve (x-axis = number of training examples, y-axis = accuracy on test data).Connect the points to show one line representing accuracy with pruning, the other without. Include your plot in your pdf, and answer two questions: a. What is the general trend of both lines as training set size increases, and why does this make sense?b. How does the advantage of pruning change as the data set size increases? Does this make sense, and why or why not?Note: depending on your particular approach, pruning may not improve accuracy consistently or may decrease it (especially for small data set sizes). You can still receive full credit for this as long as your approach is reasonable and correctly implemented.5. (1.0 points) Use your ID3 code to learn a decision tree on cars_train.data. Report accuracy on the cars_train.data, cars_valid.data and cars_test.data datasets. If you accuracy on cars_train.data is less than 100%, explain how this can happen. Prune the decision tree learned on cars_train.data using cars_valid.data. Run your pruned decision tree on cars_test.data, and explain the resulting accuracy on all three datasets.6. (2.0 points) Use your ID3 code to construct a Random Forest classifier using the candy.data dataset. You can construct any number of random trees using methods of your choosing. Justify your design choices and compare results to a single decision tree constructed using the ID3 algorithm.Suggestion: You may find it helpful work with Weka (https://www.cs.waikato.ac.nz/ml/weka). To work with ID3 in Weka, you may need to install the simpleEducationalLearningSchemes. A large number of Weka tutorials exist on the Web.Submission Instructions Turn in your homework as a single zip file, in Canvas. Specifically: 1. Create a single pdf file ps1.pdf with the answers to the questions above, and your graphs. 2. Create a single ZIP file containing: o ps1.pdf o All of your .py code files3. Turn the zip file in under Homework #1 in Canvas. Note: You may also complete the assignment and include all responses in a single Jupyter Notebook in a single ZIP file. Good luck, and have fun!
1. [4.5 points] In this excerise you will map out how to build a vision system. You want to build a robot to take the place of the ‘ball boy/girl” during a tennis match. Your robot is modelled after WALL-E (link).Write psudeo-code calling algorithms covered in class to build the robot’s visual system and fulfill its destiny. Your robot already knows the following commands to aid you: faceDirection(X,Y,Z); moveToLocation(X,Y,Z); grabObjectAtLocation(X,Y,Z); victoryDanceAtLocation(X,Y,Z). It also comes with camera calibration matrices K, [R|t].Check out a demo Video of a simpler model; note your robot should work during a tennis match, instead of these controlled conditions, but is also equipped with stereo cameras!(a) [1 point] Brainstorm about the robot’s world, what it will encounter, what data it will need for training, what challenges it will face, etc. Create a brainstorming diagram to include in your PDF.(b) [1 point] Create a flow chart linking together the main processing pipeline the robot will use; reference algorithms from the course (e.g. cannyEdgeDetection) and the actions taken, e.g. moveToLocation(X,Y,Z).(c) [2.5 points] Write psuedo-code to implement your robot, run algorithms from the course by name, e.g. cannyEdgeDetection and include relevant arguments. You will be marked on completeness and ingenuity (i.e. how we think your robot will work, the conditions it can handle, etc.).2. [8.5 points] In this exercise you are given stereo pairs of images from the autonomous driving dataset KITTI (http://www.cvlibs.net/datasets/kitti/index.php). The images have been recorded with a car driving on the road. Your goal is to create a simple system that analyzes the road ahead of the driving car and describes the scene to the driver via text. Include your code to your solution document.• In this assignment the stereo results have been provided with the following stereo code: http://ttic.uchicago.edu/ dmcallester/SPS/spsstereo.zip. For those interested in actually running the code yourselves, please grab it from this link.Since the code doesn’t easily install on CDF, you are given a few fixed files in cdf compile.zip. Once you’ve download the stereo code, please unzip cdf compile.zip inside the stereo code folder. Then follow the readme instructions provided by the code.• You are provided code for the object detector called Deformable Part Model in the folder code/dpm (the original code can be found here: http://www.cs.berkeley.edu/ rbg/latent/voc-release5.tgz). You will need to compile the code, by running compile in Matlab inside the code/dpm directory. Make sure you add all the subdirectories to your Matlab path. If you encounter errors during compilation, then commenting out the lines: fv compile(opt, verb); and cascade compile(opt, verb); in compile.m should make it to work.Note, DPM is a powerful object detector and could be trained for other tasks (i.e. projects).Note to Python users: DPM has been one of the most used detectors in Computer Vision. Unfortunately, the authors released the code in Matlab. But you can use their code to compute detections in Matlab, and then store them in a Pythonfriendly format, and do the rest of the assignment in Python.• In the assignment’s code folder you will find a few useful functions. In order to use them, please first open globals.m and correctly set the paths of your data. • You are also given a function called getData (Matlab) which will help you to easily browse all the provided data. Look at the function to see all the options it has. It provides you with loading as well as some plotting functionality.• In your data directory you are given a folder called train and test. You will need to compute all your results only for the test folder. Using train will be optional. You only need to process the first three images written in the data/test/test.txt file. The easiest to get the list of train/test images is via getData: data = getData([], “test”, “list”); ids = data.ids(1:3);.• Matlab: Before running any code, position yourself in the code folder and type addpath(genpath(pwd)). This will add all the paths to the code you need.(a) [1 points] The folder results under test contains stereo results from the algorithm called spsstereo. For each image there is a file with extension LEFT DISPARITY.png that contains the estimated disparity. For each image compute depth. In particular, compute depth which is a n × m matrix, where n is the height and m the width of the original image. The value depth(i, j) should be the depth of the pixel (i, j). In your solution document, include a visualization of the depth matrices. In order to compute depth you’ll need the camera parameters: Matlab users: You’ll find the camera parameters via the getData function (pass the “calib” option).Python users: In the test/calib folder there are text files with extension ALL CALIB.txt which contain all camera parameters.Note that the baseline is given in meters.(b) [2 points] For all test images run the DPM detectors for car and person and cyclist. How to run a detector on one image for car is shown in a function demo car. Store the detections (variable DS) in the results folder. Storing is important as you will need them later and it takes time to compute. Once you compute everything, I suggest that you add a subroutine in getData that loads the detections for each image. Make sure you store also to which class (car, person or cyclist) each detection belongs to.The variable DS contains a detection in each row of the matrix. Each row represents a rectangle (called a bounding box) around what the detector thinks is an object. The bounding box is represented with two corner points, the top left corner (xlef t, ytop) and the bottom right corner (xright, yright). Each row of DS has the following information: [xlef t, ytop, xright, ybottom, ID, score]. Here score is the strength of the detection, i.e., it reflects how much a detector believes there is an object in that location. The higher the better. The variable ID reflects the viewpoint of the detection and you can ignore it for this assignment.(c) [1 point]In your solution document, include a visualization of the first three images with all the car, person and cyclist detections. Mark the car detections with red, person with blue and cyclist with cyan rectangles. Inside each rectangle (preferably the top left corner) also write the label, be it a car, person or cyclist. (Matlab: Help yourself with the function text.)(d) [1 point] Compute the 3D location (centre of mass) of each detected object. How will you do that? Store your results as you’ll need them later. Hint: Use depth information inside each detection’s bounding box.(e) [2 points] We will now perform a simple segmentation of each detected object. By segmentation, we mean trying to find all pixels inside each detection’s bounding box that belong to the object. You can do this easily as follows: for each detection you have computed the 3D location of the object. Find all pixels inside each bounding box that are at most 3 meters away from the computed 3D location.Create a segmentation image. This image (a matrix) has the same number of columns and rows as the original RGB image. Initialize the matrix with all zeros.Then for i-th row in ds (which is the i-th detection), assign a value i to all pixels that you found to belong to detection i. In your solution document, include a visualization of the segmentation matrix (for the first three test images).(f) [1.5 points] Create a textual description of the scene. Try to make it as informative as possible. Convey more important facts before the less important ones.Think what you, as a driver, would like to know first. Think of the camera centre as the driver. In your description, generate at least a sentence about how many cars, how many people and cyclists are in the scene. Generate also a sentence that tells the driver which object is the closest to him and where it is. For example, let’s say you have an object with location (X, Y, Z) in 3D and label = car and you want to generate a sentence about where it is.You could do something like: d = norm([X, Y, Z]); % this is the distance of object to driver IF X ≥ 0, txt = “to your right”; else txt = “to your left”; end; fprintf(“There is a %s %0.1f meters %s ”, label, X, txt); fprintf(“It is %0.1 meters away from you ”, d); Even if you didn’t solve the tasks in the rest of Q2, you can still get points for this exercise by writing some pseudo code like the one above. Clearly explain what the piece of code is supposed to do.3. Extra: [1.5 points] total. (this is an optional exercise) Show (0.75 points) and explain (0.75 points) some interesting initial findings and/or intermediate results from your component of your final project. You can use synthetic data, or manual inputs to replace missing modules from your project-mates.Note: If your project is the autonomous driving project, you must go beyond any code/activity performed for this assignment to be elgibile for the extra credit.
1. [2 points] A robber left his/her shoe behind. Police took a picture of it, see shoe.jpg. Estimate the width and length (in centimeters) of the shoe from the picture as accurately as possible! Show your work.2. For this question you do not need to write code, you do need to write the equations and show your work (i.e. how you derived them). If you need to calculate the location of any points or lines in the image plane, state those as givens; but use the minimal set. You can assume that the ground plane is orthogonal to the image plane. Hint: Draw the scenes on paper from the side.(a) [2 points] Examine image tracks.jpg. Assume you are given K, R, t. Are you able to estimate the distance between adjacent railway ties in world co-ordinates? If so, write the necessary equations as a function of the pixel locations, camera intrinsic and/or extrinsic matrices.(b) [2 points] Examine image man.jpg. The camera centre is 95 centimetres off the ground. You can assume the ground is planar. Are you able to estimate the height of the man in centimetres without K? If so, derive and write the necessary equations as a function of the pixel locations in the image, and estimate the height.3. You’ve joined a CSI unit, our suspect mugShot.jpg has been implicated in a grisly crime. Raiding his apartment we recovered a photograph of him sitting with his accomplice, but he knew we were on to him and shredded the photograph! We need you to implement RANSAC and re-assemble it. You may also use a downloaded implementation of SIFT and any code you wrote for Assignment 2. Python users check opencv-contrib.(a) [2 points] Create a controlled test case between two affine transformed images, and develop your RANSAC algorithm to calculate the affine transformation via least-squares. Visualize the best transformation for the best matching image just like you did for Assignment 2, exercise 2(d). You can use any tutorial code to help create your test-case image, or draw one, or take some pictures.(b) [2 points] Shredded contains the shredded picture pieces. Using the mugShot, try reassembling the image in random permutations and keep the one that best fits your model. Rank your models by the mean residual SSD. You could alternatively try a greedy or dynamic programming approach. Show the re-constructed image. Display your final, best reassembled image.Hint: For speed use down-sampling.4. For this question you will build your own panorama stitching program. You can use your RANSAC code from above, in conjunction with your matching code from assignment 2 to establish correspondence. However, you now need to estimate a homography via least squares instead of an affine transformation (the math is in Lecture 9).You may also use SIFT and any code you wrote for Assignment 2. If you were unable to get RANSAC working, you can manually set your valid correspondences (or just use the top k), but state it clearly. You can look at the example here to see the workflow, but you must write your own code to compute the homographies and blend the panorama.Do not use matchfeatures.m, estimateGeometricTransform.m, step.m. Note, matlab users imwarp uses xA for its transform, and we’ve written things for Ax (a) [1 point] Compute the homography between pairs of adjacent images via your matches. Write your own solution via eigendecomposition; don’t use maketform.m or equivalents. Visualize your result by transforming your keypoints from one image onto the next, and displaying them as a different colour. Use the image set in hotel.(b) [1 point] Perform the projective transformation to place the images points into a common co-ordinate system (at the central image). Remember, this must be performed sequentially and you’ll need to accumulate your transforms from/to the centre image. Instead of the images, transform the image co-ordinates (via meshgrid, or 4-point rectangles) and display the resulting plot. Your result should look something like panoMap.png but with axes to show your co-ordinate system.(c) [1 point] Create your panorama. First create a large enough area to display it; look at your co-ordinate system from (b). You can use imwarp to transform your images. You do not need to implement any fancy blending, just sum or overlap your results.5. Extra: [3 points] total (this is an optional exercise) Augment your panorama stitching program to include image blending with centre re-weighting and Laplacian pyramids. See Chapters 3.5.3 and 9.3 in the course textbook.(a) [1 point] Use centre re-weighting to simply average the image pairs. (b) [1 point] Use centre re-weighting to weight the Laplacian pyramids. (c) [1 point] Create your own fun examples showing the better performance in comparison to 4d.1 Sources 1. man.jpg Chris Ford, https://www.flickr.com/photos/chrisschoenbohm/4817576839/ 2. tracks.jpg Ryan Voetsch, https://www.flickr.com/photos/voetshy/
