All Questions
0
votes
0answers
2 views
How do we know N=NP? is not hypothetical?
How do we know the N=NP? problem is not hypothetical?
That is, what is the evidence that N could equal NP?
I guess this is the same as asking:
If it's trivial that $N \subset NP$, then why is this ...
0
votes
0answers
4 views
Is the reverse postorder of a digraph's reverse the same as the postorder of the digraph?
I've been reading Sedgewick's intro to algorithms book, and he says that the reverse postorder of a digraph's reverse is not the same as the postorder of the digraph, however in both cases it seems ...
0
votes
0answers
3 views
Why do we not store the min in any of the recursive clusters in a Van Emde Boas tree?
I was reading the chapter of van Emde Boas in CLRS (page 547 section 20.3 3rd edition) and it says:
However, Iw as not sure why that was true. Usually I put more details on my question but I don't ...
0
votes
1answer
15 views
NP Class notation: $L_R = \{w\#y\space|\space R(w,y)\}$?
In the context of class NP.
What is the set
$$L_R = \{w\#y\space|\space R(w,y)\}$$
Specifically what kind of conditional is $R(w,y)$?
Also what's the purpose of $\#$?
This comes from page 2 of the ...
0
votes
0answers
16 views
Do poly-time algorithms exist whose time complexity is unprovable?
If not, is there a decision procedure that successfully classifies any
polynomial time algorithm as poly-time within a time polynomially bounded
by the length of the input algorithm?
1
vote
1answer
19 views
Average depth of a Binary Search Tree and AVL Tree
My professor recently mentioned that the average depth of the nodes in a binary search tree will be O(Log(n)) where n is the amount of nodes in the tree. I ended up drawing out a bunch of binary ...
2
votes
0answers
17 views
Original proof that orders eliminate deadlocks?
A well-known approach to eliminate the possibility of a deadlock when accessing exclusive ressources is enforcing a partial (or total) order in which the ressources may be requested.
Which ...
1
vote
1answer
21 views
Converting regular language to regular expression by replacing commas with union
I know that regular languages are those that can be described by regular expressions. For the language {0,1}*, is the corresponding regular expression ...
2
votes
1answer
17 views
Product Matching problem in pattern matching
The Product Matching problem is defined as follows:
Input: Text T=t0,...,tn and pattern P=p0,...,pm over alphabet Σ=N .
Output : All of the i places in the text where exists ci which holds
ti+j = ci ...
0
votes
5answers
90 views
How can there be 10 steps in the binary search algorithm for the phone book search problem?
The following example was given in an online lecture I was watching.
A phone directory is 1000 pages long, and we have to find the name "Zurich Smith". The algorithm is as follows:
Split the phone ...
2
votes
2answers
14 views
What's the real difference between throughput and capacity of a network cable?
I was preparing a presentation in work on GPON & other optical network technologies using documentation provided by a supplier, and the claim it made was "GPON networks have a capacity of up to ...
2
votes
1answer
24 views
What is the complexity of finding a regular expression equivalent to a given DFA?
I had taken a course long ago on complexity theory. I only remember basic things,
so I am reading "Introduction to the Theory of Computation by Michael Sipser". The book in its first chapter ...
2
votes
0answers
21 views
BIT: range updates, point queries; true meaning of tree[x]
for the past few days I've been studying Binary Indexed Tree (aka. Fenwick tree) data structure.
I understand the basic form of BIT (point update, range query), and I see the intuition behind it, but ...
-2
votes
1answer
23 views
Show that $L^c$ is also in NP
Let L be a language over Σ i.e., $L\subseteq Σ^∗$. Suppose L satisfies the > two conditions given below.
L is in NP and
for every n, there is exactly one string of length n that belongs ...
0
votes
0answers
25 views
What kind of Neural Network (if any) could fit two sets of data points?
I have two datasets, one of animal migration patterns (collected over the course of a couple years) that consists of many points on an x, y plane (latitude, longitude), and the other of ocean surface ...
-5
votes
0answers
29 views
I am a beginner and I want to know what programming language to learn [on hold]
Please suggest me some popular and most used programming languages. Thanks.
-2
votes
0answers
10 views
why is the every third one showing up again [on hold]
import java.util.HashSet;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
...
4
votes
1answer
134 views
Google Deep Dream has these understandings?
From my own exploration of Google Deep Dream, largely with Dreamify for IOS, and also from Google Image results on the topic, a few of the images I have produced/seen have led me to 3 conclusions ...
3
votes
2answers
49 views
Every graph with $\delta(G) \ge 2$ has a cycle of length at least $\delta(G)+1$?
I'm reading up on graph theory using Diestel's book. Right on the outset I got confused though over proposition 1.3.1 on page 8 which reads:
Proposition 1.3.1. Every graph G contains a path of ...
2
votes
0answers
14 views
What's a data structure for organizing strings of adjacent differences in a signal? [on hold]
My inputs will be strings of a fixed length k = 2^m that come from Forex rate data. So strings of real numbers [1.101, 1.102, 1.165, 1.133, ...], or lists or whatever you want to call them.
So let ...
2
votes
1answer
17 views
Party optimization: maximum weight independent set in a tree/graph
From Cornell
Suppose we want to throw a party for a company whose organization
chart is a binary tree. Each employee has an associated fun value, and
we want the set of invited employees to ...
9
votes
3answers
851 views
How much complexity difference can there be between finding a solution to a Sudoku puzzle and PROVING that the solution is the unique solution?
So usually Sudoku is $9 \times 9$, but this question extends to $n^2 \times n^2$ puzzles with $n > 3$ as well. There are many polynomial time deduction rules that can make progress in finding a ...
4
votes
0answers
45 views
Can any PEG grammar be parsed in linear time?
On the Wikipedia for PEG it is claimed:
Any PEG can be parsed in linear time by using a packrat parser, as described above.
However, packrat parsers can't handle left recursion.
You can ...
-3
votes
0answers
17 views
Find the number of cycles and instructions on a processor given that they execute a program in a given amount of time [on hold]
How can I find the number of cycles and instructions performed by a clock/processor in its execution of a program with given data?
Given a processor with a 4GHz clock rate, and 2.2 CPI; and ...
2
votes
1answer
28 views
Can I Use Machine Learning to Predict the Likelihood of an Order Being Shipped?
Let's say I have a database of freight orders. The job is to match freight carriers with customers who need their freight moved. I have the customer's information, the freight carrier's information, ...
4
votes
2answers
63 views
Are Strings Scalar?
I have always considered strings scalar and the main reason for that is that in programming we treat string values a lot like primitive values. But this and this Wikipedia definitions, as far as I ...
2
votes
1answer
35 views
Can one find the minima of a convex function efficiently?
Say I have a real valued convex function $f$ on the hypercube $[-1,1]^n$ and let $f'$ be its restriction on the discrete hypercube $\{-1,1\}^n$.
Is there any $poly(n)$ algorithm that for any class ...
2
votes
0answers
18 views
Register images containing objects with varying distance to the cameras
I'm learning about using image registration to align two images, e.g., two photographs of the same scene taken from a slightly different location. What factors influence how well we can align the ...
-2
votes
0answers
29 views
1
vote
1answer
56 views
Time complexity of Ackermann's Function
How would one go about classifying the time complexity of Ackermann's function, and can we say that all primitive-recursive functions are asymptotically bounded by the complexity of the Ackermann ...
4
votes
1answer
22 views
Find the shortest OPEN path connecting a set of 2D points (special case)
I want to trace the shortest path between a set of points on 2D space. The points have integer coordinates and visually appear to follow a well-defined unique path, though they're disordered.
The ...
16
votes
3answers
961 views
Given RSA, why do we not know if public-key cryptography is possible?
I was on wikipedia on list of unsolved computer science problems and found this:
Is public-key cryptography possible?
I thought RSA encryption was a form of public-key cryptography? Why is this a ...
1
vote
1answer
29 views
Till which layer does the loopback packet goes?
I want to know exactly till which layer the 127.0.0.1 (loopback) packet goes till it is returned to the upper layer. I read some where it goes till data link layer. but as i was told data link layer ...
16
votes
3answers
2k views
What is dynamic programming about?
Sorry in advance if this question sounds dumb...
As far as I know, building an algorithm using dynamic programming works this way:
express the problem as a recurrence relation;
implement the ...
5
votes
0answers
33 views
What is 2g-precedence?
I am currently reading a couple of papers about event processing. In the context of ordering events, "2g-precedence" is frequently mentioned. I don't know what it is, and I cannot find much ...
3
votes
1answer
44 views
Proving that a language is not Recursive
I have the following language:
T = {M | there exists w such that M accepts w within |w| steps}
I am trying to prove that this language is not recursive and that it is recursive-enumerable. To prove ...
3
votes
1answer
38 views
Sequence of total languages whose limit is turing complete
First let me clarify what I mean by a number of things.
A language is a decidable set of natural numbers which encode functions from natural numbers to natural numbers $ \mathbb{N} \to \mathbb{N}$. A ...
3
votes
0answers
52 views
If BQP is contained in any level of the Polynomial Hierarchy, does it then follow that $NP \subseteq BQP$ implies $PH \subseteq BQP$?
I think this is implied in this paper by Aaronson (http://www.scottaaronson.com/papers/bqpph.pdf) but I am not sure.
Begin with $NP \subseteq BQP$ (*)
$\Sigma_{2}^{P} = NP^{NP} \subseteq BQP^{BQP} = ...
2
votes
1answer
21 views
Alternative Method for Computing Two's Complement Binary -> Decimal
I proposed this method of converting a two's complement binary number to decimal to my professor and he said it was wrong. Some older guy in the class just shook his head at me and gave me a ...
3
votes
2answers
35 views
Testing the property of being a union of three disjoint cliques
Design an $\epsilon$-test for the following property in the dense graph model: $G(V,E)$ is a union of three disjoint cliques.
I've been sitting for a few hours and I don't have any idea of how to ...
2
votes
0answers
40 views
palindromic factorization
Is there a linear time algorithm that, given a string of length n, tells if it is a sequence of non overlapping palindromes (each of even length, in a binary alphabet)?? I found algorithms that return ...
2
votes
1answer
38 views
Finding Second large element from a set of 4 element
Is there any special algorithm of lowest complexity for finding 2nd largest element from a set of 4 elements?
2
votes
0answers
19 views
Baker Gill Solvay Relativization Result
I am reading the book by Arora and Barak, in which they try to prove there exists a langauge $U$ such that $P^{B} \neq U$.
I completely understood the proof except one problem in the end, they use ...
-1
votes
1answer
23 views
Fixing a grammar
I'm sorry I don't know the technical terminology for this. All I see in my notes is fixing a grammar. Can someone please help explain this? What exactly is this called?
0
votes
0answers
25 views
What is a good book to learn algorithm analysis and data structures for Ioi for a 15 year old with an ok math background? [on hold]
I can code Python and I am now willing to learn algorithms and data structures and I need to know where to start.
3
votes
0answers
53 views
Why does a first-child-next-sibling tree implementation have parent pointers?
Below is the code,
...
-1
votes
0answers
31 views
Whats that sign mean? [duplicate]
Whats that sign meanning?
taken from Intro to algorithms exercise 20.2-10
-4
votes
0answers
23 views
Apps / websites / blogs to pass the time [on hold]
I'm an aspiring programmer and I constantly find myself waiting in line or sitting in the car staring at my phone, checking all my social media. However I'd like to spend my time more productively. ...
0
votes
1answer
37 views
How to deal with $n\sqrt n$ in master theorem?
In classifying the following formula's asymptotic complexity using master theorem, I have $a = 8$, $b = 4$, and $d = ?$
$T(n) = 8T(n/4) + n\sqrt n$
How do I handle $n\sqrt n$ in this case to get $d$ ...
3
votes
3answers
266 views
Is an irregular language concatenated with a language with which it has no common symbols irregular?
Here's an example of what I'm talking about. Suppose I have a languages
$$
L_{1} = \{a^ib^i \mid i>0\},\\
L_{2} = \{c^i \mid i>0\}
$$
and
$$
L_{1}L_{2} = \{a^ib^ic^i \mid i>0\}
$$
Is it ...
