All Questions

31,062 questions
72 views

Can we find every 216 digit number combination? [on hold]

This question popped to my head when I watched Pi where the mathematican told the Jews "Didnt you calculate every 216 digit number allready?" So I want to find every possible 216 digit number ...
12 views

the some good languages for creating networking software [closed]

after continuously looking around for a python GUI library that allows for my software to look like a web designed landing page instead of windows XP bloatware. an example being: lance remastered. i ...
76 views

Algorithm for generating random incrementing numbers up to a limit

I'm trying to write a code to generate incremental sequences of numbers such as: 0 + 1 + 3 + 5 + 1 = 9 0 + 5 + 1 + 1 + 1 = 8 0 + 1 + 1 + 2 + 1 = 5 I have 3 ...
29 views

Can BPP be bounded around any constant other than 1/2?

A language $L$ is in BPP if there exists a randomised TM such that it outputs a correct answer with probability at least $1/2+1/p(n)$ for some polynomial $p(n)$, where $n$ is the length of the input. ...
25 views

Turing machine loop and reject example

I'm getting confused on these both. Reject the string does a stop while loop the machine goes on and on. My textbook has one example on a reject state and no physical one for loop: Assume that no ...
21 views

Multi-tape to single tape Turing Maching transition complexity

Suppose we have a k-tape Turing machine M and we wanna model it with a Single tape Turing machine N with a register. Suppose the time complexity of M is T(n): ...
43 views

Is the language L = {(a,b)* | #a * #b is an odd number} regular?

Is the following language regular? $$\{ w \in \{a, b\}^* |\ \text{the product of the number of a's and the number of b's is an odd number}\}$$ If i'm not mistaken the condition is the same as ...
25 views

Complexity of a Turing Machine when changing its alphabet to binary

I found in 'Computational Complexity: A Modern approach' Book the following statement that i dont quite understand its proof: For every f : {0, 1}∗ → {0, 1} and time-constructible T : N → N, if f ...
46 views

How do you write a diff algorithm given limited amount of RAM?

Say you have two large files (100 TB each) and only 1 MB of RAM. What's an efficient algorithm that will print the missing lines (diff)? The files don't necessarily contain duplicates. The two files ...
25 views

Alternate notation for natural numbers and their addition? [closed]

The conventional way of expressing natural numbers uses base 10 notation which according to https://matheducators.stackexchange.com/questions/4367/how-to-teach-binary-numbers-to-5th-graders, some ...
29 views

Shortest path in a incomplete graph

I know the Dijkstra algorithm to solve the "single source shortest path" problem in a graph. And I've seen people discuss solutions in a dynamic graph where edge/vertices are subject to change. ...
37 views

Assign weights to the edges in a DAG so that, for all S and T, all paths from S to T have equal weight

I have a DAG, and on each edge, I have a minimum and maximum weight. I would like to assign (or determine it's impossible to assign) exact weights to each edge so that Each edge's weight is between ...
19 views

Cross Entropy Function

I've seen two versions of the cross entropy cost function, and conflicting information about it. \begin{equation}J(\theta) = -\frac{1}{N} \sum_{n=1}^N\sum_{i=1}^C y_{ni}\log \hat{y}_{n_i} (\theta)\end{...
38 views

34 views

Time complexity of subset sum problem with reals instead?

It is well known that the conventional subset sum problem with integers is NP-complete. What if the array elements can be any real numbers and also target sum can be any real number? Is it NP-complete ...
16 views

Good Reference For Design And implementation Of Proof-Assistant

Hello I'm searching for any good review article or book about the design an implementation of a proof-assistant, something such as the Dragon book for programming language. My background is ...
27 views

Why ambiguous grammars are allowed for operator precedence parser?

I am aware of what is ambiguity, and why is it necessary to eliminate ambiguity in compilers in a certain context, but how can we allow ambiguity for operator precedence parser? Say I have a set of ...
33 views

Using pumping lemma to prove irregularity of regular language - what is my error? [duplicate]

I have a vital misunderstanding of the pumping lemma. In the following example I show an example of using it on a regular language to come to incorrect conclusions. What am I doing wrong? L={ab}, ...
24 views

time complexity of k-bubble sort [duplicate]

I'm a student. today I answered a question wrong, the question is this: Spouse we have a k-bubble sort, which means except sorting 2 elements each time, it has a magical function that can sort $k$ ...
16 views

Provide five examples from other fields that illustrate the problems associated with a reactive risk strategy [closed]

I cannot understand how to define those fields... What are the fields, can anyone plz provide five of those fields..
15 views

Partially persistent linked list data structure: would lookup of the first element at a specific version be O(|versions|) and not O(1)? [migrated]

The result by Driscoll et al 1989 states Any pointer-machine data structure with O(1) pointers to any node can be made partially persistent with O(1) ammortized multiplicative overhead and O(1) ...
57 views

divide and conquer algorithm for finding a 3-colored triangle in an undirected graph with the following properties?

In an undirected Graph G=(V,E) the vertices are colored either red, yellow or green. Furthermore there exist a way to partition the graph into two subsets so that |V1|=|V2| or |V1|=|V2|+1 where the ...
41 views

Is it possible to create a black box program where the source code is completely obfuscated? [closed]

I was wondering whether I can write a program and compile it and give the exec file to my friend. But this exec file must work as a black box. He should only be able to interact with it without ...
23 views

NL problem? $CONN$= {$〈G,k〉$ ∶$G$ is undirected graph with at least k connected components}

Consider the following decision problems: $CONN$= {$〈G,k〉$ ∶ $G$ is undirected graph with at least $k$ connected components} $E-CONN$= {$〈G,k〉$ ∶ $G$ is undirected graph with exactly $k$ connected ...
71 views

What is the height of a tree with recursion formula: $T(n) = T(n - \sqrt{n})$

I know if the time complexity of an algorithm is given with the above formula, then the algorithm works in constant time but my question is that what will be the height of the recursion tree for this ...
147 views

how to find total paths in a graph which have only one vertex common with a given path

Assume I have a undirected graph $G$ without cycles (i.e., a forest) and I am provided with pair of nodes $a$ and $b$. How can I find the total number of paths in the graph that do not share any edge ...
5 views

Regular expression program in C language which may check for matching word in a given regular expression [closed]

/I have the following recursive code but it is not working perfectly such as for Regular Expression a.b* means a must be followed by b. Can anyone suggest the amendment in this code? Thanks */ //...
I have been reading papers about the construction of this matrix in Shor's Algorithm all night. The behavior of the controlled modular multiplication matrix is described as C U_{a^{2}}(|c\rangle|y\...