Algorithm Learning Notes #1: Module 1

Module 1

INTRODUCTION

These are my notes while learning from an algorithm course

Algorithms are methods of solving a problem.

Data structure are methods of storing information

Data Structures

Arrays stores items in a list, and labels them with integers starting from 0

Linked List is like a array but with pointers pointing to the next item 

Stack: Follows Last In, First out principle, like a stack of plates, if u want to access the data, you have to "pop" the last one off the top.

Queue: Inverse of stack, so it First In, First Out, The first one in is the first one out.

Hash/Map/Dictionary: A Hash is like an Array but instead of integers, you define the keys to the items

Tree: Sometimes those the linear methods above can be inefficient, so the tree method stores the data in a hierarchy that can usually be more easily traversed. 

Graph: Sometimes the tree method might be a bit too rigid of a method so instead, a graph structure can be used. 

Datastructures are useless without the algorithms coded, 

Functions: block of code, that takes and input and "returns" an output. 

Functions can be called from other parts of the code 

The function calling could also have input parameters that can feed back into the function

In this case, if we send 2, and 3. the Add function has "a" and "b" to store those, and we could manipulate those values with operators in the code body. (Add, equals, greater than..etc)

When a code produces a value it's called an expression

Sometimes a piece of code doesnt return a value and instead just performs an action

The if statement is an example of a statement and is an example of conditional logic, if the condition is true then it will run code and another code if it is false. 

A popular statement are loops, an example would be the while loop, it keeps repeating code until the condition is true

while loops can be useful, but its most likely and more useful to loop over a iterate datatype like an array.

Most programming languages use a for loop to iterate through these  datatypes

sometimes functions dont return a value which means this function is a void. 

a function can call itself, which could lead to an infinite loop

This happens because when u call a function, the program will put it into short term memory called a callstack. 

when a language keeps pushing a function onto the callstack, it'll eventually overload and become a stack overflow. 

In order to prevent this, we need a base condition that will terminate the loop.

The Big OH Notation

In order to check if our algorithm is good, we need to follow the Big Oh Notation.

this is a standard of approximating the performance of an algorithm as its input size grows. 

The variable N, determines the number of inputs

It make take more time complexity(how much time a result is given) or space complexity(how much memory in the computer)

If N is being scaled up to infinity, the faster the result grows after each step, the worst the algorithm performs.

Technical  interviews often want you to estimate the time and space complexity of your algorithm.

This is a loop over an array of elements, this takes exactly one unit of time to loop over everthing. 

The array of elements is an example of linear time as there's a one to one relationship between the amount of inputs and the time it takes to execute the algorithm.

Often we can create a more faster algorithm.

This is called a sorted array and we can perform a binary search where the pointer starts at the middle and jump back and forth until we find to find the actual value we're looking for. 

The sorted array is an example of logarithmic time which is way more efficient at higher amount of inputs

This algorithm searches up the desired value in an array by its index. 

That is an example of constant time which means it should always take the same amount of time no matter high big the array is. 

on the lesser efficient end, we have an example, a loop within a loop, this raises the number of inputs to thee number of 2. 

The least efficient way is exponential time which an example would be an algorithm that loops over every single value. 

Topic Overview

Why learn algorithms? 

The impact of algorithms is very broad and far reaching. Algorithms are used in the internet, biology, commercial computing, computer graphics, computer security, social networks and scientific applications. 

• The main reason is to use algorithms to solve problems that otherwise cannot be addressed. 
• Intellictual stimulation 
• To become a proficient programmer- Data structure and algorithms is a core of programming.
• To have fun and profit. 

Mini-test: Java

Hello World

Hello and Goodbye: User Inputs

UNION FIND 

The Union Find Problem, a set of algorithms that can solve problems relating to dynamic connectivity.

Steps Of Developing a Usable Algorithm 

* Model the Problem, Whiteboard, Pen and Paper, Understand the problem, find out requirements and elements

