re-arrange folders

5 files changed, 442 insertions, 0 deletions

diff --git a/unit/01/README.md b/unit/01/README.md
new file mode 100644
index 0000000..2087e64
--- /dev/null
+++ b/unit/01/README.md
@@ -0,0 +1,325 @@
+Read:
+
+* https://en.wikipedia.org/wiki/List_of_algorithms
+* https://www.topcoder.com/community/competitive-programming/tutorials/the-importance-of-algorithms/
+
+Watch:
+
+* https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/lecture-videos/lecture-1-algorithmic-thinking-peak-finding/
+
+## The need for efficiency
+
+* Number of operations
+* Processor speeds
+* Bigger data sets
+
+## Interfaces
+
+An `interface` sometimes also called an `abstract data type`, defines the
+set of operations supported by a data structure and the semantics,
+or meaning, of those operations.
+
+### Queue
+
+* `add(x)`: add a value to the queue (a.k.a enqueue, push)
+* `remove()`: remove the next value from the queue and return it. (a.k.a. dequeue, shift)
+
+FIFO (first-in-first-out) removes items in the same order they were added.
+
+A priority Queue always removes the smallest element from the Queue, breaking ties arbitrarily.
+`remove()` is sometimes called `deleteMin()`.
+
+### Stack
+
+LIFO (last-in-first-out) the most recently added element is the next one removed.
+
+* `add(x)`: add a value to the queue (a.k.a enqueue, push)
+* `remove()`: `pop()` the item at the top of the stack.
+
+### Deque
+
+Is a generalization of both the FIFO Queue and the LIFO Queue (stack).
+A deque represents a sequence of elements, with a front and a back.
+
+### List
+
+Represents a sequence, x0,...,xn-1, of values.
+
+* `size()`: return the length of the list.
+* `get(i)`: return the value xi
+* `set(i, x)`: set the value of xi to equal to x
+* `add(i, x)`: add x at position i, displacing xi,...,xn-1;
+* `remove(i)`: remove the value xi displacing xi+1,...,xn-1;
+
+The operations can be implemented with a Deque interface.
+
+* `addFirst(x)` -> `add(0, x)`
+* `removeFirst()` -> `remove(0)`
+* `addLast(x)` -> `add(size(), x)`
+* `removeLast()` -> `remove(size() - 1)`
+
+### USet
+
+The `USet` interface represents an unordered set of unique elements, which
+mimics a mathematical set. A `USet` contains `n` distinct elements; no
+element appears more than once; the elements are in no specific order. A
+`USet` supports the following operations:
+
+* `size()`: return the number, `n`, of elements in the set.
+* `add(x)`: add the element `x` to the set if not already present;
+* `remove(x)`: remove `x` from the set;
+* `find(x)`: find `x` in the set if it exists
+
+### SSet
+
+The `SSet` interface represents a sorted set of elements. An `SSet` stores elements
+from some total order so that any two elements x and y can be compared. In code
+examples, this will be done with a method called `compare(x, y)` in which:
+
+* < 0 if x < y
+* > 0 if x > y
+* = 0 if x == y
+
+An `SSet` supports the `size()` and `add()` and `remove()` methods with
+exactly the same semantics as in the `USet` interface. The difference
+between a `USet` and an `SSet` is in the `find(x)` method:
+
+> successor search: locate x in the sorted set;
+> find the small element y in the set such that y >= x.
+> return y or null if no such element exists.
+
+
+The extra functionality provided by a SSet usually comes with a price that
+includes both a larger running time and a higher implementation complexity.
+SSet implementations may have a `find(x)` running time of of logarithmic
+and a USet may have a running time of constant time.
+
+
+## Math Review
+
+### Exponentials and Logarithms
+
+The expression b^x denotes the number `b` raised to the power of `x`.
+
+* when x is negative, b^x = 1/(b^-x)
+* when x is 0, b^x = 1
+
+
+```text
+b^x = b * b * ... x b
+      |____________|
+            |
+         x times
+```
+
+```ruby
+b ** x = (x.times.inject(1) { |m, _| m * b }
+```
+
+```irb
+irb(main):001:0> 2 ** 10
+=> 1024
+irb(main):002:0> 10.times.inject(1) { |m, _| m * 2 }
+=> 1024
+```
+
+log b(k) deontes base-b logarithm of k. i.e b^x = k
+
+```text
+  log b(k) == b^x = k
+```
+
+```ruby
+irb(main):016:0> 2 ** 10
+=> 1024
+irb(main):017:0> Math.log2(1024)
+=> 10.0
+```
+
+An informal way to think about logarithms is to think of logb(k) as the number
+of times we have to divide k by b before the result is less than or equal to 1.
+
+For example, when one does binary search, each comparison reduces the number of
+possible answers by a factor of 2. This is repeated until there is at most one
+possible answer. Therefore the number of comparisons done by binary search when there
+are initially at most n + 1 possible answers is at most log2(n+1).
+
+Another logarithm that comes up several times in this book is the natural logarithm.
+Here we use the notation ln k to denote log e(k), where e -- Euler's constant -- is given by:
+
+![eulers constant](./eulers-constant.png)
+
+The natural logarithm comes up frequently because it is the value of a particularly common integral.
+
+### Factorials
+
+> n!: pronounced n factorial. `n! = 1 * 2 * 3 ... n`
+
+* 0! is defined as 1
+
+```ruby
+irb(main):001:0> class Integer
+irb(main):002:1>   def !
+irb(main):003:2>     (1..self).inject(:*)
+irb(main):004:2>   end
+irb(main):005:1> end
+=> :!
+irb(main):006:0> !2
+=> 2
+irb(main):007:0> !3
+=> 6
+irb(main):008:0> 2.!
+=> 2
+irb(main):009:0> 3.!
+=> 6
+```
+
+#### binomial coefficient
+
+* `(n/k)` pronounced "n choose k".
+* counts the number of subsets of an `n` element set that have size `k`.
+
+i.e. the number of ways of choosing k distinct integers from the set {1,...,n}.
+
+
+### Asymptotic Notation
+
+When analyzing data structures we want to talk about the running times of various operations.
+The exact running times will, of course, vary from computer to computer and even from run to run on an individual computer.
+When we talk about the running time of an operation we are referring to the number of computer instructions
+performed during the operation. Instread of analyzing running times exactly, we will use the so-called
+big-Oh notation: For a function `f(n)`, `O(f(n))` denotes a set of functions.
+
+
+E.g.
+
+```c
+void snippet() {
+  for (int i = 0; i < n; i++)
+    a[i] = i;
+}
+```
+
+* 1 assignment (int i = 0;
+* n + 1 comparisons (i < n)
+* n increments (i++)
+* n array offset calculations (a[i])
+* n indirect assignments (a[i] = i)
+
+We could write thi running time as:
+
+```text
+T(n) = a + b(n+1) + c*n + d * n + en,
+
+where a, b, c, d and e are constants that depend on the machine running the code and
+represent the time to perform assignments, comparisons, increment operations, array offset calculations,
+and indirect assigments, respectively.
+```
+
+With big-Oh notation the running time can be simplified to:
+
+```text
+T(n) = O(n)
+```
+
+## The Model of Computation
+
+To analyze the theoretical running times of operations on data structures we use a
+mathematical model of computation. We use the w-bit word-RAM model.
+
+RAM stands for Random Access Machine. In this model we have access to a
+random access memory consistenting of cells, each of which stores a w bit `word`.
+This implies that a memory cell can represent, for example, any integer in the set {0,...,2^w - 1}.
+
+In the word-RAM model, basic operations on words take constant time. This includes arithmetic operations
+`(+, -, *, /, %)`, comparisons `(<, >, =, <=, >=)` and bitwise boolean operations (bitwise AND, OR, and
+exclusive-OR).
+
+Any cell can be read or written in constant time. A computer's memory is managed by a memory management
+system from which we can allocate or deallocate a block of memory of any size we would like.
+Allocating a block of memory of size `k` takes `O(k)` time and returns a reference (a pointer) to
+the newly-allocated memory block.
+
+The word-size `w` is a very important parameter of this model. The only assumption we will
+make about `w` is that the lower bound `w >= log(n)`, where n is the number of elements stored in
+any of our data structures.
+
+Space is measured in words, so that when we talk about the amount of space used by a data structure, we
+are referring to the number of words of memory used by the structure. All of our data structures
+store values of generic type T, and we assume an element of type T occupies one word of memory.
+
+The w-bit word RAM mode is fairly close match for the 32-bit Java Virtual Machine when w = 32.
+The data structures presented in this book don't use any special tricks that are not implementable on the
+JVM and most other architectures.
+
+
+Performance of a data structure
+
+1. Correctness: The data structure should correctly implement its interface.
+2. Time complexity: The running times of operations on the data structure should be as small as possible.
+3. Space complexity: The data structure should use as little memory as possible.
+
+Running time guarantees:
+
+1. Worst-case running times: These are the strongest kind of running time guarantees. If the worst case is `f(n)` then one operation will never take more than `f(n)` time.
+2. Amortized running times: If we say that the amortized running time of an operation in a data structure is `f(n)`, then this means that the cost of a typical operation is `f(n)`.
+3. Expected running times: If we say that the expected running time of an operation on a data structure is `f(n)`, this means that the actual running time is a random variable and the expected value of this random variable is at most `f(n)`.
+
+Worst-case versus amortized cost:
+
+Home costs $120,000.00
+10 year mortgage with a monthly payment of $1200.00/month.
+Worst case monthly payment is $1200.00/month
+
+Buying the house costs $120,000.00. After 10 years, this works out to $1,000.00/month.
+
+Worst-case versus expected cost:
+
+Fire insurance on $120,000.00 home.
+Insurance company charges $15.00/month and expects a cost of $10.00/month.
+Do we pay the $15.00/month or try to save $10.00/month ourselves. $10.00/month
+is less than $15.00/month but the actual cost may be much higher. If the whole
+house burns down then it will cost $120,000.00.
+
+## Code Samples
+
+List Implementations
+
+| name | get(i)/set(i, x) | add(i, x) / remove(i) |
+| --- | --- | --- |
+| ArrayStack | O(1) | O(1 + n - i)^a |
+| ArrayDeque | O(1) | O(1 + min {i, n - i})^a |
+| DualArrayDeque | O(1) | O(1 + min{i, n-1})^a |
+| RootishArrayStack | O(1) | O(1 + n - i)^a |
+| DLList | O(1 + min{i, n-1}) | O(1 + min{i,n-1}) |
+| SEList | O(1 + min{i, n-1}/b) | O(b + min{i,n-1}/b)^a |
+| SkiplistList | O(logn)^e | O(logn)^e |
+
+USet Implementations
+
+| name | find(x) | add(x)/remove(x) |
+| --- | --- | --- |
+| ChainedHashTable | O(1)^e | O(1)^a,e |
+| LinearHashTable | O(1)^e | O(1)^a,e |
+
+SSet Implementations
+
+| name | find(x) | add(x) / remove(x) |
+| --- | --- | --- |
+| SkiplistSSet | O(logn)^e | O(logn)^e |
+| Treap | O(logn)^e | O(logn)^e |
+| ScapegoatTree | O(logn) | O(logn)^a |
+| RedBlackTree | O(logn) | O(logn) |
+| BinaryTrie | O(w) | O(w) |
+| XFastTrie | O(logw)^a,e | O(w)^a,e |
+| YFastTrie | O(logw)^a,e | O(logw)^a,e |
+| BTree | O(logn) | O(B + logn)^a |
+| Btree^x | O(logb n) | O(log b n) |
+
+Priority Queue Implementations
+
+| name | findMin() | add(x)/remove() |
+| --- | --- | --- |
+| BinaryHeap | O(1) | O(logn)^a |
+| MeldableHeap | O(1) | O(logn)^e |
+
diff --git a/unit/01/dyck_word.rb b/unit/01/dyck_word.rb
new file mode 100644
index 0000000..9cdea96
--- /dev/null
+++ b/unit/01/dyck_word.rb
@@ -0,0 +1,36 @@
+require 'bundler/inline'
+
+gemfile do
+  source 'https://rubygems.org'
+
+  gem 'minitest'
+end
+
+require 'minitest/autorun'
+
+=begin
+A Dyck word is a sequence of +1’s and -1’s with the property that the sum of any prefix
+of the sequence is never negative.
+For example, +1,−1,+1,−1 is a Dyck word, but +1,−1,−1,+1 is not a Dyck word since the prefix +1 − 1 − 1 < 0.
+
+Describe any relationship between Dyck words and Stack push(x) and pop() operations.
+=end
+
+class Example < Minitest::Test
+  def dyck_word?(stack)
+    sum = 0
+    stack.each do |item|
+      return if sum.negative?
+      sum += item
+    end
+    true
+  end
+
+  def test_valid_word
+    assert dyck_word?([1, -1, 1, -1])
+  end
+
+  def test_invalid_word
+    refute dyck_word?([1, -1, -1, 1])
+  end
+end
diff --git a/unit/01/eulers-constant.png b/unit/01/eulers-constant.png
new file mode 100644
index 0000000..ed64e0b
--- /dev/null
+++ b/unit/01/eulers-constant.png
diff --git a/unit/01/matched_string.rb b/unit/01/matched_string.rb
new file mode 100644
index 0000000..2836d16
--- /dev/null
+++ b/unit/01/matched_string.rb
@@ -0,0 +1,51 @@
+require 'bundler/inline'
+
+gemfile do
+  source 'https://rubygems.org'
+
+  gem 'minitest'
+end
+
+require 'minitest/autorun'
+
+=begin
+A matched string is a sequence of {, }, (, ), [, and ] characters that are properly matched.
+For example, “{{()[]}}” is a matched string, but this “{{()]}” is not, since the second { is matched with a ].
+Show how to use a stack so that, given a string of length n, you can determine if it is a matched string in O(n) time.
+=end
+
+class Example < Minitest::Test
+  def matches?(open, close)
+    case open
+    when '('
+      return close == ')'
+    when '{'
+      return close == '}'
+    when '['
+      return close == ']'
+    else
+      raise [open, close].inspect
+    end
+  end
+
+  def matched_string?(string)
+    stack = []
+    string.chars.each do |char|
+      case char
+      when '{', '[', '('
+        stack.push(char)
+      else
+        return unless matches?(stack.pop, char)
+      end
+    end
+    stack.size.zero?
+  end
+
+  def test_valid
+    assert matched_string?("{{()[]}}")
+  end
+
+  def test_invalid
+    refute matched_string?("{{()]}")
+  end
+end
diff --git a/unit/01/reverse.rb b/unit/01/reverse.rb
new file mode 100644
index 0000000..a50f062
--- /dev/null
+++ b/unit/01/reverse.rb
@@ -0,0 +1,30 @@
+require 'bundler/inline'
+
+gemfile do
+  source 'https://rubygems.org'
+
+  gem 'minitest'
+end
+
+require 'minitest/autorun'
+
+=begin
+Suppose you have a Stack, s, that supports only the push(x) and pop() operations.
+Show how, using only a FIFO Queue, q, you can reverse the order of all elements in s.
+=end
+
+class Example < Minitest::Test
+  def test_valid
+    s = []
+    s.push('A')
+    s.push('B')
+    s.push('C')
+
+    q = Queue.new
+    3.times { q.enq(s.pop) }
+
+    x = 3.times.map { q.deq }
+
+    assert x == ['C', 'B', 'A']
+  end
+end