sanjar-notes / dsa Goto Github PK

Acknowledge this. And study more about this observation.

There are times in DnC when we use partitioning of problems just for the sake of avoiding brute force enumeration, and we may not combine solutions to subproblems at all.

Maybe this is not DnC, but it's an alternative to brute-force enumeration.

Here's a problem that I solved using this "kind of DnC" approach: https://leetcode.com/problems/count-number-of-pairs-with-absolute-difference-k/

https://youtu.be/oBt53YbR9Kk - 5hrs

Add master theorem, it's quite useful. See https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)

Copying from activity_logger

All single pass 1D array problems rely on the "knowing" what has happened in the past - i.e possibility of creating a fast lookup structure for the till-seen part of the array.

This fast lookup structure may be a number (e.g. in case of Kadane's algorithm) or a hashmap or a heap, anything.

Approximately, this should takeo(n) space and/or o(n) lookup time (small O notation).

If this is not possible - i.e. one cannot create a structure at all or it exceeds the said bound, two (or more) loops are inevitable.

*more than one loop is inevitable

This thinking could be extended to more dimensional structures like n-dimensional arrays or trees or graphs or a combination.

Why this might work - noob level information theory

Object oriented programming and design roadmap
https://youtu.be/wWejXusF9qU

This may make writing recursive functions more involved, and less obvious. Basically it'll add need for a basic test of whether the base case is valid for some cases.

This is undesirable, if true.

• More relevant
• Looks less relevant

Th Vimeagen (Prims algo) https://youtu.be/om4nY7nQyBQ?si=F70CoVp8eREBMAjx (see first 1 min)

• One reason I always feel lazy thinking/starting out with trying out DSA is the setups one needs to do. Maybe there's a lib already. Example - adjacency lists, iterators, stack funcs, fun data examples.
• Also make sure there's exactly one representation of each algo/ds/idea. Variations (including important ones are 'collapsed' by default). One source of truth for each algo/ds.
• Make a debug, animation layer (optional). May be irrelevant or even harmful for some algo/ds.

I haven't finished string algorithms properly so do it now,
https://www.coursera.org/learn/algorithms-on-strings

1. Optimal substructure, and examine problems that have/don't have it.
2. Overlapping subproblems, and examine problems that have/don't have it.
3. Relation between DP and Divide and Conquer
4. Effect of nature of the problem and these algorithm design techniques

I first encountered the problem here. Dividing into halves doesn't work here because the minimum problem size is > 2 (4 in this case).

Questions:

1. Can it be made to work by doing halfsies?
2. If not, how to divide the problem then?

https://leetcode.com/submissions/detail/740514206/

https://www.linkedin.com/feed/update/urn:li:activity:6964319815750586368?utm_source=share&utm_medium=member_android

https://stackoverflow.com/questions/6184869/what-is-the-difference-between-memoization-and-dynamic-programming

The terminology is the confusing part. Goal: understand it.

https://youtu.be/B31LgI4Y4DQ
Very good course, original channel embedded in video description

https://towardsdatascience.com/graph-visualisation-basics-with-python-part-iii-directed-graphs-with-graphviz-50116fb0d670

https://youtube.com/playlist?list=PLauivoElc3gh3RCiQA82MDI-gJfXQQVnn&si=DLh0VaV9Egls5w-J

Consider this problem to understand Trapping Water - LeetCode

Understanding the problem

Suppose we start from the left and continue, we would stop at a height >= where we started, 
and then calculate the water = left * (k - j - 1) - sum(blocks in the way).

Now, apply the same logic to the largest and 2nd largest heights. Basically, we cut the maximum height to be 
the 2nd maximum height for each case (of selection of region). 
We will basically after finding water between them, 
the part on the left and right are completely independent. 
So we do have optimal substructure. 
But we don't have overlapping subproblems. So this can be done by divide and conquer.

trap(i, j) = trap(i, a) + water(a...b) + trap(b, j) where a, b are first and second maximas (in any order). 
Trap will return a number.

Also, we can reuse the walls of a region for outer regions.
*/

/*
Approach 1 - simple recursion is optimal? because we have no overlapping subproblems, so nothing to store. 
And recursion is a must because input selection is variable for each case.

As we are doing everything optimally, this is optimal? Is it?

By the way, this gave TLE error on LeetCode.

Use CodingNinjas syllabus (in and as repo contents) and study in depth from these.

• Mr Kulikov - many courses have CP like content
  • Algorithms in General ["Algorithmic Toolbox"]
  • Data structures - See this Specialization also for a hint of what he's taught.
  • CP mentality
  • Geometric algorithms
  • String algorithms
  • Graph algorithms and problems
• Mr Rukhovich, for full on CP - 2 courses