02. Algorithms

DataStructures-And-Algorithms

Data Structures :-

Data Structures is a way of storing/organising data in the memory, in such a way that access, management and modification become efficient.

Algorithms:-

Algorithms is any approach you use to perform operations on data (like searching, sorting, traversing, ..Etc.).

---

This Folder is the continuation of 01. DataStructures to proceed with Algorithm part, so the approach will be that we will follow the DSA sheet by LoveBabbar and in the process of solving Qs we will also buid up the concept of algorithms in proper sequence and moreover our DataStructures will also get revised because algorithm is something which we apply on data structures.

TimeComplexity

• Weightage of Algos

  1 < log N < sqrt(N) < N < N log N < N² < 2^N < 3^N < N !

• 10⁸ Operation rule

  

What is O(Log N) ?

Log N in Mathematics :-

• In mathematics log has a default base as 10. e.g., log₁₀ 100
• Find value of log 1000 ?
  • log₁₀ 1000 = x
  • 10^x = 1000
  • x=2 So log 1000 = 3 because base is 10.
• Find value of log₂ 8 ?
  • log₂ 8 = x
  • 2^x = 8 OR log 8 / log 2
  • x = 3

Log N in Computer :-

• In CS log has a default base as 2. e.g., log₂ 8

O(log N) basically means times goes up linearly while N goes up exponentially.

• 1sec to compute 2elements...log₂ 2 = x ...2^x=2
• 2sec to compute 4elements...log₂ 4 = x ...2^x=4
• 3sec to compute 8elements...log₂ 8 = x ...2^x=8

Difference between (Subset/Powerset)VS (Subsequence) VS (Substring/SubArray)

• (Powerset/Subset) - Any possible set of elements from parent Set is called subset there is no restriction of same directions. So subsequence of any parentSet is also Subset/powerSet.

  • e.g. arr[]={1, 2, 3, 4, 5, 6, 7}--->
  • {1, 3, 5, 7} or {1, 5, 3, 7} or {7, 1, 3, 5} etc... any one can be opt for subset.
  • {1, 4, 6, 7} or {1, 6, 7, 4} or {7, 6, 4, 1} etc... any one can be opt for subset.
  • {1, 2, 3} or {2, 1, 3} or {3, 2, 1} etc.. any one can be opt for subset.
  • etc.......

• (Subsequence) - Elements should be in one direction. Not neccesary to include adjacent elements i.e., gaps are possible between elements.

  • e.g. arr[]={1, 2, 3, 4, 5, 6, 7}--->{1, 3, 5, 7}, {1, 4, 6, 7}...e.t.c

• (Substring/SubArray/Power Set) - No gaps are possible between elements. Continuous elements should be there.

  • e.g. arr[]={1, 2, 3, 4, 5, 6, 7}--->{1, 2}, {1, 2, 3}, {4, 5, 6}, {6, 7}...e.t.c

Cycle in Array can be achieved :-

Array is of size N

• case 1 : Your i pointer is standing on N-1 then to go to 0 we do ((i+1) % N)

• case 2 : Your i pointer is standing on 0 then to go back to N-1 we do ((i-1+N) % N)