All Questions

7,643 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
70 views

What will be the computational complexity of a system with two pipelined algorithms?

A system consists of two separate algorithms (operated in pipeline). Algorithm#1 is iterated m times and has a time complexity ...
84 views

Counting (enumerating) minimal solutions of a dual horn formula

Is there an efficient algorithm ("does not necessarily have to be a polynomial time algorithm") to compute all "minimal" solutions for a Dual Horn formula (conjunction of clauses where each clause ...
82 views

Show that a problem belongs to NP

A logistics company has two trucks and has to deliver some packages to some addresses. The manager has to create a plan for every driver. Input Data: A set of V locations, an array d[v,u] for every ...
677 views

On if then condition in linear programming?

I have variables $a,b\in\mathbb R$ and if $a>1$ I want $b=1$ or else $b=0$. Can this be encoded by linear programming (no integer variables)? Even $b<0.5$ and $b>0.5$ is ok.
608 views

Applying a Chernoff bound with Only an Upper Bound of the Expectation

First, I am aware at least one or two similar questions have already been asked on stack exchange, but I've gone through the answers they got and didn't find one that was satisfactory for my case. The ...
24 views

Count points on same distance from set of points

Let's consider finite grid of points with size of $N$ by $M$ and set of $x$ points ($x$ is small number, up to 10, $N$ and $M$ are big numbers, up to 30000 )). Each of the $x$ points is described with ...
60 views

49 views

Regular Expression Building

I'm having trouble constructing a regular expression to meet the following criteria: $$\sum = \{0,1\}$$ $$\epsilon \in L$$ $$0 \in L$$ $$1 \in L$$ $$\forall x \in L, 110x \in L \land x01 \in L$$ ...
457 views

Number of paths of length N inside a graph

Number of different paths (length N) between vertices x and y inside of a clique Kn or a bipartite graph Kn,n? I am looking for simple paths. Therefore, in case I have n vertices N can be maximum n-1....
103 views

In the Hamming code, how many control bits are needed to be able to correct an error in 15-bits transmited

i don't know if right answer is 4 or 5 ! what did you understand from this question if it was a QCM ? thanks
61 views

Are dynamic and agent-based network formation models exclusive groups?

I am studying network formation models and I have seen the separation of those models into two groups (wikipedia): Agent-based models: Aka game-theory based models. This distinction makes sense to ...
254 views

Subnets in computer network

Question: Given: Class B IP address 169.202.0.0. Network when divided into 4 sub networks, each one requires 16,000 IP addresses. They need to be assigned sequentially without gaps. Find the sub ...
46 views

Possible orderings with constraints

Given variables {A, B, ,,,,,Z} We want to sort these varibles according to given constraints. The constrains are in below format: X Y Z meaning the third variable (Z) is not in the range ...
496 views

Finding multiple shortest path trees from an undirected, weight graph

In an undirected, weighted graph G the set of shortest paths from an arbitrary start vertex s form a spanning tree of G. We're calling this spanning tree a shortest path tree. How do I find an ...
758 views

Code size of Instruction set Architecture

For the following assume that values A, B, C, D, E, and F reside in memory. Also assume that instruction operation codes are represented in 8 bits, memory addresses are 64 bits, and register addresses ...
150 views

Check if $P^{NP} = P^{coNP}$

Check if $P^{NP} = P^{coNP}$ To my eye answer is "unknown". I would try to show that it implies that $coNP=NP$, what is unknown fact. Lets suppose that $P^{NP} = P^{coNP}$. Then we use simply ...
5k views

Minimum spanning tree using DFS and BFS

Can we construct minimum spanning tree for an undirected graph with distinct weights using bfs or dfs? I have gone through many answers but each answer says something different and I am not convinced....
36 views

227 views

Query regarding PP complexity class vs NP?

Considering the complexity classes $NP$, $co-NP$ and $PP$: $NP$ and $co-NP$ are both contained in $PP$. For any Language $L$ suppose we have the mechanism that: If the oracle of $co-NP$ implies $No$ ...
257 views

construct a deterministic PDA for the language

Can someone help me to construct a deterministic PDA for the following language: $L = \{0^n1^m | n \geq m$ and $m,n \geq 0 \}$ Here is my suggestion : the states are z0,z1,z2 , z0 is final state ...
934 views

Filling a container with boxes

I have a problem in my Algorithms Class which i am trying to solve for the past two days but I can't. I want to fully fill a container with the MINIMUM number of given boxes with dynamic programming. ...
53 views

Graph Is 1) A D F E G C B and; 2) A D F E G B C is one of deep-first transverse? The code below is written in java and method1 and method2 is two different implementation. ...
3k views

