All Questions

31,062 questions
106 views

Why isn't there a big HTM machine already?

I've been reading a bit about Hierarchical Temporal Memory and Memory Prediction. I found a great paper: How the brain might work: A hierarchical and temporal model for learning and recognition, ...
930 views

Find node that splits tree in half

Given a tree $T = (V , F)$, find an algorithm which finds $u \in V$, so in the graph $T = (V \setminus \{u\} , F)$ the size of each connected component is $\lceil |V| / 2 \rceil$ at most. What is the ...
628 views

Minimizing Turing machine-like automaton with no final states

I have a deterministic finite automaton which behaves mostly like a Turing machine, with following difference (relevant to this question): The tape is initially finite. The automaton can insert and ...
4k views

How do we find the optimal modulus q in Rabin-Karp algorithm?

I asked a similar question here on Rabin Karp algorithm. My present question is, how do we find the best $q$ (i.e modulus)? What is the criterion? We need to choose a $q$ which will be quick to ...
984 views

Problem with Cormen's treatment of the Rabin-Karp algorithm

I am reading chapter 32 - String Matching from the book "Introduction to Algorithms" 3rd edition Cormen et al. The Rabin-Karp Algorithm is not clear to me despite heaving read it several times. ...
207 views

780 views

Why can the state space of the 15 puzzle be divided into two separate parts?

I am trying to understand the proof here of why the state space in 15 puzzle is divided into two separate parts, but the explanation is complicated for me. Could someone please explain it in simpler ...
1k views

How does 'deforestation' remove 'trees' from a program?

I think understand how deforestation consumes and produces a list at the same time (from a fold and an unfold function -- see this good answer on CodeReview here), but when I compared that with the ...
56 views

Approximate target subset by intersecting other subsets

Let $S$ be a finite set of integers (this set contains about 200000 elements). Let $T \subset S$ be a particular subset of $S$ called target. $S$ keeps growing. So does $T$. Each new element of $S$ ...
830 views

Decidable languages and unrestricted grammars?

Turing machines and unrestricted grammars are two different formalisms that define the RE languages. Some RE languages are decidable, but not all are. We can define the decidable languages with ...
291 views

Shift-resolve parsing - questions

I've recently came across a paper describing the parsing technique mentioned in the title. Unfortunately, the terminology used in said paper is somewhat beyond my comprehension, so I've been ...
393 views

What is Harrison hashing, its applications in web search engines?

What is Harrison hashing and what are its applications in web searching? Can some one give me some relevant information? Update: I found it here , and is a part of M.Tech syllabus of a friend ...
337 views

Closure of regular Language - Transition Function : Sipser Proof

I was going through construction proofs for closure of regular languages under union, star and concatenation operation in the book: "Introduction to Theory of Computation" by Michael Sipser. I have ...
78 views

Statistical anomaly detection in time series

I'm looking for some algorithms that detect statistical anomaly in time series. For example, Google Trend automatically detects peaks of a specific search query in time, and associates those peaks ...
829 views

1k views

Data structure and algorithms for a medical diagnosis software

For an academic question, I plan to design a medical diagnosis system. Given a description of symptoms, produce a list of probable diseases (with closeness matching). I'm having some trouble finding ...
594 views

first order logic resolution unification

Assuming I have shown part of the knowledge base in the clausal format:  p1(banana).  not p1(X) or p2(Y).  p1(X) or not p3(F). ... and more rules. ...
5k views

Why does bubble sort do $\Theta(n^2)$ comparisons on an $n$ element list?

I have a quick question on the bubble sort algorithm. Why does it perform $\Theta(n^2)$ comparisons on an $n$ element list? I looked at the Wikipedia page and it does not seem to tell me. I know that ...
1k views

Leftist heap - determining time complexity

The time complexity of merge (union) operation is said to be $O(\lg (n_1 + n_2))$, where $n_1$ and $n_2$ are the numbers of elements in the merged heaps, respectively. I do not understand this - the ...
1k views

Confusion related to a divide and conquer problem

I have some confusion related to a divide and conquer problem. Here is the problem You’re consulting for a small computation-intensive investment company, and they have the following type of problem ...
4k views

What graph data structure works fastest with Dijkstra's algorithm?

What data structure should I store my graph in to get the best performance from the Dijkstra algorithm? Object-pointer? Adjacency list? Something else? I want the lowest O(). Any other tips are ...
2k views

CPU Cache is managed by which software component?

CPU caches are used by exploiting temporal and spatial locality. My question is who is responsible for managing these caches? Is this Operating system that identifies a particular access pattern and ...
25k views

Is Dijkstra's algorithm just BFS with a priority queue?

According to this page, Dijkstra's algorithm is just BFS with a priority queue. Is it really that simple? I think not.
13k views

Is search a binary heap operation?

According to the Wikipedia page, search is "not an operation" on binary heaps (see complexity box at top-right). Why not? Binary heaps may not be sorted, but they are ordered, and a full graph ...