DEV Community: Omar

Message Queue

Omar — Sat, 29 Apr 2023 11:52:08 +0000

Hello, this article is an attempt to explain message queue without particular tool, but rather a big picture of what they offer without entering details of each message queue technologies like kafka, rabbitMQ, nats

What is Queue

A queue also known as FIFO ( First In First Out ) , it's a data structure that allows to operate the data in the order they have been inserted.
Example: we have 3 persons A, B and C that are waiting the store to open. First A will enter the queue so now we have person A in the queue

------------
| A
------------

then after couple of minutes person B have arrived, so now we have in the Queue two persons A and B

------------
| B A
------------

each one of them waiting for their turn, now the store opens,
the store will start taking orders of person A first because they entered first. So now we only have B in queue

------------
| B
------------

The person C have arrived and entered the queue, so the person C will wait person B to finish.

------------
| C B
------------

and so on.
With same concept in computation we can imagine the persons are tasks, or giving data we need to process in order.
This is the queue in it's simplest form, we have many queues types, like a priority queue, where each person have a priority and they are served based on their priorities.
And we have Concurrent Queues that works with multiple threads, and so on.

What is message queue

A message queue is also a concurrent data structure that hold messages, those messages can be any kind of data in addition to metadata that can help the messages system to manage the messages, like it's source and it's destination, how long the message will live and so on...

Why we need a message queue

Let's take a study case, where we have a service A that collect some articles from internet and it send them to service B, and let's assume that time of processing the article is slower than collecting it. If A keeps sending many articles to service B while service B is already processing an article, the article will be lost, so we need a kind of data persistence were we can get the article
that process this data.
A message channel acts as a temporary buffer for the receiver. Unlike the direct request-response communication style, messaging is inherently asynchronous, as sending a message doesn’t require the receiving service to be online.

Pattern of message queues

1- Point to point

Point to point is simplest form of message queuing where there is a single producer ( the service that emit the message ) and single consumer ( the service that receive the message )

2- Competing Consumers

Where there is one producer and multiple consumers, how ever only one consumer will receive the message.

3- Publish-Subscribe

the Publish-Subscribe Channel delivers a copy of the message to each consumer.

Those are not the only patterns, but it gives a brief idea on how we can use multiple queues and link them together.
Like we can use the request-reply pattern, where producer sends the message in a channel A and the consumer reply to the consumer with another channel B.

Guaranty

Message brokers are designed to be scale horizontally, that means they are meant to be distributed.
And like any distributed system it comes with it's own challenges, and each broker take different implementation with it's tradeoffs.

For message delivery guaranty many message brokers support:

1- At-most-once delivery. This means that a message will never be delivered more than once but messages might be lost.

2- At-least-once delivery. This means that we'll never lose a message but a message might end up being delivered to a consumer more than once.

3- Exactly-once delivery. The holy grail of messaging. All messages will be delivered exactly one time.

it's impossible to achieve exactly once, because the consumer instance has to delete a message from the channel once it’s done processing it so that another instance won’t read it. If the consumer instance deletes the message before processing it, there is a risk it could crash after deleting the message but before processing it, causing the message to be lost for good. On the other hand, if the consumer instance deletes the message only after processing it, there is a risk that it crashes after processing the message but before deleting it, causing the same message to be read again later on.

Because of that, there is no such thing as exactly-once message delivery. So the best a consumer can do is to simulate exactly-once message processing by requiring messages to be idempotent and deleting them from the channel only after they have been processed.

Failures

When a consumer instance fails to process a message, the visibility timeout triggers, and the message is eventually delivered to another instance. What happens if processing a specific message consistently fails with an error, though? To guard against the message being picked up again, we need to limit the maximum number of times the same message can be read from the channel.

To enforce a maximum number of retries, the broker can stamp messages with a counter that keeps track of the number of times the message has been delivered to a consumer. If the broker doesn’t support this functionality, the consumer can implement it.

Once we have a way to count the number of times a message has been retried, we still have to decide what to do when the maximum is reached. A consumer shouldn’t delete a message without processing it, as that would cause data loss. But what it can do is remove the message from the channel after writing it to a dead letter channel — a channel that buffers messages that have been retried too many times.

This way, messages that consistently fail are not lost forever but merely put on the side so that they don’t pollute the main channel, wasting the consumer’s resources. A human can then inspect these messages to debug the failure, and once the root cause has been identified and fixed, move them back to the main channel to be reprocessed.

Backlogs

One of the main advantages of using a message broker is that it makes the system more robust to outages. This is because the producer can continue writing messages to a channel even if the consumer is temporarily unavailable. As long as the arrival rate of messages is lower than or equal to their deletion rate, everything is great. However, when that is no longer true and the consumer can’t keep up with the producer, a backlog builds up.

A messaging channel introduces a bimodal behavior in the system. In one mode, there is no backlog, and everything works as expected. In the other, a backlog builds up, and the system enters a degraded state. The issue with a backlog is that the longer it builds up, the more resources and/or time it will take.

There are several reasons for backlogs, for example:

more producer instances come online, and/or their throughput increases, and the consumer can’t keep up with the arrival rate
the consumers performance has degraded and messages take longer to be processed, decreasing the deletion rate
the consumer fails to process a fraction of the messages, which are picked up again until they eventually end up in the dead letter channel. This wastes the consumer’s resources and delays the processing of healthy messages.

To detect and monitor backlogs, we can measure the average time a message waits in the channel to be read for the first time. Typically, brokers attach a timestamp of when the message was first written to it. The consumer can use that timestamp to compute how long the message has been waiting in the channel by comparing it to the timestamp taken when the message was read. Although the two timestamps have been generated by two physical clocks that aren’t perfectly synchronized, this measure generally provides a good warning sign of backlogs.

Fault isolation

A single producer instance that emits poisonous messages ( message that repeatedly fail to be processed ) can degrade the consumer and potentially create a backlog because these messages are processed multiple times before they end up in the dead-letter channel. Therefore, it’s important to find ways to deal with poisonous messages before that happens.

If messages are decorated with an identifier of the source that generated them, the consumer can treat them differently. For example, suppose messages from a specific user fail consistently. In that case, the consumer could decide to write these messages to an alternate low-priority channel and remove them from the main channel without processing them. The consumer reads from the slow channel but does so less frequently than the main channel, isolating the damage a single bad user can inflict to the others.

Go and copies

Omar — Fri, 16 Jul 2021 17:50:40 +0000

Copying concept was always weird for me , when I learned GO it was like why? Why! Why GO favorite option is to work on a copy?!
Today I make discovery that I will like to share.

I was reading a book "composing software" and I see an example about Shared State.
"Shared-state concurrency means that concurrent computations communicate through reading and updating a shared location in memory."-source

I know the title said GO but the examples that let me understand the importance of copying in GO was an example in the book which is JavaScript , so the examples are in JavaScript.

Let's take a look at this example taken from the book.

// Shared state
const x = {
    val: 2
};

// Mutates shared state
const x1 = () => x.val += 1;

// Mutates shared state
const x2 = () => x.val *= 2;

x1();
x2();

console.log(x.val); // 6

// This example is exactly equivalent to the above, except...
const y = {
    val: 2
};

const y1 = () => y.val += 1;

const y2 = () => y.val *= 2;

// ...the order of the function calls is reversed...
y2();
y1();

// ... which changes the resulting value:
console.log(y.val); // 5

this code seems logical , but let's say we have 2 threads (or routines) accessing the same object x in same time.
both of them are modifying the same object , so the output depends on race condition.

so to avoid this we use (yes you guess it) a copy!

const x = {
    val: 2
};

const inc = x => ({...x, val: x.val + 1});
const double = x => ({...x, val: x.val * 2});

console.log(inc(double(x)).val); // 5

const y = {
    val: 2
};

/*
Because the functions don't mutate, you can call
these functions as many times as you want, in any order,
without changing the result of other function calls.
*/

// These calls do nothing:
inc(y);
double(y);

console.log(inc(double(y)).val); // 5

the three dots ... are spread operator basically it will copy the propriety of the object and the function will return a new copy with modified value. Once I read this code I directly remembered GO , the idea in GO that everything is a copy was weird for me. And as we know go main feature is concurrency so everything as a copy seemed a very good and safe choice by go designers.
so the advantage of working on a copy is safety , isolation , multi threading , but it also have disadvantage like deficiency.

That's why we like in GO to avoid as much as we can using pass as pointer.

that was my discovery today that I liked to share with community , please if you have more information that can help us , share it with us!

#011 DS&A - Sorting

Omar — Thu, 08 Oct 2020 19:38:26 +0000

Sorting Techniques

Insertion sort algorithm and analysis

Insertion-sort(A)
{
    for j = 2 to A.length
        key = A[j]
        // insert A[j] into sorted sequence A[1...j-1]
        i = j-1
        while(i>0 and A[i] > key)
            A[i+1] = A[i]
            i = i-1
        A[i+1] = key
}

