8. A school is creating class schedules for its students. The students submit their requested courses and then a program will be designed to find the optimal schedule for all students. The school has detormined that finding the absolute best schedule cannot be solved in a reasonable time. Instead they have decided to use a simpler algorithm that produces a good but non-optimal schedule in a more reasonable amount of timne. Which principle docs this decision best demonstrate? A. Unreasonable algorithms may sometimes also be undecidable O B. Heuristics can be used to solve sorme problems for which no reasonable algorithm exists O Two algorithms that solve the same problem must also have the same efficiency D. Approxirmate solutions are often identical to optimal solutions:

8. A school is creating class schedules for its students. The students submit their requested courses and then a program will be designed to find the optimal schedule for all students. The school has detormined that finding the absolute best schedule cannot be solved in a reasonable time. Instead they have decided to use a simpler algorithm that produces a good but non-optimal schedule in a more reasonable amount of timne. Which principle docs this decision best demonstrate? A. Unreasonable algorithms may sometimes also be undecidable O B. Heuristics can be used to solve sorme problems for which no reasonable algorithm exists O Two algorithms that solve the same problem must also have the same efficiency D. Approxirmate solutions are often identical to optimal solutions:

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Q: The Night Owls Society is arranging a conference. To minimize costs, they want to schedule as many…

A: 1) A problem is said to have optimal sub structure if solutions to the problem can be found…

Q: This question concerns computational complexity. In this question, the perfect square problem is the…

A: In this question we have to adapte Heron's algorithm (a square root approximation method) into a…

Q: Write a form algorithm for the following problem with Condition 1 using Round Model, where a round…

A: Given Write a form algorithm for the following problem with Condition 1 using Round Model, where a…

Q: Use Hall's Theorem to answer the following Suppose that m people are selected as prize winners in a…

A: Hall's Theorem, also known as Hall's Marriage Theorem, which it is an important result in graph…

Q: A* search is essentially a uniform cost BFS heuristic search technique. What characteristics of the…

A: If there are more than one solutions for a given problem, then BFS will provide the minimal solution…

Q: Design a greedy algorithm for this problem and find how long it will take to cross the bridge by…

A: The current scenario here is to solve the bridge crossing puzzle .Here we are going to use a greedy…

Q: A team sport game has m players in a team and a tournament can have n competing teams. Team T1 ranks…

A: The question is asking to design an algorithm to determine if two teams can be ranked based on their…

Q: Consider a sequential search algorithm. Given a value, the algorithm scans a linear array until the…

A: Linear Search: The simplest search algorithm is linear Search. It sequentially traverses the array…

Concept explainers

Introduction to Greedy Algorithm

A greedy algorithm is a problem-solving method that makes the locally optimal selection at every stage to reach a globally optimal solution. It solves a problem in two stages: Scanning the list of items and Optimization. However, in most problems, the greedy algorithm fails to provide a globally optimal solution.

Question

100%

8. A school is creating class schedules for its students. The students submit their
requested courses and then a program will be designed to find the optimal
schedule for all students.
The school has determined that finding the absolute best schedule cannot be
solved in a reasonablo time. Instead they have decided to use a simpler
algorithm that produces a good but non-optimal schedule in a more
reasonable amount of time.
Which principle does this decision best demonstrate?
O A Unreasonable algorithms may sometimes also be undecidable
O B. Heuristics can be used to solve some problems for which no reasonable
algorithm exsts
O C.
efficiency
Two algorithms that solve the same problem must also have the same
O B. Approximate solutions are often identical to optimal solutions

Expert Solution

This question has been solved!

Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.

This is a popular solution!

SEE SOLUTION Check out a sample Q&A here

Problem Analysis :

VIEW

Correct Answer :

VIEW

Trending now

This is a popular solution!

Step by step

Solved in 2 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions

