Data Science PT 6: Motivation for Scientific Programming

 

Let's go over an example, such as this code real quick to show why computational complexity is so important:

x=[]; 

for n=1:9999; 

    x=[x n]; 

end

This is because we need to create a new x' temporarily and copy the contents of x to x' causing 1 + 2 + ... + N, or (N)(N + 1)/2 operations. 

This code is slow, and we need to optimize it. According to Wikipedia, an algorithm is a self-contained step-by-step set of operations to be performed. Algorithms perform calculation, data processing, and/or automated reasoning tasks.

We want to predict resources used by an algorithm. these resources are running time, memory consumption, communication requirements, number of logic gates, and power consumption. We use a random access machine model to model the instructions executed separately, ignoring minor stuff only sniffing out the important details. We want to primarily focus on running time, particularly the worst case, average case, and best case. We can guarantee at most the worst case on runtime, so we focus on this the most. 

We want to measure runtime as a metric of input size. Could be # items in input, # bits to represent input, or multiple parameters. We can measure running time as the number of steps executed, with constant time per line (in random access machine though this isn't 100% true) and adding the amount of time it takes to call a routine.

Now, let's talk about the sorting algorithms. In insert sort, we maintain sorted list so far, and the next number gets inserted into the list. In merge sort, we divide the problem into 2 parts, conquer each problem, and merge each solution. 

The running time T(n) of insert sort is n^2. For merge sort it's n log2n. Sometimes merge sort implemented by a bad programmer will beat out insert sort, if the constant in front of nlog2n is large, but that's usually not the case. It can also be insert sort runs on a cluster while merge sort runs on a regular machine. 

Here's an example of running time comparison: 

If T(n) =  an^2+bn+c, asymptotically, a matters, but b and c don't.

Consider the problem of determining whether a sequence of N numbers contains N distinct numbers, or instead at least one number occurs multiple times. We can basically sort in O(Nlog2N) time, then take O(N) time to scan.