When browsing the BigQuery docs, I discovered that BigQuery now supports the QUALIFY-clause. At time of writing, it’s in preview, but you can already try it out.
The QUALIFY-clause lets you filter on the output of analytic functions. This allows me to scratch an itch I’ve had for a while:
A common pattern is: “For each distinct value in column X, find the row where column Y takes it’s maximum value”. You can accomplish this by using ROW_NUMBER() OVER (PARTITION BY X ORDER BY Y DESC) AS rank.
An example of this would be to find the date at which each of a set of countries reported the largest number of new confirmed covid-19 cases. We’ll be using the
bigquery-public-data.covid19_open_data dataset.
I’ve been on the hunt for a $1000 Linux UltraBook for personal use. I finally decided on a Lenovo Yoga Slim 7 Pro, with a Ryzen 7 5800 CPU and 16 GB RAM. I’ll leave the in-depth hardware review for others, but I’ll offer a nano-review: I’m happy with both build quality and specs. Best value for money I’ve seen in a while!
I’m less happy about the Realtek 8852 WiFi module not having built-in support in the 5.13 Linux kernel. Everything else worked out of the box with a fresh installation of Fedora 34 (my distro of choice).
Drivers for the Realtek 8852 module can be downloaded here, but the included Makefile doesn’t work with Fedora if you’re using secure boot. I’ll provide some quick notes below on how to install the drivers on Fedora 34.
You’ll still need to install a few packages, and get code on your computer. Try using your phone as a USB tethered modem. If you need to purchase additional hardware (USB network interface), consider just replacing the WiFi module at probably the same cost.
[Read More]Mutual information and its cousin, the Uncertainty coefficient (Theil’s U) are useful tools from Information Theory for discovering dependencies between variables that are not necessary described by a linear relationship.
Plenty of good material already exists on the subject: see Section 1.6 in “Pattern Recognition and Machine Learning” by Bishop, freely available as PDF online. What I hope to contribute here are some trivial examples, to help build intuition, based on categorical/multinomial variables.
[Read More]Advent of Code 2020 has finally started! I’ve been looking forward to it, as it will be a good excuse to brush off my absolute favorite general purpose language: Racket.
Follow my solutions on: https://github.com/AvitusA/adventofcode2020
Racket
To try out Shiny, I created an interactive visualization for Kullback-Leibler divergence (or KL Divergence). Right now, it only supports two univariate Gaussians, which should be sufficient to build some intuition. [Read More]
In this post, we will prove that the decision version of the set-covering problem is NP-complete, using a reduction from the vertex covering problem (which is NP-complete). This is Exercise 35.3-2 in CLRS3.
We will follow the template given in an earlier post.
We seek to answer whether a set cover \(\mathcal{C}\) exists for \(X\) (the set containing the elements to be covered), containing a maximum of \(k\) sets.
[Read More]This is the first post in a series of posts where I will attempt to give visual, easy to understand, proofs of NP-completeness for a selection of decision problems. I created these while studying them back in college. Hopefully, they’ll be helpful for someone.
In this post, I will give a “template” which can be used (and will be used for the proofs I post). [Read More]
In this post, we will prove that 0-1 integer programming is NP-complete using a reduction from 3-CNF-SAT (which is NP-complete).
We will follow the template given in an earlier post.
The decision problem for 0-1 integer programming is formulated as follows:
Given an integer \(m \times n\) matrix \(A\) and an integer \(m\)-vector \(b\), determine whether there exists an integer \(n\)-vector \(x\) with elements in \(\{0, 1\}\), such that:
\[ Ax \le b \] [Read More]
In this post, we will prove that the set-partition problem is NP-complete using a reduction from the subset sum problem (which is NP-complete). This is also happens to be Exercise 34.5-5 in CLRS3.
We will follow the template given in an earlier post.
Given a set \(S\) of numbers, determine whether \(S\) can be partitioned into \(A\) and \(\overline{A} = S - A\), such that: \[ \sum_{x \in A} x = \sum_{x \in \overline{A}} x \] [Read More]