johnhw

FATA

Why do data structures like splay trees or dynamic arrays have good average-case guarantees? Explain the idea of amortized analysis in this context, and connect it to practical considerations such as memory hierarchy and cache-friendliness.

Explain the “lens laws” in functional programming, using examples in a language other than Haskell. Why are these laws important, and how do they help in reasoning about programs that manipulate data structures?

Matching problems such as bipartite matching or stable marriage are fundamental in algorithms. Explain how randomized approaches can improve the performance or robustness of matching algorithms. Why might randomisation help in avoiding worst-case behaviour, and what provable guarantees can still be made?

GIST

johnhw

from numpy.fft import rfft, irfft 
import numpy as np

def int_to_vec(x, base=10):
    """Convert an integer to a list of digits in a given base."""
    return [int(s, base) for s in str(x)]

def vec_to_int(v, base=10):
    """Convert a list of digits to an integer in a given base;
    values of the list can be any integer, carries will 

johnhw

import ctypes
import json
import os

# Load the libtcd shared library using ctypes
# set the path here to the location of the libtcd.so file
lib_path = "/usr/lib"
libtcd = ctypes.CDLL(f"{lib_path}/libtcd.so")  

# Path where the xtide TCD files are located

johnhw

import math

def itr(n, q, v, t):
    # Calculate the probability of each choice being selected (assuming equally likely)
    p_choice = 1 / q
    
    # Calculate the entropy for each question's choices
    entropy_per_question = -p_choice * math.log2(p_choice) * q
    
    # Calculate the total entropy across all questions

johnhw

date,asl
2013-06-02 00:00:00,0.816
2013-06-02 00:15:00,0.845
2013-06-02 00:30:00,0.865
2013-06-02 00:45:00,0.902
2013-06-02 01:00:00,0.94
2013-06-02 01:15:00,0.983
2013-06-02 01:30:00,1.023
2013-06-02 01:45:00,1.086
2013-06-02 02:00:00,1.132

johnhw

johnhw

# Converts Ordnance Survey Terrian 50 United Kingdom data to a simple NumPy array of terrain altitudes
# The original OS data is freely downloadable from: https://www.ordnancesurvey.co.uk/business-government/products/terrain-50
# Directly converts the zipped terrain file to a NPZ file
# Resulting array is a (24600, 13200) array of float64 
# Requirements:
# * pycrs 
# * lxml 


import os, sys

johnhw

import numpy as np
from sklearn.metrics import confusion_matrix
from collections import defaultdict


def itr(confusion_matrix, timings, eps=1e-8):
    """Take a confusion matrix of the form
                     (actual) a   b   c   d 
    (intended)                
         a                     10  0   1   9

johnhw

from matplotlib.collections import LineCollection

def plot_connected_pairs(a,b,*args,**kwargs):
    """
    Draw lines between two arrays of 2D points.
    a and b must be the same shape, both [N,2] arrays to be plotted.
    
    Parameters:
    -----------
    a:  [N,2] array of points to plot from

johnhw

# bivariate colormaps in matplotlib
import numpy as np
import matplotlib as mpl
import matplotlib.pyplot as plt


## Bivariate colormapping
from scipy.interpolate import RegularGridInterpolator