Questions tagged [intuition]
Questions that ask for help building intuition for formal or complex concepts.
45 questions
2
votes
2
answers
350
views
Why does it make sense to minimize regret?
In fields such as game theory and reinforcement learning, it is standard to consider the regret-minimization strategy. I don't get the motivation for the definition.
Yes, doing your best under worst-...
- 171
0
votes
1
answer
94
views
Clarifying an interpretation of the definition of the subset-sum problem
I recently heard about the subset-sum problem, and its definition got me thinking.
Is it true that, to answer "yes" to a specific instance of the subset-sum problem, an explicit subset also ...
- 103
0
votes
1
answer
322
views
Intuition for Using Greedy Approach in Container with Most Water Problem
Link to leetcode problem: https://leetcode.com/problems/container-with-most-water/?envType=study-plan-v2&envId=top-interview-150
if we consider this solution:
https://leetcode.com/problems/...
1
vote
1
answer
350
views
Eulerian Path and Circuit Algorithm - How does it work?
I have found several versions of algorithms the find a Eulerian path/circuit in a graph, but I'm having trouble understanding why they work. For example http://www.graph-magics.com/articles/euler.php ...
- 275
2
votes
1
answer
201
views
Seeking an "intuitive" proof
Consider the following claim.
Let $a_i$'s and $y_i$'s be positive real numbers such that:
\begin{gather*}
y_1 \leq y_2 \leq y_3 \ldots \leq y_n \\
a_1 y_1 + a_2 y_2 + a_3 y_3 + \dots + a_n y_n = v \\
...
- 129
2
votes
2
answers
916
views
Bellman-Ford algorithm intuition
We recently learned Bellman-Ford algorithm for shortest path in class, but I didn't understand it.
Can you give me intuition for why the algorithm works? And can you please explain why it is correct? ...
- 121
2
votes
0
answers
726
views
Understanding the behaviour of different variations of Binary Search
Binary Search is a fairly simple and standard algorithm that can be used (among other things) to find a target element in a sorted array. There are subtle variations in code to do this, however all of ...
- 121
3
votes
3
answers
2k
views
Why don't integer multiplication algorithms use lookup tables?
It seems to me that we can use lookup tables for multiplication of two integers of size $\log(n)/2$, and that the number of entries for each table of these numbers should be $O(n)$.
Now, multiplying ...
- 917
1
vote
0
answers
102
views
Intuition behind balancing of link/cut data structure
My question concerns link/cut tree structure after an access operation. I am assuming an implementation with splay trees. As far as I can tell, once you access a node v and splay it to the root, it no ...
- 13
1
vote
1
answer
571
views
What is the simplest/smallest subset an OOP language like C#/JavaScript that is Turing-complete?
This question is not meant to be too theoretical or nitpicky. I have experience programming, so I'm trying to get a better understanding of what it takes to get Turing-completeness by using my ...
- 277
2
votes
0
answers
284
views
Edmond's Blossom algorithm (Maximum Matching) explanation
I asked this question on Math Stackexchange but it didn't get much attention, so I am asking it here.
Edmond's Blossom algorithm (Wikipedia), or simply the blossom algorithm, is a popular graph ...
- 197
2
votes
1
answer
2k
views
Intuition behind straight-line programs
Wikipedia defines straight-line programs in the following manner:
In mathematics, more specifically in computational algebra[disambiguation needed], a straight-line program (SLP) for a finite group ...
- 1,081
4
votes
3
answers
770
views
To what extent is my interpretation of computable numbers correct?
Interpretation: Consider the comic strip below, where a person tries to prevent a robot from dismembering them by asking the robot to compute $\pi$ - the robot quickly produces an algorithm to ...
- 281
2
votes
1
answer
105
views
Of monotone formulas and same ones satisfying certain properties
There is the following theoretical computer science, namely:
For a particular monotone formula $M$ of size $n$, there's an equivalent formula of depth $\text{O}(\text{ln}\,n)$.
(I am reading the ...
3
votes
0
answers
538
views
What is the intuition behind balancing in AVL trees?
I am not sure that my question is clear from the first sight. But I will try to explain what I mean. For now, I am learning balancing the trees on the example of AVL trees. We know that to balance ...
- 131