SDP Max Cut Approximator

While taking CS294-145 (Approximation Algorithms), I wanted to implement Goemans-Williamson's 0.879-approximation for max cut (I had also seen it in CS294-134 (Beyond Worst Case Analysis)). I wrote the randomized 0.5-approximation algorithm (pick a random cut with equal-sized halves), the derandomized greedy 0.5-approximation algorithm (repeatedly add a vertex to the set that increases the cut more) and the 0.879-approximation algorithm, using cxvpy and numpy.

Code and basic tests can be found in the associated Github repo.

Developing And Deploying A Reddit Bot With AWS EC2, SQS, And Lambda

I've always enjoyed seeing the various functions bots perform on reddit, so I decided to make my own. I used PRAW (Python Reddit API Wrapper) running on an AWS EC2 instance to find comments that begin with "!markovchaincomment", then add the comment ID to an AWS SQS queue, then pull from that queue with an AWS Lambda function that creates a markov chain based off the specified user's recent comments and also write out some logs to AWS CloudWatch.

Code can be found in this Github repo.

Fakcharoenphol-Rao-Talwar (and other) Trees Implementation and Distortion Analysis using HTML5 canvas and ReactJS

Another cool tool I learned in CS 294-145 (Approximation Algorithms) was low-distortion Fakcharoenphol-Rao-Talwar (FRT) trees. I wanted to implement them in an interactive environment instead of just in a Jupyter-or-terminal-like environment, so I've implemented them along with minimum spanning trees (Prim's and Kruskal's) and random spanning trees with HTML5 canvas and ReactJS. I also did some analysis on the average and maximum distortion with numpy, pyplot, and Google Colab.

The interactive demo is here, the Google Colab is here, and the scripts are in this part of my website repo.