* Find an algorithm to solve the problem.

* Is it fast enough? Fits in Memory?

* If above != true,  find out why. 

* Find way to improve problem.

* iterate until finished

Given a set of N objects:

* Union Command: Connect Two Objects

* Query: Is there a path connecting the two objects

Example: This would need a computer, and an algorithm to find the answer. 

Applications involve manipulating objects of all types

* pixels in a digital photo

* computers in a network

* friends in a social network

* Transisters in a  computer chip

* elements in a mathematical test

* variable nams in fortran program

* metallic sites in a composite system

When programming, convenient to name objects 0 - N-1.

* Use integers as array index

* Suppress details not relevant too union find

Modelling The Connections

We assume "is connected" is a equivalence relation "="

* Reflexive: p is connected to p.

* Symmetric: if p is connected to q, then q is connected to p.

* Transitve: if p is connected to q and q is connected to r, then p is connected to r

Implementing the operations

* Find query: check if two objects are in the same component

(* union command: replace components containing two onjects

Goal: Design efficient data structure for union find.

* Number of objects N can be huge

* Number of operations M can be huge

* Find queries and union commands may be intermixed

public class UF

Two methods, one to implement union and one for connected. 

void union(int p, int q)

boolean connected (int p, int q)

int find(int p)

int count())

Testing

One practice before getting to far into coding is to check the api design. By building a client.

take integer from standard input

create uf object out of it 

while loop, while the input is not empty, 

read 2 integers from the input

if they'[re not connected, connect and print. 

QUICK FIND

"Eager Approach"

we check if p and q have the same id in the array, since id[6] = 0 and id[1] = 1. 6 and 1 are not connected.

QUICK FIND DEMO

If Four is supposed to be union with three. Then we're going to change, all entries, 

whose ID is equal to the first ID to the second one. So in this case, we

 need to change the four to a three.

If we're connecting 3-4 to 8, 3-4 is already connected and need to be changed to 8. 

the "connected" operation checks if 8 and 9 are connected/already unioned. since 3-4-8-9 have the same id of 8, they are connected.

another example would be connected(5,0) where it would return false as 5 = 5 and 0 = 0. If we want it to be connected, we do a union and 5 and 6 would be equal to 0 to match 0 

This is an example on how it would be done, this isn't a working code but it's meant to show a generalised method and approach.

Is QuickFind effective?

The Find Operation is quick, but it is too expensive for large problems. As computers get faster and bigger, quadratic algorithms get slower. A rough standard for now is that people have computers that can run billions of operations per second, and they have billions of entries in main memory. This means that, with huge memory, we can address huge problems, but the problem with that quick find algorithm is that it would take ten^18th operations, or 30 some years of computer time. To avoid this, we are developing more efficient algorithms for solving problems like this.

QUICKUNION

QuickFind is established to be too slow, so another way called the "Lazy Approach"

The point of programs and algorithms is to make work more efficient, and to avoid doing work. 

This approach uses the same data stucture but with a different interpretation

The array can be though off as a set of trees called a forest. Each entry in the array is going to contain a referencce to its parent 

the example here shows that 3's parent is 4, and 4's parent is nine. 2 is also connected to it. 

The "Roots" are identified by elements that are all by themselves in just, in their own connected component, eg: 0 is 0, 1 is 1, 9 is 9, 6 is 6, 7 is 6, 8 is 8. while others such as 2 are connected to 9. 

Now, once we can calculate these roots, then we can implement the find operation just by checking whether the two items that we're supposed to check with are connective where they have the same root.

To merge components containing two different items. Two items that are in different components.

 All we do is set the ID of P's route to the ID of Q's route. Let's make P's tree point to Q. So in this case, we would change the entry of nine to be six to merge three and five. The components containing three and five. And with just changing one value in the array we get the two large components emerged together. That's the Quick-union algorithm. 
 

