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.

1.2 Problem Approach

Read More »

Morality of Self Driving Cars

Mon Oct 22 2018

Although the movie I Robot has not aged well, it still brings up some interesting ethical questions that we are still discussing concerning self driving cars. The protagonist Detective Spooner has an almost unhealthy amount of distrust towards robots. In the movie, a robot decided to save Spooner’s life over a 12 year old girl in a car accident. This ignites the famous ethical debate of the trolley problem, but, now with artificial intelligence. The debate boils down to this: are machines capable of making moral decisions. The surface level answer from the movie is presented as no when Spooner’s presents car crash antidote. This question parallels the discussion that we are currently having with self driving cars. When a self driving car is presented with two options which result in the loss of life, what should it choose?

Read More »

Everything Fibonacci

Sun Oct 07 2018

If you have ever taken a computer science class you probably know what the fibonacci sequence is and how to calculate it. For those who don’t know: Fibonacci is a sequence of numbers starting with 0,1 whose next number is the sum of the two previous numbers. After having multiple of my CS classes give lectures and homeworks on the Fibonacci sequence; I decided to write a blog post going over the 4 main ways of calculating the nth term of the Fibonacci sequence. In addition to providing the python code for calculating the nth perm of the sequence, a proof for their validity and an analysis of their time complexities both mathematically and empirically will be examined.

1 Slow Recursive Definition

By the definition of the Fibonacci sequence, it is the most natural to write it as a recursive definition.

def fib(n):
    if n == 0 or n == 1:
        return n
    return fib(n-1) + fib(n-2)

Read More »

C to C++ Tutorial

Thu Aug 02 2018

This post aims to cover all the major topics that C programmers need to know before they start writing C++ programs. I kept this post as short and concise as possible to enable people to use this as a quick reference to quickly jump into C++. This post assumes that you have prior knowledge of both C and object oriented-programming concepts. Each topic is quickly covered in a code snippet and some additional explanation is provided if necessary.

1 Input/Output

Input and output in C++ is easy, you use “cout” and “cin”. When printing with “cout”, you separate what your printing with “<<”; “endl” prints a new line.

using namespace std;                        //namespaces talked about below
#include <iostream>                         //Include statement for terminal IO.

int main()
{
    cout << "Hello World" << endl;          // HELLO WORLD!
    
    int a;
    cin >> a;                               //inputs an int into a -- notice how arrows face the direction of IO
    
    cout << "You entered: " << a << endl;   //prints what you entered
    
    return 0;                               // return sucess code
}

Read More »

Gremlin in 10 Minutes

Sat Jul 28 2018

1 What is Gremlin?

Gremlin is a graph traversal language: think of Gremlin as the SQL for graph databases. Gremlin is not a graph database server, it is a language; but, there is a Gremlin Server and a Gremlin Console available for interacting with graph databases. It is possible to use Gremlin on large database platforms like Titan and HBase.

2 Graph Data Base Basics

A graph database is based on graph theory. A graph is composed of nodes, edges, and properties. A key object/component in a graph database is stored as a node. Nodes are connected via edges representing relationships. For example, you may represent people as nodes and have edges representing friendships. You can assign properties to both nodes and edges. A person (node) may have the properties of age and name, where a friendship (edge) may have a start date property.

2.1 Why Graph Databases?

Read More »