All Questions

Filter by
Sorted by
Tagged with
-4
votes
1answer
28 views

Proving correctness of Polynomial reduction

Given a problem A is NP-Hard and A ≤𝑝 B, is there a way to prove that B is also NP-Hard?
-1
votes
0answers
32 views

Can a machine that, given infinite space, functions as a non deterministic turing machine actually exist in the real world?

I am a novice when it comes to computer science. But I know that traditional quantum computers are not non deterministic Turing machines. But it seems to me that the principles of quantum mechanics ...
0
votes
1answer
81 views

Vertex Cover with minimum degree 1

In Special Vertex Cover, we are given an undirected graph $G$, and an integer $k\in \mathbb{N_0}$. The objective is to decide whether there exists a vertex cover $S$ of $G$ of size at most $k$ such ...
0
votes
0answers
19 views

Is there any problems with equating Turing Machines with Algorithms and Language with Problems?

In a lot of the online explanation of complexity theory, the author proposes the following. "The definition associated with complexity theory (e.g., definition of NP) is phrased in terms of ...
0
votes
0answers
13 views

Relation between time complexity and conditional statement [closed]

I need examples for the types of time complexity for conditional statement
-1
votes
0answers
18 views

Control Flow Graph - How to represent returns in code

Consider the following program int someCode1(int x){ if (x < 0) return 0; else return x; Last Statement;} Last statement could be either "printf(...
0
votes
2answers
34 views

How to solve $T(n) = T(27n/9) + n^3$ with substitution method

I'm trying to solve this recurrence with the substitution method. My guess is $O(n^3)$. These are some steps: $$T(n) \leq cn^3 \\ T(n) \leq 27cn^3+n^3$$ How can I continue?
2
votes
1answer
36 views

Prove $\text{CorrectSuccintSolver} \in \mathbf{coNP}$

