cpp/cs103/hw-recursion/sqrt Source

Viewing cpp/cs103/hw-recursion/sqrt by daveagp@gmail.com. You have unsaved changes. Log in above to create, edit, preview and publish Websheets.

Property Value

Description
html markup
shown to student

Using recursion, define a function <tt>rec_sqrt(x)</tt>
that computes the square root of <tt>x</tt>.
We will use binary search: think of it as binary-searching
the real line for the number $y$ satisfying $y^2=x$.
<p>We will use recursive binary search. Each time, the recursive function
should be told the target value <tt>x</tt>, as well as
lower bounds and upper bounds for where $\sqrt{x}$ could live.
The binary search will be recursive: each recursive call cuts
the search range in half.
<p>Since <tt>rec_sqrt(x)</tt> only takes one argument, recursing on the
"range" needs more work.
Let's define a second function, call it <tt>rec_sqrt_helper(x, lo, hi)</tt>
that is actually recursive: it does binary search in the specified range.
<p>Then <tt>rec_sqrt(x)</tt> only needs to get things started by calling
the helper function once.

Epilogue
html markup
shown when solved

remove
Public permissions remove
Remarks
Comments, history, license, etc.

remove
Engine
Choices
json list of string, bool pairs
e.g. [["good", true], ["bad", false]]

Correct answer
Template / Reference solution

Template / Reference solution

#include <iostream>
using namespace std;

// you'll define this further below.
double rec_sqrt_helper(double x, double lo, double hi);

// function to compute the square root of x. Assumes x >= 0.
double rec_sqrt(double x) {

// since sqrt(x) is between 0 and x+1, use that initial range
double initial_lo = \[ REDACTED ]\;
double initial_hi = \[ REDACTED ]\;

// start the binary search
return rec_sqrt_helper(\[ REDACTED ]\);
}

// recursive function. finds sqrt(x) within range lo..hi
double rec_sqrt_helper(double x, double lo, double hi) {

// base case. if range is very small, accept it as sqrt
if (hi - lo < 1E-8) {
return lo; // return some point in range
}

// recursive case.

double mid = \[ REDACTED ]\; // midpoint between lo and hi
// is mid smaller or bigger than sqrt(x)?
// i.e. is mid^2 smaller or bigger than x?

if (\[ REDACTED ]\) {
// recurse on the appropriate half of the range
return rec_sqrt_helper(\[ REDACTED ]\);
}
else {
// recurse on the appropriate half of the range
return \[ REDACTED ]\;
}
}

Java test suite
See manual

C++ test suite
json list of stdin/args tests
e.g. [{"stdin":"hi", "args":["4", "5"]}, {"stdin":"noargs"}]
to just run once with no input use [{}]

C++ test suite
See manual

[
["check-function", "rec_sqrt", "double", ["double"]],
["call-function", "rec_sqrt", ["16"]],
["call-function", "rec_sqrt", ["103"]],
["call-function", "rec_sqrt", ["1.23456"]],
["call-function", "rec_sqrt", ["23432.989"]],
["call-function", "rec_sqrt", ["0.25"]],
["call-function", "rec_sqrt", ["4E14"]],
["call-function", "rec_sqrt", ["9E-6"]]
]

Forbidden substrings
json list of strings
e.g. ["for","while"]

["#include", "for", "while"]
remove
Solution visibility remove
Java imports
json list of importables
e.g. ["java.util.*"]

remove
Override Java classname
else defaults to
websheet name
remove
Dependent on other websheets?
json list of websheet names in this folder
e.g. ["DataStructure"]

remove
Is example?
i.e., just a demo
remove
Add compiler flag(s)
json list of flags
e.g. ["-Wno-unused-variable"]

remove
Remove default compiler flag(s)
json list of flags
see default_cppflags
e.g. ["-Wno-write-strings"]

remove

Property	Value
Description html markup shown to student	Using recursion, define a function <tt>rec_sqrt(x)</tt> that computes the square root of <tt>x</tt>. We will use binary search: think of it as binary-searching the real line for the number $y$ satisfying $y^2=x$. <p>We will use recursive binary search. Each time, the recursive function should be told the target value <tt>x</tt>, as well as lower bounds and upper bounds for where $\sqrt{x}$ could live. The binary search will be recursive: each recursive call cuts the search range in half. <p>Since <tt>rec_sqrt(x)</tt> only takes one argument, recursing on the "range" needs more work. Let's define a second function, call it <tt>rec_sqrt_helper(x, lo, hi)</tt> that is actually recursive: it does binary search in the specified range. <p>Then <tt>rec_sqrt(x)</tt> only needs to get things started by calling the helper function once.
Epilogue html markup shown when solved	remove
Public permissions	remove
Remarks Comments, history, license, etc.	remove
Engine
Choices json list of string, bool pairs e.g. `[["good", true], ["bad", false]]`
Correct answer
Template / Reference solution
Template / Reference solution	#include <iostream> using namespace std; // you'll define this further below. double rec_sqrt_helper(double x, double lo, double hi); // function to compute the square root of x. Assumes x >= 0. double rec_sqrt(double x) { // since sqrt(x) is between 0 and x+1, use that initial range double initial_lo = \[ REDACTED ]\; double initial_hi = \[ REDACTED ]\; // start the binary search return rec_sqrt_helper(\[ REDACTED ]\); } // recursive function. finds sqrt(x) within range lo..hi double rec_sqrt_helper(double x, double lo, double hi) { // base case. if range is very small, accept it as sqrt if (hi - lo < 1E-8) { return lo; // return some point in range } // recursive case. double mid = \[ REDACTED ]\; // midpoint between lo and hi // is mid smaller or bigger than sqrt(x)? // i.e. is mid^2 smaller or bigger than x? if (\[ REDACTED ]\) { // recurse on the appropriate half of the range return rec_sqrt_helper(\[ REDACTED ]\); } else { // recurse on the appropriate half of the range return \[ REDACTED ]\; } }
Java test suite See manual
C++ test suite json list of stdin/args tests e.g. `[{"stdin":"hi", "args":["4", "5"]}, {"stdin":"noargs"}]` to just run once with no input use `[{}]`
C++ test suite See manual	[ ["check-function", "rec_sqrt", "double", ["double"]], ["call-function", "rec_sqrt", ["16"]], ["call-function", "rec_sqrt", ["103"]], ["call-function", "rec_sqrt", ["1.23456"]], ["call-function", "rec_sqrt", ["23432.989"]], ["call-function", "rec_sqrt", ["0.25"]], ["call-function", "rec_sqrt", ["4E14"]], ["call-function", "rec_sqrt", ["9E-6"]] ]
Forbidden substrings json list of strings e.g. `["for","while"]`	["#include", "for", "while"] remove
Solution visibility	remove
Java imports json list of importables e.g. `["java.util.*"]`	remove
Override Java classname else defaults to websheet name	remove
Dependent on other websheets? json list of websheet names in this folder e.g. `["DataStructure"]`	remove
Is example? i.e., just a demo	remove
Add compiler flag(s) json list of flags e.g. `["-Wno-unused-variable"]`	remove
Remove default compiler flag(s) json list of flags see default_cppflags e.g. `["-Wno-write-strings"]`	remove

Optional properties:

Note: problems are open-source by default (see 'Public permissions'). Assumed license for open problems is Creative Commons 4.0 Attribution-ShareAlike unless specified in 'Remarks'.