Skip to main content

Questions tagged [intuition]

Questions that ask for help building intuition for formal or complex concepts.

Filter by
Sorted by
Tagged with
0 votes
1 answer
42 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/...
penguin365's user avatar
1 vote
1 answer
169 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 ...
Robin Andrews's user avatar
2 votes
1 answer
171 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 \\ ...
Brian's user avatar
  • 129
2 votes
2 answers
607 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? ...
user14732's user avatar
2 votes
0 answers
658 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 ...
ffledgling's user avatar
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 ...
Matt Groff's user avatar
1 vote
0 answers
63 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 ...
Karl's user avatar
  • 13
1 vote
1 answer
469 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 ...
user600670's user avatar
3 votes
0 answers
240 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 ...
ab123's user avatar
  • 207
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 ...
Mike Battaglia's user avatar
4 votes
3 answers
670 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 ...
Chill2Macht's user avatar
1 vote
1 answer
74 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 ...
CS Theory Student's user avatar
3 votes
0 answers
419 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 ...
Turkhan Badalov's user avatar
2 votes
0 answers
328 views

Intuitive Explanation on Converting BNF Grammar to LR(1)

Consider the following BNF Grammar G: ...
Grant Miller's user avatar
8 votes
1 answer
876 views

Elimination rule for the equality type aka J axiom

I'm implementing a interpreter for lambda calculus, and now I want to add the equality type. The introduction rule for it is easy, but the elimination rule is rather obscure for me. I found this ...
盛安安's user avatar
  • 944
6 votes
2 answers
310 views

Is the following intuition valid for understanding $k$-wise independent hash functions?

I really enjoy reading up on algorithms and data structures and in the course of doing so often come across ones that rely on $k$-wise independent families of hash functions. I'm perfectly comfortable ...
templatetypedef's user avatar
5 votes
3 answers
8k views

What does it mean for a problem to be both NP hard and coNP hard

I have a faint notion of what NP hard is (that a problem is legit difficult 3 SAT for example). I have forgotten what coNP hard, and Wikipedia tells me that the complement of coNP hard is NP hard......
Fraïssé's user avatar
  • 821
4 votes
1 answer
264 views

An intuitive explanation for LR grammars?

With LL grammars, there seems to be a very intuitive explanation, in terms of first and follow tables.( The first letter/s encountered in a particular state, can only mean a particular rule). With LR ...
user2277550's user avatar
1 vote
5 answers
664 views

Google's Deep Dreamer

I was just wondering on a more technical side, if anyone could explain what Google does to create these amazing images from it's deep dream system. Could anyone explain to me in a step by step way, ...
George's user avatar
  • 67
33 votes
7 answers
7k views

Is there a more intuitive proof of the halting problem's undecidability than diagonalization?