Define the following languages: $$ \text{SUCC-CVAL}=\{(S,x,i) : \substack{S \text{ is a succint representation for circuit } C \\ \text{ and } C_i(x)=1 \text{ where } C_i \text{ is the i'th gate in }...
1
vote
1answer
30 views

Which part of the CPU is responsible for executing instructions

I was reading about the machine cycle. Everything was clear until I started with the execution of instructions. I know how an ALU and a CU work. I'm also aware of the process of fetching and decoding. ...
1
vote
0answers
12 views

(Branchless) Bitonic Sorting Network for a Set of Floating Point Numbers

In the past I've implemented a branchless Bitonic Sorting Network on a gpu using CUDA, for integers. I am facing a related problem: In my Order Independent Transparency implementation, I would like to ...
1
vote
1answer
49 views

There are n cities and m possible bidirectional roads and k temple. build roads with minimum cost such that each city has access to at least 1 temple

There are n cities and m possible roads and k temples. The cost of each road is given. Build ...
1
vote
2answers
54 views

How was swapping program born?

Code: a=10 b=5 temp=a a=b b=temp I am studying Python and I stumbled upon the classic program: The Swapping Program. It is simple: ...
0
votes
1answer
23 views

Turing machine accepting square

I'm trying to figure out following assignment and I could use your help, because I'm stuck. Task: Construct a Turing machine accepting words in format $1^k$, where $k=n^2$, $n$ being an integer. ...
2
votes
0answers
76 views

Is it NP-hard to find different roots of different matrices simultaneously?

Consider the following problem: input: pairwise distinct natural numbers $k_1,\dots,k_m$ that are all $\leq n$, and matrices $A_1,\dots,A_m \in \Bbb Q^{n \times n}$ where $m \leq n$. output: a ...
0
votes
1answer
26 views

Are there complexity classes so that RE ⊂ C ⊂ ALL?

If so what are they? These are Computational Complexity Classes that are not in RE but are in ALL. What would a problem in one of these classes look like? Would any of these problems be decidable?
1
vote
1answer
26 views

How can vector angle comparison between lattice points be done without using floating-points? (Convex Hull)

Let's say I have a point $(x_0, y_0)$, and some other points $(x_1, y_1), (x_2, y_2) ... (x_n, y_n)$, such that all of them are lattice points; all have integer coordinates. Let's further assume that ...
1
vote
1answer
44 views

Why does the CwF definition require a set of types under a context rather than a class of types?

In "Syntax and Semantics of Dependent Types" at the top of page 24, Martin Hoffman describes $\mathit{Ty}_{\mathcal C}(\Gamma)$ as the collection of semantic types under context $\Gamma$. It ...
-3
votes
0answers
28 views

Store password without hashing

There is a way to store password in a database without using hash and for preventing online brute-force?
1
vote
1answer
25 views

Finding time complexity $T(n) = 2^n T(n/2) + n^n$

I am applying substitution method to find the time complexity of the following recurrence relation. But I am having difficulty solving it past a certain point. $$T(n) = 2^n T(n/2) + n^n$$ After ...
0
votes
0answers
17 views

Learn BASIC with the Dinosaurs

In the mid-90's I came across a book in my local public library, in France. The title was something like "Apprends le BASIC avec les dinosaures" ("Learn basic with the dinosaurs") ...
0
votes
0answers
35 views

Is there a static type system (implemented or not) that can detect ignored parameters and re-type them to increase generality?

I came across this question while playing with the SKI combinators. (Skip to the bottom for the question, if you don't care about the motivation.) You can implement the combinators in Haskell as ...
1
vote
0answers
9 views

What datastructure to query nearest neighbor with constraint on parameters

I have about 200'000 data points distributed on the unit-sphere. Aside of each point's location on the unit-sphere, it has also assigned a width and height. I can perform nearest-neighbor queries by ...
1
vote
1answer
43 views

What is the big-$O$ notation of a summation of logs where the arguments add to $n$?

For: $$\sum^{k}_{i=1} \log(x_i)$$ where: $$\sum^{k}_{i=1} x_i = n$$ Is there any big-$O$ result in terms of $n$ ? I found this, but is not what I'm looking for.
1
vote
0answers
59 views

Maximum money that can be made

Came across the following question. All the answers provided there have used brute force, more or less. My hunch was that it could be solved using dynamic programming or perhaps, network flow ...
1
vote
1answer
18 views

Creating an algorithm which utilizes an already known optimal solution to max matching

Assume that there is a maximal matching of size k in an bipartite graph, G=(U,V,E). I now want to utilize this maximal matching in order to find a maximal matching in the bipartite graph where we add ...
0
votes
0answers
21 views

Algorithm for dividing a polygon into rectangles?

I have a polygon as a set of coordinates (fex [(0,0), (1,0), etc.). I'd like to find a way to divide this into as few rectangles as possible. The background for this is that I wish to have a user ...
0
votes
1answer
20 views

Algorithm to compute a div d and a mod d

I wanted to ask here a question about a simple algoirhtm to compute a div d and a mod d. My doubt specifically depend on ...
1
vote
2answers
50 views

Prove my algorithm that solves ABC String problem in Codeforces is correct

Here's the statements of problem A, "ABC String" in Educational Codeforces Round 105 (Rated for Div. 2) You are given a string a, consisting of n characters, n is even. For each i from 1 to ...
3
votes
0answers
64 views

Deciding whether a given flow is unique in $O(\lvert V \rvert + \lvert E \rvert)$ time

I am stuck with the following exercise: Is it possible to decide whether a given flow $f$ is a unique mamimum flow in $O(\lvert V \rvert + \lvert E \rvert)$ time? I am not sure that this is possible....
1
vote
0answers
12 views

Are there any references for this theorem of Lercher?

Let $\Delta = \lambda x.(x)x$ and consider $\Omega = (\Delta)\Delta$. Then $\Omega$ is exactly the only $\lambda$-term of the form $(\lambda x.t)v$ such that $(\lambda x.t)v=t\{v\ /\ x\}$. Does ...
1
vote
1answer
24 views

Confusion about whats being processed in a quantum computer

Please correct me if im wrong but this is how I think quantum computers work. Say we have a q-bit. The q-bit is put through a quantum gate to put it into a superposition and manipulate its ...
0
votes
0answers
20 views

Shallow Binding with static scope, is it possible?

I'm new in programming, I'm currently studying programming languages. I'm trying to implement Shallow Binding with static scope, starting from an abstract syntax (producing a programming language ...
0
votes
0answers
20 views

Partition a graph into subgraphs such that a partition contains up to X number of a particular node type

I have a DAG graph which contains two types of nodes, A and B. I am looking for a graph partitioning algorithm that can partition a graph in sub-graphs such that each sub-graph contains up to X number ...
-3
votes
0answers
10 views

Finding out the language generated by a context-free grammar

how can i find out the language that accepted by this cfg : S -> A B | B C A -> B A | x B -> C C | y C -> A D | x D -> y
0
votes
1answer
21 views

Why does python's threading library use OS level threads when it can't achieve parallelism?

I was surprised to hear that the threading module from python uses OS level threads. From what I know, OS level threads are more expensive (but can achieve parallelism) meanwhile green threads are ...
0
votes
1answer
45 views

How to reduce clique to Hamiltonian cycle in an undirected graph?

Recently, I studied how to prove a problem is NP-complete. From the book Introduction to Algorithms (CLRS, 3rd edition), there is an example of reducing vertex cover to Hamiltonian cycle. I believe ...
0
votes
1answer
40 views

Lower bound on computing $x^n$

I know that we can compute $x^n$ in $\log n$. Are there any lower bound for computing $x^n$?
1
vote
1answer
34 views

Finishing Time in DFS, is that necessary?

According to DFS algorithm for graph traversing: ...
1
vote
1answer
128 views

Stuck on a possible greedy problem

I am currently dealing with a problem that I believe to be a Greedy releated problem and I'm trying to find some similar problems in order to solve it. I would like to have some hints or resources to ...
1
vote
1answer
32 views

Efficient Way To Compute Points Where Convolution Equals Zero

I want to model the following procedure. Given a shape $L\subseteq\mathbf{R}^2$ (imagine e.g. a letter) and another (could be convex if it makes life easier) shape $K\subseteq\mathbf{R}^2$, I want ...
0
votes
1answer
30 views

Assignment/Scheduling Problem while Minimizing Sum of Pairwise Abs(Difference) [closed]

This is an attempt at solving a scheduling problem. The goal would be to run it a number of times in sequence to get a weekly schedule for a sports league defined as follows: There are 48 ...
0
votes
1answer
31 views

Reduce subset sum to simple path

I have a similar question as this post:Given a complete, weighted and undirected graph $G$, complexity of finding a path with a specific cost My question: Given a weighted and directed graph $G$, it ...
1
vote
2answers
31 views

Resolving a dependency graph with insufficient resources to store all states

A common way to resolve a dependency graph is to compute an execution order, and then execute each stage in turn - storing and fetching the resources as necessary. In this example, when executing ...
1
vote
1answer
43 views

Is the language containing Turing machine $(M_1, M_2)$ such that $L(M_1) \cup L(M_2) = \Sigma^*$ decidable?

We are given two Turing machines $M_1$ and $M_2$ and we wish to decide whether the union of the language $L(M_1)$ accepted by $M_1$ with the language $L(M_2)$ accepted by $M_2$ coincides with $\Sigma^...
1
vote
1answer
55 views

Algorithm to find shortest distance from source to all other vertices of graph in O(m)?

My question is for (c), as I struggle to find an algorithm that can do this in O(m) time.
1
vote
0answers
52 views

Is there a complexity measure on regular grammars connected to the descriptional complexity of the DFAs?

This question is directed at DFAs/NFAs and regular languages and regular grammars. Define the "descriptional complexity" of a language as the size complexity of the family of DFAs that ...
0
votes
0answers
11 views

Arranging rectangular textures in square texture atlas and optimize sub texture proximity

I have a mesh consisting of about 100'000 - 200'000 quads. Each quad has a rectangular texture. I'm packing these rectangular textures into a power-of-two atlas. My packing algorithm currently works ...
5
votes
1answer
98 views

discrete optimization problem with a matrix inverse

I'm trying to solve this discrete optimization problem:$\newcommand{\I}{\mathcal{I}}\newcommand{\R}{\mathbb{R}}$ $$\max_{|\I| \le k} f(\I) \qquad\text{where}\; f(\I) :=x_{\I}^{\top} (\Sigma_{\I})^{-1} ...
0
votes
0answers
29 views

How do right contexts work in context-sensitive L-Systems?

I am working on an implementation of context-sensitive 2-L systems as described in The Algorithmic Beauty of Plants by Aristid Lindenmayer, and am in need of clarification regarding context matching ...
1
vote
1answer
21 views

Histogram representation of a database

I'm reading though The Algorithmic Foundations of Differential Privacy and the authors define a database in a mathematically convenient way. Unfortunately I'm a little confused about what the ...

15 30 50 per page