Remember, It is important to associate new knowledge with those you’ve already learnt.

---

Chapter 9. Stacks and Queues

Stacks and queues are used to handle temporary data.

Stacks follow the rule of LIFO, which stands for “Last In, First Out”. This means the item pushed onto a stack is always the first item poped from it. While a stack is not a built-in data structure in most programming languages, it’s still an abstract data type revolves around some other built-in data structure. A programming language linter is an example of the implementation using stacks, and the ‘undo’ function in a word processor is also a great use case for a stack.

Queues follow the rule of FIFO, which stands for “First In, First Out”.

Exercise

Write a function that uses a stack to reserve a string.
The stack class is given as follows:

# It is "class", not "Class"
class Stack
    def initialize
        # @ marks data as an instance variable, which means that every data is unique inside every instance
        @data = [] 
    end

    def push(element)
        @data << element
    end

    def pop
        # removes and returns the last element
        @data.pop
    end

    def read
        # only returns the last element
        @data.last
    end
end

Solution:

require_relative 'stack.rb'
def reverse_strings(string)
    reversed_string = ""
    # instance name = (class name).new
    stack = Stack.new

    # Turn strings into char's array by string.chars
    # (iterable object).each do |element|
    string.chars.each do |char| # Or string.each_char do |char|
        stack.push(char)
    end
    
    # stack.read likely evaluates to true as long as there is an element to read
    while stack.read
        reversed_string << stack.pop
    end
    
    return reversed_string
end

reversed_string = reverse_strings("abcdefg")
puts reversed_string

---

Chapter 10. Recursion

Recursion needs a base case to prevent from infinitely recalling itself. In the following case:

function countdown(number)
    console.log(number)
    if(number === 0) {
        return;
    } else{
        countdown(number - 1);
    }
}

0 is the base case for the countdown() function.
Stack overflow might be caused when the recursive functions are recalled again and again until the computer doesn’t have enough memory to hold all the data.

Exercise

Write a recursive function that prints all the numbers contained in this array.

array = [   1,
            2,
            3,
            [4, 5, 6],
            7, 
            [8,
                [9, 10, 11,
                    [12, 13, 14]
                ]
            ],
            [15, 16, 17, 18, 19,
                [20, 21, 22,
                    [23, 24, 25,
                        [26, 27, 29]
                    ], 30, 31
                ], 32
            ], 33
        ]

Solution:

# the base case would be the last element in the array
def print_numbers(array)
    array.each do |element|
        # .kind_of?(specific kind of data)
        # As a kind of data, start with a big letter: 'Array' instead of 'array'.
        if element.kind_of?(Array)
            print_numbers(element)
        else
            puts element
        end
    end
end

print_numbers(array)

---

Chapter 11. How to Write Recursive Functions

when writing recursive functions, it is important to identify the subproblem of the problem. Now, we have to write a function that sums up all the numbers in a given array. If we pass an array, [1, 2, 3, 4, 5] into the function, then the subproblem will be getting the sum of [2, 3, 4, 5], since [1, 2, 3, 4, 5] = 1 + [2, 3, 4, 5].

Factorial refers to calculate the production of consecutive positive numbers starting from 1 to n. The following code is an implementation example to proceed the factorial(n).

def factorial(n, i=1, product=1)
    return product if i > n
    return factorial(n, i + 1, product * i)
end

When going bottom up, we’re employing the same strategy for making the calculation as same as we’re using a loop:

def factorial(n)
    product = 1
    (1...n).each do |num|
        product *= num
    end
    return product
end

The code that solves the factorial problem by using top-down approach would be like this:

def factorial(n)
    return 1 if n == 1
    return n * factorial(n-1)
end

Technically, we assume that the function will return the correct value without necessarily understanding how the internal factorial functions work. Writing recursive function using a top-down approach can be achieved through three processes:

1. Imagine that someone else has alreay implemented the function you’re writing. You only need the return value of that function.
2. Identify the subproblem of the problem.
3. Add the base case.
   This approach benefits us with ignoring the nitty-gitty details of how the algorithms actually works and free our mind.

Exercise

Exercise 1

Use recursion to write a function that accepts an array of strings and returns the total numbers of characters across all the strings.
My solution:

def char_counter(array)
    # subproblem
    # pseudocode: char_counter(array) = sum(array[0]) + char_counter(array[1, array.length - 1])
    sum = array[0].length
    # base case
    return sum if array.length == 1 # using array.length to get the length of an array
    return sum + char_counter(array[1, array.length - 1])
end

array = ['ab', 'c', 'def', 'ghij']
sum = char_counter(array)
puts sum

