All Questions

32,536 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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) ...
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 ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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?
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?
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-...
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 ...
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 ...
54 views

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$$ ...
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
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 ...
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....
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
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 ...
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 ...
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?
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 ...
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 ...
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, ...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
39 views

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? ...
782 views

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 ...
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