Misc Flashcards
Online vs offline algo definition
an online algorithm[1] is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start.
In contrast, an offline algorithm is given the whole problem data from the beginning and is required to output an answer which solves the problem at hand
Performance of online vs offline algorithms
For many problems, online algorithms cannot match the performance of offline algorithms
What are competitive online algorithms?
If the ratio between the performance of an online algorithm and an optimal offline algorithm is bounded, the online algorithm is called competitive.[1]
Random access
more precisely and more generally called direct access) is the ability to access an arbitrary element of a sequence in equal time or any datum from a population of addressable elements roughly as easily and efficiently as any other, no matter how many elements may be in the set. In computer science it is typically contrasted to sequential access which requires data to be retrieved in the order it was stored.
NALSD
Non abstract large system design
Cons
is a fundamental function in most dialects of the Lisp programming language. cons constructs memory objects which hold two values or pointers to values.
Big O vs little o notation
think of big-O meaning “grows no faster than” (i.e. grows at the same rate or slower) and little-o meaning “grows strictly slower than”
Cache oblivious algorithm
an algorithm designed to take advantage of a CPU cache without having the size of the cache (or the length of the cache lines, etc.)
inplacement/in-place-algorithm
an algorithm which transforms input using no auxiliary data structure. However, a small amount of extra storage space is allowed for auxiliary variables. The input is usually overwritten by the output as the algorithm executes. An in-place algorithm updates its input sequence only through replacement or swapping of elements. An algorithm which is not in-place is sometimes called not-in-place or out-of-place.
Are sets unique
Yes
In core vs out of core
In core = all data can be held in RAM
Out of core algorithms are also called
External memory algorithms
Is dynamic programming simply recursion plus caching?
Essentially. But more specifically it is the concept of dividing a problem into sub problems, and any time one of those sub problems is solved, caching the solution such that in the future if the sub problem is called, it takes O(1) to solve the problem
