- Questions & Answers
- Accounting
- Computer Science
- Automata or Computationing
- Computer Architecture
- Computer Graphics and Multimedia Applications
- Computer Network Security
- Data Structures
- Database Management System
- Design and Analysis of Algorithms
- Information Technology
- Linux Environment
- Networking
- Operating System
- Software Engineering
- Big Data
- Android
- iOS
- Matlab

- Economics
- Engineering
- Finance
- Thesis
- Management
- Science/Math
- Statistics
- Writing
- Dissertations
- Essays
- Programming
- Healthcare
- Law

- Log in | Sign up

has to be in c language and in linux environment with the solution video and commands to run

A5_guide.dvi School of Computer Science University of Guelph CIS*3490 The Analysis and Design of Algorithms Winter 2023 Instructor: Fangju Wang Assignment 5 Guide Hints and suggestions for individual questions: • Q1: For the subset sum problem, please read pages 427 and 428 for more information. – For Q1.1, you can create the 2n subsets, calculate the sum for each of them, and find the subset that maximizes the sum. Your program input and output can be something like: Brute force program for subset sum problem Enter the file name and subset sum: data_A5_Q1_1.txt 1200 Number of all the subsets: 33554432 Number of the subsets whose sums are 1200: 8909 Execution time = 4764 ms – For Q1.2, you can follow the algorithm illustrated in Figure 12.4 (p428). Your program input and output can be something like: Backtracking program for subset sum problem Enter the file name and subset sum: data_A5_Q1_1.txt 1200 Number of dead ends: 14838675 Number of the subsets whose sums are 1200: 8909 Execution time = 2093 ms The numbers of dead ends may differ slightly. • Q2: For the person-job assignment problem, please read page 119 for more information. – For Q2.1, you can generate all the permutations (representing all the possible person- job assignments), evaluate all of them and find the one that has the maximum value. Your program input and output can be something like: Brute force program for assignment problem Enter the file name: data_A5_Q2_1.txt The number of all the possible assignments: 479001600 The person-job assignment selected: 8 4 2 1 12 6 3 7 11 5 10 9 The total value: 993 Execution time = 31899 ms 1 In the person-job assignment expression, the jth integer is the person assigned to job j. For example, person 8 is assigned to job 1, person 4 is assigned to job 2, and so on. – For Q2.2, please read pages 433-436. You can follow the algorithm illustrated in Figures 12.5, 12.6 and 12.7. Please note the example in the figures is to find the minimum, whereas this question is to find the maximum. Your program input and output can be something like: Branch and bound program for assignment problem Enter the file name: data_A5_Q2_1.txt Maximum upper bound: 1044 Maximum upper bound: 1030 Maximum upper bound: 1025 Maximum upper bound: 1025 Maximum upper bound: 1025 Maximum upper bound: 1025 Maximum upper bound: 1004 Maximum upper bound: 992 Maximum upper bound: 976 Maximum upper bound: 976 Maximum upper bound: 976 Maximum upper bound: 976 The person-job assignment selected: 8 4 9 1 12 6 3 7 11 5 10 2 Max total value 976 Execution time = 2 ms The person-job assignment is expressed in the same way as in Q2.1. The upper bounds may differ slightly. A branch and bound algorithm may or may not get the optimal solution. Note: You can develop your programs using any C system, as long as your programs can be correctly compiled and executed on the Linux system in SoCS. You are allowed to use standard library functions. Your programs should be submitted as a tar file or zip file containing your program files and readme and makefile. The readme file should contain a brief description of how to compile and run each program. Any compilation error or warning will result in a mark deduction. There will be some marks allocated for documentation. Each file should have a comment at the beginning containing your name, id, date, and the assignment name. Each function should have a brief comment describing its purpose. Also, any section of code where it is not easily apparent what the code does should have a short comment. 2 A5.dvi School of Computer Science University of Guelph CIS*3490 The Analysis and Design of Algorithms Winter 2023 Instructor: Fangju Wang Assignment 5 (100%) For this assignment, you are required to write programs in C. No pseudocode. Question 1: Subset-Sum Problem (50%) The subset-sum problem is to find a subset of a given set A = {a1, a2, ..., an} of n positive integers, such that the subset’s sum is equal to a given positive integer d. For example, for A = {1, 2, 5, 6, 8} and d = 9, there are two subsets {1, 2, 6} and {1, 8} whose sums are equal to 9 . Write the following programs for finding the number of the subsets whose sums are equal to a given positive integer d. In the above example, the number is 2. 1.1 A program to implement a brute force (exhaustive search) algorithm (15%) 1.2 A possibly more efficient program based on the backtracking technique (35%) Requirements: When a program is executed, it prompts for a file name and a positive integer d, reads in the file containing the set A, and computes and reports the number of the subsets whose sums are equal to d. The program for 1.1 is also required to report the number of all the subsets evaluated. The program for 1.2 is also required to report the number of the dead ends. The programs are not required to list the subsets. A program is required to report the running time for finding the subsets. The running time should not include the time for reading the file. You can use file data A5 Q1 1.txt to develop/test your programs. This file contains 25 integers. A different data file will be used to grade your programs. The numbers of integers and data formats of the two data files will be the same. Question 2: Person-Job Assignment Problem (50%) In an assignment problem, there are n people who need to be assigned to execute n jobs, one person per job. Each person is assigned to exactly one job and each job is assigned to exactly one person. A person creates a value in doing a job. In this assignment problem, V [i.j] in the n × n matrix V stores the value created by person i in doing job j (i, j = 1, 2, ...n). The problem is to find a person-job assignment that maximizes the total value. 1 Write the following programs to solve the assignment problem with a given V . 2.1 A program to implement a brute force (exhaustive search) algorithm (15%) 2.2 A possibly more efficient program based on the branch-and-bound technique (35%) Requirements: When a program is executed, it prompts for a file name, reads in the file containing matrix V , and computes and reports the assignment and the total value created. Please see the guide for the format for reporting and assignment. The program for 2.1 is also required to report the number of all the assignments evaluated. The program for 2.2 is also required to report the maximum upper bound in each step. A program is required to report the running time for finding the assignment. The running time should not include the time for reading the file. You can use file data A5 Q2 1.txt to develop/test your programs. This file contains a 12 × 12 matrix, for 12 persons and 12 jobs. A different data file will be used to grade your programs. The numbers of integers and data formats of the two data files will be the same. Note: Write your own code for this assignment. NO code from any source is allowed. Due time: 08:00am, Monday April 10, 2023. Submit your work as a tar or zip file to Moodle. 2 71 544 136 89 15 223 2 974 29 7 62 361 773 52 26 258 8 21 63 9 328 31 39 130 10 71 44 13 89 15 23 12 74 29 7 39 12 62 61 73 52 26 58 8 21 63 92 55 78 28 31 39 30 10 19 84 89 64 77 65 22 57 84 49 34 13 5 23 12 40 10 67 78 9 76 43 66 41 32 19 28 33 91 49 58 59 66 11 18 11 67 52 23 43 55 13 53 72 29 17 71 19 35 34 90 35 50 81 43 89 45 54 64 60 9 17 15 31 82 66 38 48 22 36 81 12 18 69 73 52 56 47 58 70 55 12 25 10 31 39 16 65 51 89 48 95 33 27 42 17 56 54 27 83 52 47 19 53 56 88 92 96 45 37 18 23 29 63 54

A5_guide.dvi School of Computer Science University of Guelph CIS*3490 The Analysis and Design of Algorithms Winter 2023 Instructor: Fangju Wang Assignment 5 Guide Hints and suggestions for individual questions: • Q1: For the subset sum problem, please read pages 427 and 428 for more information. – For Q1.1, you can create the 2n subsets, calculate the sum for each of them, and find the subset that maximizes the sum. Your program input and output can be something like: Brute force program for subset sum problem Enter the file name and subset sum: data_A5_Q1_1.txt 1200 Number of all the subsets: 33554432 Number of the subsets whose sums are 1200: 8909 Execution time = 4764 ms – For Q1.2, you can follow the algorithm illustrated in Figure 12.4 (p428). Your program input and output can be something like: Backtracking program for subset sum problem Enter the file name and subset sum: data_A5_Q1_1.txt 1200 Number of dead ends: 14838675 Number of the subsets whose sums are 1200: 8909 Execution time = 2093 ms The numbers of dead ends may differ slightly. • Q2: For the person-job assignment problem, please read page 119 for more information. – For Q2.1, you can generate all the permutations (representing all the possible person- job assignments), evaluate all of them and find the one that has the maximum value. Your program input and output can be something like: Brute force program for assignment problem Enter the file name: data_A5_Q2_1.txt The number of all the possible assignments: 479001600 The person-job assignment selected: 8 4 2 1 12 6 3 7 11 5 10 9 The total value: 993 Execution time = 31899 ms 1 In the person-job assignment expression, the jth integer is the person assigned to job j. For example, person 8 is assigned to job 1, person 4 is assigned to job 2, and so on. – For Q2.2, please read pages 433-436. You can follow the algorithm illustrated in Figures 12.5, 12.6 and 12.7. Please note the example in the figures is to find the minimum, whereas this question is to find the maximum. Your program input and output can be something like: Branch and bound program for assignment problem Enter the file name: data_A5_Q2_1.txt Maximum upper bound: 1044 Maximum upper bound: 1030 Maximum upper bound: 1025 Maximum upper bound: 1025 Maximum upper bound: 1025 Maximum upper bound: 1025 Maximum upper bound: 1004 Maximum upper bound: 992 Maximum upper bound: 976 Maximum upper bound: 976 Maximum upper bound: 976 Maximum upper bound: 976 The person-job assignment selected: 8 4 9 1 12 6 3 7 11 5 10 2 Max total value 976 Execution time = 2 ms The person-job assignment is expressed in the same way as in Q2.1. The upper bounds may differ slightly. A branch and bound algorithm may or may not get the optimal solution. Note: You can develop your programs using any C system, as long as your programs can be correctly compiled and executed on the Linux system in SoCS. You are allowed to use standard library functions. Your programs should be submitted as a tar file or zip file containing your program files and readme and makefile. The readme file should contain a brief description of how to compile and run each program. Any compilation error or warning will result in a mark deduction. There will be some marks allocated for documentation. Each file should have a comment at the beginning containing your name, id, date, and the assignment name. Each function should have a brief comment describing its purpose. Also, any section of code where it is not easily apparent what the code does should have a short comment. 2 A5.dvi School of Computer Science University of Guelph CIS*3490 The Analysis and Design of Algorithms Winter 2023 Instructor: Fangju Wang Assignment 5 (100%) For this assignment, you are required to write programs in C. No pseudocode. Question 1: Subset-Sum Problem (50%) The subset-sum problem is to find a subset of a given set A = {a1, a2, ..., an} of n positive integers, such that the subset’s sum is equal to a given positive integer d. For example, for A = {1, 2, 5, 6, 8} and d = 9, there are two subsets {1, 2, 6} and {1, 8} whose sums are equal to 9 . Write the following programs for finding the number of the subsets whose sums are equal to a given positive integer d. In the above example, the number is 2. 1.1 A program to implement a brute force (exhaustive search) algorithm (15%) 1.2 A possibly more efficient program based on the backtracking technique (35%) Requirements: When a program is executed, it prompts for a file name and a positive integer d, reads in the file containing the set A, and computes and reports the number of the subsets whose sums are equal to d. The program for 1.1 is also required to report the number of all the subsets evaluated. The program for 1.2 is also required to report the number of the dead ends. The programs are not required to list the subsets. A program is required to report the running time for finding the subsets. The running time should not include the time for reading the file. You can use file data A5 Q1 1.txt to develop/test your programs. This file contains 25 integers. A different data file will be used to grade your programs. The numbers of integers and data formats of the two data files will be the same. Question 2: Person-Job Assignment Problem (50%) In an assignment problem, there are n people who need to be assigned to execute n jobs, one person per job. Each person is assigned to exactly one job and each job is assigned to exactly one person. A person creates a value in doing a job. In this assignment problem, V [i.j] in the n × n matrix V stores the value created by person i in doing job j (i, j = 1, 2, ...n). The problem is to find a person-job assignment that maximizes the total value. 1 Write the following programs to solve the assignment problem with a given V . 2.1 A program to implement a brute force (exhaustive search) algorithm (15%) 2.2 A possibly more efficient program based on the branch-and-bound technique (35%) Requirements: When a program is executed, it prompts for a file name, reads in the file containing matrix V , and computes and reports the assignment and the total value created. Please see the guide for the format for reporting and assignment. The program for 2.1 is also required to report the number of all the assignments evaluated. The program for 2.2 is also required to report the maximum upper bound in each step. A program is required to report the running time for finding the assignment. The running time should not include the time for reading the file. You can use file data A5 Q2 1.txt to develop/test your programs. This file contains a 12 × 12 matrix, for 12 persons and 12 jobs. A different data file will be used to grade your programs. The numbers of integers and data formats of the two data files will be the same. Note: Write your own code for this assignment. NO code from any source is allowed. Due time: 08:00am, Monday April 10, 2023. Submit your work as a tar or zip file to Moodle. 2 71 544 136 89 15 223 2 974 29 7 62 361 773 52 26 258 8 21 63 9 328 31 39 130 10 71 44 13 89 15 23 12 74 29 7 39 12 62 61 73 52 26 58 8 21 63 92 55 78 28 31 39 30 10 19 84 89 64 77 65 22 57 84 49 34 13 5 23 12 40 10 67 78 9 76 43 66 41 32 19 28 33 91 49 58 59 66 11 18 11 67 52 23 43 55 13 53 72 29 17 71 19 35 34 90 35 50 81 43 89 45 54 64 60 9 17 15 31 82 66 38 48 22 36 81 12 18 69 73 52 56 47 58 70 55 12 25 10 31 39 16 65 51 89 48 95 33 27 42 17 56 54 27 83 52 47 19 53 56 88 92 96 45 37 18 23 29 63 54

Answered 3 days AfterMar 31, 2023

SOLUTION.PDF## Answer To This Question Is Available To Download

- Use C to finish the assignment, more information is in Readme. md. And check the code similaritySolvedMay 25, 2023
- antt chart appropriate to the projectHigh level Project Design with diagram 2Project design prototype: Project with block diagramsstep by step (you can use UML/Use cases/flow 5charts)Budget...SolvedMay 16, 2023
- MIS 312 Week 5 AssignmentSetup for the Assignment: This week’s reading is drawing your focus on how to refine your user story telling skills and then how to start thinking about how to use UI...SolvedMay 02, 2023
- the question is in the assignment please keep the answer as simple as possibleSolvedApr 27, 2023
- Working with ColorV I S U A L M E D I A D E S I G N 10 5COLOR ESSENTIALSColors can be specified in InDesign according to three different color models:PROCESS COLORS This is the color...SolvedApr 26, 2023
- CHECK FILES BELOW..... WOULD NEED THE EXPERT WHO WORKED ON ORDER118761TO WORK ON THIS ONE AS ALL ASSIGNMENTS ARE RELATED TO EACH OTHER. THE EXPERT HAS A COPY OF THE PDF E-BOOK. IF NOT, I WILL PROVIDE...SolvedApr 24, 2023
- SQL project 3 and project 4. Would like to get it completed in my LAB worksheet which means the expect needs to login into my student account and complete it. thanksSolvedApr 23, 2023
- Project3: Analysis of the Amazon co-purchasing data.Provided data:Amazon co-purchasing data is stored here:http://snap.stanford.edu/data/amazon-meta.htmlGoal:1) Visualize the data (like...SolvedApr 17, 2023
- This assignment is focused on machine learning, mainly on the implementation of 2 different algorithms - Stochastic Gradient Descent & ID3 decision tree. The assignment is divided into two sections,...SolvedApr 16, 2023
- A Predictive Model for Diagnosis in BiomedicineGroup Number: 7Group members: 3Motivation: To provide clinicians with a fast and accurate diagnostic tool that can aid in early detection and...SolvedApr 15, 2023

Copy and Paste Your Assignment Here

Copyright © 2023. All rights reserved.