All Questions

1
vote
1answer
4 views

Find all $k$ local maximums in an array of length $n$ in $O(n \log k)$ time

Given a sequence of numbers $a_1, a_2, ..., a_n$, a number $a_i$ is called the $k$ local maximum $\iff i > k$ and $a_i$ is the largest number among the $(k+1)$ numbers $a_{i-k}, a_{i-k+1}, ..., ...
-1
votes
0answers
4 views

Design an instruction set

Assuming a 16 bit word size and a 64MB memory is used state all bus widths. Design an instruction set. Design the circuitry arrangement inside the ALU.
-1
votes
0answers
3 views

Is there any program where you input pairs of words and then you use it to memorize the pairing between these words?

Is there any program where you input pairs of words and then you use it to memorize the pairing between these words? I do not only mean something functioning like a flashcard, I also mean something ...
0
votes
0answers
6 views

MAX-SAT for ising spin glass

What is the best MAX-SAT solver problems for Ising spin glass? I tried Scip-Max-sat and open-wbo. While open-wbo cannot solve the instance with only 27 variable Scip-max-Sat fail to solve the one with ...
0
votes
0answers
4 views

Creating branch less than equals zero MIPS instruction in single cycle circuit

As a project I'm trying to implement a MIPS processor. I have a circuit similar to the one below. My question is what would be a way to implement a ...
0
votes
1answer
16 views

Bayes nets - calculating probabilities

Given a Bayesian network, say a -> b -> c, all binary random variables (I won't show the CPTs, assume they are given). You are told b and c are true. How do you calculate the P(a=True)?
0
votes
0answers
10 views

Unrestricted grammar for a^n^2

I have a basic idea of how to generate an unrestricted grammar for a^2^n, a^3^n, or any a^c^n where c = constant. For a^2^n: S -> @aP P -> e P -> RP aR -> Raa @R -> @ @ -> e For a^3^n: S -> ...
1
vote
0answers
7 views

Disc covering problem

I have an arbitrary 2d area on the xy plane. I want to cover it with N discs such that all points in the area have at least one disc overlapping it. A disc with center (xc, yc) placed inside this area ...
0
votes
0answers
12 views

Are nondeterministic algorithm and randomized algorithms algorithms on a deterministic Turing machine?

An algorithm on an abstract machine is a finite sequence of operations of the machine. (Correct me if I am not correct.) Are nondeterministic algorithm algorithms on a deterministic Turing machine? ...
1
vote
1answer
17 views

Find a collection of sets where each number from a given list is contained in a different set

I have a set of numbers S of cardinality N, and a collection of sets each containing some subset of S. The cardinality of each of these sets can be anywhere from 1 to N. The number of sets is ...
0
votes
0answers
18 views

Are these two algorithms the same?

An algorithm is a finite sequence of operations on an abstract machine. (Correct me, if I am not correct). If two algorithms can take the same set of inputs, and for each input, they generates the ...
1
vote
0answers
9 views

TSP cycle approximation proofs

Having a hard time formulating the proof for this. The professor kinda breezed through the problems and I just want an explanation on how best to tackle this and how one would prove what it's ...
0
votes
0answers
14 views

Find different coin

You have 12 coins. But one of them is different by weight. But it's unknown that different coin is lighter or heavier than other others. So, in 3 steps by using scales you have to find the different ...
1
vote
0answers
7 views

A reference for pseudocode for Monge-Elkan algorithm?

Does anyone have a good reference to pseudocode for Monge-Elkan string comparison algorithm or a single class Java/C implementation? I have access to original two papers, but they do not show the ...
0
votes
0answers
2 views

Literature on pattern recognition for symbolic sequences

Actually, I'm not sure the title is correct since I'm a complete novice in the field and admit that I can mix (or make) up terms. What I would like to research is the following problem: having a set ...
3
votes
1answer
17 views

Why can't we search lexicographicaly ordered programs to compute Kolmogrov complexity?

Kolmogrov complexity is known to be uncomputable. Why can't we enumerate all programs of size i = 0 in lexicographical order - if any produce string s, that is the Kolmogrov complexity; if not, ...
2
votes
0answers
12 views

Distributed push relabel with changing graph topology

There is at least one (1) distributed version propsosed for the push-relabel maximum-flow algorithm. I wonder if and how this algorithm can cope with nodes leaving or enterig the graph during runtime. ...
0
votes
0answers
24 views

Equivalence of definitions of balanced parentheses strings

The strings of balanced parentheses can be defined in at least two ways. A sring w over alphabet {(,)} is balanced IFF: a) w has an equal number of ('s and )'s and b) any prefix of w has at least ...
0
votes
0answers
4 views

