#
CS191 21 04 17
Wed, Apr 17, 2019

# Hoare 1969

Sorting of a mass of items where the keys of each of these items are held in locations lower than a dividing line.

The lower pointer starts at lower address, moves upward in the store, while the other upper pointer starts at higher address and moves downward.

The pointer refers to the first location of the block. It is sufficient to adopt the rule of always postponing the processing of the larger of the two segments.

The number of exchanges will vary from occasion to occasion, and the partition is achieved if all the values of $r$ between 1 and $N$ inclusive are equally likely, giving them a probability of $\frac{1}{N}$

A lower resulting segment is $\frac{(N-r-1)(r-1)}{N}$. To partition a segment of $N$ items ultimately take the form.

[
a N+b+\frac{c}{N}
]
The exact solution of the recurrence equation is the following:
[
\begin{array}{l}{T*{N}=\frac{2(N-1)}{M(M-1)} \sum*{1}^{M-1} T*{r}+\frac{(N+1) c}{M(M+1)}} \ {-\left[\frac{2(N+1)}{M-1}-1\right] b} \ {-\left[2(N-1) \sum*{M=1}^{N} \frac{1}{r}-\frac{4(N+1)}{M+1}+N+4\right] a}\end{array}
]

Optimization of Key Comparison Loop in that quicksort is one of the methods used to avoid requirement by the use of sentinels. Sentinels exist in the form of items with impossibly large and small key values placed at the end of the data to be sorted. Each test is made with both pointers stopped and the exchange between different comparisons. If pointers are not crossed, an exchange is made and partition is continued. Meanwhile, the crossing over comes to an end otherwise.

This is a good example of good design in programming algorithms. I like the mathematical notation and the rigor of showing correctness.

# De Millo, Lipton, Perlis 1979

Alan Peris led the chair in Yale such that computer science has become an intellectually independent discipline in the institutions that provide influential models.

The big idea is that programming should be made more mathematics-like in order to increase one’s confidence in software. A proof only creates one step in confidence, never absolute confidence.

Principia Mathematica is an example of formalist view of mathematics. Russell showed how to go beyond elementary facts of arithmetic, what can be done in principle and what cannot be done in practice.

Verifies always face a tradeoff between efficiency and robustness. Ideally, one should have code that checks through as many test cases as possible, but realistically, there is only so much limited time for creating and running tests that judgment is needed to decide how to best allocate resources to running tests.