This is what I’ve learned from my time attempting to design an 8 bit cpu to FPGAs, to designing a single board AVR based computer and OS. These topics were never really well investigated in school. I had taken computer science and mathematics courses, but never really breadboarded, soldered, or done any hardware/FPGA/architecture design in school.

Some time during the pandemic, I wrote some small snippets of C code for low level processes that I thought were interesting.

I found this youtube video that was absolutely fantastic and wanted to share. It does an incredible job of tying Godel’s Incompleteness Theorems, Computability and a few other topics into a really nice easy to digest format.

The greatest thing I learned this year, was imagine every dynamic programming question as some subproblem of knapsack. Once you think of it as knapsack, it feels magnitudes easier to solve if you know the \(O(nW)\) dynamic solution and \(W\) is sufficiently a small enough factor. K-dimensional dynamic programming has become a lot easier, but I still struggle from time to time.

Note: even though this was written October 11 2019, it will not be made public until October 19 2019.

So I decided to play more with just ocamllex and get a toy language according to the guide I am using to be parsed. It’s definitely cool to say the least.

So I am off to basic lexing in Ocaml. I can tell you it is definitely fun. I am having some difficulty with the theory, but I will keep pushing along in it. Currently I’m still figuring out ocamllex, and this was the first lexer I have written. It doesn’t do much, and I’m still trying to figure out how to run it, without writing all of it by hand. I definitely think this will be a fun project now. Here’s what my first lexer looks like.

So I began, well at least trying to eventually, write a compiler. I am reading Modern Compilers Implementation in ML by Andrew Appel. I find it to be a very great read. I am only a couple chapters in, but I think this will a great read, and a very fun project to try to finish by the end of the summer Currently I am working on I believe to be ASTs, abstract syntax trees. I have some stuff that looks like, the entire thing should be findable at Tiger Ocaml.

I began using my Raspberry Pi, so I could have a real desktop, as all I own/have currently are laptops. So having a dedicated computer is a nice luxury to have again. I found the Raspberry Pi, to be completely awesome. It gives you the luxury of complete control, that I would otherwise be too hesistant to try out with my traditional x86 counterparts, that are considerably more expensive. I believe that this switch will leave me many times more productive in the end. Vim has a very considerable learning “wall”. I highly recommend however, using i to insert, esc to leave insert mode, :wq and :q! for saving+quitting, and quitting without saving. Those were the only tools I knew before going to deep into Vim usage.

So I have just begun using a Raspberry Pi as a total desktop. And I am really enjoying it. The text editor choices are very lean, so I’ve been using VI, and I really like using it to be honest. I’ve added some screenshots below.

Note: This was written in vim entirely. I am running on a Raspberry Pi with Raspbian installed. So I will probably make a few extra errors. So this may be biased, because I currently am in a 4 year program for Computer Science at a public university. However, as much as I believe a four year education is not necessary to modern life, it’s a little twisted in the computer field. There is a lot of demand for computer programmers, and not so much for computer scientists. And that leads to the argument that theory is not as important as schools make it out to be. I for one am against that train of thought. The level of theory may not be important, but undergraduate education in computer science, is important to teach the basics of computing. I do think schools do a poor job of executing this, and computer science is plagued by many people only in it for the paycheck.

So now that the semester has finally ended for me, I will finally have time to really dedicate to some more studies, and I will be working full time this summer at NineFx Inc in Columbia, SC as a Software Engineer. I wanted to talk about my time at Open Source 101 in Columbia. The main event for me was, the talk about Machine Learning, where an engineer Dan Zaratsian, had shown that a trained neural network was able to tell if patients had cancer, or other diseases solely through images. It was extremely eye opening, to actually see what I’ve been hearing, and the fear that computers will soon be able to do many if not all of our essential jobs. Other than that, I enjoyed many of the talks given at the conference.

In a similar vein, I’ve noticed through my undergraduate career, that there is a movement of the Computer Science degree to continue to devolve into a high volume, low skill degree. I believe that this degree needs to remain rigorous. It is unfortunate that we have been seeing this all across the country. It’s the main reason I picked up a Math major while I’m in University as well. Hopefully it will fill the void of rigor and difficulty that is absent in the Computer Science departments at many universities. Hopefully through continued pressure and lobbying at my university by many of the students and professionals that are either board members or lobby the IAB(Industrial Advisory Board) at the University of South Carolina.

I have decided to come back to the TSP problem. I have optimized my approximation. So first of all, my nearest neighbor was not very good in the previous one. I have fixed it, and now we get really nice graphs to start with. One of the main flaws of what I have is we’re kind of forced to begin in a place for the nearest neighbor(depending where you start it may give you less or better beginning approximation). The other main issue with what I have, is I don’t know if what I have is really any good. It’s sort of a mix mash of heuristics from Wikipedia. I’ll post more some other day, but I have attached the approximations I have been able to create. These were all calculated in under 30 seconds, most of them in the 4-10 second range on a modern i7 2.9 Ghz CPU.

This is more of an addendum to Travelling Salesperson. I quickly made a solution to Minimum Spanning Tree problem. This algorithm runs in \(O(\alpha(E)E\log(E))\) time. This is the Inverse Ackerman function \(\alpha\), and it grows incredibly slow, \(\alpha (2^{2^{2^{65533}}} - 3) = 4\). So the analysis of this algorithm would basically be \(O(E\log(E))\), however our set-up is always a connected graph, so we can just denote it as \(E=n(n-1)/2\), which is ~\(n^2\). And for when \(n=|V|\), our algorithm runs in \(O(\alpha(n^2)n^2 2\log(n))\) which is \(O(n^2\log(n))\). For a more detailed analysis, check Wikipedia’s for a simple to follow one here.

So the Travelling Salesperson Problem, is a really cool problem in Mathematics and Computer Science. For more information see, Wikipedia and Youtube Visualization.

I have decided to add a page with all the Youtube channels I enjoy, as well as videos. I will try to keep it as manicured as I can. Youtube is an amazing resource. It was what first got me into Computer Science. For a long time, it was the only resource I had to learn Mathematics. Unfortunately it cannot replace a traditional education, … yet, it is an amazing way to introduce yourself to new concepts.

Youtube Videos

You can click on the link above, or here to get to the new Youtube page.
Note I believe a key to effective Youtube videos is excitement, I try to choose videos that can get people excited about topics.

This problem was posed in the Spring 2019 ACM Lower Division Codeathon. I chose this problem because it is a very nice strategy problem. Not necessarily solely an algorithm problem anymore. It is also partly a strategy and optimization problem all rolled into one. The original analysis was from USACO’s Nick Wu, Cow Tipping. The Original Problem.

Welcome to my blog, it is definitely a work in progress at this very moment, and it is 2:01 AM, so I will keep this short. This project was forked straight from Jekyll-Now. I tried running a Gatsby set-up, because I would prefer to have React, but Jekyll has better integration with Github Pages, so here we are.