Tagged Questions

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

learn more… | top users | synonyms

4
votes
1answer
45 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 ...
-1
votes
1answer
70 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 ...
2
votes
2answers
64 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 ...
1
vote
5answers
190 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 ...
3
votes
2answers
120 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 ...
2
votes
3answers
720 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 ...
13
votes
6answers
3k views

What are the characteristics of an $O(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 ...
2
votes
2answers
259 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 ...
11
votes
3answers
241 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 ...
6
votes
4answers
452 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 ...
7
votes
3answers
565 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 ...
8
votes
1answer
118 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 ...
11
votes
2answers
1k 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 ...
0
votes
1answer
603 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 ...
44
votes
7answers
2k views

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 ...
15
votes
4answers
397 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 ...