#
CS191 17 04 03
Wed, Apr 3, 2019

# Reflecting on Speaker Notes

It isn’t all positive, where if you want to get the sense of the vote other by town meetings.

When you have multiple users separating from each other, you really cannot say how people are making the correct bindings, unless the tape s simple. Typesafe world in programming right now. Packets of aggregates have every field’s safety not guaranteed.

The hardware barriers are the things that don’t shape the Moore’s law curve.

# Gale, Shapley 1962

This is a good paper in that it utilizes certain principles of the “algorithm” and “computer” without even using the word “algorithm” or “computer”.

Colleges and marriages have a matching problem challenge that warrants more investigation. This matching problem is seen in colleges and marriages. A set of n applicants assigned m colleges and qi is the quota of the ith college, each applicant ranks the college in order of preference just as each mates rank their anticipated lovr in order of preference.

Ultimately an algorithm allows for stable assignments and a marriage problem to persist such that the ranking of the individuals is preserved across all individuals.

There exists an optimal solution for this problem. Like so, the knowledge of calculus is not presupposed and individuals do not need to know how to count. The way this question is formalized into a mathematical problem is certainly most intriguing.

# Blum, Floyd, Pratt, Rivest, Tarjan 1972

This paper is pretty interesting in discussing complexity of recursive functions. We have Rabin’s axiomatic approach, which is determining whether a legal measure of functional complexity. This definition is the number of steps needed to compute a function and the amount of machine tape needed for a computation.

This is illustrative of Turing’s Turing machine, which is pretty influential with the tape design. The decision for a machine independent complexity theory simply means that the computations have different types of computations.

For example, to compute the function within a class of multitape machines, the class with a base 2 input-output will compute certain functions for measuring complexity, independent of the class of machines.

The class of speed-up theorem illustrates the 0-1 valued recursive functions that computes the number of steps in a compression machine.

The compression theorem is the inverse of the opposite of the speed-up theorem. We are corresponding to the machine such that another computation is faster.

The number of steps needed to computer f wedges between the bounds $\Phi$ and $\Phi _i^7$

# Knuth 1976

Knuth’s 1976 paper discusses the fundamental classical question of $O(f(n))$ to stand for any function whose magnitude is bounded above by a constant times $f(n)$ for extremely large n. Classical literature often dictates that these writings of $O$ notation serves some useful purpose, but it is hard to say what purpose this is often used for.

The beginning of big O notation is formalized in the following way:

$O(f(n))$ denotes the set of all $g(n)$ such that there exist positive constants C and $n_0$ with $|g(n)|\leq C f(n)$ for all $n\geq n_0$. Meanwhile, $\Omega(f(n))$ denotes the set of all $g(n)$ such that there exist positive constants $C$ and $n_0$ with $g(n) \geq C f(n)$ for all $n \geq n_0$. This is very consistent with the big O notation learned in CS124: Data Structures and Algorithms.