The soluton given in the book:

def character_count(array)
    return 0 if array.length == 0
    return array[0].length + character_count(array[1, array.length - 1])
end

Exercise 2

Use recursion to write a function that accepts an array of strings and returns the total numbers of characters across all the strings.
My solution:

def get_even_numbers(array, even_numbers=[])
    # pseudocode: 
    # if array[0] is even, save it into an array
    # get_even_numbers(array[1, array.length - 1])
    if array[0] % 2 == 0
        even_numbers << array[0]
    end
    # base case
    if array.length == 1
        return even_numbers
    end
    return get_even_numbers(array[1, array.length - 1], even_numbers)
end

array = [1,2,3,4,5,6,12,14,15,16,33,42,53]
even_numbers = get_even_numbers(array)
puts even_numbers

The soluton given in the book:
First, let’s pretend the select_even function already works. Next, let’s identify the subproblem: if we try to select all the even numbers in an array, [1, 2, 3, 4, 5], the subproblem would be select_even([2, 3, 4, 5]) which returns [2, 4]. Finally, add the base case which returns [] under the situation where there are not any element in the array .

def select_even(array)
    return [] if array.empty?
    
    if array[0].even?
        return [array[0]] + select_even(array[1, array.length - 1])
    else
        return select_even(array[1, array.length - 1])
    end
end

Exercise 3

Write a function that acceptsa a number for N and returns the correct number from the “Triangular Numbers” series. The pattern begins as 1, 3, 6, 10, 15, 21, and continues onward with the Nth number in the pattern, which is N plus the previous number. For example, 3=1+2, 6=3+3, 10=6+4.
My solution:

def get_triangular_number(n)
    # 1. assume that someone else has already implemented this function, 
    # I only need the return value: Nth number would be N + (N-1)th
    # 2. identify the subproblem: get the (N-1)th number from the "Triangular Numbers"
    # 3. add the base case

    # base case
    return 1 if n == 1
    # Nth number = N + (N-1)th
    return n + get_triangular_number(n - 1)
end

puts get_triangular_number(6)

Exercise 4

Use recurtion to write a function that accepts a string and returns the first index that contains the character ‘x’. To keep things simple, assume that the string has at least one ‘x’.
My solution:

def get_index_of_x(string)
    # 1. assume that someone has already finished this function and returns that index.
    # 2. identify the subproblem: the function that returns the first index that contains the character 'x', 
    # which accepts a sub string of the original ranging from index $1$ to index $length - 1$
    # 3. add the base case: when we have found the index of 'x'

    # base case 
    return 0 if string[0] == 'x'
    # plus one since we have moved the first character every time we recursively call the function
    return get_index_of_x(string[1, string.length - 1]) + 1 
end

string = 'abcdefghijklmnopqrstuvwxyz'
puts get_index_of_x(string)

Exercise 5

the “Unique paths” problem: you have a grid of rows and columns. Write a function that accepts a number of rows and a number of columns, and calculates the number of possible “shortest” paths from the upper-leftmost square to the lower-rightmost square.
My solution:

def unique_paths_problem(number_of_rows, number_of_columns)
    # 1. assume that the function has been implemented. It would return the number of possible paths.
    # 2. identify the subproblem of this problem: you've already moved one step to the right, or one step downward, 
    # and you are supposed to calculate the rest number of possible paths 
    # by `unique_paths_problem(number_of_rows - 1, number_of_columns)` or `unique_paths_problem(number_of_rows, number_of_columns - 1)`. 
    # The total number of possible paths would be the sum of the number of moving to the right and the number of moving downward.
    # However, you would also have to consider the situation in which you have moved to the edge of the bottom side and the right side.
    # 3. add the base case

    # base case
    return 1 if number_of_rows == 1 && number_of_columns == 1
    return unique_paths_problem(number_of_rows, number_of_columns - 1) if number_of_rows == 1
    return unique_paths_problem(number_of_rows - 1, number_of_columns) if number_of_columns == 1
    return unique_paths_problem(number_of_rows - 1, number_of_columns) + 
            unique_paths_problem(number_of_rows, number_of_columns - 1)
end

puts unique_paths_problem(3, 7)

The soluton given in the book:

def unique_paths_problem(rows, columns)
    return 1 if rows == 1 || columns == 1
    return unique_paths_problem(rows - 1, columns) + unique_paths_problem(rows, columns - 1)
end

puts unique_paths_problem(3, 7)

---

Chapter 12. Dynamic Programming

The following code returns the Nth number in the Fibonacci sequence.

