All Questions

-1
votes
1answer
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 ...
-1
votes
0answers
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 ...
1
vote
2answers
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 ...
1
vote
1answer
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. ...
0
votes
1answer
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 ...
0
votes
0answers
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): ...
2
votes
2answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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. ...
3
votes
0answers
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 ...
2
votes
0answers
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{...
2
votes
0answers
38 views

Closure under polynomial reduction

Having some trouble generalizing when a complexity class $D$ is closed under polynomial reduction. For instance, take the following examples: $\bigcup_{c \ge 1} \mathsf{DTime}(2^{cn^5})$ $\bigcup_{...
5
votes
1answer
71 views

Searching a Treasure

I was selected for a UG interview for computational natural science program and the following was one of the questions asked: "Suppose we have an $8 \times 8$ grid. Under one of the blocks, I (the ...
1
vote
2answers
50 views

How can the length of a string be $O(\log n)$?

I have just started learning about time complexities and am currently reading Logarithmic Complexity. Here's an example of a piece of code which is $O(\log n)$: ...
4
votes
2answers
42 views

Can every Turing Machine be translated into a SAT formula?

For the proof of "Cook-Levin Theorem", for a Turing Machine $M$ that accepts a language $L \in NP$ and input $x \in \{0,1\}^*$, we can create a SAT Formula, that is satisfiable if and only if $M$ ...
0
votes
0answers
41 views

On the same group data strcture

In a particular school, $n$ students are taught, and we are given a list of interrelations between students. The teacher asks the students to divide into a maximum number of groups (on his part, ...
2
votes
0answers
25 views

Distributed algorithms for finding n largest elements

It's easy to come up with a simple distributed algorithms for finding the maximum element in a set (totally ordered): Divide and conquer. There are a few publications that present algorithms for ...
1
vote
0answers
23 views

Find the m-th largest separation

The m-th largest number in a list of n numbers can be found in $O(m \log n)$ using a max-heap. This avoids sorting. Suppose I'm interested not in the actual numbers, but separation between adjacent ...
0
votes
0answers
15 views

FOLLOW of LL(1) grammar [duplicate]

Please consider following grammar: E -> P : P P -> X R R -> . P | ε X -> num Y Y -> num Y | ε I am searching FIRST/FOLLOW. First: ...
0
votes
0answers
32 views

$\Omega$-notation for insertion sort [duplicate]

I'm reading the CLRS book and there is a statement for instance, the running time of insertion sort is not $\Omega(n^2)$, since there exists an input for which insertion sort runs in $\Theta(n)$ ...
0
votes
0answers
6 views

Suffix-automaton Largest common substring of multiple strings

Can anyone help with understanding how to solve "Largest common substring of multiple strings" problem with usage of Suffix-automaton? I've found this a really good article about SA . But ...
0
votes
0answers
12 views

CODE ERROR Trying to add png file in python [closed]

Snake game by Abdul A link is provided below to see how the code works with A normal square and circle please help I want to add a png file in place of the circle https://pastebin.com/6bm2caU0 ...
0
votes
1answer
101 views

Proving NP completeness of maximal length path

I have this question to answer: For each node i in an undirected network $G = (N,E)$, let $N(i) = \{j \in N : \{i, j\} \in E\}$ denote the set of neighbors of node $i$ and let $c_e\geq0$ denote the ...
0
votes
1answer
14 views

Incentive for block creation in a private blockchain

Bitcoin miners are incentivized to produce valid blocks via a trasactional reward. But let's say I wanted to implement blockchain as part of my private data system. Who would my miner's be? I think ...
2
votes
3answers
53 views

How is functional property guaranteed in type theory when function type is defined?

I understand that functions are not defined in type theory the same way they are defined in set theory, hence functional property is not directly defined when defining function type in type theory. ...
-1
votes
0answers
11 views

When programming using command line, my files are not recognized. Why? [closed]

I'm taking a coursera python class and pretty much everything is thorough cmd. I still have't figured it out. I'll hit dir in desktop and it doesn't list my files! So if i put a program in a desktop ...
0
votes
0answers
11 views

Class timetable generation program in C#

As a "fun" project for school, I am attempting to create a timetable generation program which will automatically assign students and teachers to lessons and those lessons to one of 5 periods within a ...
4
votes
2answers
62 views

Count paths of length $n$ that a player can take

I'm writing a video game, and I'm trying to find an efficient way of calculating this. The goal is to count the number of paths of length $n$ that a character can take, where the character can move ...
1
vote
0answers
13 views

Example of a Karp reduction between problems in NP that is not a Levin reduction?

What is an example of a Karp reduction $f$ between two problems $A, B$ in $\textbf{NP}$ such that $f$ does not provide a way to transform certificates of one problem into certificates of the other? In ...
2
votes
3answers
199 views

Is time complexity more important than space complexity?

I've noticed quite a few cryptographic algorithms speak mainly of the time complexity of an algorithm. For example, with a hashing function h, find x given y = h(x). We normally speak on how long it ...
2
votes
1answer
22 views

Showing Maximum Independent Set is $NP-hard$

I've read about Maximum Independent Set problem being both $NP-hard$ and $CoNP-hard$. I know this can be shown using reduction from the corresponding Max-Clique problem, But I'm wondering - Is that ...
1
vote
0answers
8 views

Simple Question About the Nature of Supervised Learning Predictive Models in Relation to their Training Data

Would a deployed or deployment-ready (i.e., already-trained) supervised learning model have a 100% accuracy rate for predictions on the training data (if you were to run the training data through it ...
1
vote
0answers
18 views

Is there an algorithm to partition a set of points into two disjoint polytopes far away from the origin?

Suppose I have a finite point set $P = \{p_1,\ldots, p_K\} \subset \mathbb R^D$ and all $p_i \ne 0$. What I would like to do is partition $P$ into two disjoint pieces $A \cup B$ so the convex hulls $\...
0
votes
1answer
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
0
votes
2answers
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}, ...
1
vote
0answers
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$ ...
0
votes
0answers
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..
0
votes
0answers
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) ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
0
votes
2answers
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 ...
1
vote
1answer
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 ...
-1
votes
0answers
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 */ //...
0
votes
0answers
19 views

How Voronoi Tessellations and Scutoids can help in computation?

Recently I came across a computerphile video https://www.youtube.com/watch?v=FGiBHsUkVzU about the use of Voronoi Tessellations and Scutoids in computation. But the video just explains what are ...
1
vote
0answers
29 views

How is the modular multiplication matrix unitary in Shor's Algorithm?

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

15 30 50 per page