Find the solution set of the following Activity-selection Problem. ⚫ • • By earliest starting time: sorting starting time (s;) in non-decreasing order. By earliest finish time: sorting finishing time (fi) in non-decreasing order. By shortest interval: sorting (fis;) time in non-decreasing order. ai 1 2 3 4 5 10 6 7 8 00 9 10 11 Si 3 1 0 12 10 5 8 3 2 8 6 5 fi 5 4 6 14 9 11 8 13 12 10 7
Determine the expected case running time of the algorithm. Fully justify your solution. Determine the best case running time of the algorithm and state what condition must be true forit to occur. No justification is needed! Determine the worst case running time of the algorithm and state what condition must be true forit to occur. No justification is needed!
We can implement requests to the waiter as either a queue of requests or as a periodic retry of a request. With a queue, requests are handled in the order they are received. Th e problem with using the queue is that we may not always be able to service the philosopher whose request is at the head of the queue (due to the unavailability of resources). Describe a scenario with 5 philosophers where a queue is provided, but service is not granted even though there are forks available for another philosopher (whose request is deeper in the queue) to eat.If we implement requests to the waiter by periodically repeating our request until the resources become available, will this solve the problem described in the above Exercise? Explain.
Suppose that a manufacturing company builds n different types of robots, sayrobots 1, 2, . . . , n. These robots are made from a common set of m types of materials, saymaterials 1, 2, . . . , m. The company has only a limited supply of materials for each year,the amount of materials 1, 2, . . . , m are limited by the numbers b1, b2, . . . , bm, respectively.Building robot i requires an aij amount from material j. For example, building robot 1requires a11 from material 1, a12 from material 2, etc. Suppose the profit made by sellingrobot i is pi. Write an integer linear program for maximizing the annual profit for thecompany
1. Let S = {1,2...n} be a set activities, where activity i € S has a start time si, a finish time f; and a profit p, asSociated with it. Design an dynamic programming algorithm for computing a set of compatible activities of maximum profit. Argue that the time complexity of you algorithm is O(n log(n)). (You must start with the correct definitions, and then write a recurrence relation.)
Consider the following functions as time complexities of some algorithms. (a) First write the worst-case runtime of each algorithm in Big-O notation. (b) Then arrange functions from low to high (Consider their Big-O notations as you arrange them; as n grows, the function that grows slower should come sooner than the one that grows faster). (c) Arbitrary, select TWO of arrangements in part (b) and for each one of them justify why you have chosen such an ordering for the corresponding function. Provide formal proof. For example if fl<=f2<= f3<= f4<=f5 you may choose to formally justify why (1) fl<=f2 and why (2) f4<=f5 . fI(n)=n², f2(n)=210 nlogn, f3(n)=3", f4(n)=n, f5(n)=1, f6(n)=5*logn, f7(n)= n", f8(n)=4 n*n, f9(n)=2log(n³)
Q1 Dan has a list of problems suitable for the assignment. The difficulties of these problems are stored in a list of integers a. The i-th problem’s difficulty is represented by a[i] (the higher the integer, the more difficult the problem). Dan is too busy eating saltines to worry about assignment decisions, so he asks Michael to select at least two problems from the list for the assignment. Since there are many possible subsets of the problems to consider and Michael has a life, he decides to consider only sublists (definition follows) of the list of problems. To make grading the assignment easier, Michael wants to pick problems that don’t vary too much in difficulty. What is the smallest difference between the difficulties of the most difficult selected problem and the least difficult selected problem he can achieve by selecting a sublist of length at least 2 of the original list of problems? Definition: A sublist of a list a is any list you can obtain by removing some (possibly 0)…
A school is creating class schedules for its students. The students submit their requested courses and then a program will be designed to find the optimal schedule for all students. The school has determined that finding the absolute best schedule cannot be solved in a reasonable time. Instead they have decided to use a simpler algorithm that produces a good but non-optimal schedule in a more reasonable amount of time. Which principle does this decision best demonstrate?