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.

Myhill-Nerode Theorem

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.

Problem Approach



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.

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)

Time Complexity



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.

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
}



University vs Teaching Yourself Programming

Tue Feb 13 2018

Many people on the internet furiously debate whether it is better to learn how to program in college vs teaching yourself. This is not necessarily a one-sided debate, there are merits of both teaching yourself how to program and taking computer science in college.

University

The main advantage of taking Computer Science in college is that you are also taking a lot of math and science courses. When talking to a professor from Clarkson University he said that they were not teaching students simply how to get jobs, but how to pioneer and shape the field. It is possible to buy a book and teach yourself how to program Python or attend a coding boot camp. However, the tech field is changing at a rapid pace, and what you learn now may be irrelevant in five years. The combination of programming courses and other math and science related courses allows students to create the tech of the future. Think about all the advancements in artificial intelligence we have made in the past year, all that requires higher level statistics and calculus.



Using English Conventions To Write Clean Code

Thu Feb 08 2018

Is that English?

private boolean canCompressBlock(Coordinate start, int size){
   return size == (int)Arrays.stream(this.rawImage, start.getRow(), start.getRow() + size)
           .filter(r-> size == (int)Arrays.stream(r, start.getCol(), start.getCol() + size)
                   .filter(c-> c == this.rawImage[start.getRow()][start.getCol()])
                   .count()).count();
}                   

After 30 minutes of brain boiling work, I finally finished crafting the most beautiful lambda statement in Java. What could have simply been done in two nested for loops, I decided to tackle the problem with the infamous lambda statement– feared by most programmers. Lambda statements by no stretch makes code any easier to read since the same tasks can be accomplished through using simpler and more recognizable syntax. Yet I decided to utilize this excessive lambda statement. After much contemplation, I realized that I was only using lambda statements due to the fact that people inside of a field typically try to write to impress their peers. This code chunk is clearly a sophisticated use of functional programming and will likely impress people inside the computer science community; however, 95% of my computer science class would not understand a single word of this statement. This poses a dilemma to newer programmers which may have difficulty reading this “sophisticated code”. After years of helping students learn to program in my high school, I know that students struggle with making their own code legible. Their code often lacks sophistication and clarity. However, at the same time many of my college professors which are embedded in the field of computer science often write code that is too sophisticated and obscure for anybody to easily understand. This got me thinking, how can we teach students to programming in a way that yields legible code for everybody in the computer science field? I turned towards English. It turns out that programming can take a few pointers from English to improve its clarity. The same skills used to teach writing can be applied when teaching students to program because excellent code and writing contains thought through structure, clear phrasing and readability.