Skip to content

Instantly share code, notes, and snippets.

🏠
Working from home

Diego Gallegos DiegoGallegos4

View GitHub Profile
View lifo_fifo.py
class Stack:
def pop(self):
pass
def top(self):
pass
def push(self, key):
pass
View doubly_linked_list.py
class Node:
def __init__(self, key, next=None, prev=None):
self.key = key
self.next = next
self.prev = prev
class DoublyLinkedList:
def __init__(self, head=None):
self.head = None
self.tail = None
View tree.py
class BinaryTree:
def __init__(self, key, left=None, right=None):
self.key = key
self.left = left
self.right = right
def insert_left(self, key):
if self.left:
node = BinaryTree(key)
node.left = self.left
View singly_linked_list.py
class Node:
def __init__(self, key, next):
self.key = key
self.next = next
class List:
def __init__(self, head=None):
self.head = head
self.tail = None
@DiegoGallegos4
DiegoGallegos4 / quicksort.py
Last active Apr 15, 2019
Divide and Conquer: Quicksort
View quicksort.py
def partition(A, left, right):
pivot, j = A[left], left
for i in range(left + 1, right + 1):
if A[i] <= pivot:
j += 1
A[i], A[j] = A[j], A[i]
A[left], A[j] = A[j], A[left]
return j
View merge_sort.py
def merge(A, B):
C = []
while len(A) and len(B):
a, b = A[0], B[0]
if a <= b:
C.append(A.pop(0))
else:
C.append(B.pop(0))
while len(A):
C.append(A.pop(0))
View selection_sort.py
def selection_sort(A):
for i in range(len(A)):
min_index = i
for j in range(i+1, len(A)):
if A[j] < A[min_index]:
min_index = j
A[i], A[min_index] = A[min_index], A[i]
return A
@DiegoGallegos4
DiegoGallegos4 / karatsuba.py
Created Apr 11, 2019
Karatsuba Multiplication
View karatsuba.py
def karatsuba(A, B, n):
"""
A(x) = a_1 * x + a_0
B(x) = b_1 * x + b_0
C(x) = a_1 * b_1 * x^2 + (a_1 * b_0 + a_0 * b_1) * x + a_0 * b_0
Rewrite as
C(x) = a_1 * b_1 * x^2 + ((a_1 + a_0) * (b_0 + b_1) - a_1 * b_1 - a_0 * b_0) * x + a_0 * b_0
@DiegoGallegos4
DiegoGallegos4 / dc_poly_mult.py
Created Apr 11, 2019
Naive Divide & Conquer: Polynomial Multiplication [WIP]
View dc_poly_mult.py
import math
import numpy as np
def dc_poly_mult(A, B, n, a, b):
"""
A(x) = D1(x) * x^n/2 + D0(x)
where
D1(x) = a_n-1 * x^(n/2-1) + a_n-2 * x^(n/2-2) + ... + a_(n/2)
@DiegoGallegos4
DiegoGallegos4 / poly_mult.py
Created Apr 11, 2019
Naive Polynomial Multiplication
View poly_mult.py
def naive_poly_mul(A, B, n):
"""
Multiplies two n -1 polynomials A and B
Args:
A(x) = a_n-1 * x^n-1 + a_n-2 + ... + a_1*x + a_0
B(x) = b_n-1 * x^n-1 + b_n-2 + ... + b_1*x + b_0
Returns:
C(x) = c_2n-2 * x^2n-2 + c_2n-3 * x^2n-3 + ... + c_1 * x + c_0
You can’t perform that action at this time.