Emerick Bosch xpcoffee

These are part of my notes for the Coursera course: Algorithms, Pt I (Princeton).

##The Problem

Say we have have some points, which we decide to store in an array.
Say we number these points so that we can tell them apart.

What we have is something like this:

point array: [1][2][3][4] ... [N]

These are part of my notes for the Coursera course: Algorithms, Pt I (Princeton). A setup of the the Dynamic Connectivity problem is explained here

##QuickFind

We make all connected points have the same id-array entries.

A more formal way of putting it is: points are only connected together if their entries in the id-array are the same.
This means that trees have a maximum depth of 2.

These are part of my notes for the Coursera course: Algorithms, Pt I (Princeton). A setup of the the Dynamic Connectivity problem is explained here.

##Quick Union We know from the Dynamic Connectivity setup that points with the same roots are connected. We also know that all points within a tree (or connected component) share the same root. So two points - and therefore two trees - can be connected by making their roots equal. The root of the one point is set as the root of the second point.

To check if two points are connected, their roots are compared.

These are part of my notes for the Coursera course: Algorithms, Pt I (Princeton).
The QuickUnion algorithm is explained here

##QuickUnion Weighting

Tall trees are the major reason that QuickUnion takes time to check if two items are connected.
If the height of trees can be minimized, QuickUnion will be faster.

Weighting makes sure that when two trees are connected, the smaller of the two trees is added to the larger tree (not the other way around).
In other words: the root of the smaller tree is assigned the value of the root of the larger tree.

These are part of my notes for the Coursera course: Algorithms, Pt I (Princeton).
The QuickUnion algorithm is explained here.

##QuickUnion Path Compression

QuickUnion mostly takes time when finding the roots. While finding the root of a point, we may touch multiple nodes on the way to the root.

If we make all of these nodes (including our initial point) connect to the root once we find it, it will save time later on.

These are part of my notes for the Coursera course: Algorithms, Pt I (Princeton).

##Doubling Hypothesis This is used to determine the variables of a power law quickly:

T = a*N^b

Methodology

Run algorithm many times, doubling inputs with each run.

These are part of my notes for the Coursera course: Algorithms, Pt I (Princeton).

##Selection Sort

####Concept

iterate through all items to find the smallest
swap the found item with the front-most item | Repeat

These are part of my notes for the Coursera course: Algorithms, Pt I (Princeton).

##Insertion Sort

####Concept

iterate through items
with each iteration, a new item is 'discovered'

These are part of my notes for the Coursera course: Algorithms, Pt I (Princeton).

##Shellsort

####Concept

sequence of H-Sorts (with differing h values) which result in a fully sorted array.
sequence of h values must be well chosen as it has a significant effect on the runtime and efficiency of the operation

	/*
	Author: Emerick Bosch

	This script imports new transaction history values.
	Input is a .csv file - downloaded from FNB, Account, Transaction History.
	The input .csv is uploaded to Google Drive and converted to a Google Sheet.
	The input file name, as well as the google serial numbers of the input file and its containing folder are needed and entered below.
	*/