All Questions

0
votes
1answer
33 views

Implementation-level of a Turing machine that accepts a specific language

I'm trying to figure out a way to implement this kind of a Turing machine that accept the following language: $$\Sigma = \{ 0,1,2 \}, \quad\quad L(A) = \{ abc \mid a=b \land c = a^R \}$$ I was ...
-2
votes
0answers
19 views

What are the 2 algorithms that I have written represented as? [on hold]

I have been writing an algorithm to find the sum of 2 numbers. I have done some research on how algorithms can be represented. Algorithms can be represented as Flowcharts,pseudocode,structured English,...
1
vote
1answer
62 views

Pass by Value or by Reference and Impure or pure functions

Beginner question: I am teaching myself the two passing techniques: Pass by Value and Pass by Reference. Can Pass by Value change the states of an object? If yes, how? Which of the two techniques ...
0
votes
0answers
16 views

Proving the Complement of a DCFL is DCFL [duplicate]

If I Have a DCFL $L$ ( a CFL which can be recognised by a DPDA ), How do I prove that $\overline{L}$ is also a DCFL I checked my textbook for a proof but I wasn't able to understand the language. Can ...
0
votes
0answers
20 views

Hello i have a project that need me to calculate data throughput? [on hold]

This is what my project asks but i am really stacked on how to calculate the actual throughtput. The throughput measurement should be carried out for two scenarios, with and without a security ...
1
vote
2answers
41 views

Term for the tree of all paths starting from a given vertex in a graph

What is the term for the tree (or a part of the tree) of all possible paths in a graph that start from a given (source) vertex? This is the tree that is implicitly or explicitly constructed when ...
-2
votes
1answer
38 views

design a DFA for words a and b with at most 3 letters [on hold]

I was able to decipher the language but im confused how to draw its DFA $$L=\{a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,bab,bba,bbb\}$$
1
vote
0answers
16 views

Can we ignore the postcondition in the Hoare conditional rule when there is a return statement?

I'm proving the correctness of naive string matching using Hoare logic. I have the following pseudocode: ...
-2
votes
0answers
32 views

Example for which breadth first search would work more efficiently than depth first search [on hold]

Is there any scenario where breadth first search works more efficiently than depth first search?
4
votes
0answers
43 views

Finding a negative cycle in a bipartite graph

The Bellman-Ford algorithm can be used to find a negative cycle in a general graph, in time $O(|V||E|)$. Is there a faster algorithm for finding a negative cycle in a bipartite directed graph, where ...
3
votes
2answers
90 views
+50

How does the bitlength of the divisor affect the running-time complexity of division algorithms?

Wikipedia lists $O(M(n))$ as the best complexity (out of the algorithms listed) for division on two $n$-digit numbers, where $M(n)$ is the complexity of the multiplication algorithm of choice. This is ...
0
votes
0answers
12 views

Does '/boot/efi' locate in Memory as ROM [migrated]

I learned from the book Computer Science: An Overview that boot loader reside on Memory In a general-purpose computer, a program called the boot loader is perma- nently stored in the machine’s ...
0
votes
1answer
52 views

How do I prove that SPACE($n^{555}$) $\neq$ NP?

I thought about finding a language with a polynomial verificator "larger" than $n^{555}$, but then I realized it would not imply the space needed for computation is the size of the verificator.
2
votes
0answers
32 views

Decision problems with complex input validation

In an answer to a question regarding input validation in decision problems, @Apass Jack wrote It is easy to check whether a problem instance is a valid instance or not for almost all decision ...
1
vote
1answer
62 views

An algorithm to maximize the number of parallel tasks

I have a set of compute tasks I want to schedule, these tasks have dependencies and a task may not be executed until all its dependencies are executed. The problem can be represented as a directed ...
0
votes
1answer
20 views

Virtual address translation

I'm in an OS class now. I've been wrestling this problem for a while and can't convince myself of a solution. My professor is very busy and hasn't made time to help. Also, this question is from an ...
1
vote
2answers
33 views

What is the difference between Consensus and Leader Election problems?

