All Questions
47,775
questions
0
votes
1
answer
30
views
Guess the output of a c program [closed]
I have come across a c program like this .
int main()
{
int a,i=4;
int z=5;
a=--i+ --i+ --z;
printf("%d %d",a,i);
return 0;
}
What will be the output? I need some explanation.
0
votes
0
answers
19
views
CFG PL for L=\{a^ib^j \mid j = i^2\}
where i got it from. This was weird so I wanted to try it myself because they way he did it seemed wrong. So this is my attempt is it correct?
I did not add the basic parts of the pumping lemma proof ...
1
vote
1
answer
19
views
How is $\mathsf{RP\cap UP}$ not a class containing only unsatisfying languages?
$\mathsf{RP}$ can be deterministically defined as:
A language $L\in\mathsf{RP}$ iff there exists a polynomial $p$ and deterministic Turing machine $M$, such that:
$M$ runs for polynomial time $p$ on ...
- 1,429
0
votes
0
answers
26
views
How do you use Rice's theorem and why does it make sense? (Use provided Rice's theorem)
So this is the Rice's theorem we were provided:
Definition: $TM$-$FUNC(S)$
Input: Turing machine $M$
Question: Is $f_M \in S$
Let $S$ be a set of computable partial functions with $\emptyset \neq S \...
- 1
10
votes
1
answer
612
views
Are there associative cryptographic / collision resistant hashes?
Git uses SHA hashing as a content address key. This relies on their being a vanishingly small probability that two different pieces of content will ever hash to the same key.
For content ...
- 263
-1
votes
1
answer
37
views
Does the Halting Problem Explain the Fermi Paradox?
The Fermi Paradox asks why we have not yet encountered other intelligent life given the high chance of intelligent life emerging.
I recently had the following thought:
Evolution shapes the behaviour ...
- 1
0
votes
0
answers
23
views
Proving $A_{TM}$ is mapping reducible to certain language
I've been asked to prove that the language $A_{TM} = \{ \langle M,w\rangle \mid M$ is a TM that accepts $w\}$ is mapping reducible to the language $LOOP-ONE = \{\langle M \rangle \mid M$ is a Turing ...
- 229
0
votes
0
answers
31
views
Dynamic Program to find well formed set in a rooted tree
You are given a rooted tree $T=(V,E)$ with $n$ nodes and the root $r$. Each node $u\in V$ has an integer label $l(u)$. Suppose $S⊆V$ then $S$ is well-formed if for every $u,v\in S$ if $u$ is an ...
- 139
0
votes
0
answers
33
views
Proof that DFS order is P-complete [closed]
Suppose we are given an oriented graph G with a selected number of nodes s, where for each node some particular ordering of edges leading from it is specified. If we run a depth-first search algorithm ...
0
votes
0
answers
52
views
Designing a Turing machine (TM) to multiply a unary number by 2
Now, I have assumed the unary number to be 1.
and my doubts are
Do you design this machine similar to normal unary multiplication assuming that the constant 2 (11) is always present in the input tape?...
1
vote
0
answers
36
views
Find maximum sized rectangle on a plane
I'm given a rectangular plane with width, height and a set of rectangles defined by left, <...
- 31
0
votes
0
answers
12
views
Flowgarithm for common child program for a beginner (without pointers)
I'm a first year BCA student. Can you help me with flowgarithm of the common child problem (LCS) without pointers
0
votes
1
answer
19
views
What is the name of the diagram used in JSON spec for representing a context-free language?
If you go to the JSON spec page : https://www.json.org/json-en.html, then you'll see the language represented by some diagrams showing graphically what the language looks like. I wondered, does this ...
- 101
-1
votes
1
answer
26
views
1
vote
1
answer
17
views
Max flow, min cost with upper and lower bounds
:)
I am trying to implement an algorithm that fairly distributes people into groups, given their ranking of those groups, while also taking into account their preference for partners.
I have modeled ...
- 11
-1
votes
0
answers
12
views
Need Clarification on Storage Media Statements - Seeking Help
I am currently working on a set of questions related to storage media, and I've come across a statement that seems a bit confusing to me. The question is as follows:
Mark all correct statements ...
0
votes
0
answers
42
views
The second shortest path on a directed graph
The question asks to write an algorithm using Dijkstra's algorithm with time complexity of
$\Theta(|E| \log |V|)$ that find the second shortest path between s∈V and t∈V.
The farthest I managed to get ...
- 1
-1
votes
0
answers
22
views
Backpack assigment
Can you help me solve this problem. Names of items NAME, sizes SIZE and values VALUE are given. Using dynamic programming, find the optimal filling of backpacks of size M. NAME = {A, B, C, D, E}, SIZE ...
- 1
0
votes
1
answer
30
views
Determine if all the continuous subsequences of an array contain at least one unique element in O(n lgn)
Given an array of length n, how to determine if all the continuous subsequence of this array contains at least one unique element.
Any subarray array[start, end] ...
- 1
3
votes
0
answers
42
views
Shortest path in polygon from 2 points such that entire polygon is visible
Given an isothetic polygon (sides parallel to the x-axis or y-axis) and 2 points (start and end) on the boundary of the polygon,
find the shortest path traveling only in the direction of the x or y ...
0
votes
0
answers
12
views
Dynamic programming problem for minimum cost tower placement
I have an algorithmic problem in which I have a highway that is a straight line of length n and a set of unique respective costs for construction of a radio tower for each mile on the highway. I am ...
0
votes
0
answers
36
views
data flow analysis reaching definition analysis meaning
I'm trying to understand reaching definitions and I'm having hard problem wrapping it around my head with the following definition (taken from the the following paper page 114):
$B_i\;\text{be a ...
- 103
0
votes
0
answers
30
views
Two Counter word count language Nondeterministic Pushdown Automata (NPDA) problem actually Context Sensitive unless counters are multiples
Classic text (Linz, P., & Rodger, S. H. (2022). An introduction to formal languages and automata. Jones & Bartlett Learning.) describes the following language where one is to describe an ...
0
votes
0
answers
3
views
Two Counter word count language npda' problem actually Context Sensitive unless counters are multiples [duplicate]
Classic text (Linz, P., & Rodger, S. H. (2022). An introduction to formal languages and automata. Jones & Bartlett Learning.) describes the following language where one is to describe an ...
0
votes
0
answers
4
views
Two Counter word count language npda' problem actually Context Sensitive unless counters are multiples [duplicate]
Classic text (Linz, P., & Rodger, S. H. (2022). An introduction to formal languages and automata. Jones & Bartlett Learning.) describes the following language where one is to describe an ...
0
votes
1
answer
30
views
Will a FIFO buffer eventually stagnate?
Below depicts a FIFO buffer:
So the buffer is there for when the speed of data written into the FIFO buffer is faster than the data read.
But I don't understand one thing. Wouldn't eventually all the ...
- 101
-3
votes
0
answers
16
views
python django- adding a like function button [closed]
I am trying to add a like function to my blog, but I keep getting this error.
0
votes
0
answers
11
views
What are some good books for vlsi cmos design? Or some good educational software?
I'm a student trying to learn more about CMOS design, I already understand assembly and computer architecture, but VLSI is very interesting and I was wondering if you guys knew some good books/games ...
1
vote
0
answers
18
views
Approximation Algorithm for Bin packing Variant with Packing Overhead
I recently came up with this bin packing variant and was wondering, if someone has studied it before:
Given: Instance $I$ is a set of tuples $\begin{pmatrix}s_{i} \\ o_{i}\end{pmatrix}$ with $s_{i}, ...
- 11
1
vote
1
answer
39
views
(Co)-induction, fixpoints and inference systems
I'm learning about induction and co-induction. From what I know, given a set of judgments $U$ and an inference system $\Phi \subseteq \wp(U) \times U$, where $(\left\{ h_1,\dots,h_n \right\}, c) \in \...
- 13
-1
votes
0
answers
18
views
How to construct a turing machine from L= {w (a Ub)* | w = wR} [closed]
How to construct a Turing machine from L= {w (a Ub)* | w = wR} . I have to design a Turing machine in exam. help me.
-2
votes
0
answers
22
views
Maximum flow of multiples [closed]
The problem is that I'm given 3 numbers N which represents the number of nodes in my graph, M which reprensents the amount of vertexes and x which represents an amount of people. The problem is that I ...
- 1
-1
votes
0
answers
8
views
I need help plotting a 3D trajectory field for a 3x3 matrix [closed]
I'm trying to plot the trajectories of a 3x3 matrix. I can do this on the 2D plane but cannot get it to work on the 3D plane as needed for a 3x3 matrix. When I try to use
from sage.plot.streamline ...
0
votes
1
answer
59
views
Visiting all nodes of a directed graph exactly once (not dfs)
Consider a directed unweighted graph (in a adjacency matrix for example), how can I visit each node exactly once? By once I mean for example in a DFS traversal, a node can get finished and we should ...
- 35
0
votes
0
answers
35
views
Greedy Maximum Bipartite Matching
To find the maximum matching on a bipartite graph, I propose the following greedy algorithm:
At each iteration, pick an unmatched vertex with the smallest degree and match it to one of it's neighbours ...
1
vote
0
answers
19
views
Computing the centroid of an "ellipsoid slice"
I want to compute the centroid of a body of the following form:
$$
E\cap H_1\cap \cdots \cap H_T
$$
where:
$E$ is an ellipsoid in $\mathbb{R}^d$: $E = \{x = c + Bu | u^T u \leq 1\}$, where $c$ is the ...
- 5,730
3
votes
0
answers
73
views
Subset sum problem with big items
Consider the variant of the Subset Sum problem, where the input is a list of $2 m + 1$ positive integers of sum $2 S$, and the goal is to find a subset with the largest sum that is at most $S$. The ...
- 5,730
0
votes
1
answer
20
views
Variant of Bounded Subset Product
Edited Version
Consider the following decision problem:
Given $([b_1, \cdots, b_n],t)$, where $[b_1, \cdots b_n]$ is an array of natural numbers each less than $n^c$ and $t$ is a target natural number,...
- 1
1
vote
0
answers
53
views
Borůvka's step in linear time
I am trying to understand this Expected linear time MST algorithm, and I have a problem in the implementation of the Borůvka's step.
My problem is with the removal of duplicate edges between merged ...
- 12.5k
-5
votes
0
answers
17
views
DFA testing exercice ASAP please [duplicate]
I have a question :
If my word can be only AA or BB or A or B how i will write my regular expression ?
And if 0 is a par number it also may be to include ?
it is something like this : A|B|epsilon) (AA|...
0
votes
1
answer
34
views
Complexity of multiplying 3 matrices
There are algorithms that speed up matrix multiplication over the naive $n^3$ algorithm. But supposing you have 3 matrices $A$, $B$ and $C$, is there a way to compute $ABC$ that is asymptotically ...
- 101
-1
votes
1
answer
21
views
CFGs and Pushdown Automata
Is this the CFG for part (a),
S -> AxxyxxA
A -> Ax|ε
If this is the answer then this grammar would accept &...
- 1
0
votes
1
answer
26
views
What is the largest "allowed" seed for a PRNG to not give any extra power to a deterministic machine?
Suppose a polynomial time machine that has an access to a polynomially long string of bits independent on the input. On average, it's impossible to compress this string to a subpolynomially long ...
- 1,429
0
votes
0
answers
24
views
Greedy algorithm for trading cryptocurrencies with perfect price information
Assume the following hypothetic scenario:
You know the values $v_1^0, \ldots, v_n^0$ of $n$ cryptocurrencies. You know the values this currencies will have for the following $m$ days; this is, $v_0^1,...
- 181
0
votes
0
answers
7
views
Understanding atomic requests/transactions in a snooping coherence protocol
I've been reading the book "A Primer on Memory Consistency and Cache Coherency", and it contains the following paragraph:
The Atomic Requests property states that a coherence request is
...
- 111
0
votes
0
answers
40
views
Complexity of topological sorting with a special restriction
Let $G = (V, E)$ be a connected DAG (representing a circuit) with every vertex may be one of the following three types:
Input variable, with in-degree $0$ and out-degree $\geqslant 1$.
A gate, with ...
- 13
1
vote
0
answers
37
views
How do i make a 2d array as same as i possibly can with another one?
Say i have an 2d array A of nxn size, int values already given for each item.these values can be the same or different.
There's gonna be another nxn array B being input.
I can only interchange one row ...
- 11
-2
votes
2
answers
193
views
Could this novel algorithm be qualified to be published in Nature or Science
I recently designed an algorithm for single-source shortest paths in graph structures, which can limit the number of edges as Bellman-Ford while approaching the performance of SPFA. Of course, it also ...
0
votes
0
answers
56
views
Necklace Alignment Problem
We are given two cyclic $\{0,1\}$ strings $X$ and $Y$ with both length $n$, containing $k$ 0s and $n-k$ 1s. Suppose positions of 1 in $X$ are $x_0,\dots,x_{k-1}$, for $Y$ are $y_0,\dots,y_{k-1}$. We ...
- 1
-1
votes
0
answers
14
views
Clique to SAT example explanation
We are at college trying to implement the reduction of the clique problem to a SAT problem but I dont quite get the examples of the slides if someone can give me a not so technical explanation of what'...
