All Questions
44,851
questions
-4
votes
0
answers
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
1
vote
1
answer
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 ...
- 149
-1
votes
0
answers
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
0
votes
1
answer
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
0
votes
1
answer
39
views
Tiling a simple polygon with hexagons
Let $T$ be a hexagonal tiling of the plane and assume we are given a simple polygon $P$ (we define $P$ as the union of the points on its boundary and its interior). The task is to find the subset of $...
- 1
0
votes
0
answers
25
views
Persona matching algorithm
I have a project to match two groups of people. Under insurance, if the initial sales agent leaves the insurer, their customers will become so-called “orphan customers”. I've given a big data set ...
- 1
5
votes
0
answers
98
views
Prove: Self-organizing list that uses Move-to-Front is 2-Competitive
Preparing for my finals in my "advances algorithms" course. Usually there is a question to prove one of the theorems that was given over the course. I'm currently trying to write a full ...
- 209
0
votes
1
answer
44
views
Any ideas for Parallel Computing Project?
I have to make an application as my Parallel Computing university course project.
The application should make use of parallel processing. Any ideas or examples for these kinds of applications ??
3
votes
1
answer
34
views
Algorithm for maximum non-crossing edge set in bipartite graph with a fixed permutation
I'm trying to identify an algorithm to solve this computational problem
Input:
Bipartite graph (V, W, E), with E ⊆ V×W
A fixed ...
- 53
1
vote
0
answers
21
views
Are there systems in computer science where we have several logic systems working all at once and without isolation?
Are there systems in computer science where we have several logic systems working all at once and without isolation? I am thinking there are system where subsystem A uses Paraconsistent logic, ...
- 111
0
votes
0
answers
8
views
Reference/notes for introduction to (von Neumann) architecture
I am interested in understanding what we mean by a von Neumann architecture and need something at a very introductory level. Does anyone know of any good and readable references or notes that will ...
- 101
0
votes
0
answers
23
views
Black Box Optimization
I want to find the maximum possible value of an unknown function on a rectangle. What is the optimal method of doing this? Do I need to use simulated annealing?
- 1
0
votes
0
answers
16
views
Give examples of data structure usage which can be used and cannot be used in amortized analysis
Preparing for my finals in my "advance algorithms" course. In one of the previous exams, there was the following question:
Let there be some arbitrary data structure (it is not known ...
- 209
0
votes
0
answers
19
views
Оrder-preserving hash function for indexes of sparce multidimensional array?
There is a sparce multidimensional array, I need a hash function that maps index tuples into integers preserving their order. Obviously such hash function has to be perfect but not minimal.
This is ...
- 211
-1
votes
0
answers
15
views
Is there a thing called Non-Persistent Parallel Vs Non-Persistent Serial HTTP connections?
This sound weird. They're vaguely described in internet resources.
Few of the descriptions.
Here we've a website that contains 2 objects that need to be downloaded.
Non-persistent and parallel:
TCP 3 ...
- 1
0
votes
0
answers
14
views
is the solution to the following Turing program in the Turing machine correct?
The following graph represents a Turing machine:
The alphabet consists of 0 and 1, the blank symbol is _ . Start and end node are not shown in order to preserve the symmetry of the picture. The start ...
1
vote
0
answers
19
views
What does it mean to have the processor ignore interrupt request line?
I was reading a textbook on COA, it says
If the processor is going to ignore the interrupt request line till the execution of the first instruction of the ISR, how will it know which device to ...
- 11
1
vote
0
answers
30
views
Minimizing operations to reach a set of goal stack states
I'm trying to sort the elements of a set of "goal" stacks to minimize the number of pushes/pops to reach each state. The inputs and outputs can be some other structure rather than stacks, ...
- 11
1
vote
1
answer
34
views
Are there adaptive algorithms/data structures for sparse and non sparse vectors?
A sparse 1D array of integers is commonly encoded as pairs of [index, value], which consumes 2 memory spots per value.
A dense 1D array is commonly encoded as a linear array of values [value1, value2, ...
- 131
2
votes
0
answers
66
views
Is there a way to parallelise find and inserts for a binary search tree?
Background: I'm working on a data structure benchmark tool to benchmark insert and search time and I am trying to improve my own implementation of a BST to support parallelism.
I have implemented a ...
- 129
2
votes
1
answer
82
views
Find if a given number must be in a set that is closed under gcd and lcm with some given elements
Source: https://oj.vnoi.info/problem/cryptkey (problem statements are in Vietnamese, so here it is translated).
There is a set $S$ of positive integers. If $A$ and $B$ are in $S$, then $\gcd(A, B)$ ...
0
votes
1
answer
60
views
Page fault question
How many page faults are there in the following accesses of pages in case of FIFO mechanism where page frame size is 8?
$$11,21,23,53,8,7,10,3,3,38,3,37,7$$
Soln: This question appeared in one of my ...
- 127
1
vote
1
answer
79
views
Are really only ~1% of the physical CPU space used for computing
In a Talk by Herb Sutter C++ and Beyond 2012: Herb Sutter - atomic Weapons 1 of 2 at 46:30 the point is made that only around 15% of the physical space (or the transistors) on a CPU do actual ...
- 13
-1
votes
1
answer
28
views
Does a minimum spanning tree necessarily provide the lowest cost path between any 2 nodes?
If I'm given a minimum spanning tree, my understanding is that it is a structure that connects all nodes to each other through some path, and that the overall weight of the tree is smallest. However, ...
- 125
0
votes
0
answers
33
views
How to read and interpret these expressions?
I am reading a research paper in which following equation is given:
$\underset{\small{X}\\\text{s.t}\sum_{(i,k)\in \mathcal{A}}x_{ik}=1, \forall i\in \mathcal{M}}{\operatorname{max}} u$
where $\small{...
- 1
-1
votes
1
answer
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
0
answers
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
1
answer
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
-3
votes
0
answers
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:
...
- 95
0
votes
2
answers
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
1
answer
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 ...
- 279
0
votes
1
answer
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
0
votes
5
answers
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
0
votes
0
answers
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
1
vote
2
answers
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
0
answers
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
1
answer
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, ...
- 121
0
votes
0
answers
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?
0
votes
1
answer
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 (...
0
votes
2
answers
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. ...
- 3
1
vote
1
answer
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
0
votes
2
answers
31
views
Regex for string does not contain the substring "110"
Can anyone help me figure out the error in my approach to this problem from Sipser 1.18 (1.6f)?
Write a regular expression for the language L = {w | w does not contain 110}
So, the answer I get is: $(...
- 3
0
votes
0
answers
56
views
Question about complexity of two topics in programming language theory
I am a student who is currently finishing second year of university mathematics. This summer I have to choose a topic for my diploma. Because I am particularly interested in computer science I am ...
- 203
7
votes
1
answer
271
views
Are there superexponential NP-complete problems?
Are there any NP-complete problems where the fastest known algorithm solves the problem in superexponential time (like $O(n!)$ time)? Every NP-complete problem that I am aware of has fastest known ...
- 237
-1
votes
0
answers
49
views
P vs NP Proof Strategy
Let's assume P!=NP. There are 3 barriers to P vs NP, I haven't gone through them, hence I ask if barriers cover the following case:
Can a "fundamental" property (theorem) Z about Turing ...
- 133
0
votes
0
answers
22
views
Is this A* pseudocode taking the condition of admisible ad consistent heuristic function hypothesis for granted?
This is the pseudocode for A* from wiki:
...
0
votes
3
answers
43
views
Algorithm with amortized time complexity
While I understand the process of considering/observing an algorithm and finding an average time, necessary to perform an operation that happens in this algorithm, I still cannot quite gasp the idea, ...
- 173
-1
votes
0
answers
70
views
How to find parallel efficiency for word count algorithm?
There're not a lot of books and explanations around this example topic, so I thought asking here would be appropriate for future learners including me as well.
Background:
Problem:
Consider a very ...
0
votes
0
answers
61
views
Using topological sort to find inconsistencies represented by cycles in directed graphs
Consider the following scenario.
Let $x_1,...,x_n$ be a group of cars that all drive from some point A to some point B. Each car starts driving in index order. i.e. $x_1$ starts driving strictly ...
3
votes
0
answers
36
views
Can fine-grained hardness be proved directly from classical hardness (e.g., $\sf P \neq NP$) in some way?
I have just learnt about some typical result of fine-grained hardness in 15-455 by Prof Ryan: CNF-SETH implies ${\sf DIAMETER} \notin {\sf TIME}(mn^{1-\epsilon})$. (Here DIAMETER stands for the graph ...
- 118