All Questions

Filter by
Sorted by
Tagged with
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.
Shahed al mamun's user avatar
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 ...
Grandma Kisses's user avatar
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 ...
rus9384's user avatar
  • 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 \...
Yuirike's user avatar
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 ...
Benjohn's user avatar
  • 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 ...
Josh's user avatar
  • 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 ...
Yarin's user avatar
  • 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 ...
Sooraj S's user avatar
  • 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 ...
Robin Petr's user avatar
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?...
Saeba Ryo's user avatar
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, <...
popcorn's user avatar
  • 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
Anandhakrishnan's user avatar
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 ...
hl037_'s user avatar
  • 101
-1 votes
1 answer
26 views

What is a real life analogy of busy waiting by process "i" when "turn=i"?

...
barnyard9's user avatar
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 ...
Lucy Kalwa's user avatar
-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 ...
cricket900's user avatar
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 ...
Daniel's user avatar
  • 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 ...
mmartiss's user avatar
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] ...
patayala's user avatar
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 ...
swastik sarkar's user avatar
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 ...
Izzy Handkammer's user avatar
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 ...
Jorayen's user avatar
  • 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 ...
John Daniels's user avatar
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 ...
John Daniels's user avatar
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 ...
John Daniels's user avatar
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 ...
cm64's user avatar
  • 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.
african_geek's user avatar
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 ...
1grungler1swag's user avatar
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}, ...
blackdra_gon's user avatar
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 \...
dalz's user avatar
  • 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.
Phone Myint Zaw's user avatar
-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 ...
Faz's user avatar
  • 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 ...
user164686's user avatar
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 ...
shh's user avatar
  • 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 ...
eeeeellllll's user avatar
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 ...
Erel Segal-Halevi's user avatar
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 ...
Erel Segal-Halevi's user avatar
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,...
adelta's user avatar
  • 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 ...
Nathaniel's user avatar
  • 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|...
Duarte Grilo's user avatar
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 ...
user34722's user avatar
  • 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 &...
Don senu's user avatar
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 ...
rus9384's user avatar
  • 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,...
lafinur's user avatar
  • 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 ...
eof's user avatar
  • 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 ...
user779130's user avatar
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 ...
HelpmePlease's user avatar
-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 ...
Shawxing Kwok's user avatar
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 ...
Fireond's user avatar
-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'...
user164639's user avatar

15 30 50 per page