If we want 3 to be a root of a tree and 4 to be connected all we have to do is change the root of 4 to 3. 

This is a code that can implement Quick union

1. we set each object to be it's own root. 

2. set a private method where we chase the parents pointers until we reach the roots, if we can't we move the pointer and make it i

3.check if p and q have the same root. 

4. change root of p to the point of root q. 

Is Quick Union Effective?

Quick-union is faster than Quick Find, but it is too slow for large problems. The defect for Quick-union is that the trees can get too tall, meaning that the find operation would be too expensive. Costing involving in the ray axises just to do the find operation is too slow if you have a lot of operations.

How to improve Quick Union?

Quick Union simply can't support a huge dynamic connectivity problems. So, how are we going to do better? That's what we'll look at next. A very effective improvement, it's called weighting. And it might have occurred to you while we are looking at these algorithms. The idea is to when implementing the quick union algorithm take steps to avoid having tall trees. 

When we have a large and small tree, a quick union might put the larger tree below the smaller tree, in a weighted quick union, both trees are balanced.

This can be done by linking the root of the smaller tree to the root of the larger tree. 

In a weighted algorithm we always put the smaller tree lower. 

Weighted Quick Union Demo

First we start out in the starting position. 

But now if we have to merge 8 with 4 and 4, we put 8 as the child, no mattter which order the arguments come as the its the smaller tree. 

Same here if we needed a 9 to merge. 

So overall, we make the smaller tree always smaller than the larger one in a weighted algorithm.

Quick Union vs Weighted Quick Union

This is what happens if we don't have weight. A lot of nodes are far away from the root while the weighted ones are close to the root. 

Java Implementation

Nearly identical structure to the normal quick union code however, we modify it to check the size of the tree, then it adds the small tree to the large tree. 

the find operation takes time proportional to the depth of p and q, 

The union takes constant time, given roots. 

Depth of any node x is at most lg N,

we use Lg for logorathm to the base 2, n10 = 1000, n20 = million, n30 = biliion

 

The depth of x will increase by 1 when it's tree t1 is merged into some other tree, t2. x at least doubles after merge. 

what happens in the design of algorithms is now that we understand what it is that gains performance, we take a look and see, well, could we improve it even further. And in this case, it's very easy to improve it much, much more. And that's the idea of path compression. And this idea is that, well, when we're trying to find the root of the tree containing a, a given node.

Union Find Applications

Percolation

percolation refers to the flow of information, data, or signals through a network or system. It is often used to describe the process of filtering information through multiple layers or levels, like a percolating liquid flowing through a porous material. The concept of percolation is used in various fields, such as graph theory, computer networks, and statistical physics.

In graph theory, percolation refers to the study of how information spreads through a network, considering the nodes of the network as potential points of transmission and the edges as possible pathways for information flow. In computer networks, percolation is used to study the transmission of data through the network, the behavior of the network under different conditions, and the reliability and robustness of the network.

In essence, percolation in computer science is the process of understanding and modeling the flow of information through a system.

Analysis of algorithms

Programmers needs to develop a working solution.

Client wants to solve the problem efficient.

Theoritician wants to understand.

Algorithms has to reach it's solution in the shortest possible time. 

The main reason we analyse algorithms is that get rid of performance bugs, 

FFT algorithm is an efficient algorithm for computing the discrete Fourier transform (DFT) of a sequence of complex numbers. It uses a divide-and-conquer strategy to split the DFT into smaller DFTs, which can then be calculated recursively. This reduces the number of operations needed to calculate the DFT, making the FFT much faster than directly evaluating the DFT. It has numerous applications in fields such as signal processing, image processing, and scientific computing.

The Discrete Fourier Transform (DFT) is a way of representing a signal in terms of its different frequencies. This can be useful when we want to analyze the frequency content of a signal, or when we want to manipulate the signal by changing the amplitude or phase of certain frequencies.

Use scientific method of analysing algorithm

Observation of Algorithms