Data Structure

Data Structure main topics:
----------------------------------
Linked List
Stack
Queue
Tree
--------------------------------------------------------------------------------------------------------
Array: is the best data structure in terms of accessing time as the time complexity of it is O(1) the time required to access any element of it is constant. Problem: Memory usage!

Linked List: 
is the best data structure in terms of memory management but in terms of accessing time is O(N). Problem: Accessing time- Time complexity is O(N)!

Types:
          - Simply Linked List.
          - Doubly Linked List.

-------------------------------------------------------------------
Key Word to implement linked list is to draw it.
--------------------------------------------------------------------
Note:
Each node in the linked list should be similar to all o them. As the struct (Node) is considered as a user-defined data type so each structure is a data type defined by the number and the type of its members. So we can not change the node structure as that means change the type of the pointer used within the node to point to the next node and the previous one.



=======================================================
Stack (Last In First Out (LIFO)):
--------------------------------------------
* Push in Stack
             - Before pushing data we should make sure the stack is not full.
*Pop from Stack
             - Before popping from the stack we should make sure that the stack is not empty.

Stack use case:-
---------------------
We can mirror a string by pushing it in a stack then popping it again.

3 Elements For the Stack:
----------------------------------
- Pointer to the Top of Stack (TOS)
- Store Stack Size
- Store Data in Stack

So we need to implement Stack as :

typedef struct stack
{
       int *stkTos; /*Pointer to the top of the Stack*/
       int tos;  /**/
      int size;  /**/
}stack;

________________________________________________________________________

Read More

Sorting Algorithms

Sorting Algorithms:
---------------------------
1- Selection Sort
2- Bubble Sort
3- Merge Sort
============================================================
1- Selection Sort: 
- Time Complexity : O(N^2)
---------------------------------------
void swap(int*ele1,int*ele2)
{
int temp;
temp=*ele1;
*ele1=*ele2;
*ele2=temp;
}

/*
in this code: the use of mini variable is to determine the index of the smallest number in the array first then we swap after the inner loop finishes. Without the mini variable, we have to move the swap function into the inner loop and swap whenever the condition is true and that takes more time!
*/
void selectSortElements(int*arr,int size)
{
int i,j,mini;
for(i=0;i<size-1;i++)
{

mini=i;

/* The inner for loop is used to determine the index of the smallest element in the array */
for(j=i+1;j<size;j++)
{
if(arr[j]<arr[mini])
{
mini=j;
}
}
swap(&arr[i],&arr[mini]);
}
}

=================================================
2-Bubble Sort:-
--------------------

void bubbleSort(int*arr , int size)
{
    int i,j;

    for(i=0;i<size-1;i++)
    {
        for(j=0;j<size-i-1;j++)
        {
            if( arr[j]>arr[j+1])
            {
                 swap(&arr[j],&arr[j+1]);
             }   
         }
    }
}

The above function always runs O(n^2) time even if the array is sorted.It can be optimized by stopping the algorithm if inner loop didn’t cause any swap.

The optimized version of bubble sort:
---------------------------------------------------

void bubbleSort(int*arr, int size)
{
int i , sortFlag=0;
while(!sortFlag)
{
sortFlag=1;
for(i=size-1;i>=0;i--)
{
if(arr[i]<arr[i-1])
{
swap(&arr[i],&arr[i-1]);
sortFlag=0;
}
}
}
}

NOTES:
========

Worst and Average Case Time Complexity: O(n*n). Worst case occurs when array is reverse sorted.

Best Case Time Complexity: O(n). Best case occurs when array is already sorted.

=========================================================
Merge Sort:
------------------

Perfectly explained: https://www.geeksforgeeks.org/merge-sort/

Read More

Searching Algorithm

Searching Algorithms:
---------------------------
1-Sequential Search
2- Binary Search
----------------------------------------------------------
1- Sequential Search:
    -Searching in an array of N.
    -Time complexity: O(N)

int sequentialSearch (int * arr, int size, int data)
{
       int index= -1;
       int i;
       for(i=0;i<size;i++)
       {
          if(arr[i] == data)
          {
           return i; /* Once the data is found return the index and exit the function*/
           }
         }
       return index;
}