While writing out the cores (to make parsing table) for SLR(1) and CLR(1) grammars why do we write lookaheads for only CLR?

I mean both SLR(1) and CLR(1) can look 1 symbol ahead. Why do we consider that lookahead only in CLR and not in SLR while drawing cores to make the table
1
vote
1answer
13 views

Big-O Notation for Menezes-Vanstone Elliptic Curve Cryptography?

I need someone help me about . how can compute time complexity for this algorithm (Menezes-Vanstone Elliptic Curve Cryptography). I have spent much time reading journals and papers but as yet have ...
3
votes
2answers
666 views

How is a Turing Test defined?

Turing Test definition taken from wikipedia: The Turing test is a test of a machine's ability to exhibit intelligent behavior equivalent to, or indistinguishable from, that of a human. In the ...
0
votes
0answers
6 views

Bulk-loading R-tree with data with extent

When bulk-loading R-tree with points one can simply sort the elements by some coordinate and split to equal-sized chunks. But if the elements have some extent, sorting them by their coordinate value ...
2
votes
3answers
34 views

Recursive methods with stacks

I'm doing some practice papers for revision for my finals and I came across this question: "This question is about recursion. A recursive method can always be implemented by an iterative method ...
0
votes
1answer
14 views

Kleene positive closure - help in proofing this claim

I just started a course called 'Automata and Formal Languages'. I'm having difficulty in proofing\disproofing this equality. $ (L_{1} \circ L_{2})^{+} = L_{1}^{+} \circ L_{2}^{+} $ Where: $ ...
0
votes
0answers
24 views

Does an abstract machine only have one language? [on hold]

An abstract machine has a language which contains all the strings it recognize. In that sense, is it correct that an abstract machine has only one language? On a computer, there is a (unique?) ...
5
votes
1answer
201 views

Is a secondary TM sufficient to detect all loops?

Procedure: Start a secondary TM in parallel with the first, but have the second perform exactly 1 step each 2 steps the first TM performs (i.e. it runs at half speed). If the second machine ever ...
1
vote
2answers
35 views

What is the set of operations of a Turing machine?

From https://en.wikipedia.org/wiki/Abstract_machine A typical abstract machine consists of a definition in terms of input, output, and the set of allowable operations used to turn the former ...
1
vote
0answers
14 views

How to solve the following recurrence: g(n) = g(log n) + n^(1/2) [duplicate]

Doesn't fit the Master method, and I am not sure where to go from here. Thanks
2
votes
0answers
27 views

Quick method for approximate integer square roots

I'm looking for an algorithm that -- given a positive integer $n$ -- outputs a positive integer $\bar{n}$ with the following two properties: $(\bar{n}+1)^2>n$; $(\bar{n}-1)^2<n$; So we have ...
1
vote
0answers
8 views

Why having a simple multiplication loop and very good avalanche isn't enough to produce well-distributed hash values?

Modern non-cryptographic 32- and 64-bit valued hash functions, for example, lookup3, MurmurHash3 and CityHash, have quite sophisticated loops, each iteration of which include many multimplications, ...
-1
votes
0answers
15 views

Master method question [duplicate]

Given the following equation: T(n)=5∗T(n/3)+4n Am I right that a = 5, b = 3, d = 4 which would fulfill case 2 of the Master Method (a < b^d), and gives O(n^d) running time, or am I missing ...
3
votes
2answers
127 views

Finite number of Turing machines running concurrently on multi-tapes Turing-machine-equivalent?