every time you visit an element you check the one before it if it's greater swap them , if their is a swap you compare the new element with old elements in array.

Worst case is Teta(n^2) is if the sorted list is backward sorted from biggest to lowest , and best case is Omega(n) if array is already sorted , and space complexity is O(1) called inplace which mean we don't use extra spaces.

We can't optimize it if we apply binary searching the comparison between new element and old elements is O(log n) and movement required is O(n) , in doubly linked list it require O(n) for comparison and O(1) for movement. In both cases we have bottleneck to O(n)

Merge sort algorithm and analysis

MERGE(A, p , q , r)
{
    n1 = q-p+1
    n2 = r-q
    let L[1...n+1] and R[1 to n2+1] be the new arrays
    for(i=1 to n1)
        l[i] = A[p+i-1]
    for(j=1 to n2)
        R[j] = A[q+j]
    L[n1+1] = inf
    R[n2+1] = inf
    i = 1 , j = 1
    for(k = p to r)
        if(L[i] <= R[j])
            A[k] = L[i]
            i=i+1
        else
            A[k] = R[j]
            j=j+1
}
// A is array , p is start index , q is end of sorted arr1 index , r is last index

The merge here work having a main array contain 2 sorted arrays inside of it

0	1	2	3	4	5	6	7
1	5	7	8	2	4	6	9

this will be divided into 2 arrays L and R
L from p to q

0	1	2	3	4
1	5	7	8	Inf

R from q+1 to r

0	1	2	3	4
2	4	6	9	Inf

after dividing the main array to 2 it will start to compare R[j] with L[i] if will increment the index of the lower like if L[i] < R[j] i will be incremented by 1 , and inserting them into array , and note that Inf here is large number with same type of data.

then array will become

0	1	2	3	4	5	6	7
1	2	4	5	6	7	8	9

this algorithm will take O(n) for dividing arrays and n+n to copy elements back to array is O(n) so time taken is O(n)

space complexity is O(n) also.

merge-sort(A, p , r) - T(n)
{
    if p<r
        q=L[(p+r)/2]
        merge-sort(A,p,q) - T(n/2)
        merge-sort(A,q+1,r) - T(n/2)
        merge(A,p,q,r) - O(n)
}

the size of stack required for merge-sort is log(n)+1 so space complexity is o(log n) and merge will require is O(n) so total is O(n) + O(log n) which n is dominated so O(n) is space complexity.

T(n) = 2*T(n/2)+O(n) = O(n*log(n) we use here the master theorem to calculate time complexity

so what ever is the size of problem it will always take O(n*log(n))

Quick sort algorithm and analysis

PARTITION(A,p,r)
{
    x = A[r]
    i = p-1
    for(j=p to r-1)
    {
        if(A[j] <= x)
        {
            i=i+1
            exchange A[i] with A[j]
        }
    }
    exhange A[i+1] with A[r]
    return i+1
}

Partition algorithm is about putting the last element of array in it's right place where left of it are values which less (no sorted) of it's value and right is greater (not sorted) . Since the for will loop n times so time complexity will be O(n)

QUICKSORT(A,p,r) - T(n)
{
    if(p<r)
    {
        q = PARTITION(A,p,r) - O(n)
        QUICKSORT(A,p,q-1) - T(n/2)
        QUICKSORT(A,q+1,r) - T(n/2)
    }
}

it will keep sub-Quick-sorting and return every time it will face p==r or p>r

worst space complexity is O(n) and average is O(log n)

time complexity is T(n)=2*T(n/2)+O(n) = Teta(n log(n) ) using the master theorem

the worst case is where the number the last element is in the right order.

time complexity will be

T(n) = T(n-1) + O(n)
     = T(n-1)+cn
     = T(n-2)+c*(n-1)+c*n
     = T(n-3)+c*(n-2)+c(n-1)+c*n
     ...
     = c+2c+3c+...+c*n
     = O(n^2)

Introduction to heaps

heap trees are is a binary tree or 3-ary tree or n-ary tree.

let's talk about binary tree heap only , heap have their root is max heap and all nodes sub-tree should be smaller than the parent node.

A complete Binary tree of height h has 2h-1 nodes. Out of these 2h-1 are leaf nodes and rest (2h-1-1 are non-leaf)

Canonical labeling of nodes

Label the Nodes in the level-wise fashion from left to right, as shown below:

The advantage of canonical labeling is that such a tree can be stored in an array where value of a node is stored at the index equal to its label in the tree.

This way we will save a lot of memory because we do not need to store all the pointers. If you have noticed, there is a relationship between the labels of a node and its children above:

2*a is nothing but left shifting , so it's easy to implement in computer. 10 is a binary number represent 2 in decimal if i left shift it it will become 100 which is 4 in decimal.

This way, it becomes easy to move in either upward or downward direction of a tree, even when it is stored in an array.

Below trees are NOT almost complete binary trees (the labeling has no meaning, because there are gaps).

-- source

The input of an Algorithm affect the time complexity a lot let's take those cases

	insert	search	find min	delete
unsorted array	O(1)	O(n)	O(n)	O(n)
sorted array	O(n)	O(log n)	O(1)	O(n)
unsorted linked list	O(1)	O(n)	O(n)	O(n+1)=O(n)
min heap	O(log n)		O(1)	O(log n)

Max heapify algorithm and complete binary tree

to build A heap in first place we should re-arrange it in a way that the parent always bigger than children.

max-HEAPIFY(A,i)
{
    l = 2*i;
    r = 2*i+1;
    largest = i;

    if(l <= A.heap-size and A[i] > A[i]) largest = l; // check if it's have a left child 
    if(r <= A.heap-size and A[r] > A[largest]) largest = r; // check if it's have a right child
    if(largest != i)
    {
        exchane A[i] with A[largest]
        max-HEAPIFY(A,largest)
    }
}

the heart of this Algorithm is if we have sub-trees are max-heap but we need to make the root max-heap also.

time complexity is O(log n) which is the height of the tree , space complexity is the number of recursive calls O(log n)

Build max heap algorithm and analysis

BUILD-max-heap(A)
{
    A.heap-size = A.length
    for( i = floor(A.length/2) down to 1) 
        max-HEAPIFY(A,i)
}

take this array A as an example 9,6,5,0,8,2,1,3

length of A is 8 floor(8/2)+1 = 4+1 = 5 (we add 1 because we start from 1 not 0)

so from index 5 to 1 we need to apply max-HEAPIFY(A,i) , index 5 is already a leaf so nothing to do go to index 4 0<8 so swap them

then in index3 we have 5 > 2 > 1 so nothing to do , go to index 2 we have 6<8 so swap

and index 1 is already the biggest so nothing to do.

what is the total time taking to build this max-HEAP ?

height of tree is log n and we are applying it n times so you will think that will take O(n log n) but it's not the time complexity is not the way to do it.

the number of nodes at height is

Therefore, the cost of heapifying all subtrees is:

where is nothing than 2 (there is a proof for this)

and for space complexity required will be O(log n)

Extract max from heap

Heap-extract-max()
{
    if A.heap-size < 1
        error "heap underflow"
    max = A[1]
    A[1] = A[A.heap-size]
    A.heap-size = A.heap-size - 1
    max-HEAPIFY(A,1)
    return max
}

Now that we have the Heapify procedure, the Extract-Max procedure isn't hard to define at all. Suppose we have the following heap.

Extracting the node with maximum value is easy enough - by the definition of a heap, it is at the top. So we return it. Fine. Now the question is how to turn what remains,

back into a heap. We can almost run the heapify procedure on the whole thing, except that we have two complete binary trees, not one.

So we move the node at the bottom right to the top.

Now we can perform the Heapify procedure on the whole tree.

time taking is O(log n) and same for space.

Heap - increase key

Heap-Increase-Key(A, i, key)
// Input: A: an array representing a heap, i: an array index, key: a new key greater than A[i]
// Output: A still representing a heap where the key of A[i] was increased to key
// Running Time: O(log n) where n =heap-size[A]
1 if key < A[i]
2   error(“New key must be larger than current key”)
3 A[i] ← key
4 while i > 1 and A[Parent(i)] < A[i]
5   exchange A[i] and A[Parent(i)]
6   i ← Parent(i)

because it's increase a key we don't need from our key to be less than element so we return error, and we loop until we reach the root , and for every node we see it's parent if it's less or bigger than the key we exchange it.

if we need to decrease a node we need to max-heapify for the tree in that node , which in worst case will take O(log n)

Heap Sort

HEAP-sort(A)
{
    BUILD-max-HEAP(A)
    for(i = A.length down to 2)
    {
        exchange A[1] with A[i]
        A.heap-size = A.heap-size-1
        max-HEAPIFY(A,1)
    }   
}

we are running max-HEAPIFY n times so time complexity is O(n * log(n)) where log n is time complexity of max-HEAPIFY

Bubble sort

BubleSort(int a[] , n)
{
    int swapped,i,j;
    for(i=0;i<n;i++) {
        swapped = 0;
        for(j=0 ; j<n ; j++) {
            if(a[j] < a[j+1]){
                swap(a[j] , a[j+1]);
                swapped = 1;
            }
        }
        if(swapped == 0) break;
    }
}

the worst case is reversed sorted array which is O(n^2)

and average case is O(k*n) and best case is O(n)

Bucket sort

bucket sort generally use to solve kind of problem where numbers are float and range from a to b with a and b are float.

0.35 , 0.12 , 0.43 , 0.15 , 0.04 , 0.50 , 0.132

it will take first number . and put it in it's place if is already an element there it will sort them then printing them in order.

0.04 , 0.12 , 0.132 , 0.15 , 0.35 , 0.43 , 0.50

in best case where the numbers will be inserted without need to sort to place new item in cell so every insertion will take O(1) , so all the insertion will take O(n) and space complexity will be O(n+k)

the worst case O( (n/k) * n ) = O(n^2)

Counting sort

Counting sort have restrictions to apply , the restriction is that the input is in a range.

let's say our range is from 1 to 5

so we will take an array of 5 elements 2 2 3 4 1 5 1 5

INDEX	appearance
1	2
2	2
3	1
4	1
5	2

then we print them in order 1 1 2 2 3 4 5 5

time complexity isO(n+k) and space complexity is O(k)

the disadvantage we can not go outside range and if the range is big , and the elements are few

1 1000 2 3 so the amount of space we need is 1000 for only 4 elements.

### Radix sort

Do following for each digit i where i varies from least significant digit to the most significant digit.

Sort input array using counting sort (or any stable sort) according to the i’th digit.

Example

Original, unsorted list:
170, 45, 75, 90, 802, 24, 2, 66

Sorting by least significant digit (1s place) gives:
[*Notice that we keep 802 before 2, because 802 occurred
before 2 in the original list, and similarly for pairs
170 & 90 and 45 & 75.]

Sorting by next digit (10s place) gives:
[*Notice that 802 again comes before 2 as 802 comes before
2 in the previous list.]

802, 2, 24, 45, 66, 170, 75, 90

Sorting by the most significant digit (100s place) gives:
2, 24, 45, 66, 75, 90, 170, 802

Let there be d digits in input integers. Radix Sort takes O(d*(n+b)) time where b is the base for representing numbers, for example, for the decimal system, b is 10. What is the value of d? If k is the maximum possible value, then d would be O(logb(k)). So overall time complexity is O((n+b) * logb(k)). Which looks more than the time complexity of comparison-based sorting algorithms for a large k. Let us first limit k. Let k <= nc where c is a constant. In that case, the complexity becomes O(nLogb(n)). But it still doesn’t beat comparison-based sorting algorithms.
What if we make the value of b larger?. What should be the value of b to make the time complexity linear? If we set b as n, we get the time complexity as O(n). In other words, we can sort an array of integers with a range from 1 to nc if the numbers are represented in base n (or every digit takes log2(n) bits).

-- source

#003 - Clean Code - Functions

Omar — Sat, 26 Sep 2020 00:35:54 +0000

Functions

functions are what we do virtualing all the code we do , functions contain all the code that we do , so it's worth to know how to do them well.

how big should a fuction be? big ?? smal??

A function should do it once , do it well and do it only. But what does one thing mean?

The first rule of functions

The functions should be small , in old ages the size should be small as the screen size , those days technologie is cheaper than what is was before , now we have multiple screens we big sizes and lot of pixels , so this math relation is no longer correct , maybe the range of a clean function should be between 4-7 lines.

to minimize the function size we should extract all checks if elses to an boolean function .

Remember the scope rule we talk about , if the variable is far from the scope the name should be long and if it is close for be small , In the class we have more than 1 function so the functions should have long descriptive names.

if we have a function that it's big and operate on set of variables , well this is the behavoir of a class. When we convert our function into a class we take the set of variables that the entier class work on into a constructor.

are you out of your mind?

you will say wait my code is now full of small functions I feel lost inside a forest , well that's where a good name came into play a well named classes and functions will never make you lost if you lost it mean your names are bad.

the goegraphy metaphor

Why do we feel so uncomfortable about writing small functions? well it's about our human nature , yes really! We evolve from explorers who love landscapes we like landscapes. so Big functions look more familiar to us.

We put hidden marks to recognize the path like special shapes or signs , in coding those marks are the comments the try and catches . But if someone new join the project he will feel lost. But if we put navigations he will not feel lost. Just as every day we get in the car the road have signs to where we are and where were going. So good logical seperation and naming will help newbies to explore our land (code) .

The bedroom metaphor

We all have our messy room that we don't like any one to touch it , because we know where our stuff are even if it's messy I know if I need my pants that I wear yesterday it's on the floor. If someone organize it for us , we will go back and rearrange it the way we like.

But not all mens love to be single , so some of them will make the biggest mistake of their life , they will link themself to an annoying wife. Now we need to organize all the rooms , all the jars with names on them.

So to go back to our real life , the work . We are going to work with a team so the best way is to put the code in nicely named place , where it can be found later and understoud.

One thing

I hear word say one thing , didn't you? one thing could mean anything. And one thing here should be not for us who write the code it's for those who will read the code after us.

Let's say we need from our function to scrable an website , but this website need to login and our crawler need an driver browser and so on. It's doing onething which is scrable an website but this one thing contain many sub things with it. So we need a thing to tell us if our function is doing only one thing.

Extract till you drop

how to make sure that our function will do one thing?

We extract things from function until we have nothing to exctract any more , and sure we need to exctract things that do one thing Again and again.
Well let's be realistic forget everything we talk about before and look at this.

#010 DS&A - Time and Space Analysis

Omar — Sat, 19 Sep 2020 18:29:10 +0000

Introduction

Nothing to say more than hello 👋,
In Case your wondering who is this man in the banner it's the Khwarizmi the inventor of algorithms concept.
Make sure to follow because I will start more advanced series in future.

Algorithms

Time and Space Analysis

Introduction to asymptotic

In order to solve any problem in computer science we usually write a program , before writing program it's better to write it in formal description which is called Algorithm .

let's say we have a problem P we need to write a program , let's say we write it in c , to write program we need first to write an Algorithm , let's say P have many solutions s1,s2,s3,s4.... the thing that will differ solution from another is time and memory , the science of it is called Design and analysis of algorithm.

some of the notations used in Algorithms are these:

Asymptotic notation

Big(oh) represented by O

if time Increasing as input increasing so the the worst case or upper bound is C*g(n) and satisfy those conditions

f(n) <= C*g(n) ; n >= n0 ; c>0 , n0 >= 1
f(n) = O(g(n))

let's take this example

f(n) = 3n+2 and g(n) = n
f(n) = O(g(n))
f(n) <= C * g(n) , c > 0 , n0 >= 1
3n+2 <= c*n
take c = 4
3n+2 <= 4n => n >= 2

we can pick g(n) = n^2 or n^3 ... n^nbecause f(n) can be written with respect to g(n) but it is preferred to take the smallest one which is n

Big omega represented by Ω

f(n) >= C*g(n) ; n >= n0 ; c>0 , n0 >= 1
f(n) = O(g(n))

example

f(n) = 3n+2 and g(n) = n
f(n) = O(g(n))
f(n) >= C * g(n)
3n+2 >= c*n
take c = 1 and n0 >= 1
3n+2 = Ω(n)

example 2

g(n) = 3n+2 g(n)=n^2
3n+2 ?= Ω(n^2) 
3n+2 >= c*n^2 , n0

We can not find a C that satisfy this solution , so we need to pick things lower than n like log(n) or log(log(n))

Big theta represented by Θ

f(n) = Θ(g(n))
c1*g(n) <= f(n) <= c2*gn(n) ; c1,c2 > 0 , n >= n0

example

f(n) = 3n+2 , g(n) = n
f(n) <= C2*g(n)
take c2 = 4
3n+2 <= 4n

f(n) >= c1*g(n)
take c1 = 1
3n+2 >= n , n0 >= 1

O this mean their is no bigger time than this , and it's called worst case.

Ω this mean their is no better time than this , and it's called best case.

Θ this mean it's the average case , and it's called the average case.

we usually don't care about best case , we care about worst case. If the worst and best cases are the same we generally go for average case.

example: take this array with n elements

0	1	2	3	4	5	6	7
5	7	1	2	4	10	20	11

let's say we need to find element x , best case is Ω(1) , worst case is O(n), average case is Θ(n/2)= Θ(n)

Time Complexity Analysis

the f(n) is not the real time is just approximation time that program take to finish.

there is 2 types of Algorithms :

iterative:
A()
{
    for i=1 to n
        max(a,b)
}

recursive:

A(n)
{
    if() A(n/2)
}

any iterative can be written as recursive and vise versa.

If the Algorithm doesn't have loops or recursion time complexity is constant O(1) , if the time complexity is O(n^2+n) we take the biggest degree so we take it O(n^2)

examples

A()
{
    int i;
    for(i = 1 to n) pf("text");
}

time complexity : O(n)

A()
{
    int i;
    for(i = 1 to n) 
        for(j = 1 to n)
            pf("omar");
}

time complexity : O(n^2)

A()
{
    int i;
    while (s <= n)
    {
        i++;
        s = s+i;
        pf("omar");
    }
}

time complexity : O(sqrt(n))
/*
Analysing :
s : 1 3 6 10 15 21 ...
i : 1 2 3  4  5  6 ...
s will stop on n
let's say k is the final i
and s is nothing but new i + all old i (6 = 3+2+1) so it will stop when it reach
k(k+1)/2 > n
(k^2+k)/2 > n
k = O(sqrt(n))
*/

A()
{
    int i;
    for(i=1;i^2<=n;i++) pf("omar");
}

time complexity : O(sqrt(n))
// Here all the cases are the same

A()
{
    int i,j,k,n;
    for(i=1 ; i<n ; i++)
    {
        for(j=1;j<=i;j++)
        {
            for(k=1 ; k <= 100 ; k++)
            {
                pf("omar");
            }
        }
    }
}

time complexity : O(n^2)

/*
Analysing :
i = 1 , j = 1 time  , k = 100   times
i = 2 , j = 2 times , k = 200   times
i = 3 , j = 3 times , k = 300   times
...
i = n , j = n times , k = j*100 times

1*100+2*100+3*100+...+n*100 
 = 100 (1+2+3+...+n)
 = 100 (n(n+1)/2) = O(n^2)
*/

int i,j,k,n;
for(i = 1 ; i <= n ;i++)
{
    for(j=1 ; j <= i^2 ; j++)
    {
        for(k=1 ; k <= n/2 ; k++)
        {
            pf("omar");
        }
    }
}

time complexity : O(n^4)

/*
Analysing :
i = 1 , j = 1 time  , k = n/2 * 1 
i = 2 , j = 4 times , k = n/2 * 4   
i = 3 , j = 9 times , k = n/2 * 9   
...
i = n , j = n^2 times , k = n/2 * n^2 times

n/2 * 1 + n/2 *4 + n/2 *  9 + ... + n/2 * n^2
 = n/2 * (n(n+1)(2n+1))/6
 = O(n^4)
*/

A()
{
    for(i = 1 ; i < n ; i = i*2)
        pf("omar");
}

time complexity : O(log(n))

/*
Analysing :
i :  1  , 2   , 4   ... n
    2^0 , 2^1 , 2^2 ... 2^k
2^k = n => k = log(n) = O(log(n))
since i is multiplied by 2 every step so log here is base 2
if i is multiplied by k we say log of base k
*/

A()
{
    int i,j,k;
    for(i=n/2 ; i <= n ; i++)
        for(j=1 ; j <= n2 ; j++)
            for(k=1 ; k <= n ; k=k*2)
                pf("omar");
}

time complexity : O(n^2 * log(n))

/*
Analysing :
n/2 * n/2 * log(n) = O(n^2 * log(n))
*/

A()
{
    int i,j,k;
    for(i=n/2 ; i <= n ; i++) // n/2
        for(j=1 ; j <= n ; i = 2*k) // log n
            for(k=1 ; k <= n ; k = k*2) // log n
                pf("omar");
}

time complexity : O(n*(log(n))^2)

A()
{
    // assume n >= 2
    while(n>1)
    {
        n = n/2;
    }
}

time complexity : O(log(n))

A()
{
    for(i = 1 ; i <= n ; i++) // n
        for(j = 1 ; j <= n ; i = j+i) // 
            pf("omar")
}

time complexity : O(n*log(n))

/*
Analysing :

i = 1 , j = 1 to n ; n   times
i = 2 , j = 1 to n ; n/2 times
i = 3 , j = 1 to n ; n/3 times
...
i = n , j = 1 to n ; n/n times

n(1+ 1/2 + 1/3 + ... + 1/n )
 = n (log n) = O(n * log(n))
*/

A()
{
    int n = (2^2)^k;
    for(i=1;i<=n;i++) // n
    {
        j = 2
        while(j <= n)
        {
            j = j^2;
            pf("omar");
        }
    }
}

time complexity : O(log(log(n)))

/*
Analysing :

k = 1 ; n = 4       ; j = 2,4               ; n * 2 times
k = 2 ; n = 16      ; j = 2,4,16            ; n * 3 times
k = 3 ; n = (2^2)^3 ; j = 2^1,2^2,2^4,2^8   ; n * 4 times

n = (2^2)^k => log n = 2^k => log(log(n))=k
n*(k+1) = n(log(log(n)) + 1) = O(log(log(n)))
*/

Time analysis of recursive

A(n)
{
    if(...)
    return A(n/2)+A(n/2);
}

T(n) = c+2*T(n/2)

A(n)
{
    if(n>1) return A(n-1);
}

T(n) = 1 + T(n-1) 
= 1 + 1 + T(n-2) 
= 2+1+T(n-3) 
= k+T(n-k) // k = n-1
= (n-1)+T(1) = n-1+1 = n

back substitution

T(n-1) = 1+T(n-2) -> 2
T(n-2) = 1+T(n-3) -> 3

T(n) = n + T(n)
T(n-1) = (n-1)+T(n-2)
T(n-2) = (n-2)+T(n-3)
-----------------------
T(n) = n + T(n-1)
     = n + (n-1) + T(n-2)
     = n + (n-1) + (n-2) + T(n-3)
     = n + (n-1) + (n-2)+...+(n-k)+T(n-(k+1))
with n-(k+1)=1 => n-k-1=1 => k=n-2
= n+(n-1)+(n-2)+...+(n-(n-2))+T(n-(n-2+1))
= n+(n-1)+(n-2)+...+1
= n(n-1)/2
= O(n^2)

recursive tree method

T(n) = 2*T(n/2) + C ; n>1
     = C ; n = 1

T(1) = T(n/n)
c+2c+4c+...+nc
c(1+2+4+...+n)
c(1+2+4+...+2^k)
c(1 (2^(k+1) - 1) / (2-1) )
c(2^k+1 - 1)
c(2n-1)
O(n)

T(n) = 2*T(n/2)+n ; n > 1
     = 1 ; n = 1

comparing various functions

let's say we have two functions n^2 and n^3 they have n^2 as common so I rewrite it as 1 and n .

If f(n) is given and g(n) is given we take biggest degree and compare them. If they are constants like 2 and 4 we consider them the same.

examples

2^n                         n^2
n log(2)                    2 log(n)
n                           2*log(n)
consider n = 2^100
2^100                       2*log(2^100)
2^100                       200
2^100 >>>>>>>>>>>>>>>>>>>   200
so 2^n growing very large

3^n                         2^n
n*log(3)                    n*log(2)
cancel n and compare it
log(3)                      log(2)

n^2                         n*log(n)
concel common terms
n*n                         n*log(n)
n           >               log(n)

n                           log(n)^100
log(n)                      100*log(log(n))
take n = 2^128
128                         100*log(128)
128                         700
let's take n = 1024
1024                        100*log(1024)
1024                        1000
so n growing larger

n^log(n)                    n*log(n)
log(n)*log(n)               log(n)+log(log(n))
for n = 10^1024
1024*1024                   1034
for n = (2^2)^20        
2^20*2^20                   2^20+20
so n^log(n) is larger

sqrt(log(n))                log(log(n))
1/2 * log(log(n))           log(log(log(n)))
take n = (2^2)^10
5                           3.5

n^(sqrt(n))                 n^log(n)
sqrt(n)*log(n)              log(n)*log(n)
sqrt(n)                     log(n)
1/2 * log(n)                log(log(n))
n = 2^128
64                          7

f(n) =  {
            n^3         0<n<10000
            n^2         n>=10000
        }
g(n) =  {
            n           0 < n < 100
            n^3         n > 100
        }

	0-99	100-9999	10,000 ....
f(n)	n^3	n^3	n^2
g(n)	n	n^3	n^3

we take care about the function in infinity so g(n) is bigger in infinity

Masters theorem

first there is a different between log^2(n) and (log(n))^2 , because (log(n))^2 = log(n) * log(n) and log^2(n) = log(log(n))

masters theorem used to solve reclusive problems

examples

T(n) = 3T(n/2) + n^2
a = 3 , b = 2 , k = 2 p=0
a < b^k
3 < 4
so it's the case 3)a so T(n) = O(n^2 * log^0(n))

T(n) = 4*T(n/2) + n^2
a=4 , b=2 , k=2 , p=0
4=2^2
so it's case 2)a T(n) = O(n^log(4) * log(n)) = O(n^2*log(n))

T(n) = T(n/2)+n^2
a=1 , b=2 , k=2 , p=0
1 < 2^2
it's case 3)a T(n) = O(n^2 * log^0(n)) = O(n^2)

T(n) = 2^n*T(n/2)+n^n master theoreme is not applied

T(n) = 16*T(n/4)+n
a = 16 b=4 k=1 p=0
16>4
so it's 1)

T(n) = 2*T(n/2)+n*log(n)
a=2 b=2 k=1 p=1
2=2 , p>-1 so it's 2)a

if it doesn't directly look like theorem we need to refactoring it

T(n) = 2*T(n/2)+n/log(n)
     = 2T(n/2)+n*log^-1(n)
     a=2 , b =2 , k=1 p=-1
     s = 2^1 so it's case 2)b

T(n) = 2*T(n/4)+n^0.51
a=2 b=4 k=051 p=0
2 < 4^0.51
case 3)a

T(n) = 05*T(n/2)+1/n
a=0.5 not valid

T(n) = 6*T(n/3)+n^2*log(n)
a=6 b=3 k=2 p=1
6 < 3^2
so it's 3)a

T(n) = 64 T(n/8) - n^2 * log(n)
can not apply master theorem

T(n) = 7*T(n/3)+n^2
a=7 b=3 k=2 p=0
7 < 3^2
case 3)a

T(n) = 4*T(n/2)+log(n)
a=4 b=2 k=0 p=1
4 > 2^0
case 1

T(n) = sqrt(2)*T(n/2)+log(n)
a=sqrt(2) b=2 k=0 p=1
sqrt(2) > 2^0
case 1

T(n) = 2*T(n/2)+sqrt(n)
a=2 b=2 k=1/2 p=0
2>2^1/2
case 1

T(n) = 3*T(n/2)+n
a=3 b=2 k=1 p=0
3 > 2^1
case 1

T(n) = 3*T(n/3)+sqrt(n)
a=3 b=3 k=1/2 p=0
3>3^1/2
case 1

T(n) = 4*T(n/2)+C*n
a=4 b=2 k=1 p=0
4 > 2^1
case 3)b

T(n)=3*T(n/4)+(n*log(n))
a=3 b=4 k=1 p=1
3 < 4
case 3)a

