I downloaded a file of the assignmentSCHOOL OF ENGINEERING OF TECHNOLOGY TCSS 343 – Programming...

Question

I downloaded a file of the assignmentSCHOOL OF ENGINEERING OF TECHNOLOGY TCSS 343 – Programming Assignment February 19, 2020 1 GUIDELINES This is a group assignment. Each group may consist of 1 or 2 students. In other words, you can choose to work by yourself, or with one single colleague. Please state the names of your group members on your submission. Each group is also expected to give a 5-minute presentation and demo of your submis- sion during the last two classes. Details: In this assignment, you will implement algorithmic techniques in Java or Python. There is also a bonus challenge that also involves these techniques and an implementation in Java or Python. Homework should be electronically submitted via Canvas before midnight on the due date. Each group is expected to submit the following files: • Report. The submitted report MUST be typeset using any common software and submit- ted as a PDF. We strongly recommend using LATEX to prepare your solution. You could use any LATEX tools such as Overleaf, MiKTeX/TeXworks, TexShop etc. When presenting your results, use log-scale graphics if/when results are too different (tiny vs. huge) to coexist on the same linear-scale graphic. • Java/Python source code. Submit one single Java or Python file containing all your code, except for the challenge which must be in one single separate source file. You must name your source code tcss343.java or tcss343.py for the normal part of this assignment, and challenge.java or challenge.py for the bonus challenge. 1 Execution. We will use the following command(s) to execute your program for the normal part of this assignment: java tcss343 or python tcss343 The challenge has its own format described below. Remember to cite all sources you use other than the text, course material or your notes. 2 2 PROBLEM STATEMENT Consider the Subset Sum Problem, formally defined as: Subset Sum (SS): INPUT: a list S[0 . . .n −1] of n positive integers, and a target integer t ≥ 0. OUTPUT: TRUE and a set of indices A ⊆ {0 . . .n −1} such that ∑i∈A S[i ] = t if such an A exists, or FALSE otherwise. We have seen in class that this algorithm can be solved by brute force and with dynamic programming. The following clever algorithm has also been proposed to solve SS: 1. Split the indices {0. . .n −1} into two sets of nearly equal size, L = {0 . . .bn/2c} and H = {bn/2c+1. . .n −1}. 2. Compute a table T of all subsets of L that yield a subset of S of weight not exceeding t (that is, a table containing all I ⊆ L such that ∑i∈I S[i ] ≤ t ). If equality holds for some I , i.e. ∑ i∈I S[i ] = t , then return TRUE and I , and stop. 3. Compute a table W of all subsets of H that yield a subset of S of weight not exceeding t (that is, a table containing all J ⊆ H such that ∑ j∈J S[ j ] ≤ t ). If equality holds for some J , i.e. ∑ j∈J S[ j ] = t , then return TRUE and J , and stop. 4. Sort table W in ascending order of weights. 5. For each entry I in table T , find the subset J ⊆ H that yields the maximum weight not exceeding t when joined to I , i.e. (∑ i∈I S[i ] )+ (∑ j∈J S[ j ])≤ t . If equality holds for some I and some J , i.e. (∑ i∈I S[i ] )+ (∑ j∈J S[ j ])= t , then return TRUE and I ∪ J , and stop. 6. If no subsets I and J yield equality, return FALSE and the empty set, and stop. The overall goal of this programming assignment is to test and compare these three proposed solutions. 3 YOUR TASKS 3.1 BRUTE FORCE (4 points): Design and implement a brute force solution for this problem. Run it according to the testing procedure described below in section 3.4. What is the asymptotic running time complexity of this algorithm? What is its asymptotic space complexity (memory requirements for tables and similar data structures)? Justify your complexity analysis. 3 3.2 DYNAMIC PROGRAMMING (DP) (6 points): Design and implement a DP solution for this problem. Run it according to the testing procedure described below. What is the asymptotic running time complexity of this algorithm? What is its asymptotic space complexity (memory requirements for tables and similar data structures)? Justify your complexity analysis. 3.3 CLEVER ALGORITHM (8 points): Design and implement a solution for this problem based on the (allegedly) clever algorithm. What is the asymptotic running time complexity of this algorithm? What is its asymptotic space complexity (memory requirements for tables and similar data structures)? Justify your complexity analysis. 3.4 TESTING (4 points): Design and implement a method Driver that, given two integers n and r and a Boolean value v as input, creates a sequence S of n random elements sampled from range 1 to r , then tests each of the above algorithms on S for a target t chosen as, for v = TRUE, the sum of a random subset of S (so that a solution is guaranteed to exist), and for v = FALSE, a random value larger than the sum of all values on S (so that there is no solution). The Driver method must measure the time (in milliseconds) each of the three algorithms takes to complete, and record how much table space each algorithm needs for that particular combination of n and t . When the tests are done, Driver must also print the values of n and r , the generated sequence S and, for each of the three algorithms, the subsequence of elements from S each algorithm found that sums up to t (or an indication that none such subsequence exists), and the running time and table space requirements of that algorithm for that S. Run Driver for each of the following combinations: • r = 1,000, v = TRUE or FALSE (test both), and n = 5,6,7, . . . up to the largest value of n each algorithm can test so that it takes no more than 5 minutes for that n; • r = 1,000,000, v = TRUE or FALSE (test both), and n = 5,6,7, . . . up to the largest value of n each algorithm can test so that it takes no more than 5 minutes for that n. Notice that the largest value of n may be different for each algorithm. If a certain combi- nation of n, r , and v is infeasible for some algorithm, skip that algorithm but test the other one(s). 3.5 ANALYSIS OF RESULTS (4 points): Analyze the results using visualization (you may use MS Excel or equivalent spread- sheet software for that). 4 Plot the running time (in milliseconds) as a function of n for the range of n values described above and for each r and v . Also plot the table sizes (in number of entries) as a function of n for the range of n values described above and for each r and v . Use log-scale graphics whenever the discrepancy between the cases is so large than linear- scale graphics will make it too hard to compare those cases visually, or if the graphics simply do not fit the visual space. Your analyses should be included in the submitted document. 3.6 DOCUMENTATION (4 points): Provide a well prepared document that describes your solutions, complexity analy- ses, and result analyses including the graphics. You must submit your code, which should be well documented as well. If there is any known error in the code, you must point that out. Also, document the division of labor (who did what) in your report. Remember: your presentation must briefly describe all of these items. 4 BONUS CHALLENGE (5 POINTS): THE d -DIMENSIONAL n-QUEENS PROBLEM The well-known 8-Queens problem consists of placing 8 queens on an otherwise empty chessboard in such a way that no two queens attack each other (hence, there are no two queens on the same row, column, or diagonal, and no other pieces on the chessboard), as shown in fig. 4.1. Figure 4.1: Sample solution to the 8-Queens problem A trivial generalization is the n-Queens problem, where the task is to place n queens on an n ×n board instead. This problem has real-world applications like managing distributed memory storage or preventing deadlocks in computer networks. A not-so-trivial generalization is the d-dimensional n-Queens problem, which simply asks how many queens can be placed on a d-dimensional chessboard of size n ×n × ·· · ×n (d times, i.e. nd cells). The answer is easy for d = 2, since one can place exactly n queens on 5 a 2-dimensional chessboard in non-attacking configuration (every queen must be alone on each row and each column, and there are n rows or columns on a 2-dimensional chessboard). But for d > 2 the answer is not known exactly, and in general has to be determined by direct inspection. For instance, it is possible to place 4 non-attacking queens on a 3-dimensional chessboard of size 3×3×3. 4.1 FORMALIZATION In general, a queen on a d-dimensional chessboard of size nd is specified by a tuple q := (q0, q1, . . . , qd−1) of coordinates where 0 ≤ q j

Abr Writing · Accepted Answer

I have created an IPYNB notebook which is a Python Notebook that contains all the code, and inline documentation for each function and commented out each step in the process. However, In the report, you can see all the plots but they are for max time of 0.5 seconds instead of 300 seconds. In the 300 seconds report you can see that I have ran only the brute force algorithm and not anything else. You might be thinking that other two algorithms are faster than BF than why I am not running them for 300 seconds but just 0.5 seconds, right? 
This is why!

SCHOOL OF ENGINEERING OF TECHNOLOGY TCSS 343 – Programming Assignment February 19, 2020 1 GUIDELINES This is a group assignment. Each group may consist of 1 or 2 students. In other words, you can...

Answer To: SCHOOL OF ENGINEERING OF TECHNOLOGY TCSS 343 – Programming Assignment February 19, 2020 1 GUIDELINES...

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment