- 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

Programming in C

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

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

Mar 30, 2023

SOLUTION.PDF## Get Answer To This Question

- Everything is in the document. I started a chat with a person and it disappeared and they haven't responded. If you have any questions I'd be happy to try to answer but the file is self explanatory....Aug 28, 2024
- THE PANCAKE PROBLEM (100 Points)A messy cook has adisordered stack of 10 differently sized pancakes [size from 1 to 10] and aspatula thatcan be inserted at any point in the stack and used to flip all...Jun 26, 2024
- CST8390 Assignment #3 – Data Analysis and Visualization [30%]This assignment relates to the following Course Learning Requirements (CLR). CLR 9: Interpreting and reporting results, presenting...SolvedApr 04, 2024
- CST8390 Assignment #2 – Statistics and Data Analysis [25%]This assignment relates to the following Course Learning Requirements (CLR). CLR 4: Explain the fundamental concepts of data mining and...SolvedMar 06, 2024
- CST8390 Assignment #1 – Data Extraction, Preprocessing, and Analysis [20%]This assignment relates to the following Course Learning Requirements (CLR). CLR 6: Explain basic statistical...SolvedFeb 09, 2024
- 11/20 11/20 11/20 This is a special type of LED light, used even during the day. The Principal wants to find an alternative means of pressing so that as many consecutive light bulbs as possible can be...Dec 04, 2023
- CS 6320.001 - Natural Language Processing - F23Take Test: Homework 3CS 6320.001 - Natural Language Processing - F23 AssignmentsTake Test: Homework 3 Test...SolvedNov 06, 2023
- code in python Write a detailed annotated bibliography for at least 10 bibliographic (find 6 more )referencesfrom scholarly peer-reviewed academic journals about Convolutional Neural Networks...Oct 19, 2023
- Classifying Ships from Automatic Indentification System (AIS) Data — Data Mining (pantelis.github.io)This is the assignment. I need a google colab file that works and does every coding part that is...SolvedOct 06, 2023
- Hello,Its an assignment on Natural Language Processing, I couldn't find this field in Computer Science section. I am attaching the zip file here which has all the required files. In that zip file...SolvedSep 14, 2023

Copy and Paste Your Assignment Here

Copyright © 2024. All rights reserved.