Book hand wrote:The preponderance of bonuses on hard stuff whose easy part was, say, "this thing contrasted with refraction" felt a bit silly; but perhaps that's just my lack of real knowledge showing.
I .. don't really know what this means, can you explain?
Book hand wrote:That said, can you post the bonus on IVPs whose hard part was "Lipschitz continuity", the amortized analysis bonus, and the stack/roughness tossups?
This type of differential equation problem involves finding the solution to an ODE given the value of the function of interest at the starting point or time. For 10 points each:
Name this type of differential equation problem that contrasts with a boundary-value problem.
A: \bu{IVP} [or \bu{initial}-value problem; or \bu{Cauchy} problem]
A big deal for IVPs is whether a problem is well-posed, which is the case if a solution exists, if the solution depends on the data, and if the solution has this property. It means that there is one -- and only one -- solution.
A: \bu{unique}ness
Picard's existence theorem guarantees that a solution exists and is unique for a first-order IVP if the derivative of the function has this form of continuity. It requires that the difference at any two points on a function be less than or equal to a rational number multiplied by the difference in independent variable.
A: \bu{Lipschitz} continuity [or \bu{Lipschitz} condition]
The three most common types of this technique are aggregate analysis, the accounting method, and the potential method. For 10 points each:
Name this technique for analyzing an algorithm's runtime in which one averages over a worst-case \i{sequence} of operations. Hence, it is concerned with the actual runtime.
A: \bu{amortized analysis} [do NOT accept other answers]
Robert Tarjan introduced amortized analysis as a formal method and developed a wide array of data structures. With Daniel Sleator, Tarjan created splay trees, which are self-adjusting examples of the "search" type of these trees.
A: rooted \bu{binary} search tree [or a \bu{bifurcating arborescence}; or \bu{2-ary} tree; prompt on "k-ary", "M-ary", or "N-ary" "tree"]
As amortized analysis gives an upper bound on an algorithm's run time, it uses this notation. A less common alternative is big Omega, which gives an asymptotic lower bound.
A: \bu{big O} notation [or \bu{big Omicron}]
In C, the alloca keyword allocates space on this thing, which is thus automatically freed when the function returns to its caller. Every function call reserves a frame, or activation record, on this thing, which is where the function's local variables are stored unless they are allocated using malloc, in which case they are stored on the heap. Big O of n space is required on it by recursive functions -- with n the depth of recursive calls -- but that can be reduced to big O of one by implementing tail recursion, thus avoiding a common (*)} "overflow". The first-taught way to make depth-first search non-recursive is to use this data structure. Reverse Polish notation is conceptualized using it. Insertion and deletion in it is called push and pop, respectively. For 10 points, name this last-in first-out data structure that contrasts with the first-in first-out queue.
A: \bu{stack}}
While working at Göttingen, Johann Nikuradse did seminal experiments in varying this quantity with sands. For open channels, a coefficient named for this quantity is found in the denominator of the formula for the Chézy coefficient and the denominator of Manning's formula, in both cases also being called Manning's n. This quantity is divided by about 3.7 times hydraulic diameter in an equation valid only for turbulent flow that's used to calculate the Darcy (*)} friction factor. The relative form of this quantity is given by dividing its absolute value, represented epsilon, by the inside diameter of the pipe. It is plotted against the Reynolds number in a Moody diagram. For 10 points, give this measure of the surface imperfections or irregularities of pipe walls that is disregarded when considering smooth pipes.
A: internal pipe \bu{roughness}