Computer Science Questions, Problems & Solutions : TransWikia.com ~ Page 7

What are the differences between Earliest Deadline First (EDF) and Earliest Due Date (EDD)?

From my understanding, the EDF (Earliest Deadline First) rule is essentially an iterative "version" of the EDD (Earliest Due Date) rule, which allows for preemption. At every point in time,...

Asked on 11/05/2021

1 answer

If a grammar G is left and right regular, why $||L(G)|| leq ||P||$?

I was studying automata theory and formal languages and came across this question: If a grammar $G$ is left and right regular, why $||L(G)|| leq ||P||$ ? I've...

Asked on 11/05/2021

1 answer

Scheduling jobs online on 3 identical machines - a lower bound of 5/3

Consider the Online Scheduling Problem with $3$ identical machines. Jobs, with arbitrary size arrive online one after another and need to be scheduled immediately on one of the ...

Asked on 11/05/2021

0 answer

Proof for values of d with d:= ||L|| - N(L) with $d in mathbb{Z}$ and N(L) Nerode Index

Let ||L|| be the sum of all lengths of words in L und N(L) the number of equivalence claesses for the Relation $equiv_L$ from Myhill–Nerode theorem. Proof, which values...

Asked on 11/05/2021

1 answer

Is there a way to map the concatenation operation over strings to the addition operation over $mathbb{N}$

Given an alphabet, say $Sigma = {0,1}$, I can make a one-to-one mapping from all possible strings $x in Sigma^*$ to $mathbb{N}$. This could be done by...

Asked on 10/21/2021

1 answer

Confusion in Reduction of Hamiltonian-Path to Hamiltonian-Cycle

The following is an excerpt from a material on NP-Theory:"Let G be an undirected graph and let s and t be vertices in G. A Hamiltonian path in...

Asked on 10/21/2021

2 answer

Proof: is the language $L_1={langle Mranglemidemptyset subseteq L(M)}$ (un)-decidable?

I want to show that $L_1 = {langle Mrangle mid emptyset subseteq L(M)}$ is decidable/undecidable - without rice theorem (just for the case that I can apply it). Every...

Asked on 10/21/2021 by Schleudergang

2 answer

Removing left factoring from Context-Free Grammar

I know that, removing left factoring is a simple task.And i understand following procedure: $S→aA | aB$Becomes:$S→aS'$$S'→A|B$Yet I'm running into problems...

Asked on 10/21/2021 by mmbs

1 answer

Design of a synchronized clock

I was living in a country where Internet wasn't that fast so the younger me had the following idea for compressing data Let say 2 parties want to send data...

Asked on 10/21/2021 by Ahmedou

0 answer

How do you calculate the running time using Big-O notatation?

I'm still new to Data Structure and Algorithm and therefore I would like to ease my doubts. I'm required to find the Big-O running time of myMethod(): Static int...

Asked on 10/21/2021 by Veree

1 answer

Ask a Question

Get help from others!

Computer Science : Recent Questions and Answers (Page 7)

Ask a Question