All Questions

7,643 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
-1
votes
1answer
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 ...
-1
votes
1answer
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 ...
-1
votes
1answer
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 ...
-1
votes
1answer
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.
-1
votes
1answer
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 ...
-1
votes
1answer
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 ...
-1
votes
1answer
60 views

Given three infinite languages L1 L2 L3 over the same Alphabet, that do not intirsect. could one be TR and the other TD and the third neither?

$\sum$ is the Alphabet of three infinite languages $L_{1},L_{2}$ and $L_{3}$ where $L_{1}\cup L_{2} \cup L_{3}=\sum^{*}$ and $L_{1} \cap L_{2} = \emptyset$, $L_{2} \cap L_{3} =\emptyset$ and $...
-1
votes
1answer
93 views

Sort sequence from topological sort if another value is being important

We have sequence that we got from topological sort, but because the graph may not be connected in all cases, we should sort this sequence with another factor. We should output permutation of numbers ...
-1
votes
1answer
43 views

Global optimization algorithm based on MapReduce

In the field of the intelligent swarm, there are many algorithms can find global optimization, such as Ant Colony Optimization (ACO), particle swarm optimization (PSO). Is there any optimization ...
-1
votes
1answer
252 views

Find number of swap required to club all greater than $k$?

Given an array of $N$ numbers and a number $K$, Find the minimum number of swaps required to bring all the numbers greater than or equal to $K$ together. Swap here means, swapping value of $...
-1
votes
1answer
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$$ ...
-1
votes
1answer
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....
-1
votes
1answer
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
-1
votes
1answer
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 ...
-1
votes
1answer
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 ...
-1
votes
1answer
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 ...
-1
votes
1answer
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 ...
-1
votes
1answer
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 ...
-1
votes
1answer
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 ...
-1
votes
2answers
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....
-1
votes
1answer
36 views

true dependence Question

Let's Have i1. lw $s2,0($s1) i2. lw $s1,40($s6) i3. sub $s6,$s1,$s2 i4. add $s6,$s2,$s2 i5. or $s3,$s6,$zero i6. sw $s6,50($s1) what is the true dependence ...
-1
votes
1answer
138 views

How to find a pair of array elements whose difference is smaller than the average difference?

How to find a pair of indices $1\le i \le n$,$1\le j \le n$, $i\neq j$ in array $A[1..n]$ such that $0\le A[i]-A[j]\le\frac{max(A)-min(A)}{n-1}$ in $\Theta(n)$ time? ...
-1
votes
1answer
1k views

How to convert a graph into a Boolean formula that represents all paths from a source node to a sink node?

I have a DAG. I want to construct a boolean formula $\varphi$ that represents all paths from a source node to a sink node. In particular, I have a variable for each vertex. A path $v_1 \to v_2 \to \...
-1
votes
1answer
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$ ...
-1
votes
1answer
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 ...
-1
votes
1answer
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. ...
-1
votes
1answer
53 views

About Depth first search

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. ...
-1
votes
1answer
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?
-1
votes
1answer
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. ...
-1
votes
1answer
49 views

Intersection between language and regular set

This is tangentially related to a question I asked on the math stackexchange. I read in a proof that if $$ \begin{align*} L_1 &= \{w ∈ \{a, b, c\}^* : \text{$w$ has the same number of $a$, $b$, ...
-1
votes
1answer
3k views

Divide and Conquer Algorithm for Hidden Line Removal

You are given n nonvertical lines in the plane, labeled $L_1, ..., L_n$, with the $i^{th}$ line specified by the equation $y = a_i x + b_i$. We will make the assumption that no three of the lines ...
-1
votes
1answer
165 views

Reliable path in graph

Suppose Bob has a messaging network (which is a graph), where a message travels from a vertex V to its adjacent vertex U. ...
-1
votes
2answers
95 views

finding normality from a set of samples of MEAN

I have set of 1000 samples. each sample represents MEAN of X amount transactions response time. Now I have a running transaction , I know it's current response time but I want to know if this ...
-1
votes
2answers
818 views

How to find the median of 5 elements by rote and its time complexity is O(n)

In the first step, I agree that divide n elements into groups take one pass so the time complexity is $$O(n)$$. But if we need to find the median of each 5 elements, we may have to sort them. I ...
-1
votes
1answer
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 ...
-1
votes
2answers
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?
-1
votes
1answer
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 ...
-1
votes
1answer
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 ...
-1
votes
2answers
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$ ...
-1
votes
1answer
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. ...
-1
votes
1answer
275 views

Cache (TLB) - fully associative cache

I have an exercise and I don't understand the solution. ...
-1
votes
1answer
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 ...
-1
votes
1answer
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. ...
-1
votes
1answer
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, ...
-1
votes
2answers
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 ...
-1
votes
1answer
56 views

Can randomization be proven?

There exists a collection c where c = {1, 2, 3} and a randomization of c, ...
-1
votes
1answer
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 ...
-1
votes
1answer
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 ...
-1
votes
1answer
78 views

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 ...
-1
votes
2answers
10k views

How to compute total internal and external fragmentation

I want to find the total external and internal fragmentation. What I understand is that external fragmentation occurs when processes are loaded and removed from memory, causing memory to be broken ...

15 30 50 per page