Analysis Space Complexity

same as time complexity we have space complexity for Iterative programs and recursive programs. Some times we sacrifice time for space.

Algo(A,1,n)
{
    int i;
    for(i=1 to n) A[i] = 0;
}

this space complexity is constant O(1) because we don't take the initial input into count. So we calculate extra spaces such as i

Algo(A,1,n)
{
    int i;
    create B[n];
    for(i=1 to n) B[i] = A[i];
}

the amount of space required is O(n) because we declare B[n] that contain n element. Same as Time complexity we didn't take in count the constants in other word we take higher degree.

Algo(A,1,n)
{
    create B[n,n];
    int i,j;
    for(i=1 to n)
        for(j=1 to n) B[i,j]=A[i]
}

space complexity is O(n^2)

A(n)
{
    if(n>=1)
    {
        A(n-1);
        pf(n);
    }
}

because the program is small we are going to use the tree method , take n=3

the output is 1 2 3 because every time I end call I print it

the space complexity is the number of stacks which is O(kn) where k is constant so we write it as O(n)

time complexity is T(n) = T(n-1)+1 it's not form where we can apply master theorem so we gonna use back substitution

T(n)  =T(n-1)+1
T(n-1)=T(n-2)+1
T(n-2)=T(n-3)+1
T(n) = T(T(n-2)+1)+1
     = T(n-2) +2
     = (T(n-3)+1) +2
     = T(n-3)+3
     = T(n-k)+k
     = T(n-n)+n
     = T(0)+n
     = 1+n
     = O(n)

so time and space complexity is O(n)

A(n)
{
    if(n>=1)
    {
        A(n-1);
        pf(n);
        A(n-1);
    }
}

number of recursive calls are

A(3) = 15 = 2^(3+1) - 1
A(2) =  7 = 2^(2+1) - 1
A(1) =  3 = 2^(1+1) - 1
A(n) = (2^n) - 1

this is not the space complexity because the stack will only need 4 cells A(0),A(1),A(2),A(3) in the stack in order to compute it where the stack will start to empty it self every time it reach A(0) , so it's (n+1)*k where k is the size occupied by one cell in stack so space complexity is nothing more than O(nk) = O(n).

To optimize it We can use Dynamic programming which is to store the already computed values for not compute them again.

A(n) -> T(n)
{
    if(n>=1)
    {
        A(n-1); -> T(n-1)
        pf(n); -> 1
        A(n-1); -> T(n-1)
    }
}

T(n)    = 2*T(n-1)+1 ; n > 0
T(n-1)  = 2*T(n-2)+1
T(n-2)  = 2*T(n-3)+1

T(n)    = 2(2T(n-2)+1)
         = 4T(n-2)+2+1
         = 4(2T(n-3)+1)+2+1
         = 8T(n-3)+7
         = 2^k * T(n-k) + 2^(k-1)+...+2^2+2+1
         = 2^n * T(0)+2^n-1 + 2^n-2 + ... + 2^2 + 2 + 1
         = 2^n + 2^n-1 + 2^n-2 + ... + 2^2 + 2 + 1
         = O(2^n+1) = O(2^n)

the time complexity is very big O(2^n) we can lower it with Dynamic Programming as we said.

#009 DS&A - Hashing

Omar — Sun, 13 Sep 2020 20:17:20 +0000

Hashing

Direct address Table

we have many data structures but they are all slow at searching.

type	time complexity
unsorted array	O(n)
sorted array	O(log n)
linked list	O(n)
Binary Tree	O(n)
Binary Search Tree	O(n)
Balanced Binary Search Tree	O(log n)
Priority (min and max)	O(n)

to minimize the searching time we use hashing which is O(1) , also some people use Direct address Table is just same as an array.

{1,2,3,4,5,...,100} if we need to put insert an element we put it with a key and store it let's say we need to store the number of occurrence for character C the number of ASCII let's assume it's 128

arr[99] I will store in this array the number of occurrence for c where 99 is the key of c

, and now if I need to access the number of occurrence letter c I can access it directly using arr[99] which is O(1)

Introduction to hashing

the problem with this direct access is that array should have big as key sizes , to solve this problem we use hashing.

let's say we have m keys and n elements. in order to map a key to element we need an hash function which will take time of n%m which is constant O(1) . When we need to hash a new element to element and it have same location of an previous element it's called collision example141%10=1 and 21%10=1 so this is collision because they have same key . The challenge with hash map is the collision.

  i) better hash functions
 ii) chaining (using linked list)
iii) open addressing , implemented using verious ways
  a) linear probing
  b) quadratic probing
  c) Double hashing

chaining

after computing the hash if there is a collision , the previous value will link to the new value.

worst case search - O(n)
worst case deletion - O(n)

average search O(1+ alpha)
average deletion O(1)

where n is the number of elements represented in the linked list , and m is the number of cells in linked list.

alpha = n/m where alpha is the load factor.

An advantage of chained hash table over open addressing scheme is deletion is easier.

Open addressing

open addressing AKA closed hashing

let's say we have array that can hold m elements it mean all the elements I need should be inside array not outside like chaining and U keys , where U is very large and m is limited so definitely their is a collision.

we have the load factor alpha which is always will be between 0 and 1 .

We resolve the collision by applying the hash function with a small modification , this is called probing second time. Probing is nothing but finding location in hash table where we need place an element.

we apply the hash function if we find that the element is already picked we make a combination between u and finite set [0,m-1]

the worst time here to search an element is O(m) because we need to visit all the table to find that element.

assume the X is mean that slot is not empty and N is NULL (we can put element here).

h(k)        = 0

1 is NULL so I can put k in it.

h(k1)       = 1
h(k1 , 1)   = 5
h(k1 , 2)   = 6

h(k1) is 1 but 1 is not free ( their is collision ) so we run hash function again we get 5 which also is not free , so we run it again with 2 we get 6 which is NULL.

same for searching assume we have the element we need k1 is at slot 0

h(k,0) = 2
h(k,1) = 6
h(k,2) = 3
...
h(k,7) = 0

so I take O(m) to find it in worst case

assume the k1 is at slot 5 instead of 7 so if I reach h(k,5) and find it NULL I stop because I know that this element is not presented , because if it's not NULL the hash function will occupy it for k1.

This is the case if no elements being deleting . If it's deleted I will continue searching (probing). So deletion will cause a problem so I will assign an element that mean oh there is an element let's say D here but it is deleted , and in insertion if I find D I will treat it as NULL so I place replace it with my element.

In worst case if All elements are deleted and I need an element after them , so chaining is the best in this case.

Linear probing

h : U --> {0 ... m-1}