According to this paper written by Lamport, `selecting a unique leader is equivalent to solving the consensus problem'. Based on the above quote, my question is: What is the difference between ...
0
votes
0answers
39 views

Relationship between SPACE(t(n)) and DTIME(t(n))

I'm new to complexity theory and am analyzing inclusions between complexity classes. Suppose we are given the following seven complexity classes $DTIME(n)$ $DTIME(n^2)$ $DTIME(2^n)$ $DTIME(2^{2^n})$ $...
1
vote
2answers
40 views

What is von Neumann bottleneck?

According to this Quora post, It refers to two things: A systems bottleneck, in that the bandwidth between Central Processing Units and Random-Access Memory is much lower than the speed at ...
0
votes
0answers
17 views

A lambda expression in the haskel function [closed]

This is not an exercise.It is one of the review questions. q :: (Float ,Float) -> Float -> Bool q(x,y) = \ z -> x <= z && z <=y p:: (a -> Bool) -> (a -> Bool)-> (a -> Bool) p q1 q2 = ...
1
vote
1answer
35 views

Image registration using gradient descent

I have a target image $f(x,y)$ (where $x \in [0, 250]$ and $y \in [0,300]$), and a source image $g(x,y)$ I want to align $g$ to $f$ using the transformation : $$\Psi(x,y;t_x, t_y, \theta) = \begin{...
2
votes
1answer
64 views

Reduction to a vertex cover problem-like with weighted vertices and edges

Description Let us define a new problem with an instance $I = (G = (V, E), K, L)$, whereas: $G$ is an undirected graph $K \le |V|$ $L > 0$ is the maximum limit Each vertex $v \in V$ has a weight $...
4
votes
1answer
70 views

Maximum subarray of bounded length

I'm giving an array $A[0..n-1]$ and an integer $w$. The goal is to find indices $i,j$ that maximize $$\Phi(i,j) = A[i] + A[i+1] + \dots + A[j-1],$$ subject to the requirements that $0 \le i \le j \...
5
votes
2answers
535 views

Do I need to consider instance restrictions when showing a language is in P?

I have already shown that 3-colorable for an unrestricted graph is in NP, but I was thinking about the similar language defined as the set of all acyclic $G$, where $G$ such that $G$ is 3-colorable. ...
2
votes
0answers
52 views

Is it a bad idea to require a correctness proof as part of a computable real number?

At 30:42 of Norman Wildberger's Difficulties with real numbers as infinite decimals (II) lecture, he raises the question whether "certificates of boundedness" (of the runtime of the algorithm to ...
1
vote
1answer
169 views

Are regular expressions a*a and aa* equivalent?

Let $\Sigma = \{a, b\}$ an alphabet. Are the regular expressions $a^*a$ and $aa^*$ over $\Sigma$ equivalent? Even though concatenation is not commutative, in this case it seems like the statement is ...
0
votes
0answers
15 views

Maximum response filter

I am new to the field of Image processing. I recently came across MR8 filter and it is available in this link but I could not find well written expressions for mathematical treatment of the filter. ...
-1
votes
0answers
15 views

Please give the answer of a regular expression for a string whose length is exactly two. a& b are the two symbols [closed]

Question based on regular expression Regular expression for a string whose length is exactly two. a and b are the two symbols
2
votes
1answer
40 views

Image convolution - image darkens

I'm using kernel convolution in python to blur an image, but in addition to blurring it also turns the image darker. Could someone explain why it happens? ...
1
vote
1answer
39 views

what is meant by support of a filter?

what is meant by support of a filter in context of image processing? In the attached link of a short tutorial for detecting bar in an image by gabor filter,it is said that γ=1 helps in finding the ...
0
votes
0answers
9 views

Calculating p-persistent CSMA Network probability

Let's say that, in a p-persistant CSMA network one station, X, is ready to transmit data. All other stations are idle for 5 time slots after X has become ready. What is the probability that X ...
1
vote
1answer
26 views

What are the k-collections described in ch. 8 of “An Introduction to the Analysis of Algorithms” by Sedgewick

In chapter eight of "An Introduction to the Analysis of Algorithms" by Sedgewick (1996 edition) the coupon collector problem is introduced on page 425. My confusion is how to identify the k-...
1
vote
1answer
20 views

Changing probabilities to 0/1 in definition of class IP

A language $L$ belongs to $\mathbf{IP}$ if there exists $V,P$ such that for all $Q$, $w$, $$w\in L\Rightarrow Pr[V\leftrightarrow P\text{ accepts }w]\geq2/3$$ $$w\notin L\Rightarrow Pr[V\...
0
votes
0answers
40 views

if binary heap potential function is c*size(binary heap)) then insert will not take O(logn)and extract min will not take O(1) amortized time

So i want to prove that if i choose a potential function for binary heap as any constant*size of the binary heap (n is the number of nodes) then my insert will not have O(logn) amortized cost and ...
1
vote
1answer
54 views

Counting models satisfying a boolean formula

I'm trying to implement the #2-SAT algorithm from the paper "Counting Satisfying Assignments in 2-SAT and 3-SAT" (Dahllöf, Jonsson and Wahlström, Theor. Comput. Sci. 332(1–3):265–...
8
votes
2answers
137 views

Find an optimal ordering

I came across this problem and am struggling to find a way to approach it. Any thoughts would be greatly appreciated! Suppose we are given a matrix $\{-1, 0, 1\}^{n\ \times\ k} $, for example, ...
0
votes
3answers
41 views

Does increasing k in a k-way set-associative cache always lead to a better miss rate?

As far as I know a 2-way set-associative cache works better than a one-way one considerably but going to 4 and 8-way caches leads to a marginal improvement. My question is: does increasing K (going ...
0
votes
0answers
16 views

Understanding non repeatable read anomaly in databases

This paper discusses in detail ANSI isolation levels discussed in ANSI SQL standard on page 84. Paper introduces following shorthand for describing histories which contain reads, writes, commits and ...
0
votes
1answer
34 views

Generating intermediate code

I have a problem in backpatching "if-else" statements, for generating 3 address codes. The grammar rule is : S -》 if E then M1 S1 N else M2 S2 The semantic ...
1
vote
1answer
44 views

Proving correctness of the Newton's Method for finding the square root of a number

I'm trying to prove the correctness of this simple square root calculation algorithm using SPARK: ...
0
votes
0answers
36 views

Is this a valid proof for “Karp-polynomial reduction is not symmetric”?

Let $L = \emptyset$ and $L' = \{a\}$ be two languages over an arbitrary non-empty alphabet $\Sigma$, $a \in \Sigma$. $L$ can be reduced to $L'$: the reduction just transforms anything it is given ...
0
votes
0answers
6 views

Please help to convert conditional expressions to linear [duplicate]

I have an expression: if A≤X1-X2≤B, than Y=1, Otherwise Y=0 where A and B are constants, and X1, X2 are variables. Please help to convert this to linear expressions.
1
vote
2answers
69 views

Efficient data structure for storing integers in a range?

Say I'm constantly given integers from the range $[1,2^{32}]$ in a random order and have to store these so that when a duplicate arrives I can deal with it. By the end of this algorithm all $2^{32}$ ...
0
votes
0answers
20 views

SQL - Are there row and column operations in row storage SQL database

I have a very fundamental question. When one says data is stored in a table, I understand what row-store is, but are all values in a table stored in contiguous locations? If we are trying to join ...
2
votes
1answer
20 views

Name of double sided search algorithms

I modeled the function double_sided_breadth_first_search after the ideas in "improving Dijkstra" in Cormen et al, and the OCW course on algorithms. Note that I expand the smaller boundary, in an ...
1
vote
2answers
69 views

What does $O(\alpha(n))$ amortized time mean?

DELETE(S, i): Delete integer $i$ from the set $S$. if $i \notin S$, there is no effect. from a set of consectutive integers like $S = \{1,2,3,5,6\}$ Provide a data structure and an algorithm for ...
1
vote
1answer
8 views

Help with understanding why we need an expectation in the loss

I am reading the paper SV2P - Stochastic Varaiational Video Prediction (https://arxiv.org/abs/1710.11252). In it the authors use the loss shown in the image: Why do we need expectation in the ...
0
votes
1answer
41 views

Distance function such that we visit every “color region” once [on hold]

Consider the following image: Starting at (0,0) top left, the objective is to find a dijikistra path to the bottom right. We must go through each color exactly once, and once we go outside a color, ...
3
votes
1answer
82 views

Constructing a minimum spanning tree from an all-shortest path graph?

Given an $n \times n$ shortest path distance matrix $D$. And a complete graph $G(D)$ on $n$ nodes, where edge $(i, j)$ has weight $D_{ij}$. Furthermore, the distance matrix $D$ is computed for a ...
1
vote
2answers
24 views

Random access memory and data

What kind of data is stored in the RAM when it is fresh out of manufacture? Apart from certain basic instructions (if yes, what are they), are there numbers stored as well or are most of the memory ...

15 30 50 per page