# All Questions

44,851 questions
Filter by
Sorted by
Tagged with
27 views

### RSA public and private key

Alice signs messages using RSA with a public key (e,N) and a private key d. Alice chooses d in the range N power 0.25 < d < N power 0.5 What is the time needed for Alice to calculate the ...
1 vote
40 views

### What algorithm will visit each node in a graph a number of times equal to the number of paths to that node from the root?

First Few Iterations of the Algorithm We have an algorithm in which a squirrel visits the nodes of a directed graph. Our graph has two colors of edges: black and white. Initially, the graph has black ...
33 views

### What is an expression language?

Recently I came across with the package manager Nix. According to wiki: It is also the name of the tool's programming language. As I understand there is a programming language called Nix. But, ...
• 209
26 views

### Confusion about NP vs. LINSPACE

I am working through Sipser, and have come accross the following claim, "any $f(n)$ space bounded Turing machine also runs in time $2^{O(f(n))}$", which can be proven by looking at the upper ...
• 237
39 views

34 views

### Show that if a DFA accepts all words of length < 2n then it accepts any word

Is it true that if a given DFA $M = \langle Q, \Sigma, \delta, q_0, F\rangle$ with $|Q| = n$ accepts all strings $w \in \Sigma^*$ such that $|w|\leq 2n$ then it accepts any $w \in \Sigma^*$ ?
• 99
1 vote
40 views

### Optimizing placing items in containers across a path

I'm searching for the generic name of an algorithm/method that would allow me to solve this type of problem efficiently. I have a continuous line which I traverse, from one side to the other. Along ...
• 111
1 vote
69 views

### Why do we need to "allocate" an amount of space in the context of space-complexity?

In the chapter on space complexity in "Computational Complexity: A conceptual perspective" by Goldreich, it is stated (ch 5.1.2, p 146): It is tempting to say that sub-logarithmic space ...
• 3,324
14 views

### Where there is a place my requirement of summarize the program design executed ways?

Summarize the way the high level language program(eg. Java) is executed, I know there are below executed ways to design a program: ...
50 views

### How do we run programs which are bigger than RAM itself

I know that whenever click on .exe, it will be moved into RAM so cpu can execute machine code line by line. But what if .exe is bigger than RAM? for eg: I play games which take up more space than my ...
1 vote
23 views

### prove that there does not exist a Turing machine with a particular property

Prove that there does not exist a Turing machine M such that for every Turing machine K that halts on all inputs, $M$ accepts $\langle K\rangle$ if and only if $L(K)$ is infinite. The above question ...
29 views

### Efficiently count distinct in large range

I have a pubsub channel where an event is fired every time a user logs in, and I want to be able to query the unique users in a date range. Solutions I thought: Put the data in bigquery, and then use ...
• 103
1k views

### Could a compiler automatically insert memory deallocations if it were to simulate every conditional statement?

I have read this question on compile time gc and what I understand from it is that the compiler wouldn't know if a variable is referenced or not by some other object due to conditional statements (...
• 111
71 views

### Diffie-Hellman with offline attack

There is a protocol that aims to transfer a password securely between the user and the server. The protocol is based on the Diffie-Hellman method. In the protocol, p is a prime number, g is a ...
1 vote
89 views

### Algorithm to generate points uniformly at random from a ball

Consider a 2-dimensional version of generating points in the circumference of a unit radius circle, independently generate each coordinate uniformly at random from the interval [-1,1]. How to generate ...
• 11
1 vote
8 views

### How branching programs with small width are related to Turing machines with small space?

The complexity book by Arora and Barak mentions that "branching programs of constant width (reminiscent of a TM with O(1) bits of memory) seem inherently weak." I am not able to figure out ...
• 11
1 vote
61 views

### A different algorithm called the 'bubble sort'?

In Robert Lafore's book "Object Oriented Programming in C++, Fourth Edition", on page 450, he has a section on the bubble sort. The way he describes it is as follows: Here's how it works, ...
9 views

### Is there a python library for generating a mass-spring model?

Given a 3D representation like mesh or point cloud, I want to generate a mass-spring model of it. By mass-spring model I mean this. Is there a python library for doing this?
19 views

### Transition System vs State Machines

Why there is no final state for a transition system? And why do NFA and DFA have final states? The transition system may or may not have any terminal states, but NFA/DFA has at least one final state (...
50 views

### Why is $\{ w \in \Sigma^* : M_w[\epsilon]\downarrow \land |w| \leq 7\}$ decidable?

I get that the argument for this set $\{ w \in \Sigma^* : M_w[\epsilon]\downarrow \land |w| \leq 7\}$ to be decidable is that $|w|\leq7$ meaning it is a finite set and therefore it can be decided. ...
1 vote
93 views

### Comparing automata sizes given Myhill-Nerode equivalence under a function

Consider two finite languages, $L_A$ over alphabet $A$ and $L_B$ over alphabet $B$. $A$ might be the same as $B$. Since $L_A$ and $L_B$ are finite languages, there exist minimal acyclic deterministic ...
• 816