101 questions
Filter by
Sorted by
Tagged with
1 vote
68 views

### Interval scheduling; sort by ending times

You have $n$ events on your calendar, deﬁned as intervals with a start time $s_i$ and a ﬁnish time $f_i$. The events might overlap, and you want to attend all the events, so you are going to create $k$...
• 11
1 vote
82 views

### Union of non regular and regular language

So I have a regular language L and a non-regular language L' and i want to proof wether the union of both is regular or not. Since I found counterexamples for both cases I want to look at more ...
55 views

### Question about implication in proof that predecessor subgraph is a breadth-first tree

Given the following theorem and definitions from Introduction to Algorithms 3rd edition by CLRS: Theorem 22.5: (Correctness of breadth-first search) Let $G = (V, E)$ be a directed or undirected graph, ...
1 vote
243 views

### Trying to give a proof about graphs. Having a hard time giving proof for Kruskals algorithm. Can you check my answer?

Question: Let G(V, E) be an undirected connected finite graph with the weight function w : E → R+. Let T be a minimum spanning tree of G. Prove that there exists a run of Kruskal’s algorithm that ...
1 vote
209 views

### Question about step in proof that predecessor subgraph forms a breadth-first tree

Given the following theorem and definitions from Introduction to Algorithms 3rd edition by CLRS: Theorem 22.5: (Correctness of breadth-first search) Let $G = (V, E)$ be a directed or undirected graph, ...
1 vote
59 views

177 views

### My attempt at the "This statement is false" paradox

(I haven't read any literature on this paradox nor am I good at formal proofs, so this is just my intuitive thoughts on the paradox.) If we assume the statement "This statement is false" as ...
• 1,111
63 views

### Safety VS. Liveliness Property

I have to prove whether a certain property is safety or liveliness. The property represents the absence of deadlock so I expected it to be a safety property from what I read online. The issue is that ...
• 121
247 views

### 4DM is NP-complete

Is 4DM NP-complete? An instance of 4DM consists of four disjoint sets X, Y, W and Z of size k, and a set Q of quadruples $Q = \{ (x, y, w, z) \mid x ∈ X, y ∈ Y, w ∈ W, z ∈ Z \}$ Question: Is there a ...
• 47
37 views

• 27
1 vote
548 views

### Longest path in a strongly connected component

So if we assume that we have some strongly connected component G with n vertices. I would like to find the length of the longest path in that component. My idea is: In a strongly connected component ...
• 27
286 views

### DFA containing substring to not containing substring by flipping acceptability of all states?

For example, $D_1 = \{ w | w$ does not contain baba as substring$\}$ For $D_1$, I would make $F_1 = \{q_4\}$. As I tried to design $D_2$ as the complement of $D_1$ ...
• 1,111
568 views

### Solve the following recurrence-relations: $T(n)=5T(n/3)+T(2n/3)+1,T(n)=2T(\sqrt{n})+\log_2(n)$

Solve the following recurrence-relations: my attempet for the first one was doing upper bound and lower bound by changing for lower $6T(n/3)+1$ and for upper $6T(2n/3)+1$ but i didn't get the same ...
• 211
1 vote
129 views

### Language of all even-length words with no 1's in left half

Consider the following language: $$L=\{w \in \textstyle\Sigma_1 ^*\mid|w| \text{ is even and 1's can only occur in the second half of w}\},$$ where $\Sigma_1 = \{0,1\}$. I need to show that this is ...
• 353
83 views

• 51
118 views

### $\Phi_1=1$ or $\Phi_1=2$ for the dynamic $\text{Table-Insert}$ , where $\Phi_i$ is the potential function after $i$ th operation, as per CLRS

The following comes from section Dynamic Tables, Introduction to Algorithms by Cormen. et. al. In the following pseudocode, we assume that $T$ is an object representing the table. The field $table[T]$...
• 1,122
251 views

### Proving that the two definitions of Universal Class of Hash Function are equivalent (as dealt with in CLRS)

I was going throught the text Introduction to Algorithm by Cormen et. al. where I came across the two alternative definitions of Universal Class of Hash Function. The versions are as follows: ...
• 1,122
1 vote
71 views

### For selection in worst-case linear time ambiguity in consideration of $n$ for which $T(n) =O(1)$ and $T(n)\leq cn$

I was going through the text Introduction to Algorithms by Cormen et. al. where I came across the recurrence relation for analyzing the time complexity of the linear SELECT algorithm and I felt that ...
• 1,122
90 views

### Asymptotic calculation check for triple-nested for-loops

I have the following repetition structure: ...
1k views

### Proof for LeetCode: 11. Container With Most Water problem

UPDATE: I abandoned this initial approach in favor of a more powerful invariant I worked out after posting. I've detailed that one in an answer below. I'm new to algorithm correctness proof-writing ...
• 206
159 views

### Prove $\epsilon(S\cap T)\subseteq S \cap T$

Suppose there are sets $S\subseteq Q, T\subseteq Q$ such that $T=\epsilon (T),S=\epsilon (S)$. Prove $\epsilon(S\cap T)\subseteq S \cap T$ Definition of $\epsilon$- closure for epsilon NFA is: ...
• 177
1 vote