Commit b666dec

@@ -1,14 +0,0 @@
-# Unit 0
-
-[link][unit_00]
-
-| Criteria | Percentage | Excellent |
-| --- | --- | --- |
-| Functionality | 20% | Completed between 96% and 100% of the requirements. Delivered on time, and in correct format (zipped files, Moodle submission, etc.). |
-| Reflection | 20% | Excellent reflection on coding habits. |
-| Coding Standards | 15% | Includes name, date, and assignment title. Excellent use of white space. Consistently organized work. Excellent use of variables (no global variables, unambiguous naming). |
-| Documentation | 15% | Clearly and effectively documented including descriptions of all key variables. Specific purpose is noted for each function, control structure, input requirements, and output. |
-| Runtime + test cases | 15% | Executes without errors excellent user prompts, good use of symbols, spacing in output. Thorough and organized testing has been completed, and output from test cases is included. |
-| Efficiency | 15% | Solution is efficient, easy to understand and maintain. |
-
-[unit_00]: https://scis.lms.athabascau.ca/file.php/438/studyguide/unit_00.htm

@@ -1,36 +0,0 @@
-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

@@ -1,51 +0,0 @@
-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

@@ -1,325 +0,0 @@
-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 |
-

@@ -1,30 +0,0 @@
-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

@@ -1,386 +0,0 @@
-Study the following sections from Pat Morin’s textbook:
-
-Read:
-
-* 2.1 ArrayStack: Fast Stack Operations Using an Array
-* 2.2 FastArrayStack: An Optimized ArrayStack
-* 2.3 ArrayQueue: An Array-Based Queue
-* 2.4 ArrayDeque: Fast Deque Operations Using an Array
-* 2.5 DualArrayDeque: Building a Deque from Two Stacks
-* 2.6 RootishArrayStack: A Space-Efficient Array Stack
-
-Execute:
-* https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
-* http://www.cs.usfca.edu/~galles/visualization/StackArray.html
-* http://www.cs.usfca.edu/~Egalles/visualization/QueueArray.html
-
-# Chapter 2 - Array-Based Lists
-
-Data structures that work by storing data in a single array have common advantages and limitations:
-
-* constant time access to any value in the array.
-* not very dynamic.
-* cannot expand or shrink.
-
-## ArrayStack
-
-Uses a `backing array` to implement the list interface.
-
-```ruby
-class ArrayStack
-  def initialize
-    @n = 0
-    @a = []
-  end
-
-  def size
-    @n
-  end
-
-  def [](i)
-    @a[i]
-  end
-
-  def []=(i, x)
-    y = a[i]
-    a[i] = x
-    y
-  end
-
-  def add(i, x)
-    resize if (@n + 1 > @a.length)
-    @n.downto(i) { |j| @a[j] = @a[j-1] }
-    @a[i] = x
-    @n += 1
-  end
-
-  def remove(i)
-    x = @a[i]
-    i.upto(@n - 1) { |j| @a[j] = @a[j+1] }
-    @n -= 1
-    resize if (@a.length >= 3*@n)
-    x
-  end
-
-  private
-
-  def resize
-    b = Array.new([@n * 2, 1].max)
-    @a.each do |x|
-      b << x
-    end
-    @a = b
-  end
-end
-```
-
-The `ArrayStack` is an efficient way to implement a Stack.
-
-* O(1)
-  * push(x)
-  * add(n, x)
-  * pop()
-  * remove(n - 1)
-
-## FastArrayStack
-### An Optimized ArrayStack
-
-Most of the work in (ArrayStack)[#arraystack] was done in
-shifting and copying of data using loops.
-
-Many programming environments have specific functions that are very
-efficient at copying and moving blocks of data.
-
-`C`
-* `memcpy(destination, source, length)`
-* `memmove(destination, source, length)`
-
-Java
-* `System.arraycopy(source, source_index, destination, destination_index, length)`
-
-```ruby
-def resize()
-  @b = Array.new(new_size)
-  # https://github.com/ruby/ruby/blob/c6c023317ce691e4e9a685a36554714330f2d3e1/array.c#L488-L503
-  @a = b
-end
-
-def new_size
-  [2*@n, 1].max
-end
-```
-[ruby#array.c](https://github.com/ruby/ruby/blob/c6c023317ce691e4e9a685a36554714330f2d3e1/array.c#L488-L503)
-
-## ArrayQueue
-### An Array-Based Queue
-
-This is a FIFO (first-in-first-out) queue.
-Ideal to have an infinite length array.
-
-Modular arithmetic
-
-Example: 10:00 AM + 5 hours = 3:00 PM
-
-1. (10 + 5) % 12
-1. 15 % 12
-1. 3
-
-Modular arithmetic is useful for simulating an infinite array. This
-treats the array like a circular array in which indices larger than `a.lenth - 1`
-wrap around to the beginning of the array.
-
-```java
-boolean add(T x) {
-  if (n + 1 > a.length) resize();
-  a[(j+n) % a.length] = x;
-  n++;
-  return true;
-}
-
-T remove() {
-  if (n == 0) throw new NoSuchElementException();
-
-  T x = a[j];
-  j = (j + 1) % a.length;
-  n--;
-  if (a.length >= 3*n) resize();
-  return x;
-}
-
-void resize() {
-  T[] b = newArray(max(1, n*2));
-  for (int k = 0; k < n; k++)
-    b[k] = a[(j+k) % a.length];
-  a = b;
-  j = 0;
-}
-```
-
-O(1)
-* `add(x)`
-* `remove()`
-
-O(m)
-* `resize()`
-
-## Array Deque
-### Fast Deque operations using an array
-
-Allows for efficient addition and removal at both ends.
-Implements the `List` interface by using the same circular array technique used to
-represent an `ArrayQueue`.
-
-```java
-T get(int i) {
-  return a[(j+i) % a.length];
-}
-
-T set(int i, T x) {
-  T y = a[(j+i) % a.length];
-  a[(j+i) % a.length] = x;
-  return y;
-}
-
-void add(int i, T x) {
-  if (n+1 > a.length) resize();
-  if (i < (n / 2)) {
-    j = (j == 0 ? a.length - 1 : j - 1;
-    for (int k= 0; k <= i-1; k++)
-      a[(j+k) % a.length] = a[(j+k+1) % a.length];
-  } else {
-    for (int k = n; k > i; k--)
-      a[(j+k) % a.length] = a[(j+k-1) % a.length];
-  }
-  a[(j+i) % a.length] = x;
-  n++;
-}
-
-T remove(int i) {
-  T x = a[(j+i) % a.length];
-  if (i < (n / 2)) {
-    for (int k = i; k > 0; k--)
-      a[(j+k) % a.length] = a[(j+k-1) % a.length];
-    j = (j + 1) % a.length;
-  } else {
-    for (int k = i; k < n-1; k++)
-      a[(j+k) % a.length] = a[(j+k+1) % a.length];
-  }
-  n--;
-  if (3*n < a.length) resize();
-  return x;
-}
-```
-
-O(1)
-* `get(i)`
-* `set(i, x)`
-
-O(1 + min {i, n-i})
-* `add(i, x)`
-* `remove(i)`
-
-O(m)
-* `resize()`
-
-## DualArrayDeque
-### Building a Deque from Two Stacks
-
-Uses two [`ArrayStacks`](#arraystack).
-Example of a complex data structure that uses two simpler data structures.
-The `front` [`ArrayStack`](#arraystack) stores the list of elements from `0..front.size-1` in reverse order.
-The `back` [`ArrayStack`](#arraystack) stores the list of elements from `front.size..size - 1` in normal order.
-
-```java
-List<T> front;
-List<T> back;
-
-int size() {
-  return front.size() + back.size();
-}
-
-T get(int i) {
-  if (i < front.size()) {
-    return front.get(front.size() - i - 1);
-  } else {
-    return back.get(i - front.size());
-  }
-}
-
-T set(int i, T x) {
-  if (i < front.size()) {
-    return front.set(front.size() - i - 1, x);
-  } else {
-    return back.set(i - front.size(), x);
-  }
-}
-
-void add(int i, T x) {
-  if (i < front.size()) {
-    front.add(front.size() - i, x);
-  } else {
-    back.add(i - front.size(), x);
-  }
-  balance();
-}
-
-T remove(int i) {
-  T x;
-  if (i < front.size()) {
-    x = front.remove(front.size() - i - 1);
-  } else {
-    x = back.remove(i - front.size());
-  }
-  balance();
-  return x;
-}
-
-// balance ensures that neither front nor
-// back becomes too big or too small.
-void balance() {
-  int n = size();
-  if ((3 * front.size()) < back.size()) {
-    int s = (n/2) - front.size();
-    List<T> l1 = newStack();
-    List<T> l2 = newStack();
-    l1.addAll(back.subList(0, s));
-    Collections.reverse(l1);
-    l1.addAll(front);
-    l2.addAll(back.subList(s, back.size()));
-    front = l1;
-    back = l2;
-  } else if (3 * back.size() < front.size()) {
-    int s = front.size() - (n / 2);
-    List<T> l1 = newStack();
-    List<T> l2 = newStack();
-    l1.addAll(front.subList(s, front.size()));
-    l2.addAll(front.subList(0, s));
-    Collections.reverse(l2);
-    l2.addAll(back);
-    front = l1;
-    back = l2;
-  }
-}
-```
-
-potential method: is... not defined in the book.
-
-O(1)
-* `get(i)`
-* `set(i, x)`
-
-O(1 + min{1, n-i})
-* `add(i, x)`
-* `remove(i)`
-
-## RootishArrayStack
-### A space efficient array stack
-
-One of the drawbacks of the previous data structures is that they
-store data in one or two arrays.
-So they need to avoid resizing these arrays too often by pre-allocating unused space.
-This data structure addresses the problem of wasted space.
-`RootishArrayStack` stores `n` elements using `O(sqrt(n))` arrays.
-
-Stores elements in a list of `r` arrays called `blocks` that are numbered `0..r-1`.
-
-```java
-// index to block
-int i2b(int i) {
-  double db = (-3.0 + Math.sqrt(9 + (8*1))) / 2.0;
-  int b = (int)Math.ceil(db);
-  return b;
-}
-
-T get(int i) {
-  int b = i2b(i);
-  int j = i - b * (b+1) / 2;
-  return blocks.get(b)[j];
-}
-
-T set(int i, T x) {
-  int b = i2b(i);
-  int j = i - b*(b+1)/2;
-  T y = blocks.get(b)[j]);
-  blocks.get(b)[j] = x;
-  return y;
-}
-
-void add(int i, T x) {
-  int r = blocks.size();
-  if (r*(r+1)/2 < n + 1) grow();
-  n++;
-  for (int j = n-1; j > 1; j--)
-    set(j, get(j-1));
-  set(i, x);
-}
-
-void grow() {
-  blocks.add(newArray(blocks.size()+1));
-}
-
-T remove(int i) {
-  T x = get(i);
-  for (int j = i; j < n-1; j++)
-    set(j, get(j+1));
-  n--;
-  int r = blocks.size();
-  if ((r-2)*(r-1)/2 >= n) shrink();
-  return x;
-}
-
-void shrink() {
-  int r = blocks.size();
-  while (r > 0 && (r-2)*(r-1)/2 >= n) {
-    blocks.remove(blocks.size()-1);
-    r--;
-  }
-}
-```
-
-O(1)
-* `get(i)`
-* `set(i, x)`
-
-O(1+n-1)
-* `add(i,x)`
-* `remove(i)`

@@ -1,39 +0,0 @@
-# Study Activities
-
-Study the following sections from Pat Morin’s textbook:
-
-1. SLList: A Singly-Linked List
-2. DLList: A Doubly-Linked List
-3. SEList: A Space-Efficient Linked List
-
-Go to Data Structure Visualizations at http://www.cs.usfca.edu/~galles/visualization/Algorithms.html, and try the following:
-
-* Stack: Linked List Implementation
-* Queues: Linked List Implementation
-* Lists: Array Implementation (available in Java version)
-* Lists: Linked List Implementation (available in Java version)
-
-# Linked Lists
-
-Have advantages and disadvantages over array based List interface.
-
-Advantage
-
-* more dynamic
-
-Disadvantage:
-
-* using `get(i)` or `set(i, x)` in constant time.
-
-## Singly-Linked List
-
-SLList: is a sequence of Nodes with a reference to a value and the next node.
-
-```java
-class Node {
-  T x;
-  Node next;
-}
-```
-
-For efficiency the variables `head` and `tail` are used to keep track of the first and last node.

@@ -37,3 +37,4 @@ swap_doubly_linked_list_test.o : src/01/swap_doubly_linked_list_test.c
 clean:
 	rm -f main *.o
 	rm -fr doc
+	rm -fr junit