So basically, there are several (finite number of) Turing machines being able to read off and write to the same set of tapes (the number of tapes is finite, but each tape may have infinite tape ...
-2
votes
1answer
18 views

Quantum Artificial Intelligence

Would anyone be able to point me in the direction of some good scholarly articles on Quantum Artificial intelligence. I have to write a research paper on the topic and I'm having trouble coming up ...
5
votes
2answers
45 views

Does the Y combinator contradict the Curry-Howard correspondence?

The Y combinator has the type $(a \rightarrow a) \rightarrow a$. By the Curry-Howard Correspondence, because the type $(a \rightarrow a) \rightarrow a$ is inhabited, it must correspond to a true ...
0
votes
1answer
26 views

Given two sequences of the same size, how many longest common subsequences can they have?

For simplicity assume that both have the same size N. the lengh of this subsequence can be at most N, so maybe it's max(C(N,1), C(N,2), ... , C(N,N))?
1
vote
2answers
42 views

A basic question about approximation algorithms for the Traveling Salesman Problem

Approximating the traveling salesman problem (TSP) within a constant factor $k$ is hard. The standard proof shows that the existence of such an approximation allows the Hamilton Cycle problem to be ...
2
votes
1answer
39 views

Is $AlwaysHalt$ recursively enumerable?

I was doing some complexity theory exercices and I came over this one: $AlwaysHalt = \{R(M) | M$ halts with all $x \in \{0,1\}^*\}$ Is $AlwaysHalt$ recursively enumerable? I would say YES and ...
1
vote
0answers
11 views

How does SARSA handle episode termination

When applied to domains that are episodic and have a "final" state but no final action, like a game, how does SARSA update the Q-values? e.g. A game agent would receive this series: ...
1
vote
1answer
44 views

Resolving ambiguity in dangling else

Initially the ambiguous grammar is as follows (with some cropped production rules): ...
1
vote
1answer
49 views

Are conditionals necessary in computation? [duplicate]

I know this question might seem weird, maybe I'm just overthinking, but this is really troubling me because I've been a computer engineer for some time now and conditionals (if statements for ...
-1
votes
2answers
24 views

Ambiguous Grammar to Unambiguous Grammar

I'm wondering if somebody can please help me to understand how I go about converting this grammar to an unambiguous grammar. If you can point me in the right direction, I would greatly appreciate it. ...
2
votes
1answer
84 views

compressing a set of binary strings with fixed length

I'm looking for a data structure / algorithm to store an unordered set S of binary strings of a fixed length n (i.e. all ...
2
votes
1answer
25 views

Proving approximation ratio

We recently in computational complexity class dealt with approximation algorithms and I was wondering how one would prove a heuristic having a certain ratio in regards to the optimal version. Looking ...
1
vote
1answer
18 views

Comparing coefficients of boolean functions

Let a real polynomial representing a boolean function be $P(x_1,\dots,x_n) = \sum_{a\in\{0,1\}^n}c_ax^a = \sum_{a\in\{0,1\}^n}p(a)\prod_{i\in 1_a}x_i\prod_{j\in \bar{1}_a}(1-x_j)$ where $1_a$ is the ...
-2
votes
0answers
19 views

What is difference between Oracle and SqlPlus? [on hold]

I installed Oracle 10g. There is also SQLplus in it. For starting the software we have to start with SQLPLUS. what is difference between them ? or they same or something else ?
0
votes
1answer
25 views

Karnaugh Map is this the simplest solution possible?

I'm learning to use a Karnaugh map but I'm not sure if I obtained the simplest expression possible. Have a look at this example Truth table (where A B C yield F): ...
1
vote
0answers
7 views

minimize cost and maximize quality of function in four variables

Problem: Find optimal values for four parameters which are used to tune an algorithm under the constraints of accuracy, time and memory. I have an indexing scheme used to search for the K-nearest ...
0
votes
0answers
15 views

For computer engineering student how useful are certifications? [on hold]

I hope this is the right exchange community. If it's not feel free to delete it. Right now I'm doing HP ATA connected devices: http://h10120.www1.hp.com/expertone/datacard/Certification/ATA-CDV1 ...
-2
votes
1answer
21 views

Is the given functional dependency a partial dependency or transitive dependency or both?

Relation - R(A,B,C,D) Functional dependencies AB->C BC->D Is BC->D a partial dependency or transitive dependency or both?
0
votes
0answers
32 views

Algorithm for rope burning problem [on hold]

Generalized from a technical interview question: Original question: There are two ropes, each rope takes 1 hour to burn. But either rope has different densities at different points, so there’s ...

15 30 50 per page