if I run h(k) = a so index is a , if a is not empty will I will take another hash function h primeh'(k,i)=(h(k)+i) mod m which is h'(k,1) = ( h(k)+1) mod n = (a+1) mod m = a+1 and h'(k,2) = ( h(k)+2) mod n = (a+2) mod m = a+2

it's called linear probing because if the element at a is occupied it try a+1 if it also occupied it will trya+2 if it reach m it will start again from 0 to a

so if it start at 1 it will start from 1 and end at 0 {1,2,3 ... m-1 , 0} if it start at k it will end at k-1

the number of prob sequences is m . if 2 elements have the initial prob is the same it's called secondary clustering. Primary clustering is if a continuous block of memory is sequentially occupied it mean from a to a+k is filled , so the probability of inserting an element will be k+1/m

the worst search is O(m) but the average is constant O(2.5) their is a lot of proofs but they are hard and contain a lot of advanced probability theorems.

Quadratic probing

h'(k,i) = ( h(k) + c1*i + c2 i*i ) mod m

the problem with quadratic probing is that we need to choose c1 , c2 and m in such a way that h'(k,i) will examine entire table.

Double hashing

h'(k) = ( h1(k) + i * h2(k) ) mod m

if 2 elements have the same h1 , h2 probably will not be the same

selection of h2(k)

The secondary hash function h2(k) it should never yield an index of zero

it should cycle through the whole table
it should be very fast to compute
it should be pair-wise independent of h1(k)
The distribution characteristics of h2(k)are irrelevant. It is analogous to a random-number generator - it is only necessary that h2(k) be ’’relatively prime’’ to m.

In practice, if division hashing is used for both functions, the divisors are chosen as primes.

#008 DS&A - Graphs

Omar — Tue, 08 Sep 2020 08:24:50 +0000

Graphs

graph theory is in general an algebra class to study relationships between things , in computer science the most common use is the networking.

Representation of Graphs

first representation is adjacency matrix ever case represent the link between point and another as example a doesn't have a relation with it self , while a have relation with b and a doesn't have direct relation with c

	a	b	c	d
a	0	1	0	1
b	1	0	1	0
c	0	1	0	1
d	1	0	1	0

another popular representation is linked list

every node have pointer to nodes that connects to.

a dense graph it's a graph that have lot of connections between it nodes.

if the dense isE=O(v^2) where E is the number of edges and v is the number of vertexes , and it mean that graph had lot of connection between them self , in other words matrix is almost all 1 .

let's say we need a similar network for any social platform , the linked list make more sense because we are not going to connect with all in the network just with few friends.

and the order of linked list is O(V+2E) which is <O(v^2)

BFS and DFS

Visited mean that I visit or print it.

Explored mean that I explore all the connections that she made (Neighbors).

visited	explored	meaning
0	0	not visited and not explored
1	0	visited but not explored
1	1	visited and explored

you can use array for check visited nodes , for explorer there algorithms that use Queue or Stack, the one that use Queue is called BFS (Breadth First Search) and the one that use the stack called DFS (Depth First Search)

BFS will traverse the tree like this

DFS will traverse the tree like this

BFS algorithm

// the graph G and array visited[] are global
// visited[] is initialized to 0
BFS(v)
{
    u = v;
    visited[u] = 1;
    repeat
    {
        for all vertices w adj to u do
        {
            if(visited == 0)
            {
                add w to q;
                visited[w] = 1;
            }
        }

        if q is empty then return;
        delete the next element u from q;
    }
}

graph G

visited array is initialized to 0

1	2	3	4	5	6	7	8
0	0	0	0	0	0	0	0

queue q

first iteration u=1 and vertices w adj to u are w={2,3} , so visited and queue will be

1	2	3	4	5	6	7	8
1	0	0	0	0	0	0	0


2

after adding it to the queue 2 will be marked as visited

visited array is initialized to 0

1	2	3	4	5	6	7	8
1	1	0	0	0	0	0	0

now we finish from 2 we need to go to 3 because we have a for loop here to go to all adjacent of 1 which they are {2,3}

1	2	3	4	5	6	7	8
1	1	1	0	0	0	0	0


2	3

now we finish the for loop q is not empty so we are going to delete the next element from q which is 2 , now our u become 2 and neighbors of 2 are w={1,4,5} since 1 is visited we are not going to visit it again and we do same logic as before until we reach an empty q which mean all are visited and explored.

BFS analysis on linkedlist

the queue implementation will take space complexity of O(v)

the linkedlist will take O(v+E)

BFS analysis on adjacency matrix implementation

if we have 8 vertexes it mean we need a matrix of 8x8 size , the array and Queue implementation of it each will have space complexity of O(v) where v is number of vertexes , and the time complexity is T(v^2)

Breadth First Traversal using BFS

in order to know if the graph is connected , it mean all the nodes are in same graph

those can be separated into 2 graphs U and G there at least one node that doesn't have intersection from U with V

to traverse those two sub graphs

BFT(G,n)
{
    // this loop to fill the array with not visited yet
    for i=1 to n do
        visited[i] = 0
    // this will visit every node that is not visited yet
    for i=1 to n do
        if(visited[i]==0) then BFS(i) //BFS not BFT !!!!!
}

let each case represent a Node

the first 4 boxes are the U graph with 4 nodes , he will start from 1 and mark from 1->4 as visited , then he will break.

after this it will start with V and do same thing.

time complexity is O(E+V) and space complexity O(V)

DFS Algorithm

DFS(v)
{
    visited[v] = 1;
    for each vertex w adj to v do
    {
        if(visited[w] == 0) then
            DFS(w);
    }
}

in DFS we start with a point and explore it , if the next node in it not explored we leave the previous node and explore the new node.

initializing the visited array is done in the program that called the function , and we take it in count when we calculate the time complexity.

V=1	V=2	V=4	V=8	V=5	V=6	V=3	V=7
w={2,3}	w={1,4,5}	w={2,8}	w={4,5,6,7}	w={2,8}	w={3,8}	w={1,7}	w={3,8}
2 not visited	4 not visited	8 not visited	5 not visisted	all w visited we go back to v=8 , 6 not visited	8 not visisted	all w visited we go back to v=8 , 7 not visited	all w visited , and all V are visited

as we see every time we have an unvisited node we fully explore it neighbors. if all the neighbors are visited we go back into old neighbors.

Analysis of DFS and DFT

space complexity of DFS is O(V) , the worst case if the graph is chain , because all the nodes will be on the stack in same time. So space complexity for DFS and BFS is O(v) , time complexity is O(E)+O(V) for the linked list representation where O(V) is time to initialize the visited array and O(V^2) for matrix representation , same as BFS .

DFT will be the same as BFT instead of calling BFS we call DFS .

#007 DS&A - Trees

Omar — Fri, 04 Sep 2020 16:15:56 +0000

Binary trees are those who have max 2 childs , there are 3 types of binary tree traversal

INORDER - L ROOT R - B A C

PREORDER - ROOT L R - A B C

POSTORDER - L R ROOT - B C A

to write each order , we apply this method . First add dummy edges , start from A and first time you see A write it down , same for B and C. And then for inorder if you see A for second time write it and ....

A B C - first time - PRE

B A C - second time - IN

B C A - third time - POST

Implementation and time complexity

all the implementations are recursive manner so go back to recursive section and fully understand how to visualize it.

// INORDER
struct node
{
    int data;
    struct node *left , *right;
}

void Inorder(struct node* t)
{
    if(t != NULL)
    {
        Inorder(t->left); // 1 
        printf("%c" , t->data); // 2 
        Inorder(t->right); // 3
    }
}

to better understand it go back to recursion visualization and try to trace it

time and space complexity are O(n)

to get the other traversal just change the printf location

Double order traversal

this is nothing but print every node twice (not necessarily successive)

example : abbcac

// INORDER
struct node
{
    int data;
    struct node *left , *right;
}

void DO(struct node* t)
{
    if(t != NULL)
    {
        printf("%c" , t->data); // 1
        DO(t->left); // 2
        printf("%c" , t->data); // 3
        DO(t->right); // 4
    }
}

Triple order

void TO(struct node *t)
{
    if(t)
    {
        printf("%c" , t->data); // 1
        TO(t->left); // 2 
        printf("%c" , t->data); // 3
        TO(t->right); // 4
        printf("%c" , t->data); // 5
    }
}

Indirect recursion on tress

void A(struct node *t)
{
    if(t)
    {
        printf("%c" , t->data); // 1
        B(t->left); // 2
        B(t->right); // 3
    }
}

void B(struct node *t)
{
    if(t)
    {
        A(t->left); //1
        printf("%c" , t->data); // 2
        A(t->right); // 3
    }
}

Number of binary trees possible

if we have 1 node , number of binary tress are 1

if we have 2 node , number of binary tress are 2

if we have 3 node , number of binary tress are 5

the pattern here is(2*n)C(n)/(n+1) c is combinator . so we have here (2*3)C3 / 4 = 6C3 / 4 = 20/4 = 5

