sergeyprokudin

class BinaryTreeNode:
    
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def insert(self, value):
        "insert elements in the way to maintain binary search tree structure"
        if self.value >= value:

sergeyprokudin

import numpy as np

def linear_regression_1d(x, y):
    """Solves 1 dimensional regression problem: provides w=(w_1, ..., w_n) such that:
    
    w* = min_{w} sum_{i=1}{m}[(<w, x_i> - y_i)**2]
    
    L(w) = sum_{i=1}{m}[(<w, x_i> - y_i)**2]
    
    <w, x_i> = w_1*x_{i1} + w_2*x_{i2} + ... w_n*x_{in}

sergeyprokudin

import numpy as np

def linear_regression(x, y, lr=1.0e-4, n_steps=10000, lr_decay=0.5):
    """Solves 1 dimensional regression problem: provides w=(w_1, ..., w_n) such that:
    
    w* = min_{w} sum_{i=1}{m}[(<w, x_i> - y_i)**2]  (mean squared error)
    
    L(w) = sum_{i=1}{m}[(<w, x_i> - y_i)**2]
    
    <w, x_i> = w_1*x_{i1} + w_2*x_{i2} + ... w_n*x_{in}

sergeyprokudin

class GraphNode:
    
    def __init__(self, value, neighbors):
        """Initialize graph node
        
        Parameters
        ----------
        
        name: str
            node identifier

sergeyprokudin

def dfs(g, curr_node, visited=None):
    """
    
    Parameters
    ----------
    graph: dictionary
        dictionary of nodes and its neighbors
    node: list
    
    Returns

sergeyprokudin

#https://docs.python.org/2/tutorial/datastructures.html
from collections import deque

def bfs(g, root_node):
    """ Implementation of a breadth first search (BFS)
    BFS is useful e.g. when we need to find a route between 
    It is NOT recursive
    
    Algo:
    1. Enqueue root node;

sergeyprokudin

from collections import deque

def have_route(g, start_node, end_node):
    """Find out if there is a path in a directed graph g 
    between start_node and end_node
        
    Algo #1: BFS-based. 
        0. Check if start_node=end_node. If so, return True;
        1. Add start_node to queue and while queue is not empty 
            1.1. dequeue curr_node;

sergeyprokudin

import heapq as hq

def sort_k_messed(a, k):
    """Sort an array where each element is at most k steps away from 
    its sorted position.
    
    Parameters:
    -----------
    a: list
        k-messed input array

sergeyprokudin

def fib(n):
    """ Compute nth element of a Fibonacci sequence:
    1, 2, 3, 5, 8, 13, 21, ...
    
    f(n) = f(n-1) + f(n-2)
    
    f(0) = 0
    f(1) = 1
    f(2) = 1
    f(3) = 2

sergeyprokudin

import numpy as np

def pca(x, n_components):
    """ Principal component analysis of the data
    m - number of samples
    n - number of dimensions
    k - number of components
    
    TL;DR: 
       (a) compute the covariance matrix x.T@x