There are n different sizes of boxes, from 1 to n. There is an unlimited supply of boxes of each size t, each with a value vt . A box of size t can hold several smaller boxes of sizes a1, a2, . . . , ak as long as the sum of sizes a1 + a2 + . . . + ak is strictly less than t. Each of these boxes may be filled with yet more boxes, and so on. Design an algorithm which runs in O(n2 ) time and finds the maximum value t

There are n different sizes of boxes, from 1 to n. There is an unlimited supply of boxes of each size t, each with a value vt . A box of size t can hold several smaller boxes of sizes a1, a2, . . . , ak as long as the sum of sizes a1 + a2 + . . . + ak is strictly less than t. Each of these boxes may be filled with yet more boxes, and so on. Design an algorithm which runs in O(n2 ) time and finds the maximum value t

C++ Programming: From Problem Analysis to Program Design

8th Edition

ISBN:9781337102087

Author:D. S. Malik

Publisher:D. S. Malik

Chapter10: Classes And Data Abstraction

Section: Chapter Questions

Problem 19PE

See similar textbooks

Similar questions

In computer science and mathematics, the Josephus Problem (or Josephus permutation) is a theoretical problem. Following is the problem statement: There are n people standing in a circle waiting to be executed. The counting out begins at some point (rear) in the circle and proceeds around the circle in a fixed direction. In each step, a certain number (k) of people are skipped and the next person is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last person remains, who is given freedom. Given the total number of persons n and a number k which indicates that k-1 persons are skipped and kth person is killed in circle. The task is to choose the place in the initial circle so that you are the last one remaining and so survive. For example, if n = 5 and k = 2, then the safe position is 3. Firstly, the person at position 2 is killed, then person at position 4 is killed, then person at position 1…
1. A runner targets herself to improve her time on a certain course by 3 seconds a day. If onday 0 she runs the course in 3 minutes, how fast must she run it on day 14 to stay ontarget?2. A certain computer algorithm executes twice as many operations when it is run with aninput of size k as when it is run with an input of size k − 1 (where k is an integer that isgreater than 1). When the algorithm is run with an input of size 1, it executes sevenoperations. How many operations does it execute when it is run with an input of size 25?
Q2. The following algorithm returns the product of two numbers, a and b. The parameters x and y are natural numbers. First, prove the correctness of the algorithm. Then, analyze the time complexity of the algorithm in the worst case scenario. function mult (a, b) if b = 0: return 0 else if b is odd: return (mult (2a, b/2 ) +a) else: return (mult (2a, b/2 ) )
Consider a group of balls where each ball is one of k colors. You can assume that there is an equal number of balls of each color. Each ball, aside from its color, has a written integer on it. The numbers are in no way associated with the color. a) Devise an algorithm that orders all the balls according to colors in a way that no ball comes before a ball of a lighter color. In other words, how do you order balls from lightest to darkest, however, inside one group (i. e., one color), balls can be ordered in any way with respect to the number written on the ball. Design an algorithm and analyze it. b) Now take the output from (a), and also order balls within the color. How much time is needed for this step?
Sudoku is a popular logic puzzle that uses a 9 by 9 array of squares that are organized into 3 by 3 subarrays. The puzzle solver must fill in the squares with the digits 1 to 9 such that no digit is repeated in any row, any column, or any of the nine 3 by 3 subgroups of squares. Initially, some squares are filled in already and cannot be changed. For example, the following might be a starting configuration for a Sudoku puzzle: Create a class SudokuPuzzle.java Download SudokuPuzzle.java that has the attributes • board—a 9 by 9 array of integers that represents the current state of the puzzle, where 0 indicates a blank square • start—a 9 by 9 array of boolean values that indicates which squares in board are given values that cannot be changed and the following methods: • SudokuPuzzle—a constructor that creates an empty puzzle • toString—returns a string representation of the puzzle that can be printed • addInitial(row, col, value)—sets the given square to the given value as an…
Write pseudo code of the algorithm to solve the following problem with minimum number of floor checking complexity (other logic which yields more floor will not be considered as the answer): “A firm wants to determine the highest floor of its n-story headquarters from which a gadget can fall without breaking. The firm has two identical gadgets to experiment with. If one of them gets broken, it cannot be repaired, and the experiment will have to be completed with the remaining gadget. Design an algorithm in the best efficiency class you can to solve this problem.” A prototype of the algorithm is given as: int checkHeight(Building[1..n], W1, W2) //Building with 1 to n floors and two weights w1, w2, and it will return the highest //floor number from which the weight can fall safely. Whenever, you throw a weight, //it will either break or do not break with a function ThrowWeight(FloorNo, W) //It will return 1 if the weight does not break and 0 if it breaks.
Computer Science There is an n × n grid of squares. Each square is either special, or has a positive integer costassigned to it. No square on the border of the grid is special.A set of squares S is said to be good if it does not contain any special squares and, starting fromany special square, you cannot reach a square on the border of the grid by performing up, down,left and right moves without entering a cell belonging to S. 5 3 4 9 4 X 3 6 1 9 X 4 1 2 3 5 - Design an algorithm which receives an arbitrary n × n grid, runs in time poly-nomial in n and determines a good set of squares with minimum total cost.
Euclid’s algorithm (or the Euclidean algorithm) is an algorithm that computes thegreatest common divisor, denoted by gcd, of two integers. Below are the original versions ofEuclid’s algorithm that uses repeated subtraction and another one that uses the remainder.int gcd_sub(int a, int b){ if (!a) return b; while (b) if (a > b) a = a – b; else b = b – a; return a;}int gcd_rem(int a, int b){ int t; while (b) { t = b; b = a % b; a = t; } return a;}1. Trace each of the above algorithm using specific values for a and b.2. Compare both algorithms.
The Fibonacci series begins with the terms 0 and 1 and has the property that each succeeding term is the sum of the two preceding terms. The first few terms are: 0, 1, 1, 2, 3, 5, 8, 13, 21, ... Write an algorithm in pseudo code to generate and print the first N terms of the Fibonacci series where N is user-defined. Pay attention to how your algorithm prints the first two terms.
2. A celebrity among a group of n people is a person who knows nobody but is known by everybody else. Design a decrease-and-conquer algorithm that identifies a celebrity among n people, or outputs "no celebrity identified" if there is no such person, by only asking the question "Do you know him/her?" to people. Analyze the efficiency of the algorithm.
The digital root of a positive integer is found by summing the digits of the integer. If the resulting value is a single digit then that digit is the digital root. If the resulting value contains two or more digits, those digits are summed and the process is repeated. This is continued as long as necessary to obtain a single digit. For example, consider the positive integer 24. Adding the 2 and the 4 yields a value of 6. Since 6 is a single digit, 6 is the digital root of 24. Now consider the positive integer 39. Adding the 3 and the 9 yields 12. Since 12 is not a single digit, the process must be repeated. Adding the 1 and the 2 yields 3, a single digit and also the digital root of 39. Input File: The input file will contain a list of positive integers, one per line. The end of the input will be indicated by an integer value of zero. Output File: For each integer in the input, output its digital root on a separate line of the output. Example Input: 24 39…
Design a reasonably efficient algorithm for solving each of the following problems and determine its efficiency class. a. You are given n telephone bills and m checks sent to pay the bills (n ≥ m).Assuming that telephone numbers are written on the checks, find out who failed to pay. (For simplicity, you may also assume that only one check is written for a particular bill and that it covers the bill in full.)