Algorithms And Data-Structures in C Langugae

:::::::::::::::::::::INTRO:::::::::::::::::::::::::::::::::

 Algorithm: are well-defined procedures for solving a problem.

Data-structures : are conceptual organization of information.

DATA - Structure ::

way to organize data :

1. Lists 

2. Linked Lists

3. Stacks

4. Hash Tables

5. Trees

6. Sets

7. Queues 

8. Heaps

9. Priority Queues 

10. Graphs 

 

Reasons to use DATA-Structure : 

    Efficiency

    Abstraction

    Reusability

 

ALGORITHMS ::

 An algorithm is like using right tool in workshop: 

General Approach in Algorithm Design: 

   1. Randomize algorithms : ex quicksort

   2. Divide-and-conqure : envolve three step Divide > Conquer > Combine

   3. Dynamic-programming : Breaking larger problems into  subproblems : but subproblems may share here subproblems

   4. Greedy algorithms: Make Decision that look best at that Moment : ex .Huffman coding > Algo of data-compresion

   5. Approximation Algorithims : Not tend to compute optimial solution > compute the soultion that are good enough Ex : The teaveling-salesman-algorithm . 

 

Software Engineering : : : 

tends toward 1. Modularity : data-binding , encaptulation .

                    2. Readability :

                    3. Simplicity :

                    4. Consistency : 

 

 

:::::::::::::::::::::::::::::::POINTERS:::::::::::::::::::::::::::::::::

Storage Allocation : Their size can vary 

        Note : when we declare a pointer , space is allocated only for the pointer itself no, space is allocated for the data the pointer reference .

        > Storage for the data is allocated in two ways 

            -> by declaring a variable for it (as usual)

            -> by creating storage dynamically at the runtime (by using the malloc, realloc, for example ) 

        Note : When we declare a variable , its type determines the storage  

Dynamic Storage allocation : In c when we dynamically allocate storage . we get pointer to some storage on heap , then it is better to manage the storage by using free, 

Aggregate And Pointer Arithmetics::

C supports two type of aggregrated data : structures and arrays . (Union, enums)

Pointers are used in Array manipulation , Struct handling , and Call-by-reference ,

:::::::::::::::::::::::::::RECURSION::::::::::::::::::::::::::::::::

Recursion : A powerful principal that allows a problem to be defined in terms of smaller and smaller instance of itself . In Computing , we solve problems defined recursively by using recursion function.

There is type of recursion : The famous one and most usable is Tail recursion :

Tail Recursion : A recursive function is said to be tail recursive if all recursive calls within it are tail recursive . 

    I. E. When a recursive call 's last statement that will be executed within the body of a function and its return value is not a part of an expression . 

    Are characterized by having nothing to do during unwinding phase 

:::::::::::::::::::::::::ALGO-ANALYSIS::::::::::::::::::::::::::::

For Checking Algorithim's performance , : 

we use three case meathod :

1. Worst-Case analysis.

    The metric by which most algorithms are compared . 

2. O-notation .: 

    formally express an algorithim's performance

3. Computational complexity: 

    The growth rate of resources (usually time) an algorithm requires which respect to the size of the data it processes . O-notation is a formal expression of an algorithm's complexity.

Wrost-Case-Analysis::::

we prefer worst case because it gives an upper bound on performance .

 

O-Notation ::::

if g(n) is  an upper bound of f(n) , then for some constant c it is possible to find a value of n, call it n0, for which any value n>n0 will result in f(n)<=cg(n) 

thus O-notation reflects an algorithm's order of growth.

 

like T(n) = 5n^2           ==> O(T)= n^2

like T(n) = n^3 + n^2 ===> O(T(n)) = n^3

some basic rules 

O(c)   = O(1)

O(cT) = O(T)

O(T1) + O(T2) = O(T1 + T2) = max( O(T1) , O(T2) )

O(T1)*O(T2) = O(T1*T2) = O(T1) + O(T2)

::::::::::::::::::::::::::::::::::LINKED-LISTS:::::::::::::::::::::::::::::::::

Linked-Lists : consists of a number of elements grouped together in a specific order 

Linked-lists are considered more efficient in performing insertions and deletions . 

Linked-lists also make use of dynamically allocated storage

TYPES:::

1. Singly-linked-lists:Elments are linked by single pointers 

2. Doubly-linked-lists:Elements are linked to two pointers instead of one 

3. Circular lists : Last Element is linked to the first element 

 

Singly-linked lists : usually called linked-lists ,

Each element of Linked-list consist of two part : 

    >Data member

    >Next pointer

Using two member structure , a linked list is formed by setting the next pointer of each element to point to the element that follows it. 

The next pointer of last element to zero;

 The element at the start of the list is head 

The element at the end of the list is tail

Note That : in linked list we start with head and go along it but we cannot go back for going back we have to start over .