# All Questions

29,681 questions
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 ...
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,...
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 ...
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 ...
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 ...
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 ...
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\}$$
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: ...
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?
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 ...
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 ...
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 ...
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.
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 ...
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 ...
20 views

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 ...
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 ...