but if we need to label nodes (put value for every node) is (2*n)C(n) * n! /(n+1)

construct unique Binary tree

We can construct a unique binary tree using combination between 2 of preorder , inorder and postorder

drawing all the combinations of A,B,C,D,E,F..... is time consuming so we are going to prove it with logic.

let's take IN : 1,2,3,4,5,6,7,8 , PRE: 5,3,1,2,4,6,8,7 , POST = ?

to get POST we need to get a unique Binary search tree.

let's take all the cases of IN - L ROOT R andPRE - ROOT L R where L and R are the subtree respectively to left and right.

this is our INORDER

let's say 5 is the ROOT and in the PRE 5 is also the ROOTand all the elements in the right of it will be the L and R

in the left sub tree1 2 3 4 we look at the PRE we have 3 is the next ROOT

in the right sub tree 6 7 8the PRE it is 6 8 7 so the ROOT is 6 and 8 7 to the right of it

so we have 1 2 in PRE the 2 is to the right of 1 so 2 will fall to the right

for 7 8 in PRE we have 8 is the ROOT and 7 to the left of it

so we form a unique POST binary tree from IN and PRE

if we get the POST of it it's mean print it if it's seen the 3 time.

POST = 2 1 4 3 7 8 6 5

an exercise take POST and IN and form the PRE

Recursive program to count the number of nodes

NN(T) = 1+NN(LST)+NN(RST)and if T is NULL then NN(T)=0

struct node
{
    int i;
    struct node *left , *right;
}

int NN(struct node *t)
{
    if(t)
    {
        int l,r;
        l = NN(t->left); // 1
        r = NN(t->right); // 2
        return (1+l+r); // 3
    }
    else return 0;
}

counting number of leaf

a leaf is a Node with left and right sub trees are NULL

int NL(struct node *t)
{
    if (t == NULL) return 0;
    if(t->left == NULL && t-> right == NULL)
        return 1;
    else
        return (NL(t->left) + NL(t->right));
}

time complexity : O(n)

find the full nodes

full node is the tree who have left and right child

FN(t)   = 0 ; T = NULL
        = 0 ; T is a leaf
        = FN(T->LST) + FN(T->RST); if T has on one child
        = FN(T->LST) + FN(T->RST)+1; if T is full node

int FN(struct node *t)
{
    if(!t) return 0;
    if(!t->left && !t->right) return 0;
    return ( FN(t->left) + FN(t->right)+(t->left && t->right) ) ? 1 : 0;
}

time complexity : O(n)

Recursive program to find the height of a tree

the height is the length of the path to the last leaf you can access

H(t) = {0 ; T is empty
       {0 ; T is a leaf
       {Hmax(H(LST) , H(RST)); otherwise

int H(struct node *t)
{
    if(!t) return 0;
    if( !(t->left) && (!(t->right)) ) return 0;
    int l,r;
    l = H(t->left);
    r = H(t->right);
    return (1+((l>r) ? l : r));
}

Binary search tree

50,15,62,5,20,58,91,3,8,37,60,24

every sub tree in the left is smaller than the root of it and in the right is the higher

INORDER: 3,5,8,15,20,24,37,50,58,60,62,91

so INORDER is nothing but the binary search tree sorted

Binary search tree - POST to IN to PRE

POST ORDER : 10,9,23,22,27,25,15,50,95,60,40,29

we can get directly the INORDER hence is nothing more than the BST sorted

INORDER : 9,10,15,22,23,25,27,29,40,50,60,95

to get that PREORDER we need to draw the tree

the root is 29 since it's the last in the POST , so the root construction is going to be like this , then we go backward 40>29 so it is going to fall to the right and so on..

after we trace it we get PREODER : 29,15,9,10,25,22,23,27,40,60,50,95

Number of BST with 3 Distinct keys

1 2 3

2nCn / n+1 = 6C3 / 4 = 20 / 4 = 5

Identify IN-ORDER , PRE-ORDER and POST-ORDER

1 : M B C A F H P Y K

2: K A M C B Y P F H

3:M B A C K Y F P H

we have those three trees we don't know what is the type of traversal of each one.

K appear first in 2 and last in 1 so it's the ROOT

after drawing the tree we get 1 is POST ,2 is PRE and 3 is IN

Delete a node from BST

if node is a leaf we can delete it , if node is a Non Leaf and one child the child point to the parent of deleted node. If the node have a subtree we replace the greatest element of it.

Examples:

We can delete node 2 without making any changes.
We can delete node 25 and point 27 to 30 instead
If we need to delete node 15 we replace it with 12

Finding minimum and maximum

find_min(struct node *t)
{
    while(t -> left)    t = t -> left;
}

find_max(struct node *t)
{
    while(t -> right)   t = t -> right;
}

Recursive program on testing type of tree

there is arguing on type of trees those are one of their definition , other reference may differ

complete binary is a tree which have 2 or 0 childrens.
full binary tree mean every layer should be node and last row should be leafs

int iscomplete(struct node *t)
{
    if(t == NULL) return 1;
    if(!t->right && !t->left) return 1;
    else if(t->left && t->right) return (iscomplete(t->left) && iscomplete(t->right));
    else return 0;
}

AVL Trees and balancing

AVL tree (named after inventors Adelson-Velsky and Landis) it's the most popular one there is others like (R-B) and (2-3) the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, re-balancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where is the number of nodes in the tree prior to the operation. Insertions and deletions may require the tree to be rebalanced by one or more tree balancing.

BF = height(LST)-height(RST) the root should be either {-1,0,1} else we rotated . If it is left-unbalance we rotate it clock wise else opposite clock wise.

the root is 2 != {-1,0,1} so it's not balanced , and it's left unbalanced so we need to rotate CW

now the root is 0 so now it's balanced.

constructing AVL trees and time complexity

50 , 20 , 60 ,10 , 8 , 15 , 32 ,46 , 11 , 48

go clock wise

now rotate Anti Clock wise

now it's Left-Left so we rotate CW and so on we continue and in the end we get this tree

	BST	Balanced BST
search	O(n)	O( log n )
height	O(n)	O( log n )
Insertion	O(n)	O(log n)

it's O(log n) because the height is smaller

Minimum and Maximum nodes in AVL tree

S(h) = S(h-1) + S(h-2) + 1

S(1) = 0
S(2) = 1

So let's say h = 6, then S(h = 6) will be (just replacing):

S(6) = S(6-1) + S(6-2) + 1
S(6) = S(5) + S(4) + 1 
S(6) = 2*S(4) + S(3) + 1 + 1
S(6) = 2*(S(3) + S(2) + 1) + S(3) + 2
S(6) = 3*S(3) + 2*S(2) + 4
S(6) = 3*(S(2) + S(1) + 1) + 2*S(2) + 4
S(6) = 5*S(2) + 3*S(1) + 7
S(6) = 5*1 + 3*0 + 7
S(6) = 12

Expression trees

a+b take this and let's draw the tree

PRE : +ab
IN  : a+b
POST: ab+

a+b*c

PRE : +a*bc
IN  : a+b*c
POST: abc*+

Various tree representations

The method we see is a pointer to the left and right child , what if we have like 10 childs?

There is a representation called LCRS (Left Child Right Sibling)

LC = 2*i
RC = 2*i+1
Parent = x/2

because it's binary tree multiplying by 2 is nothing but shifting by 1 bit.

if we have i = 2 (base 10) = 10 (base 2) , 2*i = 100 and 2*i+1 = 101 , same for divining by 2 in binary 100/2 = 10

another representation is like this

(Root (a b c) (d e f) ) where (a b c) is LSB of Root and (d e f) is RSB of Root and a is root of LSB and b is left leaf and c is right leaf , same for d e f

Get Waifu on terminal

Omar — Mon, 31 Aug 2020 13:35:25 +0000

Introduction

I see a lot of programmers interested in having a waifu in terminal.
So here how I do it.

first

go to any search engine and search for Anime black and white png

then open any photo editor , I use photopea online create a new transparent image with same dimension of your screen . In my case it's 1920x1080 . Drag and drop your waifu into the corner and save it as png.

final result should look like this

second

move your image to any location you like mine is $HOME/.config/kitty/ in same folder with kitty configuration.
first I am using the kitty terminal.after install it go to the config files

vim ~/.config/kitty/kitty.conf

then add those lines to the end of the files , also you can delete the config file and make new one with those lines only because all the file is just comments.

foreground white                                                                                                                     
background black                                                                                                                     
background_opacity 0.989
background_image $HOME/.config/kitty/waifu.png                                                                                                                                                                                                                     
background_image_layout scaled

#002 - Clean Code - Names

Omar — Sat, 29 Aug 2020 17:53:06 +0000

Names

Reveal your Intent

Intent : Nawaya in Arabic

Variables are all around the programm having good names will help read code.

int d; // elapsed time in days

in past documentations were good back in old days , but now it's better to have the variable name is his own comment

int elapsedTimeInDays;

if your code is something like this

int mpd = (n/2)+3

it is better to write it like this

int middle = n/2;
int days = 3;
int middlePlusDays = middle + days;

There is an old mindset that this will cost us more cpu cycles. But we live in a new world where we know now that what matter is code maintainability.

const int ID_NONE = 0; // constant ID for NONE
const int ID_FIRST = 0;// constant ID for FIRST
const int ID_SECOND = 0;// constant ID for SECOND
const int ID_BOTH = 0;// constant ID for BOTH

look at those variable names and comments , what did you understand from this code?

actually name nor comments mean nothing for me as reader.

you will tell me read code this is a shame , I am busy/lazy I don't have time for your bad code.

Avoid Disinformation

int tuesday = 1;

look at this expression What you think it mean? Well what I need is to make sure that if today is tuesday

isn't better if we write it like this?

int isTuesday = 1;

this is disinformation i give you an variable that you may miss understand that this is a boolean.

Pronounceable Names

string BMW;

how I need to pronounce this?

How I should understand this? does it mean the bmw car? should I read it like boomwww?

isn't this better?

string BestMatchingWord;

names are the tools to communicate with others , so make sure to express what you are saying well.

Avoid Encodings

those are the hungarian Notations , those was usefull back in old days to know what is the type of your variables. But now our IDE is better he can know what is the type of a variable by hovering over it , And our compiler , unit tests will protect us from any type error.

Parts of Speech

your functions should be methods like getTotal() , divide()

structs should be Adjectives like struct COLORS = {...}

your booleans should be descreptive like isUpper() , isLower()

your calsses should be like this class Account not class DATA , class INFO , class MANAGER

The Scope Length Rule

for (TestResult tr : configIssues) {
    Element element = createElement(d , tr);
    rootElement.appendChild(element);
}

tr is a fine name because the scoop where it is declared is small , and had been used directly after his declaration.

but what is not fine is d it is not declared in same scope of it's defenation

d is an instance of a class Document , it is better to call it doc or document.

so in small scope the shorter names are better , but in large scopes bigger are better , so yes size matter :)

While for functions , public functions that are going to be called in many other places outside the class should have small names. Why? the Class have a name example File.Open() Imagine calline File.openFileAndThrowIfNotFound()

and private functions should be long because they are called locally.

#006 DS&A - Stacks and queues

Omar — Sat, 29 Aug 2020 16:09:24 +0000

Introduction

Stacks and queues

Implementation of Stack using arrays

the problem of arrays that we should know the max number of elements we need to use, If you can't predict the size go with linkedlist.

A stack mean that we can only get last element and first input is last output.

int stack[max];
int top = -1; // mean stack is empty
void push(int item) 
{
    if (top == max-1) printf("overflow");
    else stack[++top] = item; // ++top will increment top first
    return;
}

int pop()
{
    int temp
    if(top == -1) 
    {
        printf("underflow");
        return -1;
    }
    else temp = stack[top--];
    return temp;
}

Linked List implementation of stack

he head will link to the new node.

struct node
{
    int i;
    struct node *link;
};

void push(int item)
{
    struct node *p = (struct node*)malloc(sizeof(struct node));
    if(p == NULL)
    {
        printf("error of malloc");
        return;
    }
    p->data = item;
    p->link = head;
    head = p;
}

pushing time is O(1)

int pop()
{
    int item;
    struct node *p;
    if(head == NULL)
    {
        printf("underflow");
        return -1;
    }
    item = head->i;
    p = head;
    head = head->next;
    free(p);
    return item;
}

pop is O(1)

Queue using circular array

even if a circular array we visualize it as an circular array.

front and rear will both be pointing to the 0 element. let's say we have an array of 4 integers

first type I need to put an element the rear will move +1 when the rear is already reach n-1 again I need to put it at n-1 so I will use (rear+1) mod n , dashed rear it mean it pass from here it start from 0 to n-1

// delete element
int dequeue()
{
    if(front==rear)
    {
        printf("Q is empty");
        return -1;
    }
    else
    {
        front = (front+1) mod n;
        item = q[front];
        return item;
    }
}

// insert element
void enqueue(item)
{
    rear = (rear+1) mod n;
    if(front == rear)
    {
        printf("Q is full");
        if(rear == 0 ) rear = n-1;
        else rear = rear-1;
        return;
    }
    else
    {
        q[rear] = item;
        return;
    }
}

Queue will be full if

(rear+1) mod n == front

Queue will be empty if

rear == front

#005 DS&A - Linked List

Omar — Fri, 28 Aug 2020 19:37:44 +0000

Introduction

Linked List

Single Linked List

struct node
{
    char data;
    struct node *next;
}

self reference structures we talk about them before.

first element is called head.

arrays are dynamic access , while linked lists are sequential accessible , it mean you need to visit all the previous element in order to reach the element you need , it mean O(n) while arrays are O(1)

searching in both will take O(n) .

struct node *p;
p = head->next->next; // 30
p->next->next->next=p; // 50 will link to 30 , so 60 is lost
head->next=p->next; // 10 will link to 40
printf("%c" , head->next->next->next->next->data); // d

This linked list is same for all the followings. We are assuming that our linked list have more than 1 node , if it is 1 node we should put conditions to make sure that if our linked list can perform certain things.

Traversing a single linked list

struct node *t;
t = head;
while(t != NULL) { // or while(t) have same meaning
    printf("%d\n" , t->data);
    t=t->next;
}

we are using t because if we lost the head , it's mean we lost the entire node.

Inserting an element in single linked list

struct node* new = (struct node*)malloc(sizeof(struct node))

this is will create a pointer called new

a) insert at beginning :

new->next=head;
head = new;

b) insert at the end

