Number Theory
The number theory is a branch of mathematics that explores
integers and their properties, is the basis of cryptography,
coding theory, computer security, e-commerce,
etc.
Divisio...
Sophisticated Search and
Modification
Fuzzy Search
When we search things like the movie title, we often want to use the
fuzzy search. For example, we want that a search of “2001,
space odyssey...
Sorting in Linear Time
CountingSort
To circumvent the bound of comparison sort, we need to get more
information than mere comparisons. Since elements to be sorted are often
numbers or strings, ...
Postprocessing Queries
Sorting
We have a single construct in SQL that sorts the result set:
123SELECT title, year_released FROM movies ORDER BY year_released This will return all movies, startin...
Random Variables and
Distributions
Introduction
Definition of Random
Variable
To simplify the complex problems into functional operations and unify
their studys, we need to use the random var...
Algorithms and Complexity
Asymptotic Notation
Big-
Notation
Definition: Big- Notation
Let and be functions from set of integers or
the set of real numbers to...
Randomization and Lower
Bounds
A Randomized Version of
QuickSort
Choosing the right pivot element can be tricky since we have no idea
a priori which element can be a good pivot. A (surprisingl...
QuickSort
Introduction
The quick sort is also a divide-and-conquer algorithm just like the
merge sort:
Divide:
Pick some element called pivot.
Move it to its final location in the sorted ...
Advanced Queries, Part 2
JOIN
Outer JOIN
An example of using JOIN is to look for the directors of
American movies released in 2018:
123456789SELECT m.year_released, m.title, p.first_name, p.su...
HeapSort
Introduction
The idea behind HeapSort is to find the largest element and move it
to the end of the array. Then we repeat this process with remaining
elements until the array is sorted....
