Data Structure

1.1 Algorithm Running times

O(n!)   - factorial complexity
O(Cn)   - exponential complexity, C - constant
O(nk)   - polynomial , k>1
O(N*logN)   -linearithmatic complexity
O(N)    - linear time complexity
O(logN) - logarithmic complexity
O(1)    - constant time complexity

1.2 Complexity classes

# Polynomial (P)
polynomial amount of time needed to solve.
not all this problems have practical appliations , eg: bubblesort

# Non-deterministic polynomial (NP)
If we have a certain solution for the problem then we can verify the solution in polynomial Time.
P is in NP
problem P=NP ? in future it may happen
Eg : Integer factorization (verfication is simple) , knapsack problem

# NP-complete 
Hardest problem in NP
Can transform NP-C to NP in P time (use Karp-reduction)
If we manage to to find a polynomial algorithm for NP-C problem then it means P=NP
Eg : Graph coloring

# NP-hard
Problem that are atleast hard as the problem in NP class
Can transform NP-H to NP-C in P time(use Karp-reduction)
Eg : Halting problem , Travelling salesman problem

2.1 Complexity case study

    O(N)     - linear time complexity      -   First element of array - JAVA
    O(logN)  - logarithmic complexity      -   Binary Search - JAVA
    O(N)     - linear time complexity      -   Linear Search - JAVA
    O(N*N)   - linear time complexity      -   Bubble Sort - JAVA

3.1 Importance of DS

    Dijkstra's algorithm (shortest path in a G(V,E)) - O(N2)
    with priority queues(heaps) - O(NlogN)

    Kruskal's algorithm (spanning tree in a G(V,E)) - O(E logV)
    with priority queues(heaps) - O(E+logV)
    

4.1 Abstract Data types

    Define the behavior without the implementation
    Eg: STACK - push() & pop()

    STACKS - use Array / Linked List
    QUEUE  - use Array / Linked List
    PRIORITY QUEUE - Heap
    ASSOCIATIVE ARRAYS - Hash Functions
    

4.2 STACK

    Memory management - stack & heap memory

    STACK - 
    special region in RAM
    small size
    stores active functions & local variables
    no fragmentation
    fast access

    HEAP - 
    special region in RAM
    memory size largerthan stack
    stores objects
    may become fragmented
    slow access

    STACK - Linked List - JAVA
    STACK - Array - JAVA

4.2 STACK - Dijkstra's Interpreter

    Interpreters have the ability to interpret given code
    Stacks are extremely useful when parsing huge XML files either with SAX or with StAX
    The shunting yard algorithm is a method for paesing mathematical expressions with the help of stack
    It was first constructed by Edsger Dijkstra, the algo maintain multiple stacks

4.3 STACK - Applications

    Browser back button
    Undo operations
    Stack memory stores - Local variables & function calls
    

5.1 Binary Search Tree

    A tree is a G(V,E) acyclic undirected graph
    Search - Array/LL - O(N)
    if Array sorted  - O(logN)