All Questions
44,241
questions
0
votes
0
answers
3
views
Find $k$ shortest paths in linear time
Suppose given number $k$ and undirected unweighted graph $G=(V,E)$, also given two vertices $s$ and $t$. Can we find $k$ shortest paths between $s$ and $t$ in $O(n+m)$ without term $k$?
I read this ...
0
votes
0
answers
4
views
The Language of All Palindromes - Is it CFL?
Regarding $L=\{ww^R~|~w\in\Sigma^*\}$ - The language of all palindromes.
Is it a CFL?
I think it is, because if we take any $\Sigma$, for example $\Sigma=\{a,b\}$, then it certainty is. CFL are closed ...
- 1
0
votes
0
answers
18
views
Formal mathematical resolution for Recurrence Relations
let's suppose we've got a simple Recurrence Relation:
$$ T(n) = \begin{cases}
1 & n=1 \\
T(n-1) + \Theta(n) & \text{otherwise}
\end{cases}
$$
At lesson we've resolved it, but I ...
- 200
0
votes
1
answer
23
views
Cosine distance in a space, and cheating?
I read an example of using cosine distance in RGB space, and it pointed out that (eg.) dark red and light red have a cosine distance (CD) of zero because CD only gives you the angle between vectors ...
- 198
0
votes
0
answers
9
views
Can you safely use the remaining space on a an external hard drive used for a recovery drive? [closed]
I created a recovery drive with the Control Panel's Advanced Recovery Tools, on an external hard drive. Is it safe (for the purposes of retaining a functional recovery drive) to create a new simple ...
0
votes
0
answers
27
views
Undirected unweighted sub-graph enumeration with threshold on node value
I have an undirected, unweighted graph $G=(V,E)$, and a function $f:V\to [0,1]$ where $[0,1]$ denotes the interval of real numbers from $0$ to $1$ inclusive.
Given an input threshold $t\in [0,1]$, I ...
- 101
0
votes
0
answers
23
views
Tight bounds for expected maximum of k binomial(n,p) IIDs
What is the tightest lower and upper bound for the expected maximum value of k IID Binomial(n, p) random variables
I tried to derive it :
$$Pr[max \leq C] = (\sum_{i = 0}^C {n \choose i}p^i(1 - p)^i)^...
- 13
1
vote
1
answer
37
views
How many different boolean functions exist up to permutation of its $n$ variables
i am relatively new here, so if this was asked before, feel free to redirect me. I am searching for an answer in form of a (iterative or recursive) Formula or even better, an algorithm to list them ...
- 13
0
votes
0
answers
14
views
How do I determine how many blocks have been replaced and what the hit ratio is of the following direct-mapped cache?
I have a direct-mapped cache with the following properties:
Address size = 32 bits
Cache block size = 8 words
Entries = 32
So we can see the cache as a 32 by 8 table where the index selects the row ...
- 121
1
vote
2
answers
41
views
Why is $A_{TM}$ not mapping reducible to $E_{TM}$?
$A_{TM}= \{ \langle M,w\rangle \mid M$ is a TM that accepts $w\}$
$E_{TM}= \{ \langle M\rangle \mid L(M) = \emptyset \}$
The standard proof for the undecidability of $E_{TM}$ is given in this ...
- 255
-3
votes
0
answers
26
views
Fixed parameter tractability Big O
Was wondering if anyone had some guidance as to whether the following big-O expressions are fpt and what the smallest possible set of parameters would be to make them fpt.
- 1
0
votes
0
answers
34
views
Binary compression algorithem with decompress by index
I have a list of 256-bit data to store. How to compress it losslessly so that I can retrieve an entry by its index without decompressing the whole data. I will also need to code this algorithm ground-...
0
votes
1
answer
15
views
Multi Objective Optimization Using Only Single Objective Optimization Algorithms
Let's say there is a single objective optimization problem SP (e.g. a linear program) and an optimization algorithm SA for it (e.g. simplex). Then applying SA to SP yields an optimal solution ...
- 123
0
votes
2
answers
45
views
A little confusion with Big Theta time complexity
I came across one Big Theta expression:
Here I am thinking this expression to be valid. But please correct me as the answer doesn't goes in the same way.
As per definition of Big Theta.. any function ...
1
vote
0
answers
23
views
Dot symbol in set-builder expressions in CRDT literature?
In Conflict-free Replicated Data Types: An Overview and other CRDT-related publications by Preguiça's group, a dot symbol often appears without definition. What does it indicate, how standard is it as ...
- 11
-3
votes
0
answers
25
views
Its about automata [closed]
Find regular expression for language that accepted exactly one double letter then find NFA and convert to DFA, find CFG for this regular expression?
1
vote
1
answer
57
views
Are reversed reverse preorder traversals equivalent to a postorder traversal?
I was viewing the solutions of other Leetcode users for the classic "post-order traversal of a binary tree" question, when to my surprise, I found a ton of users simply finding the reverse ...
- 113
0
votes
1
answer
52
views
Why is there a 'true' statement as precondition in the following loop invariant
Precondition: true
int i = 0;
while (i < a.length && a[i] != x) {
i++;
}
Postcondition: (∀ j : 0 ≤ j < i : a[j] ≠ x) ⋀ (i = a.length ∨ a[i] = x) }
As I read it, the program has no ...
- 115
-1
votes
0
answers
39
views
Implementing multidimensional integral for a custom function in C++ [closed]
I am not an expert with C++, but I am trying to implement a 4-dimensional integral using GSL numerical integration approach.
The code below shows the whole algorithm. Although it seems correct what I ...
- 111
-1
votes
0
answers
20
views
How can I calculate the computational complexity of an equation composed of $2n$ multiplications and $2nm^2$ additions? [closed]
I want to calculate the computational complexity in term of the big ($\cal O$). My equation is:
It composed of 2n multiplications and $2nm^2$ additions. The complexity of this equation is it ${\cal O}...
- 99
0
votes
0
answers
14
views
What is the Parse tree for example 2.6 from Aho's Compiler Dragon Book? [closed]
I am very sorry to screen readers for the image but I want parse trees for 9 + 5 * 2 and
9 * 5 + 2.
They have a grammar:
...
- 207
0
votes
0
answers
23
views
Is copying and pasting a sort of object embedding?
If I copy a picture and paste it into Microsoft Word, would there be the difference if I embedded the same picture into another Word file ? Are they both object embedding?(As the object is saved in ...
0
votes
0
answers
57
views
Is there a hash-map implementation optimized to favor key lookups based on frequency (if key is referenced the most then it is searched first)?
I have started to play around with HTTP3 which relies on QUIC for transport. I have noticed that I very often have a finite number of Web Transport sessions stream data continuously along side burst-y ...
- 101
2
votes
3
answers
102
views
Find the smallest difference between two numbers in a DS in O(1) time
I got an assignment to create a new data structure, with the following rules:
Init - O(1).
Insert x - O(log$_2$n).
Delete x - O(log$_2$n).
Search for x- O(log$_2$n).
Find max difference between two ...
- 21
0
votes
0
answers
17
views
Considering definitions as equalities, what would happen if you continually substituted a word’s definition?
I’ve had this question for several years now but have next to no programming experience, nor good connections to anybody who does. So I decided to see if stack exchange had an answer.
The idea is to ...
1
vote
0
answers
17
views
Relation between left derivations, right derivations and number of parse trees?
I saw this question on a test-prep site
Given a CFG and a string, what is the relation between the number of leftmost derivations, the number of rightmost derivations and the number of parse trees?
...
- 255
1
vote
1
answer
16
views
Efficient search of a large set of documents to find documents that only contain a particular set of words
Say I have a set of documents $D = \{d_1, d_2, \dots, d_n\}$ in some natural language.
Each document $d_i$ consists of a subset of words from a word pool $W = \{w_1, w_2, \dots, w_k\}$. For example, $\...
- 111
2
votes
1
answer
510
views
Is there an algorithm that in some cases is an improvement of BFS in the same way A* is an improvement of Dijkstra?
The problem concerns finding shortest paths in graph from a single source to a single destination.
So in a general non-degenerate case of a weighted graph, Dijkstra's algorithm runs in O(E+VlogV). A* ...
0
votes
0
answers
29
views
Find a set K of k vertices in a graph such that the distance between any vertex to the closest vertex in K is minimized
Given a graph with $V$ vertices and $k$, find a set $K$ of $k$ vertices of $G$. Let $c(v)$ be the distance (in BFS-like) of the vertex $v \in V$ to the closest vertex $u \in K$. How to choose the set $...
- 101
3
votes
2
answers
1k
views
Length of a regular expression
What is the definition for the length of a regular expression? This question might sound simple, yet I cannot find a definition. Do I only count letters from the alphabet? Do * and $\cup$ count?
For ...
- 43
-1
votes
0
answers
25
views
Work out corresponding logical address
this should be a simple question but I don't quite understand how to work out the logical address from the information given.
Question:
Suppose a program is running on a system with a simple base ...
- 1
0
votes
0
answers
13
views
Can you a push multiple symbols on simplified PDA stack in one transition?
I encountered this problem when I was converting a PDA to a CNF and I was looking for two transitions that push and pop the same symbol(one pushes and one pops).
The PDA I was converting had this ...
- 61
0
votes
3
answers
70
views
How is pipelining possible?
As far as I understand pipelining is a way to excecute a instruction every clock cycle. It is a process performed on single cores. My question is how does the control unit handle this, at some point ...
- 1
1
vote
1
answer
22
views
Can Boolean circuits of polylog depth represent all Boolean functions?
Consider a Boolean circuit using (2-input) logical-and, (2-input) logical-or and logical-not as basic components. The depth of the Boolean circuit is the length of the longest path from the input to ...
- 258
0
votes
1
answer
18
views
Switching between doing something and not doing it within $k$ steps in LTL
Imagine that we are designing a system in which we have the action to brake or not brake. How can we write an LTL specification that guarantees that we cannot switch between braking and not braking ...
0
votes
0
answers
20
views
Time complexity of find() operation for a Merge-Find Set
Given a Merge-Find Set implemented using a set of linked-lists, my professor says that the time complexity of find() operation is O(1). Each element of the lists ...
- 315
0
votes
1
answer
73
views
I think I have discovered a new sorting algorithm using binary search tree [closed]
If we some how transform a Binary Search Tree into a form where no node other than root may have both right and left child and the nodes the right sub-tree of the root may only have right child, and ...
-1
votes
0
answers
23
views
Time complexity of a dynamic programming algorithm?
$$a_1,\dots,a_n$$
$$b_1,\dots,b_n$$ are integers bounded in $[-B,B]$ and we want to find a common subset $I\subseteq\{1,\dots,n\}$ such that $$\sum_{i\in I}a_i=\sum_{i\in I}b_i=m.$$
This problem is $...
- 2,820
3
votes
1
answer
61
views
Allocating m rooms of varying capacity to n booking requests of varying sizes
I am developing a system which performs automated room allotment. We have finite number of rooms, each with varying capacity. Each booking request is also of varying size. The goal here is to minimize ...
- 131
1
vote
1
answer
52
views
How to convert AFA to ε-NFA / NFA / DFA?
Alternating Finite Automata is a superset of NFA while being equal in expressive power to NFAs. It is defined by 6-tuple (Q∃, Q∀, Σ, δ, Q0, F) where all outgoing transitions from Q∃ are 'or'ed and ...
1
vote
1
answer
78
views
How to find parameter sets for a big-O expression to be fixed-parameter tractable?
I've been stuck on the following assignment taken from Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis:
Imagine that the following big-O expressions ...
- 13
1
vote
0
answers
17
views
RP with very small error = P
I was asked to show the equality $ RP(1 − 2^{-2^{n}}) = P $, which seems wrong to me (?).
The $ \supseteq $ direction is obvious, and I want to show the other direction.
My first intuition was to run ...
- 111
2
votes
1
answer
109
views
Disprove: if L is decidable then Prefix(L) is decidable
The following question was sent to me by a friend and I didn't really ask him about its source so I couldn't provide the source of it. I solved the question and I need to ensure my answer not just for ...
- 313
1
vote
0
answers
28
views
Split Bipartite Graph
I have a bipartite graph $G=(U=\{U_1, U_2,\cdots\}, V=\{V_1, V_2,\cdots\} , E)$ such that edges don't "skip" the $V$ vertices. Meaning, if edge $(U_i, V_j)$ doesn't exist, neither will edges ...
- 143
0
votes
1
answer
70
views
Finding a Hamiltonian Cycle in a directed graph - graph problem
$N$ towns are given, which we can get to by passing through the northern and southern gates. If you enter a town through a gate, you have to use another gate to leave the town. The merchant would like ...
- 29
1
vote
1
answer
37
views
Is finding the union of all minimum hitting sets NP-hard?
Let's start with the well-known minimum hitting set problem (known to be NP-hard): given some collection of sets: $U = \{S_1, S_2, S_3\} = \{\{1, 2, 5, 9\}, \{1,2,7\}, \{42, 13, 23, 1, 2\}\}$ for ...
- 13
0
votes
0
answers
19
views
Entropy of a single Hint
Assume that the probability that a woman is above 80 years old is 3 times that of a man. How much information (in bits) do you get if you are given that a 80 year old person is a male?
How should I ...
0
votes
1
answer
17
views
Is there an algorithm for mapping two ambiguous and unrelated data sets?
I was curious to see whether or not there was a common algorithm for mapping two unrelated data sets.
So for example let's say I wanted to give you a spirit animal based on your name, birthday, zodiac ...
- 1
0
votes
0
answers
22
views
What kind of CNF and DNF are in P [closed]
could anyone help me to prove which languages are in P? I will present my thoughts but I do not know how to go from there. Thank for any help
l1 = {L | L is on CNF and is satisfiable}
l2 = {L | L is ...
- 103
1
vote
1
answer
18
views
Max matching algorithm lemma approximation algorithm
We have this algorithm which is supposed to find max matchings.
...
- 25