while(t->next != NULL) {
    t=t->next;
}
t->next = new;
new->next = NULL;

c) insert a node at specific element

struct node
{
    int i;
    struct node *next;
}
// asume we need to insert after node 2
while(t->i != 2) 
{
    t = t->next;
}
new->next = t->next;
t->next = new;

Deleting a node from single linked list

malloc will create a space for us while free will free the memory that we got it from malloc

// assume we are resetting the linked list to it's init state
// deleting a node from the head
head = head->next;
free(t);
// deleting a node from the tail
while(t->next->next != NULL) {
    t = t->next;
}
free(t->next);
t->next=NULL;
// delete a specific node
while(t->next->i != 3){
    t = t->next;
}
struct node *t1 = t->next;
t->next = t1->next; // or t->next->next
free(t1);

example 1

struct node
{
    int val;
    struct node *next;
};

void rearrange(struct node *list)
{
    struct node *p , *q;
    int temp;
    if(!list || !list->next) return; // if linkedlist have no or 1 element return
    p = list; q=list->next; // q pointing to 1st element and q to second
    while(q) // while q is not null do
    {
        temp = p->val;p->val=q->val;
        q->val=temp;p=q->next; // swap q and p
        q=p?p->next:0; // if p is pointing to something it will take it otherwise 0
    }
}
// output : 2 1 4 3 6 5 7

printing the elements using recursion

// print then recursion
void f(struct node *p)
{
    if(p)//1
    {//2
        printf("%d" , p->data);//3
        f(p->link);//4
    }//5
}
// output : 1 2 3 4

It will print before start go into next stack

when it's go back it will return to line 5

// recursion then print === print in reverse order
void f(struct node *p)
{
    if(p)//1
    {//2
        f(p->link);//3
        printf("$d" , p->data);//4
    }//5
}

// output : 4 3 2 1

then when it go back it will start at line 4 which printing the value of p stored inside of each stack

Reversing an single linked list using iteration

struct node
{
    int i;
    struct node * next;
}
struct node * reverse(struct node * cur)
{
    struct node *prev = NULL,*nextNode = NULL;
    while(cur)
    {
        nextNode = cur->next;
        cur->next=prev;
        prev=cur;
        cur=nextNode;
    }
    return prev;
}

Reversing an single linked list using recursion

struct node *head;
void reverse(struct node *prev , struct node *cur)
{
    if(cur)
    {
        reverse(cur , cur->next);
        cur->next = prev;
    } else 
        head = prev;
}

void main()
{
    //...
    reverse(NULL , head);
    //..
}

circular Linked List

circular linked list have it's tail pointing to sentinel which is the head but containing the number of nodes instead with pointer to first element.

while(p->next != head){}

double linked list

// insert at start
struct node {
    int i;
    struct node *prev;
    struct node *next;
};
t->next = head;
head = t;
t->prev = NULL;
head->next->prev = head;

// insert at the end
while(p->next) p = p->next;
p->next=t;
t->prev=p;
t->next=NULL;

// insert between > 1 and < n where n is number of node
t->prev=p; // p is the pointer of the element previous to t
t->next=p->next;
p->next=t;
t->next->prev=t;