# All Questions

47,363 questions
Filter by
Sorted by
Tagged with
17 views

### How does garbage collection works in operating systems?

As per the author, ...In this case, we generally need to use a garbage collection scheme to determine when the last reference has been deleted and the disk space can be reallocated. Garbage ...
1 vote
30 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, ...
36 views

### Question about remainder in automata construction that checks devisibility

I'm trying to understand de construction of a DFA from the book "Introduction to Automata Theory, Languages, and Computation by John Hopcroft and Jeffrey Ullman 1st ed" It says: Where it ...
28 views

### Why can't I prove that the regular language is closed under concatenation by this way?

I'm reading Michael Sipser's "Introduction to the Theory of Computation", and it says: THEOREM 1.26 The class of regular languages is closed under the concatenation operation In the video, ...
20 views

### WAV file header: Why 2 bytes for channel?

It is mentioned in 22 - 23 Number of Channels which will be 1 if mono, 2 if stereo. So why 22 and 23 (that is 2 bytes) allocated here? With 1 byte, we can put either 1 or 2.
15 views

### Finding min s-t cut of network with flow on the nodes

Given a network with flow on the nodes. How can we find min s-t cut in a network with flow on the nodes? We know how to find min s-t cut whenever there’s a network with flow on the edges (Ford ...
1 vote
24 views

### What is the time complexity of this algorithm

I came up with this algorithm for finding all prime numbers from 1 to n. This algorithm could already exist, if it does I don't know what it is called. ...
49 views

### Using recursion to find rotation matrices of higher dimensions

I am looking to find a way to calculate a rotation matrix of $m$ x $m$ dimensions.I was thinking since it is almost impossible to find analytically , maybe we can use recursion to solve much simpler ...
20 views

### Constructing an SAT formula from a Clique graph

We were given this practice question to do in a lecture and its solution afterwards. I have spent hours upon hours trying to understand the solution but still do not understand. From my knowledge when ...
15 views

### Minimize overlap in class schedule

At our school, we have a schedule that looks like the following (simplified): Remarks: One course can be taught multiple times a week (to different class-groups, like 1A, 1B and 2A) Multiple lessons ...
11 views

### Max flow with a minimal in-degree objective on certain nodes (for edges with non-zero flow)

The following a small-scale example meant to illustrate the general problem Suppose we have 60 marbles that we want to distribute into 3 bowls. The marbles can take 4 distinct colors and we have: 15 ...
29 views

### Which one grows faster, an exponential function where the exponent grows faster than logarithmic or a factorial powered by n?

Which function grows faster: $$f(n) = 4^{n^2 \log_2 n} \text{ or } g(n) = (n!)^n$$ Which is true? $f(n) = O(g(n))$ $g(n) = O(f(n))$ i.e., $f(n) = \Theta(g(n))$ none of the above? For lower values of ...
1 vote
30 views

### Properties of $\mathrm{Shade}$ algorithm

I am working on the following problem taken from the book Algorithms by Ojo: A relaxation of the Max-TSP problem is the Shade problem. Let us call a shade of a graph as a set of disjoint cycles that ...
17 views

16 views

### Cormen chapter 11 probability of two keys being assigned the same slot simple uniform hashing

I have been reading Cormen's chapter 11 and I stumbled upon the following statement on page 260 (3rd Edition): Let xi denote the ith element inserted into the table, for i = 1, 2 ... n, and let ki = ...
29 views

### 3sat to clique reduction program

I am searching for a program to convert 3sat to clique problem. I tried following links https://www.geeksforgeeks.org/maximal-clique-problem-recursive-solution/ https://www.geeksforgeeks.org/find-all-...
51 views

### Is there a challenge with which one could reasonably show to have found a feasible polynomial algorithm for an NP problem?

Say there is someone claiming to have solved P vs NP, by finding a (computationally feasible, i.e. no huge constants) polynomial solution to a problem in NP: Apart from a formal proof, is there any ...
171 views

### An efficient way of finding the closest point of a sampled function to another point

I have a function $f(x)$, has been sampled into a sequence $$y_0, y_1, ..., y_{n - 1}$$ at points $x_k = k \Delta x$. $f(x)$ is neither smooth or monotone. Under this assumption, what is the fastest ...
26 views

### Work and depth of DAG - problem in understanding exam question

I have some problems understanding the following 2 question from an exam last year, which I am preparing for this week in Parallel Programming. Determine the Work -> $W(n) = 7$ (#vertices) ...
26 views

### Automatic refresh of a web page!

Someone can give me an idea about how to refresh automatically a web page and get notified by email if the page ever changes (using a script of course)? ((May be using "tampermonkey"? but i ...
22 views

### Computational power of probabilistic automata

I am a bit confused about the proper role of probabilistic automata (PA) in the theory of computation. Informally, I can imagine they can accept more than finite automata (FA) as they, for instance, ...
20 views

### Prove with natural deduction

Prove P ∨ Q, Q ∨ R, P → ¬R |- Q with natural deduction. P ∨ Q, premiss Q ∨ R, premiss P → ¬R, premiss ... ... Conclusion, Q I dont know how to properly solve this question? I know somewhat how to ...
1 vote
30 views

### Finding growth rate of T(n) of a code segment

I am presented with the following code segment and asked to find the growth rate, which can be done by finding the number of times the variable sum is incremented: ...
1 vote
42 views

### Missing 770201 seconds in Y2K2038

From what I understand about the Y2K38 problem, unpatched 32 bit systems with signed UTC times will jump back from 19 January 2038 at 03:14:07 UTC to 13 December 1901, at 20:45:52. Calculating the ...
46 views
+50

### how to do incremental construction of the minimal model in logic programming?

I was reading a book titled "Essentials of Logic Programming.", most parts of the book are easy to understand. but now having a problem with Theme 45: incremental constructions of the ...
61 views

### How to prove this language is irregular without using Myhill-Nerode?

I have this language that I have to prove either regular or irregular. $$L_3 = \{mm^rn | m^r \text{ is the reverse of } m,\ m,n \in \{a,b\}^+\}$$ It's trivial to prove that it is in fact irregular ...
12 views

### Can Gomory-Hu tree algorithm be applied to graphs with more than one connected component?

If I have an undirected graph with more than one connected component, can I apply the Gomory-Hu algorithm directly on the entire graph or do I have to apply it separately to each component?
37 views

1 vote