# 1 Insertion Sort

Selection sort although not very efficient is often used when the arrays you are sorting are very small. Another benefit of insertion sort is that it is very easy to program. Essentially, this algorithm has a sorted section which slowly grows as it pull in new elements to their sorted position.

## 1.1 Functional Notation

$s([]) = []\\ s(x::xs) = i(x, s(xs))$

### Knapsack Problem

##### Tue Dec 11 2018

In this post I will go over how you can frame a question in terms of recursion and then slowly massage the question into a dynamic programming question.

# 1 Problem Description

The knapsack problem is a famous optimization problem in computer science. Given a set of items, a thief has to determine which items he should steal to maximize his total profits. The thief knows the maximum capacity of his knapsack and the weights and values of all the items.

### 2018 In Review

##### Sat Dec 08 2018

Inspired by Justin Flory and Dan Schneiderman, I decided to make a 2018 review post. I believe that it would be a good way to reflect upon what I did in 2018 and make plans for 2019. This post will be a very high level overview of the projects and activities that I did in 2018 -- nothing personal. Pictures say a thousand words, so, I will include a lot.

Eagle Ceremony

# 1 Introduction

A few weeks ago I presented my musical floppy drives at the Rochester Maker Faire with RITlug. Wow, that sentence had a ton of links-- you should check them out. This post is a quick recap of my experience at the Maker Faire and a project update for my musical floppy drive project. For those of you who don't know, Maker Faires are community gatherings where people "celebrate arts, crafts, engineering, science projects and the Do-It-Yourself (DIY) mindset".

I would like to give a huge thanks to Christian for providing me with some of these pictures and RITlug for giving me the opportunity to present at the Maker Faire.

# 2 Project Background

### CS Theory Exam 2 Review

##### Tue Nov 06 2018

This a very high level review post that I am making for myself and other people reviewing CS Theory. If you want to lean more about content in this blog post I recommend cracking open a text book-- I know, gross. This hastily thrown together post will cover how to solve typical problems relating to topics covered by my second CS Theory exam.

# 1 Myhill-Nerode Theorem

## 1.1 Definition

L is regular if and only if it has a finite index. The index is the maximum number of elements that are pairwise distinguishable. Two strings are said to be pairwise distinguishable if you can append something to both of the strings and it makes one string accepted by the language and the other string rejected. The size of an index set X equals the number of equivalence classes it has and the minimum number of states required to represent it using a DFA. Each element in the language is accepted by only one equivalence class.