Algorithms Learning Series @ylo-algorithms-blog - Tumblr Blog

Posts

Block vs Procs vs Lamda vs Methods-- Explained!

http://www.eriktrautman.com/posts/ruby-explained-blocks-procs-and-lambdas-aka-closures

Hoisting in JS

Main Concepts

Hoisting only with (variable or function) declaration

Function Declaration starts with `function`

if start not `function` ==> function expression.

examples (note none start with `function, self invoke is wrapped`):

#anonymous function expression var foo = function() { }

#named function expression var foo = function bar () { }

#self invoking function expression (function(){ })

function statement just pseudonym for function declaration

never place a Function Declarations in an if statement

place at top of scope to avoid confusion (explicit hoisting if you will)

Variable Declaration starts with `var`

initialization or expression after variable declaration is NOT hoisted

i.e. even with expression, all that is hoisted is var foo = undefined

Reference: https://javascriptweblog.wordpress.com/2010/07/06/function-declarations-vs-function-expressions/

#blog-notes

Pattern Matching

Trie

root is not labeled with character (just null)

ordered alphabetically --> allow bfs

each child also alphabetically stored

paths from leaves to root gives back the words

standard

compressed: space efficient

suffix tree: help with pattern matching

only works for data where word in text is well defined

takes up a lot of space

Compressed Trie

nodes degree of at least 2

compressing redundant links

save space? store as ranges

Uses

Index of a search engine --> internal memory

internet routers

finding prefixes

Optimizations

stop word elimination

link analysis

Suffix Trees

compressed tree for all the suffixes

Heap

Key Topics:

Heap (data structure)

Binary heap: Min vs Max heaps

Heapsort vs Quicksort

Quicksort in place

Median of Medians

Uses:

Priority queue

