All Questions

Filter by
Sorted by
Tagged with
-1
votes
2answers
51 views

Context-free grammars for two languages

How do I write context-free grammars for the following languages? $B_2 = \{0^n1^n \mid n > 0\} \cup \{0^n1^{2n} \mid n > 0\}$ $B_3 = \{a^nb^mc^k \mid k = n+m\}$ Can someone help me? I'm not ...
-1
votes
1answer
35 views

A general question in type of computer science

Where can I find a source for questions/problems with data structures (like questions about avl trees , rank-trees, 2-3 trees, heap) and algorithms? I will be happy for a references in these topics ...
-1
votes
1answer
21 views

Independence groups and fully connected groups

Let G be a connected graph, knowing that it has more than 9 vertex, Show that either its independence number is bigger-equal than 4 or its click number (the size of the biggest fully connected group) ...
-1
votes
1answer
66 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
162 views

Why don't we delete a node in adjacency list after visiting an edge in Fleury algorithm?

I was reading an article on fleury's algorithm GeeksforGeeks. In fleury's algorithm, Once an edge is processed (included in Euler tour), we remove it from the graph. To remove the edge, we replace the ...
-1
votes
2answers
39 views

how to prove a simple graph with this question [duplicate]

) Suppose G is a simple graph with n vertices. Prove that G has twice as many edges as vertices only if n ≥ 5. ? Any one can help?
-1
votes
1answer
71 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
33 views

Adding edges to a graph that satisfy logical expressions

Easy question. I have a homework problem with its answer that i am unable to interpret. An explanation on how to arrive at the answer is what I'm looking for. Please let me know what the palette ...
-1
votes
1answer
68 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
31 views

How can the binary OR function be computed by a MOD3 gate of constant fan-in?

I've been working on a problem and in order to prove the bigger picture, I need to understand how a binary OR function can be computed by a constant fan-in MOD3 gate. I would seem that the output ...
-1
votes
1answer
43 views

Beginner question in Java [closed]

I am just starting to study Java and was wondering why the following code if(x>2) x*=2; if(x>4)x=0; System.out.println(x); returns 0 for any value of x greater than 2. For example, when x=3, why ...
-1
votes
1answer
254 views

What is the regular expression for strings containing at least one a and at least one b? [duplicate]

$L = \{w \in \{a, b, c\}^*\mid w\text{ contains at least one }a\text{ and at least one }b\}$. what's the proper regular expression for the following language?
-1
votes
1answer
78 views

On NP and PP in RP?

Does $NP\subseteq RP\implies NP=RP$? Does $PP\subseteq RP\implies \oplus P=NP=RP$? At least what additional minimal conditions will give truth of above?
-1
votes
1answer
845 views

The minimum number of bits required for an instruction

For a computer architecture, called ComputerA, a MIPS-like instruction set will be used. 64 instructions are reserved for R-type instructions and 64 more instructions are reserved for I-type and J-...
-1
votes
1answer
477 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
20 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
54 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
83 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
41 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
227 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
46 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
128 views

Infix to postfix by stack [closed]

Convert in postfix (((P+Q)(R+S))/T) +(A(B+C)) note : there is * between (P+Q) (R+s) My attempt in image and size of stack = 15 given, but iam getting size =13
-1
votes
1answer
250 views

Simulating AVL Tree Right, then Left rotation

I have the following AVL tree and want to AVL-INSERT a node 5 into the tree. Since the middle branch will be unbalanced, I'm guessing that it will require a right rotation, then a left rotation to ...
-1
votes
1answer
400 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
85 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
58 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
286 views

Hamming distance [duplicate]

I have some difficulties in computing Hamming distance in following example: 11100000 00011100 10010010 01001001 I know the definition of Hamming distance (in case of two codewords) but how to ...
-1
votes
1answer
35 views

Problem in analyzing asymptotic notation in using The Master Theorem [duplicate]

As we know for master theorem: T(n)=aT(n/b)+Θ(nd) this formate is required.. But for T(n)=2T(n/2)+2^n If I want to apply theorem what will be value of d here? We cant just take d=2 here..right?
-1
votes
1answer
37 views

Why is $MOD_{p^k}P=MOD_pP$ at every prime $p$?

Complexity zoo states that $MOD_{2^k}P=MOD_2P$. It is clear that if $MOD_2P$ accepts (number of accepting paths is off) then $MOD_{2^k}P$ accepts. Why is it clear that if $MOD_2P$ rejects (number of ...
-1
votes
1answer
225 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
77 views

is it possible to do a DFA for these languages? [duplicate]

I have just started learning Automata Theory, so far I only know about regular languages, FSM (NFAs and DFAs) and regular grammars, but I come across a question like this: "Given the next languages, ...
-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
411 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
2answers
1k views

What is bit time in Ethernet CSMA/CD

"Propogation delay betwween two links is 200 bit times" I am little confused here, Propogation delay should be in seconds, milliseconds etc but here it is in bit times. I also want to know what is bit ...
-1
votes
1answer
52 views

Create DFA with String of {a,b} [duplicate]

I Want to Create Regular Expression from string of {a,b} that it contains neither the substring ab NOR ba?How I can do it?
-1
votes
1answer
542 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
68 views

Big o notation help? [duplicate]

I'm learning about data structures and have been reading up on upper bounds. Most of the stuff I understand but my professor gave us a problem in class to solve on our own for fun. I'm not sure how to ...
-1
votes
1answer
39 views

Why $\left\lceil lgn \right\rceil <lgn+1\le 2lgn\quad for\quad all\quad n\ge 2$

I have some confusion about 3.2-4 in CLRS. Here is the question : Is the function $\left\lceil \log { n } \right\rceil !$ polynomially bounded? Is the function $\left\lceil \log { \log { n } } \...
-1
votes
2answers
2k views
-1
votes
1answer
131 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
1answer
3k 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
32 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
97 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
782 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
179 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
226 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
7k views

Construct DFA’s Accept all strings containing “ 011 ” or “ 001 ” as a substring and should not contain “ 010 ” as substring

My question is Accept all strings containing “ 011 ” or “ 001 ” as a substring and should not contain “ 010 ” as substring for the following languages over the alphabet {0,1} i have solve it ...
-1
votes
1answer
2k views

Construct a Turing Machine to increment any binary number [duplicate]

Construct a Turing Machine to increment any binary number . (for example, if the input is 10010 then the output will be 10011 and if the input 111 then the output will be 1000
-1
votes
1answer
759 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
52 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. ...

15 30 50 per page