I understand the proof of the undecidability of the halting problem (given for example in Papadimitriou's textbook), based on diagonalization. While the proof is convincing (I understand each step of ...
user118967's user avatar
3 votes
2 answers
1k views

Why can Multilayer neural networks solve non-linear problems

I understand what a multilayer neural network is, but what about them allows them to solve non-linear problems unlike perceptrons? Is it the fact that they can extend to any number of outputs/hidden ...
JimmyK's user avatar
  • 131
-1 votes
1 answer
634 views

Intuition behind the max-flow min-cut theorem

What is the intuition behind the max-flow min-cut theorem? I know that the min-cut is the dual of max-flow when formulated as a linear program, but the result seems artificial to me.
Paul Herman's user avatar
6 votes
2 answers
713 views

Given the "programs as proofs" isomorphism, how do we know that the program isn't lying?

I've been studying constructive type theory (CTT) and one of the things that I'm not clear on is the proof part: Proving the correctness of a program in a form of a proof that's nothing but the ...
PhD's user avatar
  • 347
0 votes
1 answer
336 views

How does selection sort sort?

I've found the following algorithm for selection sort on the internet. ...
Anon's user avatar
  • 1
12 votes
2 answers
578 views

What do we gain by having "dependent types"?

I thought I understood dependent typing (DT) properly, but the answer to this question: https://cstheory.stackexchange.com/questions/30651/why-was-there-a-need-for-martin-l%C3%B6f-to-create-...
PhD's user avatar
  • 347
42 votes
2 answers
14k views

Why do we believe that PSPACE ≠ EXPTIME?

I'm having trouble intuitively understanding why PSPACE is generally believed to be different from EXPTIME. If PSPACE is the set of problems solvable in space polynomial in the input size $f(n)$, ...
user25876's user avatar
  • 423
1 vote
2 answers
4k views

How can I use the NP complexity Venn diagram to quickly see which class of NP problem can be poly reducible to another class?

I'm so bad at solving the problem of the type: "If $A$ is an NP-complete problem, $B$ is reducible to $A$, then $B$ is..." That I have to come here and ask these silly questions each and every ...
Olórin's user avatar
  • 859
7 votes
1 answer
859 views

Visualization of Lamport's three-dimensional "space-time diagram" with introduced "tick lines"

In the third page (the third paragraph in the right column) of the paper "Time, Clocks, and the Ordering of Events in a Distributed System" by Leslie Lamport, it says that The reader may find it ...
hengxin's user avatar
  • 9,561
-1 votes
1 answer
238 views

Learning, understanding and using algorithms [closed]

I am a 2nd year computer science student. We all have subjects about Data Structures, Theories, more more theories we all know that i have a subject this semester Design Analysis of Algorithms. So ...
Christian.'s user avatar
2 votes
2 answers
1k views

Why is automatically labeling data in unsupervised learning hard?

I currently studying machine learning and pattern recognition area. Today, my professor said implementing an unsupervised system that automatically labels data is difficult. Why is that? I think if I ...
eChung00's user avatar
  • 121
1 vote
5 answers
249 views

Real life description for (~A->A)->A

It can be shown that the logical preposition [ :- (~A->A)->A ] is a theorem (always true). I want to know if anybody knows a real life description for the preposition above? I mean an expression in ...
n.Perception's user avatar
3 votes
2 answers
194 views

What does it mean to multiply or divide polynomials?

What does it mean to multiply or divide polynomials? I have used them so many times, in error correcting codes, cryptography, etc. but it was never clear to me what would be a graphical ...
Subhayan's user avatar
  • 1,696
9 votes
5 answers
32k views

How to tell if a language is recognizable, co-recognizable or decidable?

If you have a language L, without doing any proofs, is there a way to tell if it's recognizable or co-recognizable or decidable? Basically any hints or tricks that can be used to tell. Or maybe the ...
omega's user avatar
  • 553
20 votes
7 answers
19k views

What are the characteristics of a $\Theta(n \log n)$ time complexity algorithm?

Sometimes it's easy to identify the time complexity of an algorithm my examining it carefully. Algorithms with two nested loops of $N$ are obviously $N^2$. Algorithms that explore all the possible ...
Barry Fruitman's user avatar
10 votes
3 answers
2k views

Intuition for convolution in image processing

I have read many documents about convolution in image processing, and most of them say about its formula, some additional parameters. No one explains the intuition and real meaning behind doing ...
hqt's user avatar
  • 223
13 votes
3 answers
463 views

Why larger input sizes imply harder instances?

Below, assume we're working with an infinite-tape Turing machine. When explaining the notion of time complexity to someone, and why it is measured relative to the input size of an instance, I ...
user avatar
8 votes
4 answers
4k views

Is it intuitive to see that finding a Hamiltonian path is not in P while finding Euler path is?

I am not sure I see it. From what I understand, edges and vertices are complements for each other and it is quite surprising that this difference exists. Is there a good / quick / easy way to see ...
Lazer's user avatar
  • 1,087
11 votes
3 answers
2k views

How to feel intuitively that a language is regular

Given a language $ L= \{a^n b^n c^n\}$, how can I say directly, without looking at production rules, that this language is not regular? I could use pumping lemma but some guys are saying just looking ...
doniyor's user avatar
  • 243
11 votes
1 answer
974 views

Turing Recognisable => enumerable

I get the proof of going from an enumerator to a Turing Machine (keep running enumerator and see if it matches input) but I don't see how the other way works. According to my notes and the book (...
T. Kiley's user avatar
  • 248
28 votes
2 answers
11k views

Rule of thumb to know if a problem could be NP-complete

This question was inspired by a comment on StackOverflow. Apart from knowing NP-complete problems of the Garey Johnson book, and many others; is there a rule of thumb to know if a problem looks like ...
Vitaly Olegovitch's user avatar
4 votes
4 answers
17k views

Why is $L= \{ 0^n 1^n | n \geq 1 \}$ not regular language?

I'm looking for intuition about when a language is regular and when it is not. For example, consider: $$ L = \{ 0^n 1^n \mid n \geq 1 \} = \{ 01, 0011, 000111, \ldots \}$$ which is not a regular ...
Ken Li's user avatar
  • 3,088
64 votes
8 answers
5k views

Algorithmic intuition for logarithmic complexity

I believe I have a reasonable grasp of complexities like $\mathcal{O}(1)$, $\Theta(n)$ and $\Theta(n^2)$. In terms of a list, $\mathcal{O}(1)$ is a constant lookup, so it's just getting the head of ...
Khanzor's user avatar
  • 1,451
19 votes
4 answers
558 views

Strategies for becoming unstuck in understanding TCS

I am a graduate student taking a course in theory of computation and I have serious trouble producing content once I'm asked to. I'm able to follow the textbook (Introduction to the Theory of ...
trigoman's user avatar
  • 511