# All Questions

42,733 questions
Filter by
Sorted by
Tagged with
76 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 ...
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 ...
13 views

### Relation between time complexity and conditional statement [closed]

I need examples for the types of time complexity for conditional statement
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(...
32 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?
32 views

56 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 ...
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 ...
17 views

### What's the big O notation of this function and can you please explain why?

void RandIntArray(int arr[], int n) { int i, first, second, temp; ...
20 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 ...
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 ...
47 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 ...
61 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....
11 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 ...
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 ...
19 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 ...
19 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 ...
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
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 ...
43 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 ...
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$?
33 views

### Finishing Time in DFS, is that necessary?

According to DFS algorithm for graph traversing: ...
108 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 ...
31 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 ...
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 ...
27 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 ...
25 views

### writ the code for the following using python [closed]

help! I tried to do it but I can't seem to get it right can someone help out? we are supposed to use python and create a clock with the following variables.
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 ...
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^...
53 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.