All Questions

0
votes
0answers
24 views

Probabilistic r-way cut set algorithm

I am reading Probability and Computing, by Mitzenmacher and Upfal, and the exercise 1.24 asks for a generalized algorithm for finding the cut-set of a Graph. In this generalized version, instead of ...
-2
votes
0answers
11 views

How can I build a web page with web mining my artificial intelligence? [on hold]

I would like to build a webpage which use the web-mining but for cryptocurrency mining but also my artificial intelligence training in the web page background. Can we do this? How can I do?
-1
votes
0answers
17 views

Could Web 3.0 exist without cloud and vice-versa? [on hold]

I would want to know if could web 3.0 exist without cloud and vice-versa? Would I want to know also why? and some examples. Thank you.
0
votes
0answers
18 views

Random Forest - Conditional Permutation Importance

I've been looking for the most unbiased algorithm to find out the feature importances in random forests if there are correlations among the input features. Besides the most commonly preferred ...
0
votes
0answers
38 views

Inductive proof on Quicksort with Explicit Stacking

Prove by induction that if Quicksort with Explicit Stacking is modified so that the end-points of the larger sublist are stacked, and the other sublist is sorted first, then the maximum stack size is $...
0
votes
1answer
24 views

Problems in $\textbf{DSPACE}(\log^2 n)$

Let some problem $P$ is in $\textbf{DSPACE}(\log^2 n)$ and $Q$ is a problem in $\textbf{DSPACE}(\log n)$. I can claim that $P$ is polynomial time solvable as number of turing machine configurations ...
0
votes
2answers
48 views

proving big theta [duplicate]

How would I tackle this equation? $$10n^3 +3n = \Theta(n^3)$$ I know I have to solve Big $O$ and Big $\Omega$ but have no idea how to do this. I got as far as $$10n^3+3n \leq c_1n^3$$ $$0 \leq ...
7
votes
2answers
438 views

Find a point shared by maximum segments

Given: $N$ segments (arrays) of ordered integers, integers could be from $-K$ to $K$. Example: ...
2
votes
0answers
29 views

Check if a matrix over finite fields is superregular

Is there any practical, efficient algorithm to check if a matrix over $\mathbf{F}_{p^n}$ is superregular? It need not be theoretically polynomial, just roughly be implementable for $n=32$ and for ...
0
votes
0answers
35 views

Number of ways in which you can traverse N meters by doing jumps of 1,2,3,4 or 5 meter length [on hold]

I am sorry if this is not the right platform to ask this question. I have searched for a solution for the past two days and haven't been able to find it. The problem is as follows: Design an ...
0
votes
0answers
36 views

RAM and Turing machines: time complexity of simulation

My RAM machine is very simple: it has $k$ tapes, an input tape and one special control tape it has an infinite memory (array called $A$) which can be accessed randomly the control tape is read ...
3
votes
2answers
47 views

Enumerate over all halting Turing Machines?

I understand that it is possible to enumerate over all Turing Machines. My understanding of how this works is by fixing an encoding of natural numbers to TM descriptions, and then enumerating the ...
0
votes
0answers
22 views

Converting a decimal to IEEE754 32-bit binary number

Convert 0.625 to IEEE754 32-bit binary number. 0.625 x 2 = 1.250 0.250 x 2 = 0.500 0.500 x 2 = 1.000 So, ...
1
vote
1answer
40 views

What is a search problem?

I'm looking for a formal and broad definition. Intuitively, I would say that a problem where various checks have to be done is a search problem. Is this the only criteria? How can we know that a ...
1
vote
1answer
75 views

Finding the largest possible area covered by M rectangle under a given histogram

Finding the largest rectangular area possible in a given histogram is a well-known problem and have linear solution. I have a similar but different problem. In my problem, we have $M$ rectangles ...
0
votes
1answer
41 views

Why isn't it necessary to store an integer part of significant in IEEE754 floating point notation?

We see that there is a sign, exponent, and mantissa part for the notation. But, there is no location for the significant bit. Why isn't it necessary to store an integer part of significant in IEEE754 ...
1
vote
1answer
37 views

Polynomial Time reducible explanation

Have a set of examples given to me, but I'm pretty sure they're all wrong. Can someone verify that my understanding of them is correct? If set $Y$ can be solved in $O(2^n)$ and $Y \leq_p X$ then $X ...
1
vote
0answers
24 views

Variable Capturing With Repetition of Variable Name

I am very confused as to which variables are captured by which λ in the example below: (λa.λb.(λa.a)aba)(ab) I am new to lambda calculus and the repetition of ...
1
vote
1answer
22 views

A tree edge $uv$ with $u$ as $v$’s parent is a cut edge if and only if there are no edges in $v$’s subtree that goes to $u$ or higher

Referring to these notes regarding DFS - Click Here They refer to the following claim that follows Definition 0.2. as observation: A tree edge $uv$ with $u$ as $v$’s parent is a cut edge if and ...
0
votes
1answer
32 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
15 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
17 views

Hello i have a project that need me to calculate data throughput?

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
39 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
37 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 ...
2
votes
2answers
64 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
51 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
61 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
38 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
39 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
16 views

A lambda expression in the haskel function [on hold]

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
62 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
531 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
167 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
14 views

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

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
38 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
2answers
37 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
8 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 ...

15 30 50 per page