Solution Found!

Computer science / Algorithms 1 / Chapter 7 / Problem 7.8

Algorithms | 1st Edition | ISBN: 9780073523408 | Authors: Sanjoy Dasgupta Algorithms, Christos H. Papadimitriou Algorithms, Umesh Vazirani Algorithms

Change Question

You are given the following points in the plane:(1, 3), (2, 5), (3, 7), (5, 11), (7

Chapter 7, Problem 7.8

(choose chapter or problem)

Get Unlimited Answers

QUESTION:

You are given the following points in the plane:

(1, 3), (2, 5), (3, 7), (5, 11), (7, 14), (8, 15), (10, 19).

You want to find a line ax + by = c that approximately passes through these points (no line is a perfect fit). Write a linear program (you don’t need to solve it) to find the line that minimizes the maximum absolute error,

\(\max _{1 \leq i \leq 7}\left|a x_{i}+b y_{i}-c\right| .\)

Questions & Answers

QUESTION:

You are given the following points in the plane:

(1, 3), (2, 5), (3, 7), (5, 11), (7, 14), (8, 15), (10, 19).

You want to find a line ax + by = c that approximately passes through these points (no line is a perfect fit). Write a linear program (you don’t need to solve it) to find the line that minimizes the maximum absolute error,

\(\max _{1 \leq i \leq 7}\left|a x_{i}+b y_{i}-c\right| .\)

ANSWER:

Step 1 of 2

We introduce a variable z to the formula . It remains to constrain z such that . Since we are minimizing , it is sufficient to have , which is equivalent to the requirements

Study Tools You Might Need

Chapter: 2 Problem: 2.10

Classical Mechanics 0
For a steel ball bearing (diameter 2 mm and density 7.8 g/cm3) dropped in glycerin (density 1.3 g/cm3 and viscosity 12 Ns/m2 at STP), the dominant drag force is the linear drag given by (2.82) of Problem 2.2. (a) Find the characteristic time t and the terminal speed vt. [In finding the latter, you sh

Chapter: 11 Problem: PROBLEM 11-35

Organic Chemistry 9
A student wanted to use the Williamson ether synthesis to make (R)-2-ethoxybutane. He remembered that the Williamson synthesis involves an SN2 displacement, which takes place with inversion of configuration. He ordered a bottle of (S)-butan-2-ol for his chiral starting material. He also remembered th

Chapter: 4 Problem: 10

Anatomy & Physiology 1
Differentiated cells in a developing embryo derive from ________. a. endothelium, mesothelium, and epithelium b. ectoderm, mesoderm, and endoderm c. connective tissue, epithelial tissue, and muscle tissue d. epidermis, mesoderm, and endothelium

Chapter: 4 Problem: 2

Campbell Biology 10
Which functional group is not present in this molecule? a. carboxyl b. sulfhydryl c. hydroxyl d. amino

Chapter: 11 Problem: 11

Biology: The Unity and Diversity of Life 15
Cytoplasm of a plant cell divides by the process of ___ . a. telekinesis c. fission b. nuclear division d. cytokinesis

Chapter: 18 Problem: 8

Biology for AP Courses
Which of the following are two examples of vestigial structures? a. gills in fish and parts of the throat in humans b. butterfly wings and dragonfly wings c. hind leg bones in whales and leaves on some cacti d. shark fins and dolphin fins

Chapter: 1 Problem: 13

Biology: The Dynamic Science 5
While walking in the woods, you discover a large rock covered with a gelatinous, sticky substance. What test could you perform to determine whether the substance is inanimate, alive, or the product of a living organism?

Chapter: 19 Problem: 2

Principles of Economics 9
Marshall and Lily work at a local department store. Marshall, who greets customers as they arrive, is paid less than Lily, who cleans the bathrooms. This is an example of a. a compensating differential. b. human capital. c. signaling. d. efficiency wages.

Not The Solution You Need? Search for Your Answer Here:

×

Login

Login or Sign up for access to all of our study tools and educational content!

×

Register

Sign up for access to all content on our site!

Or login if you already have an account