===================================================================
2- Binary Search: is applied on "Sorted data" 
    - Data must be sorted.
    - Time Complexity: O(log N)

int binarySearch(int*arr, int size ; int data)
{
int low=0;
int high=size-1;
while(low<=high)
{
mid=(low+high)/2;
if(data>arr[mid])
{
low=mid+1
}
else if(data<arr[mid])
{
high=mid-1;
}
else
{
return mid;
}
return -1;
}

---------------------------------------------------
The same Function using Recursion:

int recBinarySearch(int*arr,int low , int high,int data)
{
int mid=(high+low)/2;
if(low>highh)
{
return -1;
}
if(arr[mid] < data)
{
  low=mid+1;
return recBinarySearch(arr,low,high,data);
}
else if (arr[mid] > data)
{
  high=mid-1;
return recBinarySearch(arr,low,high,data);
}
else
return mid;
}
============================================================

Read More

Matrices (mathematics)

Matrices Addition and Subtraction:-
=============================
************************************************************************
Rule:
You can only Add or subtract two matrices only and only if they have the same number of rows and columns and the result will have the same number of rows and columns.

***************************************************************************
Addition or subtraction is performed between the two elements that have the same location.

Ex:

[ 5      4              [ 9      -3               [ (9+5)    (4-3)                  [14       1
   -1    6         +     8      2         =       (-1+8)   (6+2)          =        7         8
    0     7 ]               -6    1 ]                (0-6)      (7+1) ]                -6          8 ]

Read More

Pointers Questions

1- Print an array after removing duplicating numbers in it?
Solution:
https://github.com/AmrHRAbdeen/C-Programming/blob/master/RemoveDuplicatedValues.c
===================================================================
2- Find 2 Elements in the Array such that the difference between them is the Largest?
Solution:
https://github.com/AmrHRAbdeen/C-Programming/blob/master/MaxDiffInArray.c
===================================================================
3- Find the One repeated number in an Array and print number of repetition?
Solution:
https://github.com/AmrHRAbdeen/C-Programming/blob/master/findOneRepeatedValue.c
===================================================================
4- perform Cyclic Swapping on an array of 3 Elements?
Solution:
https://github.com/AmrHRAbdeen/C-Programming/blob/master/cyclicSwap.c
===================================================================
5- Adding Two Matrices
Solution:
https://github.com/AmrHRAbdeen/C-Programming/blob/master/AddingMatrices.c
===================================================================

Read More

Building Process and Critical Sections || Part(2)

Building process (Part 2):
--------------------------------
in case the variable is used repeatedly in the code and its value is not changing during the code, The compiler optimizer has the option to store it in a General purpose register (GPR) or cache it in a cache memory if exists to reduce execution time.

Ex:

var =40;
while(var==40)
{
..
..
..
}

Here, the compiler will solve this line while(var==40) to
1- Read Var from its Virtual Memory Address (or from a GPR if cached in a GPR or cache memory)
2- Compare Var to 40
3- Jump if Equal.

is caching always useful?

*No , Not really!

let's say we have that code snippet:
-------------------------------------------
var =40;
while(var==40)
{
..
..
..
}
----
ISR()
{
 var =10;
}

As we discussed earlier, the compiler will divide while condition to 3 steps. so, Let's imagine that while the CPU executes the read operation of var variable that is stored in a GPR ( as the compiler decided to cache it as it's used repeatedly in the code) , an ISR is fired modifying the value of var variable in RAM ,but CPU doesn't sense that change as var value is already cached in one of its GPRs! and that's a PROBLEM!

so we need to tell the compiler NEVER cache this variable as here we introduce volatile modifier.

Volatile Modifier: tells the compiler optimizer to NOT cache this variable. as its value may be changed in the future. 

When to use volatile Modifier?
------------------------------------------
1) Any variable is defined inside an ISR should be defined as volatile.
2) Any Variable is changed by HW.

Example:-
---------------
Registers Addresses => #define PINA *((volatile u8*)0x31) 
as PINA is an 8-bit register is modified by HardWare as PINA is updated when there's input voltage to the microcontroller.

It's a good practice to use volatile modifier whenever we define registers addresses.

3) Shared variable in multi-threading programming (OS tasks).

Read More