All Questions
47,702
questions
4
votes
1
answer
696
views
Is Determining the Number of Prime Factors Polynomial?
Our current understanding of prime factorization states that it is hard to solve. The problem asks us to find the list of prime factors for an integer. For example, 18's prime factors are 3, 3, and 2. ...
- 55
0
votes
0
answers
61
views
Finding the Depth-First Index of a Child Given the Parent's Depth First Index Index in Complete k-ary Tree
I have a complete k-ary tree with a depth of $d$. If I'm given a node's depth-first index, I'd like a closed-form formula for calculating both the nodes children's depth-first indexes along with a ...
- 101
1
vote
2
answers
70
views
Union of non regular and regular language
So I have a regular language L and a non-regular language L' and i want to proof wether the union of both is regular or not.
Since I found counterexamples for both cases I want to look at more ...
- 11
0
votes
1
answer
27
views
How does a regular expression match `.+x`?
A quick test shows what I'm describing:
> const text = 'foobarhelloworld'
> const pattern = /.+or/
> text.match(pattern) //=> 'foobarhellowor'
What is ...
- 2,163
0
votes
0
answers
59
views
In Johnson's algorithm for enumerating elementary circuits in a directed graph, why do B-lists have a different structure than the adjacency list?
I have a question on the implementation of the Johnson's algorithm in C that is actually at the interface of theory and practice.
Link to Johnson's paper
I already implemented this algorithm in R ...
1
vote
1
answer
89
views
Maximizing sum and product of an array
Given an array of positive numbers with allowed replication, what is the algorithm to find the max amount possible only with summing or multiplying elements? All numbers must be involved in some ...
- 25
0
votes
0
answers
39
views
Union of non-regular and finite language
So i got this problem where should prove whether the union of a non regular language $L$ and a finite Language $L'$ is regular or not.
My Idea was to show that any regular Language $L_r$ cannot be ...
- 11
3
votes
1
answer
31
views
Increasing families of expander graphs
I would like to know if there is any research dealing with the problem of constructing an increasing family of expander graphs.
The goal is to find a family of expander graphs $(G_i)_{i \in \mathbb{N}}...
- 31
0
votes
0
answers
19
views
Can we make Paxos live with a failure detector in W?
I was studying Paxos and Failure Detectors, and it was asked whether a failure detector W could be used to make Paxos live, but I can't figure it out.
Any suggestions?
- 1
0
votes
0
answers
18
views
How to estimate the number of nodes in a trie based on a dictionary of words?
Say I want to build a trie out of 800,000 Sanskrit "base" words (in Devanagari script), with 20 prefixes and 2,000 possible suffixes. Each word is anywhere from 1-20 characters, and prefixes/...
- 2,163
1
vote
1
answer
58
views
Complexity of non-commutative range multiplication operation
Let $G$ be a non-commutative group, such as $\operatorname{GL}_k(\mathbb F_p)$. Given a list $\vec{a}=(a_1, \cdots, a_n) \in G^n$, we use $(p, q, x)$ to denote the operation that maps $\vec{a}$ to $(...
- 13
0
votes
1
answer
17
views
Same Address and Write signal for two block of RAM?
I don't know if I asked the question in correct way but I will try to explain what's the thing I am not getting. I am currently reading book titled "Code: The Hidden Language of Computer Hardware ...
- 1
0
votes
0
answers
9
views
What is a good appropriate algorithm for localization for images?
Assume that you have an image that you going to classify its class ID.
One good option is to use interest points e.g FAST that can find coners/edges inside an image.
From these points you could ...
- 97
1
vote
0
answers
10
views
Auxiliary Space Complexity of Dictionaries whose Keys are Iterables of Variable Size
Recently, I began delving into complexity analysis with dictionaries. More specifically, I have been looking at auxiliary space complexity. For the most part, this type of analysis has been ...
- 11
0
votes
1
answer
22
views
What happens for hardware Interrupts in non-preemptive scheduling?
In non-preemptive scheduling, the running process cant be interrupted .But what will when the CPU receive a hardware interrupt such as the an interrupt from the printer indicating that the current ...
- 195
0
votes
1
answer
47
views
Prove with potential method that dynamic table with $q > 1$ expansion runs in amortized constant time
Suppose I have a dynamic table supporting $Insert$ procedure, which sets an input value after the tail of the dynamic table. If the underlying table is already full, we multiply its size by $q > 1$....
- 52
4
votes
3
answers
618
views
What is practically preventing us from applying set-theoretic types in engineering?
I know the title is sort of misleading because we do have set-theoretic types in several languages:) From a theoretic view, set-theoretic types such as intersection, union, and negation may bring some ...
- 41
1
vote
0
answers
39
views
How to evaluate the complexity of a code
Here is my code for computing the product of sequences of matrices
...
- 111
1
vote
1
answer
83
views
Algorithm for optimal item selections
I'm trying to find an algorithm for this problem:
I'm going to the shop and need to buy X grams of an ingredient.
The shop does not necessarily have an "X grams of ingredient" product.
But ...
- 111
0
votes
0
answers
27
views
Lookup Using Path Matrix in Floyd Warshall Algorithm
How is the path matrix created by the Floyd Warshall algorithm used for path lookup?
The 2 images show the graph (b) and the path matrix (c). Both are taken from the book: Foundations of Algorithms by ...
0
votes
0
answers
88
views
Finding all stable matchings in stable marriage problem
I need to find an algorithm for a modified version of the stable marriage problem. In particular, I need to find all possible stable matchings and not only one (unlike what the Gale-Shapley algorithm ...
- 1
0
votes
0
answers
13
views
Finding all stable matchings in stable marriage problem [duplicate]
I need to find an algorithm for a modified version of the stable marriage problem. In particular, I need to find all possible stable matchings and not only one (unlike what the Gale-Shapley algorithm ...
- 1
6
votes
1
answer
706
views
Representing binary functions with a finite gate set without exponential blow-up?
It is pretty well taught that any binary function can be represented using CNF. But conversion to CNF can take an exponential number of gates. The truth table is exponentially sized relative to the ...
- 327
1
vote
1
answer
44
views
Converting encrypted messages to unencrypted results of an equally hard to reverse function
If we have some function, $f$ with an exponentially sized domain, mapping the set $\{0, 1\}^N$ to $\{0, 1\}$, could we do something like this:
For ease, let's say $E(x) = x^e (\text{mod} \; n)$. This ...
- 55
0
votes
0
answers
27
views
What are the steps to create an intuitive and straightforward proof of the optimality of Huffman coding?
I am having great difficulty following the proof in class. I assume "optimal" means it minimizes the Average bit length to encode an alphabet with known frequencies. My understanding of how ...
0
votes
0
answers
37
views
fast estimation of the amount of unique combinations
Let's say I have a set of two columns - Name, Surname. I have a list of possible values for
Name -> Jacob, John
Surname -> Mayerson, Kindle.
I want to generate a set of unique combinations for ...
- 125
1
vote
1
answer
89
views
Is there an efficient algorithm for this ecommerce optimization problem?
Consider the problem of minimizing the checkout price of a shopping basket in the presence of some discount rules:
There are $n \gt 0$ distinct products in our shopping basket. Each product is ...
- 15
1
vote
1
answer
76
views
Number of decycling sets in a 3-regular planar graph
Defintitions:
A graph is said to be r-regular if every of its vertex has a degree $r$. A graph is planar if it can be drawn in a plane without any of its edges intersecting each other except at their ...
- 73
0
votes
1
answer
39
views
Implementing algorithms from online courses in code to solidify understanding
I came across the online course Design And Analysis Of Algorithms and the assignments have several questions that ask you to design algorithms, but you are not asked to implement them in code. I think ...
- 101
0
votes
1
answer
43
views
Reductions to perfect matching
Can we reduce any well-known problems to deciding whether a (possibly non-bipartite) graph $G$ has a perfect matching? I'm particularly interested in finding a reduction from deciding whether a ...
- 1
0
votes
0
answers
46
views
Turing machine for a^n b^m c^n d^m
The state diagram for the initial part of this turing machine given as:
Here, we are basically traversing through the input tape, changing occurence of 'a' to X1, and 'c' to X2. After that we go back ...
- 101
3
votes
1
answer
89
views
On a table there are $N$ stacks. Stack $i$ contains $i$ tokens. Minimum number of moves to make all stacks empty
On a table there are $n$ stacks (numbered $1$ to $n$). Stack $i$ contains $i$ tokens ($1 \leq i \leq n$). During a move, a set of stacks can be chosen and the same number of chips can be drawn from ...
- 31
0
votes
1
answer
33
views
Computability = Enumerating a sequence in the particular order?
In the paper "Computability by Probabilistic Machines" by K. de Leeuw, E. F. Moore, C. E. Shannon, and N. Shapiro (in Claude E. Shannon: Collected Papers , IEEE, 1993, pp.742-771), a ...
- 101
7
votes
2
answers
1k
views
Algorithmic Complexity of Recognizing Claw-Free Graphs
Let $H=\left(V_H, E_H\right)$ and $G=(V, E)$ be graphs. A subgraph isomorphism from $H$ to $G$ is a function $f: V_H \rightarrow V$ such that if $(u, v) \in E_H$, then $(f(u), f(v)) \in E$. $f$ is an ...
- 303
1
vote
1
answer
30
views
function is computable iff its graph is recursively enumerable?
How do I show that a (possibly partial) function is computable iff its graph is recursively enumerable?
- 23
0
votes
1
answer
32
views
Round-robin tournament scheduling, with teams that may share their home field
I need to implement an algorithm to create schedules for round-robin tournaments (where each team faces each other team exactly once), but with the constraint that up to 2 teams – that may play in ...
1
vote
2
answers
57
views
(how) is assignment or binding possible in purely functional languages?
i can't seem to find much info on the following question:
how (if at all) is the fixing of names to values (by binding or assignment) possible in a purely functional system like the lambda calculus?
i'...
- 11
0
votes
0
answers
56
views
Representation of pairs in System F
System F defines the data type pair as:
$$X\times Y := \Pi Z. (X\to Y \to Z)\to Z$$
with:
$$\langle x,y \rangle := \Lambda Z. \lambda p^{X\to Y\to Z}.p \text{ }x\text{ } y$$
Projections are defined:
$$...
0
votes
1
answer
199
views
Showing this scheduling problem is NP-hard
I've been reading up on scheduling problems and the class of them that is NP-complete. Specifically, this is a foundational text on such problems, but the reductions are not clear to me. Can someone ...
user163952
1
vote
1
answer
22
views
Linked Lists, Ordered Pairs?
I would like to model linked lists using set theory similar to that in Scheme and LISP.
There is a set theoretic definition of the ordered pair:
$p = \{\{a, 1\}, \{b, 2\}\}$
My question is how does ...
- 111
-2
votes
0
answers
30
views
1
vote
0
answers
19
views
Is $\Sigma_n^p$-SAT a complete problem for the $\Sigma_n^p$ class with polytime or with logspace reductions?
Here I define $\Sigma_n^p$-SAT to be the problem of deciding if a boolean formula in prenex normal form with $n$ alternating quantifiers, starting with $\exists$, is satisfiable.
I found several ...
- 31
1
vote
2
answers
46
views
What is point of calling syscalls in the kernel?
If syscalls are meant to transition into kernel mode from user mode, what is the point of calling syscalls in the kernel?
Reference: https://stackoverflow.com/questions/15841327/can-we-call-system-...
- 124
0
votes
0
answers
14
views
Which queue does `wait()` suspended process goes into?
According to javatpoint, ready and wait queue are different. But according to wikipedia they are synonymous, in this context. Now I am more confused.
What I want to know is, when the parent process ...
- 124
0
votes
0
answers
17
views
If the register size and the address bus are equal so do we need those segementation register to segment our memory?
In 8086, as i know we need those segementation register to segment our memory because the address bus is 20 bit and register size is 16. So, If the register size and the address bus are equal and we ...
0
votes
1
answer
26
views
Processes with communication exclusive from the OS
Most OSes use the message passing system to let 2 processes communicated with each other.This works by a shared mailbox between the OS and each process loaded in the RAM however are there processes ...
- 143
1
vote
0
answers
19
views
Parsing expression grammar for a language consisting of sentences with one character added or removed anywhere
Given a parsing expression grammar for a language, is there a way to make a parsing expression grammar for a new language that consists of the valid strings from the original language, plus the ...
- 111
0
votes
1
answer
99
views
Finding the error probability of a Monte Carlo algorithm
Let's say I have a Monte Carlo algorithm $A$ that gives the correct answer with a probability $p$ > $1/2$. I don't have any information on if it's decisional or not.
I understand that I can make ...
0
votes
2
answers
74
views
Calculating cells encompassing points in a grid
I have a sequence of points over time, and a grid of X by Y cells to which I need to calculate the cells in which the points fall, as depicted in the diagram below
Another point now arrives (as ...
- 101
0
votes
1
answer
33
views
Struggling with Recurrence Relation using Telescoping Approach
I have the following recurrence relation that I am trying to solve using the telescoping approach:
$T(n) =
\begin{cases}
T(\frac{n}{4})+ n^2 & \text{for } n \geq 4
\\
1 & \text{otherwise}
\...