Describing language generated by grammar

S -> aSb | A | B A -> aS | a B -> Sb | b is this the language generated by this CFG? Or am I missing something?
534 views

Binary search trees: multiple Successor() calls

Show that, given a tree node a, the time complexity of calling k times to Successor() is $O(k+h)$, where $h$ is the tree height. ...
49 views

167 views

Interpreting quantum oracles that makes a quantum operation

I am preparing for my master thesis in Quantum Image Processing (QImP), i choose to work with Novel Enhanced Quantum Representation of Digital Images (NEQR). To convert an image from Classical ...
590 views

How many integers can you represent with 6 bits?

I might be wrong but I think it must be 2^6 = 64 integers?
1k views

How to describe a Turing Machine that accepts zeros in power of 3?

I need to describe by a graph a turing machine that can accept the language: A = {0^(3^n ) |n≥0} = { 0 , 000 , 0^9 , 0^27 , ... }. zeros in powers of 3 This here is a turing machine that can ...
314 views

Definition of valid partner in Stable Matching Problem

From Tardos and Kleinberg's Algorithm Design, the definition for "worse valid partner" is basically — $m$ is $w$'s worse valid partner if $m$ is a valid partner of $w$, and no man whom $w$ ranks ...
102 views

Not sure which NPc problem to use for NPc reduction problem,

I'm attempting to prove a problem is NPc, but I'm not sure which one would be optimal to use, The problem is: There are $n$ boars to be caged, and $m$ cages which each cage being able to hold $k$ ...
110 views

I would like to know if there is a closed form expression from taking the reciprocal of a polynomial

I would like to know if there is a closed form expression from taking the reciprocal of a polynomial so that I can apply polynomial division to deconvolution using parallel fork-join multithreading. ...
275 views

Cache (TLB) - fully associative cache

I have an exercise and I don't understand the solution. ...
979 views

Using landmark points on the face for face recognition

I am currently working in area of computer vision for my master's thesis and am trying to use distances between landmark points on the face for recognition. My question is this: What landmark points ...
152 views

Associativity Question , Computer organization

an access sequence of cache block address of length N and contaons n unique addresses. The no. of unique block address between 2 consecutive accesses to the same block address is bound above by k. ...
200 views

Assembly decision loops

An high level language such as C has many statements for decision and loops while an assembly such the MIPS' one has few. With slt, ...
2k views

Removing epsilon transition from context-free grammar

I have the following context-free grammar from which I have to remove epsilon transitions: $S \to 0A0|0$ $A \to BC|2| CCC$ $B \to 1C | 3D | \epsilon$ $C \to AA3 | \epsilon$ $D \to AAB | 2$ By ...
56 views

Can randomization be proven?

There exists a collection c where c = {1, 2, 3} and a randomization of c, ...
192 views

To find a subsequence having largest sum among n positive integers by not choosing 3 consecutive elements

This problem is from codechef.Can anyone please help me out with this one as I am unable to find out the subproblem.Thanks in advance! Problem -: In IPL 2025, the amount that each player is paid ...
79 views

Algorithm : Select maximum number of Boxes to lift from N boxes

There are $N$ boxes and every box has some weight(non-zero). We start from $Box$ $1$ and move towards the $Box$ $N$ one by one. Now there are 2 option ,either to lift that box or leave it. We want to ...
Showing that given a graph $G$, does it exists a clique in $G$ of length $\ge k$" for a given $k\in\mathbb{N}$ is NP-complete
Let be the following problem : "Given a graph $G$, does it exists a clique in $G$ of length $\ge k$" for a given $k\in\mathbb{N}$. Show that it is NP-Complete I know how to show that a set of ...