All Questions

Filter by
Sorted by
Tagged with
-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 ...
user avatar
  • 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 ...
user avatar
-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, ...
user avatar
  • 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 ...
user avatar
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 $...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ??
user avatar
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 ...
user avatar
  • 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, ...
user avatar
  • 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 ...
user avatar
  • 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?
user avatar
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 ...
user avatar
  • 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 ...
user avatar
-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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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, ...
user avatar
  • 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, ...
user avatar
  • 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 ...
user avatar
  • 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)$ ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
-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, ...
user avatar
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{...
user avatar
  • 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^*$ ?
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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: ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 (...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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, ...
user avatar
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?
user avatar
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 (...
user avatar
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. ...
user avatar
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 ...
user avatar
  • 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: $(...
user avatar
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 ...
user avatar
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 ...
user avatar
-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 ...
user avatar
  • 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: ...
user avatar
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, ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 118

15 30 50 per page