def fib(n):
    if n == 0 or n == 1:
        return n
    return fib(n - 2) + fib(n - 1)

It has an efficiency of $O(2^N)$ which is unexpected. The reason why it happened is because the recursive functions are repeatedly calculating several Fibonicci numbers such as fib(0) for multiple times. The smaller the number is, the more times the functions are called.

One way to optimize the speed of this function is using memoization. We can store every result of fib(n) into a hash table. Before we call fib(n), it first checks that hash table to see if the the results of fib(n) has already been computed. Only if the 3 key is NOT in the hash table does the function proceed to call fib(3).

def fib(n, memo):
    if n == 0 or n == 1:
        return n
    if not memo.get(n):
        memo[n] = fib(n - 2, memo) + fib(n - 1, memo)
    return memo[n]

Memoization will raise the speed of this function up to $(2N)-1$, that is, an $O(N)$ algorithms.

The another way is that we start solving this problem with the first two Fibonacci numbers: 0 and 1. Then, use the iteration to build up the sequence.

def fib(n)
    if n == 0
        return 0
    a = 0
    b = 1
    for i in range(1, n):
        temp = a
        a = b;
        b = temp + a
    return b

Since the loop is from 1 to N, this code takes N steps, so it’s $O(N)$.

Exercise

Exercise 1

Fix the code to eliminate the unnecessary recursion

def add_until_100(array, function_calling_counter=0)
    puts "add_until_100" # outputs 31 times for the case array = [23, 1, 99, 22]
    return 0 if array.length == 0
    if array[0] + add_until_100(array[1, array.length - 1]) > 100
        return add_until_100(array[1, array.length - 1])
    else
        return array[0] + add_until_100(array[1, array.length - 1])
    end
end

My solution:

def add_until_100_memoization(array, index=0, hash_table={})
    puts "add_until_100" # outputs 5 times for the case array = [23, 1, 99, 22]
    return 0 if array.length == 0
    # Split array[0] + add_until_100(array[1, array.length - 1]) > 100 into three parts:
    # array[0], add_until_100(array[1, array.length - 1]) and > 100
    # Only implement the memoization on the result of recursive function
    if hash_table[index] == nil
        hash_table[index] = add_until_100_memoization(array[1, array.length - 1], index + 1, hash_table)
    end
    # Do the summation and comparison later
    sum = array[0] + hash_table[index]
    if sum > 100
        return hash_table[index]
    else
        return sum
    end
end

Answer:

def add_until_100_answer(array)
    puts "add_until_100" # outputs 5 times for the case array = [23, 1, 99, 22]
    return 0 if array.length == 0
    sum_of_remaining_numbers = add_until_100_answer(array[1, array.length - 1])
    if array[0] + sum_of_remaining_numbers > 100
        return sum_of_remaining_numbers
    else
        return array[0] + sum_of_remaining_numbers
    end
end

Exercise 2

The following function uses recursion to calculate the Nth number from “Golomb sequence”. Fix the code to eliminate the unnecessary recursion

def golomb(n)
    puts "golomb" # once for golomb(1), 4 times for golomb(2), 10 times for golomb(3), 19 times for golomb(4)
    return 1 if n == 1
    return 1 + golomb(n - golomb(golomb(n - 1)))
end

My solution:

def golomb_memoization(n, hash_table={})
    puts "golomb" # once for golomb(1), 4 times for golomb(2), 7 times for golomb(3), 10 times for golomb(4)
    return 1 if n == 1
    if hash_table[n] == nil # Or !hash_table[n]
        hash_table[n] = 1 + golomb_memoization(n - golomb_memoization(golomb_memoization(n - 1, hash_table), hash_table), hash_table)
    end
    return hash_table[n]
end

Exercise 3

Here is a solution to the “Unique Paths” problem from an exercise in the previous chapter. Fix the code to eliminate the unnecessary recursion

def unique_paths(rows, columns)
    # puts "unique_paths" # outputs 55 times for unique_paths(3, 7)
    return 1 if rows == 1 || columns == 1
    return unique_paths(rows - 1, columns) + unique_paths(rows, columns - 1)
end

My solution:

def unique_paths_memoization(rows, columns, hash_table={})
    puts "unique_paths_memoization" # outputs 25 times for unique_paths_memoization(3, 7)
    return 1 if rows == 1 || columns == 1
    if hash_table[[rows, columns]] == nil # Or !hash_table[[rows, columns]]
        hash_table[[rows, columns]] = unique_paths_memoization(rows - 1, columns, hash_table) + unique_paths_memoization(rows, columns - 1, hash_table)
    end
    return hash_table[[rows, columns]]
end

---