All Questions

3
votes
0answers
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, ...
3
votes
3answers
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 ...
2
votes
1answer
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 ...
3
votes
2answers
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 ...
1
vote
0answers
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. ...
7
votes
1answer
207 views

How to relate circuit size to the running time of Turing machine

From http://rjlipton.wordpress.com/2009/05/27/arithmetic-hierarchy-and-pnp/, Define, $M_{[x,c]}$ as the deterministic Turing machine that operates as follows on an input $y$. The machine treats $...
3
votes
2answers
669 views

Definition of uniform boolean circuit

Definition A family of circuits $(C_{1}, C_{2}, \ldots)$ is uniform if some log space transducer $T$ outputs $\langle C_{n}\rangle$ where $T$'s input is $1^{n}$. (from http://en.wikipedia.org/wiki/...
2
votes
2answers
352 views

What does “number of gates” mean in circuit complexity?

By "number of gates", I am wondering whether these gates include AND/OR gates that can receive several inputs or they just include AND/OR gates that receive two inputs.
4
votes
1answer
120 views

Origin of theta-joins

I've taken an introductory database course where like many good database courses, they taught relational algebra, including $\theta$-joins. However, I've recently read E. F. Codd's 1970 paper, A ...
1
vote
3answers
840 views

A* optimality of the expanded node

Suppose I have a admissible and consistent heuristic. Is it true, that when I expand a node, I have guaranteed that the path I found to this node is optimal? Look at this pseudocode from wikipedia: ...
1
vote
1answer
61 views

Operators in descriptive complexity

When we talk about operators in descriptive complexity, are they something like this: for example, if transitive closure operator $TR$ is available, we can use variable $y$ that we define as $TR(x)$ ...
2
votes
1answer
234 views

Is The Following Language Regular? [duplicate]

Let $L_{1}$ and $L_{2}$ be 2 languages over the same alphabet $\Sigma$. $$A(L_1,L_2)=\{x\in \Sigma^*|\exists y,z\in L_2\text{ such that } yxz\in L_1\}$$ Assume that $L_{1}$ is regular and $L_{2}$ ...
1
vote
3answers
664 views

Finding the shortest path in a n-dimensional grid

I have an $n$-dimensional grid space with two points on it defined by ordered pairs. I want to find the shortest path between the two points, but I can only increase one number in the ordered pair at ...
4
votes
2answers
232 views

Priority in formal grammar

From my recitation class, I have the following exercise: $\mathrm{EXP} = 0 \mid 1 \mid b \mathrm{EXP} \mid \mathrm{EXP} a \mid \mathrm{EXP} m \mathrm{EXP}$ The above grammar is ambiguous. ...
9
votes
2answers
687 views

2-D peak finding complexity (MIT OCW 6.006)

In a recitation video for MIT OCW 6.006 at 43:30, Given an $m \times n$ matrix $A$ with $m$ columns and $n$ rows, the 2-D peak finding algorithm, where a peak is any value greater than or equal to ...
12
votes
4answers
4k views

Machine Learning vs System Identification?

Could anyone explain to me the differences & similarities between machine learning and system identifications? Are these just two names of the same thing? In this page, they say: Machine ...
3
votes
1answer
318 views

ML - Type Interface

From my recitation class - Can you please explain why does operator $"+"$ signature is $ int \rightarrow (int \rightarrow int)$ ? How does this graph is build ? And what is mean $t=u \...
5
votes
1answer
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 ...
12
votes
3answers
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 ...
2
votes
0answers
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$ ...
9
votes
3answers
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 ...
10
votes
0answers
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 ...
2
votes
2answers
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 ...
1
vote
1answer
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 ...
3
votes
0answers
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 ...
1
vote
2answers
829 views

Count unhappy numbers in a large interval

An unhappy number is a number that is not happy, i.e., a number $n$ such that iterating this sum-of-squared-digits map starting with n never reaches the number 1. For example, $23\rightarrow 2^2+3^2 ...
10
votes
0answers
218 views

Is there a data-structure which is more efficient than both arrays and linked lists? [duplicate]