Heap select (i.e. select kth smallest element

Building a heap ==> O(n)

Shape property: binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.

Heap property: all nodes are either greater than or equal to or less than or equal to each of its children, according to a comparison predicate defined for the heap

A heap could be built by successive insertions. This approach requires O(n log n) time because each insertion takes O(log n) time and there are n elements. However this is not the optimal method.

The optimal method (by Floyd) starts by arbitrarily putting the elements on a binary tree, respecting the shape property. Then starting from the lowest level and moving upwards, shift the root of each subtree downward as in the deletion algorithm until the heap property is restored.

Implementation:

using an array (fixed size or dynamic array), and do not require pointers between elements

the children of the node at position n would be at positions 2n and 2n + 1 in a one-based array, or 2n + 1 and 2n + 2 in a zero-based array.

def self.child_indices(len, parent_index) [parent_index * 2 + 1, parent_index * 2 + 2].select{ |i| i < len } end

def self.parent_index(child_index) raise "root has no parent" if child_index == 0 (child_index - 1) / 2 end

Heap Methods

#insert: insert val at tail -> shift/ heapify up ==> O(logn)

#extract: pop root -> move tail to root -> shift/ heapify down ==> O(logn)

#peak: return root ==> O(1)

Select Kth Element

Naive ==> O( n log n )

Min Heap ==> O( n + k log n )

change array heap ==> O(n)

extract min k-times ==> O(k log n)

Max Heap ==> O( k + (n-k) log k )

build heap with first k elements ==> O(k)

for each element after k

compare el with root

if el < root --> extract root and push el, reheapify ==> O((n-k) log k)

root = kth smallest

Median of Medians ==> O(n)

Search set decreases at least by a constant proportion at each step, hence exponentially quickly, and the overall time remains linear. The median is a good pivot – the best for sorting, and the best overall choice for selection – decreasing the search set by half at each step. Thus if one can compute the median in linear time, this only adds linear time to each step, and thus the overall complexity of the algorithm remains linear.

The median-of-medians algorithm does not actually compute the exact median, but computes an approximate median, namely a point that is guaranteed to be between the 30th and 70thpercentiles (in the middle 4 deciles). Thus the search set decreases by a fixed proportion at each step, namely at least 30% (so at most 70% left). Lastly, the overhead of computing the pivot consists of recursing in a set of size 20% the size of the original search set, plus a linear factor, so at linear cost at each step, the problem is reduced to 90% (20% and 70%) the original size, which is a fixed proportion smaller, and thus by induction the overall complexity is linear in size.

Proof of O(n) running time

The median-calculating recursive call does not exceed worst-case linear behavior because the list of medians is 20% of the size of the list, while the other recursive call recurses on at most 70% of the list. Let T(n) be the time it takes to run a median-of-medians Quickselect algorithm on an array of size n. Then we know this time is:

Dynamic Programming In Use

Trade-off: less time, more memory

Knapsack problem:

http://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf

Others: maze solver, make change, graph traversal

Progress Tracker

Leetcode problems over weekend: 15

Week tally: 52

Total: 69

#progress

Backtracking

What is it: algorithm for finding all solutions to a problem

Premise: incrementally build candidates to the complete solution and abandons partial candidates that cannot be completed to a valid solution as soon as that’s determined

Examples: eight queens puzzle

Solution to sorted subsets without bitwise operator:

def subsets(nums) return [[], nums].take(nums.length + 1) if nums.length <= 1

val = nums[0] subs = subsets(nums.drop(1)) new_subs = subs.map{ |sub| (sub + [val]).sort }

subs + new_subs end

Solution with bitwise operator

def subsets(nums) res = [] nums_sorted = nums.sort

(1 << nums.length).times do |i| j, cur = 0, []

while j < nums.length && j <= i do cur << nums_sorted[j] if i & (1 << j) != 0 j+=1 end

res << cur end

res end

This solution cleverly utilizes the concept of bijection, mapping the binary representations of 1-n onto the 1st - n-th unique subset, with with n being the number of unique subsets. the 1 and 0 in this case function like on and off switches indicating which index in the original array need to be included in the i-th unique subset.

Problem solutions referenced: Subsets

Progress Tracker

Leetcode problems today: 3

Pair boarding problems today: 3

Week tally: 37

Total: 54

#progress

Using Binary

Signed vs unsigned: http://kias.dyndns.org/comath/13.html

Here’s a practical example of how bitwise operators improved my code. My original solution to the problem Reverse Bits used multiple loops, a helper method and various variables:

def reverse_bits(n) reverse_bin = 0 pow = 0

until n == 0 n, r = n.divmod(2) reverse_bin = r + reverse_bin * 10 pow += 1 end

zero_padding_count = 32 - (pow) reverse_bin *= 10 ** zero_padding_count

to_base10(reverse_bin) end

def to_base10(bit) base10 = 0 pow = 0

until bit == 0 || pow == 32 bit, r = bit.divmod(10) base10 += r * 2 ** pow pow += 1 end

base10 end

Here’s the improved version use bitwise operators:

def reverse_bits(n) res = 0

32.times do res = res << 1 res = res | 1 if n & 1 == 1

n = n >> 1 end

res end

Granted, both cases the complexities are O(n) time and O(1) space (with some micro-optimization from 2n to n). And in both cases the performance is linear time in terms of the number of bits or 32 in this case. But the second example is now much more concise and readable.

Of course, the most concise way would be to utilize nice ruby methods if not under any constraints regarding string conversion:

def reverse_bits(n) bin = n.to_s(2) (bin.reverse + "0" * (32 - bin.length)).to_i(2) end

The complexity of #to_s I am not sure about, but I would assume its implementation uses bitwise operators under the hood in linear time in terms of the number of bits as well. I know for certain though that #reverse will be linear in terms of the number of bits or, again, 32 in this case. So complexity in time and space still remain the same.

Problem solution referenced: Reverse Bits

Bitwise Operators

What are they: great link that covers the basic definitions

Some interesting use cases:

1. Shifts

n << i #=> n * 2**i n << i #=> n / 2**i ( if n is odd, will round down )

So a simple way to think about it, lets first set i = 1

n << 1 #=> n * 2 n >> 1 #=> n / 2

Yup, it becomes just some simple times 2 and divide by 2. Pretty cool!

2. AND, &

The & operator is pretty intuitive. One practical use is to check the first index of a binary integer:

n & 1 == 1 #=> checks if first index is true

It can also be combined with other operators for some interesting checks. For example, when combined with the shift operator, we are now able to check any i-th index in a binary integer:

n & (1 << i ) == 1 #=> check if i-th index is true

Another way to achieve this mathematically is to use division by 10, but division is commonly the slowest operation, giving bitwise operators a slight advantage.

3. OR, |

While the & operator can be practically used as a getter at the i-th index, the | operator can be used as a setter the i-th index of a binary integer:

n = n | 1 #=> returns bit with 1 at first index n = n | (1 << i) #=> returns bit with 1 at the i-th index

4. XOR, ^

XOR returns true if inputs are different (1 ^ 0 or 0 ^ 1, but not 1 ^ 1 or 0 ^ 0).

An interesting thing to note is that:

(a XOR b) XOR (b XOR c) == (a XOR c)

Haven’t encountered a practical use case, but will definitely update when I do.

Progress Tracker

Leetcode problems today: 10

Pair boarding problems today: 2

Week tally: 31

Total: 48

#progress

Understanding the LRU cache

Hash Map

Implementation:

contains buckets

hash key to determine which bucket to place key

allows O(1) look up for best case since hash function knows exactly which one bucket to look in

hash function == mod by count of buckets

rehashing

amortization: double number of buckets when limit reached

hash to rehash to figure out buckets again since bucket count has changed => hash function different

worst case O(n), but average O(1)

More to learn:

how are Javascript objects differently built?

mumur hash in ruby

Linked List

a series of nodes that have pointers to another node

Sentinel nodes:

specifically designated node used as a traversal path terminator

commonly used with linked lists and trees

used over using `nil` object

allows less type comparison, ie avoid following:

if node.nil?

as result, advantage:

increased speed of operations

reduced algorithmic complexity and code size

Doubly linked list useful in caching

LRU (Least Recently Used) Cache

what is it: algorithm that stores n capcity of items and ejects the least recently used item when capacity reached

Key point:

what to cache = time_to_make * frequency_visited

Premise:

check the cache and move to top

go get it and insert

eject the LRU

Implementation:

hash map => O(1) look-up but O(n) eject

linked list => O(1) eject but O(n) look-up

need to be doubly linked since add at head and eject at tail

thus solution => implement both hash map and linked list

#linked list #LRU cache #cache #hashmap #hash

Binary Trees

API/ Attribute Accessor: val, left, right

Depth First Search Breadth First Search Iteraction (stack or queue) vs Recursion

Problem solutions referenced: Binary Tree Level Order Traversal, Balanced Binary Tree, Same Tree, Path Sum, Min Depth of Binary Tree

Recursion

Advantage Disadvantage

"Suppose that you need to pass some data to the recursive process. You might want to keep a count of the number of nodes visited, or a set of parameters that determine what to do at each node, or anything else. In order to do this, you have to pass some data to every recursive call. This is a waste of time and space, unless your compiler is much smarter than mine. Alternatively, you can use global variables, but that's hardly a preferable solution."

reference: http://benpfaff.org/writings/clc/recursion-vs-iteration.html

Tail Call

Master Theorem: Big O Computation

Progress Tracker

Leetcode Problems today: 7

Week tally: 19

Total: 36

#progress

Dynamic Array

Single Sided Dynamic Array

#push == O(1)

@count ++

worst case is still O(n)

but average case if O(1) due to amortization

#pop == O(1)

@count--

#shift == O(n)

need to move n-1 number of elements back

#unshift == O(n)

need to move n-1 number of elements over

Circular Dynamic Array: Ring Buffer (wiki)

Attributes:

logical index:

never stored, but calculated, thus still O(1)

shifting just shifts logical index

push will push onto last logical index

physical index

cell address

indexing: use (@start_idx + logical_idx) % @length

changes shift and unshift to O(1) performance

Example:

class DynamicArray def initialize(capacity = 8) @store = StaticArray.new(capacity) @start_idx = 0 @count = 0 @length = capacity end

def idx(i) #O(1) return (@start_idx + i) % @length end

def [ ](i) #O(1) @store[idx(i)] end

def [ ]= (i, val) #O(1) @store[idx(i)] = val end

def pop #O(1) @count -= 1 # @count is one ahead of idx, so decrement first return self[@count] end

def push(val) #worst: O(N), amortized: O(1) resize! if @count == @length self[@count] = val@count += 1 end

def unshift(val) #worst: O(N), amortized: O(1) resize! if @count == @length i = (@start_idx - 1) % @length

@store[i] = val @count += 1 @start_idx = (@start_idx - 1) % @length end

def resize! new_cap = @length * 2 new_store = StaticArray.new(new_cap) @length.times { |i| new_store[i] = self[i] }

@start_idx = 0 @length = new_cap @store = new_store end end

*Side note: Ruby implements an array that between single sided and ring buffer. –> shift less efficient than push….but importance debatable

Dynamic Programming

What is it: a problem-solving approach for solving complex problems

Key attributes: (i.e. a problem can be solved using DP if it has --)

optimal substructure

overlapping subproblems

Premise: break down complex problems into simpler overlapping subproblems. The method takes advantage of the problem’s optimal substructure to solve each subproblem just once* and store their solution. Anytime the same subproblem occurs (since overlapping), the solution is retrieved and used to help solve new unsolved subproblems instead of recomputing its solution.

*Process of storing solutions instead of recomputing is called memoization

Example:

def rob(nums) return 0 if nums.empty? return nums.first if nums.length == 1

prev_val = 0 val = 0

(0...nums.length).each do |i| temp = val val = (prev_val + nums[i]) > val ? prev_val + nums[i] : val prev_val = temp end

val end

Note that prev_val and val are solutions to subproblems in the iteration. They are then memoized and referenced in the subsequent subproblem in the next iteration.

Recursion

If you are thinking..wait, decomposing a problem into a series of subproblems and then building up correct solutions to larger and larger subproblems, this sounds recursion! Then why yes.

Recursion problems can be approached using dynamic programming and use the concept of memoization to improve performance.

As talked about in Lecture #1, solving the fibonacci sequence using recursion can be as slow as exponential runtime with O(2^n) if given this:

return fib(n - 1) + fib(n - 2)

How can dynamic programming help? With something like this pseudocode:

def fib(n) return memo[n] if n <= 1

fib(n-2) if ( fib(n-2) is not already calculated ) fib(n-1) if ( fib(n-1) is not already calculated )

#store the nth fibonacci no. in memory & use previous results memo[n] = memo[n-1] + memo[n-2]

return memo[n] end

In this case, each number up to the nth number is only computed once and saved in storage. Any subsequent computations then make use of the stored computations. As a result, the order of complexity comes down from exponential to linear runtime with O(n) complexity.

v.s. Divide and Conquer

Not all problems that have substructure are solved using dynamic programming, however.

If the complex problem has (1) optimal subsubstucture and (2) non-overlapping subproblems, then the optimal approach would be divide and conquer.

Think binary search and merge sort. All can be solved recursively, all are approached using divide and conquer for O(log n) or O(n log n ) complexity, and thus, none are classified as dynamic programming.

Problem solutions referenced: house robber, fibonacci

Progress Tracker

Leetcode problems today: 6

Pair boarding problems today: 1

Week tally: 12

Total: 29

#progress

Trending Blogs

Recently Viewed Blogs

Algorithms Learning Series