All Questions

Filter by
Sorted by
Tagged with
1
vote
0answers
19 views

When Triangulating monotone polygons, how can diagonals be added to a DCEL in constant time?

I am working on the polygon triangulation algorithms from "Computational Geometry - Algorithms and applications 3rd ed", chapter 4. I've managed to turn polygons into y-monotone polygons ...
0
votes
0answers
15 views

Efficient way to do self join with minimum support?

In the apriori algorithm there's the self join step, So, say we have 1 3 2 3 3 5 2 5 If I were to do an exhaustive join I'd end up with a tuple including (1, 3, ...
2
votes
1answer
37 views

Find all combinations of adjacent records matching a graph template

I have a graph theory or combinatorics problem that probably has a solution, but I haven't been able to find it. The problem can be simple: in the second figure below, choose one yellow block from ...
3
votes
1answer
38 views

A question about hash problems in CLRS book

Consider the following problem 11.2-6 from CLRS book: Suppose we have stored $n$ keys in a hash table of size $m$, with collisions resolved by chaining, and that we know the length of each chain, ...
1
vote
0answers
41 views

How do I use the definition of the "Big-Oh" notation to prove the following statements? [closed]

I need help figuring out how to prove the following statement using the definition of "Big-Oh" notation which says that ...
6
votes
3answers
1k views

Does the Minimum Spanning Tree include the TWO lowest cost edges?

Wikipedia's Minimum Spanning Tree reads: Minimum-cost edge If the minimum cost edge e of a graph is unique, then this edge is included in any MST. Proof: if e was not included in the MST, removing ...
2
votes
0answers
19 views

How to build a minimal string matching DFA with limited memory?

I am working on finite state machine pruning, a problem that requires me to build finite state machines (in the manner of the Aho Corasic algorithm) to match an evolving input string against a set of ...
1
vote
1answer
21 views

Linear programming for prefix of graph

Question: Consider an arbitrary directed graph $G$ with weighted vertices, the weights can be positive, negative or $0$. The prefix of $G$ is a subset of vertices $P$ such that there's no edge $(u \...
3
votes
1answer
52 views

Subset sum with only two item types

Suppose we have $r$ copies of the integer $a$ and $t$ copies of the integer $b$, and a capacity $C$. We would like to find the maximum sum of the given integers, that is at most $C$. This is a special ...
2
votes
1answer
26 views

What is the outermost class 2^Σ* referring to on the Extended Chomsky Hierarchy?

After having searched a bit, it seems I can't find terminology or references for this outermost class, 2Σ* in blue -- see below. What is it describing?
1
vote
1answer
35 views

When is a stuck state not final and when is a maximal sequence not complete in transition systems?

Reading the book Practical Foundations for Programming Language. In section 5.1 Transition Systems, the author said that Whereas all final states are, by convention, stuck, there may be stuck states ...
-2
votes
0answers
32 views

Turing machine for addition

I want to make turing machine for addition. So say I want to add 2+3. I say 110111. What I want to do is convert 0 to Blank and bring it to the leftmost part. Then the resulting answer is final ...
0
votes
0answers
45 views

the store and forward mechanism transmission delay

In a computer network, the store and forward mechanism is used. In this mechanism, the packet is sent from one system to the next along the network path, and in the second system, the complete packet ...
-2
votes
0answers
41 views

How to calculate response time and throughput in LAN with cache server?

considering the cache server does cache operation for both LANs. Users in LAN1 have following conditions: L1=100,000bits, a1=15req/sec, h1=50%(hit rate) Users in LAN2 have following conditions: L2=50,...
-1
votes
0answers
18 views

When should stalls due to branch be considered in RISC?

In the image, the RISC pipeline is being assumed. The answer states that average CPI = 1 + (0.25)(0.5)(1) only accounting for the stalls due to loads followed by immediate consumers. Given 5% ...
-4
votes
0answers
22 views

How do we prove this NP hard decision problem?

How can we prove this statement? Based on a formal decision problem it can be solved, right, but how exactly we can define this problem to be proved. I am not getting this concept properly. A ∈ P if ...
0
votes
1answer
21 views

polynomial time approximation algorithm problem

How can we actually define a polynomial-time 4-approximation algorithm for vertex cover or knapsack problem? For say we have 2 approximation problems which less than equal 2C*. But when we have a ...
-2
votes
1answer
28 views

What is the difference between NP hard and NP complete?

What is the definition of P, NP, NP-complete and NP-hard? here is a good answer but it really doesn't answer mym question. np-hard-: a problem A is NP hard if for all B$\in$NP, B is polynomial time ...
2
votes
1answer
34 views

What does $g \to \lambda$ mean in the L-System for the dragon curve?

I am playing with L-System using the wonderful tool jflap. Below is the L-System for the dragon curve in the "JFLAP book: JFLAP – An Interactive Formal ...
2
votes
1answer
16 views

Comparing various ways to move a game actor having time-dependent velocity

Assume I have a game actor (name it MyActor for further references) to be moved up and down according to $z=f(t)=A\sin \omega t$ (or any non constant velocity). The ...
1
vote
0answers
18 views

Bully Algorithm Timeout After Receiving a Response from a Higher Process

Im specifically referring to the bully algorithm for synchronous systems, described in [Garcia-Molina 1982]. In it, the timeout for failure detection is concretely defined as the sum of the round trip ...
0
votes
1answer
11 views

Finding permutation of jobs such that each job finishes before deadline

Consider a set of jobs, each having its deadlines and process time. How to find a permutation of them such that if they are executed in that sequence, they all finish before their deadline or figure ...
2
votes
1answer
23 views

Find k closest numbers to the median

The formal problem statement is: Given a set S of n distinct numbers and a positive integer k<=n, determine the k numbers in S closest to the median. My thoughts: I have read about the median of ...
1
vote
0answers
25 views

Adversary argument and proving a lower bound of an algorithm. How does it work?

I need to understand how adversary argument works to prove the lower bound of an algorithm. For now, I am looking to prove that a "certain" algorithm that takes in input array requires omega(...
0
votes
0answers
16 views

How to read the optimal makespan

Hello I'm having trouble reading the optimal makespan of job scheduling algorithm. In particular what does it mean for max to have index i here?
0
votes
1answer
16 views

What does it mean to 'provide' an API call?

So I have a database pre-loaded with data related to food recipes and the assignment says: 'Provide an API call that allows us to specify an ingredient or set of ingredients and return full recipes ...
4
votes
1answer
33 views

Is there a more efficient way to obtain the optimal input sequence in this finite-state system

Context: Consider $M$ finite state systems with evolution given by: $$ x^i_{k+1} = f(x_k^i,u_k) $$ where $x_k^i\in\{1,\dots,X\}$ is the state of system $i\in\{1,\dots,M\}$, $k\geq 0$, and $u_k\in\{1,\...
-2
votes
0answers
26 views

File Format and data type

Why different format type for different data is needed?? Is each one useful for different things, or are they just being promoted by different software vendors?
3
votes
0answers
52 views

Graph coloring problem with violations

I would like a name for the following problem. We consider a relaxed vertex coloring problem, where Let $k$ be the number of colors Let $B$ be the set of edges violating coloring, i.e., $$B := \{(u,...
2
votes
1answer
48 views

Automated Query Equivalence Solver (MongoDB)

The query-equivalence problem is undecidable. However there are theorem provers that attempt to solve instances of undecidable problems. I am curious how I could go about using an automatic theorem ...
4
votes
0answers
133 views

It's possible to solve this problem in $O(n)$?

Suppose given two strings $s_1$ and $s_2$ each of length $n$. We consider $s_1$ and $s_2$ as dual, if one of the following conditions satisfied: Strings are equal. Else, if $n$ is even then: Divide $...
0
votes
0answers
15 views

I cant figure out which regular experesion solves my problem [duplicate]

The language L=a binary number with even number of digits that doesnt have 2 consecutive zeroes. What is the regular expression that can search those words and how what is your thought process when ...
-2
votes
3answers
97 views

What is the point of encoding universal turing machines?

I am unable to understand why do we need to encode turing machine at all? I heard that we are trying to build a programmeable turing machine but can't relate how encoding it will make this ...
0
votes
0answers
20 views

How to create an example for ID3 algorithm?

I am working on designing an implementation for an ID3 algorithm. The only example that I can go off is this example found in a text book. Could someone provide an example for using this algorithm ...
0
votes
1answer
26 views

Pure Directed Graph

How can a directed graph be efficiently represented in a purely functional language like Haskell? Could someone suggest relevant materials on this topic? (functional pearls perhaps?) Thanks.
2
votes
1answer
30 views

Convert a dfa to rule for a asterisk case

Here is a simple but very common grammar rule case in EBNF format, the Statements is a none terminal symbol and Statement is ...
3
votes
0answers
41 views

Cost of finding optimal elimination order in a planar tensor network?

Suppose we are computing a sum over $n$ factors which can be represented as a planar tensor network. What is the complexity of finding an optimal elimination order? For example, take the following ...
1
vote
2answers
39 views

How many Integers can be represent in Double-Precision floating-point form

How to calculate the number of Integers that can be represent in Double-Precision floating-point form?
1
vote
1answer
20 views

Can graphs have a serialized canonical form for the purpose of very fast graph structure look-up (subgraph isomorphism)?

Let suppose we order the nodes first by degree (in + out), to get a list of node structures: ...
1
vote
1answer
17 views

Hoare's Axiom Scheme Precondition

I have a question about determining preconditions for Hoare's Axiom Scheme. For example, if we have P { x=2 } x==1 and we are trying to determine the precondition, ...
0
votes
1answer
64 views

Why can $2$-SAT be solvable efficiently, but $3$-SAT not?

I am aware that 2SAT is polynomial while 3SAT is not, but I am looking for an intuition why its so. After all, even in 2SAT we can attempt all possible truth functions and its $2^n$. So I am hoping ...
1
vote
1answer
25 views

A turing machine L takes a machine <M> which has to halt at for least n Inputs

I've been wondering about this problem for a while: Say we have L = { <M>, n | M has to halt for at least n Inputs} and multitapes are simulating various inputs bla bla How do I count how many ...
1
vote
1answer
43 views

Is the MCP language really np hard?

I have a graph $G=\left(V , E\right)$ and source $s$ and target $t$. I also have a weight function $w: V\rightarrow \mathbb{R^+}^k$, meaning a vertex given $k$ non negative weights. There is an upper ...
0
votes
3answers
47 views

Are there any FNP-complete problems with a unique solution?

Are there any FNP-complete problems where there's only one possible solution? For example, the travelling salesman problem can have multiple routes all shorter than $X$. There's only one shortest ...
-2
votes
1answer
51 views

Halting problem is undecidable proof-:

Confused with this proof. I will point my confusions here. what is R(M)? They say it is representation of turing machine but what is it exactly? Is it tuples of turing machine? How do we decide w is ...
0
votes
1answer
15 views

How are vertex capacities defined in a flow network?

I'm new to network flows and I'm reading this topic from Cormen's Algorithms book (3rd edition) from 26 chapter. I came across this problem from the 26.1 section Suppose that, in addition to edge ...
1
vote
0answers
13 views

Has the similarity relation of a tree-shaped labelled transition system have finite index?

Let $T$ be an infinite countable labelled transition system with the shape of a tree and let $\sim$ be its similarity relation among nodes. Note that the alphabet of the labels is finite (hence the ...
0
votes
1answer
26 views

Can any language be expressed by regular expression?

I'm studying Autoamta Theory currently and am wondering if any Language (for example Lanugage L in Alphabet A={a,b}) can be expressed by regular expression. In my current understanding the rule is &...
0
votes
0answers
20 views

A query regarding equivalence of Parallel vs. Serial cells Turning Machine

Given: A Turing machine (set of programs) that behaves as follows: It has some fixed number of states $(S)$ and binary alphabet $(0/1)$. For some constants $k, p, (k<N, p< N)$: Its read/write ...
0
votes
1answer
30 views

Python: Assigning values to 2D-array elements

I created a 2x2 2D-array of 0's as follows: sizes=[[0]*2]*2 sizes [[0, 0], [0, 0]] I want to change the second element of the first row to 1. I do this as follows:...

15 30 50 per page
1
3 4
5
6 7
855