Background: In this question we care only about worst-case running-time. Array and (doubly) linked lists can be used to keep a list of items and implement the vector abstract data type. Consider the ...
2
votes
2answers
109 views

Proving non-confluency and adding an equation to make it confluent and terminating

I currently have a system that has {f(a) = b, f(f(x)) = x} (part of an exam question - look at page 5 - exercise 1). To start off with proving non-confluency, I am ...
19
votes
7answers
10k 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 ...
3
votes
3answers
185 views

How center the eyes of human face at specific pixels?

I am facing a problem with processing some frontal facial images. I need to adjust the centers of the eyes (irises) to be at certain specific pixels in the image. In other words, i need to transform ...
19
votes
1answer
352 views

Solving divide & conquer reccurences if the split-ratio depends on $n$

Is there a general method to solve the recurrence of the form: $T(n) = T(n-n^c) + T(n^c) + f(n)$ for $c < 1$, or more generally $T(n) = T(n-g(n)) + T(r(n)) + f(n)$ where $g(n),r(n)$ are some ...
4
votes
2answers
8k views

What is the complexity of this matrix transposition?

I'm working on some exercises regarding graph theory and complexity. Now I'm asked to give an algorithm that computes a transposed graph of $G$, $G^T$ given the adjacency matrix of $G$. So basically ...
1
vote
0answers
42 views

Algorithm for query comparison

Lets say I have a global dataset and I run queries over those data set. For example my dataset would be #id, #Name, #Employee, #Birthdate, #number_of_children 1, Nick, Nasa, 1982, 1 2, Jack, Exon, ...
1
vote
1answer
548 views

Are there languages generated by linear grammar which aren't regular?

Are there languages generated by linear grammer which aren't regular?
1
vote
3answers
344 views

Can P=PSPACE and PSPACE problems be formulated as $\Pi_1$ formula?

To say simply, can PSPACE problems be written as $\Pi_1$ formula? Or how can these problems be written in terms of (first-order) arithmetic hierarchy? edit:also currently, by what arithmetic ...
3
votes
1answer
725 views

Finding simpler equivalent regular expressions

I'm doing an exercise from my book that says: Let $r$ and $s$ be arbitrary regular expressions over the alphabet $\Sigma$. Find a simpler equivalent regular expression: a. $r(r^*r + r^*) + r^*$...
-1
votes
1answer
837 views

Constructing right-linear grammar

Is the grammar $\qquad S \to 1A0A \mid 0A \mid \varepsilon$ a right-linear grammar? $A$ is a nonterminal here, $0$ and $1$ are terminals. I know $0A$ is right-linear but what about $1A0A$? Trying ...
7
votes
1answer
5k views

How to find a local minimum of a complete binary tree?

How to find a local minimum of a complete binary tree? Consider an $n$-node complete binary tree $T$, where $n = 2^d − 1$ for some $d$. Each node $v \in V(T)$ is labeled with a real number $x_v$. ...
5
votes
2answers
1k views

String of minimum length in $\{a, b\}^*$ not in a regular expression

I'm doing an exercise in my book, the question is to find a string of minimum length in $\{a, b\}^*$ not in the language corresponding to the given regular expression. a. $b^*(ab)^*a^*$ My answer: $...
1
vote
2answers
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 ...
2
votes
1answer
594 views

first order logic resolution unification

Assuming I have shown part of the knowledge base in the clausal format: [1] p1(banana). [2] not p1(X) or p2(Y). [3] p1(X) or not p3(F). ... and more rules. ...
6
votes
2answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
8
votes
3answers
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 ...
19
votes
2answers
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.
6
votes
2answers
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 ...
1
vote
1answer
237 views

Multithreaded access to a persistent linked list data structure

I previously asked a question about persistent data structures here. After that I came across an article that introduced persistent data structures. I have got a question on the following figure from ...
2
votes
1answer
316 views

Confusion related to time complexity of fast fourier transform

I have this confusion related to the time complexity of FFT. I was reading this book related to Design and Analysis of Algorithms and I came across FFT. It says that lets say I have a polynomial of ...

15 30 50 per page