All Questions
47,363
questions
0
votes
0
answers
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 ...
- 101
1
vote
0
answers
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, ...
- 33
0
votes
1
answer
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 ...
- 101
0
votes
1
answer
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, ...
0
votes
1
answer
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.
0
votes
0
answers
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
0
answers
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.
...
- 21
-1
votes
0
answers
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 ...
- 29
0
votes
1
answer
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 ...
- 1
0
votes
0
answers
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
0
votes
0
answers
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 ...
- 3
0
votes
1
answer
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
1
vote
0
answers
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 ...
- 11
0
votes
0
answers
17
views
Is PAD(EXP) = P?
Can I say that all languages in the class $\textbf{P}$ are just a padded version of some other problem in $\textbf{EXP}$?
I am familiar with the padding argument, which states that if $\textbf{P} = \...
0
votes
0
answers
40
views
Draw a flowchart of a simple payroll system that will display an employee’s information
Ask for the name of the employee.
If the employee is full time, get his monthly salary rate. Then, display his name and salary.
If the employee is part time, get his rate per hour and the total ...
- 1
0
votes
0
answers
24
views
Minimum spanning tree using BFS
In finding a minimum spanning tree, if we use a BFS and at any node instead of deleting the edge to a repeated node, we can find the most expensive node in that cycle instead and delete it.
In such a ...
2
votes
1
answer
20
views
EXP reduction to show NEXP-completeness
I wonder why can't I allow an exponential-time reduction from all problems in $\textbf{NEXP}$ to a language $L$ and claim $L$ to be $\text{NEXP-complete}$.
The computational complexity class $\text{...
0
votes
1
answer
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 = ...
- 149
0
votes
1
answer
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-...
- 1
0
votes
1
answer
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 ...
- 101
0
votes
2
answers
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 ...
- 147
0
votes
0
answers
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)
...
- 101
-1
votes
0
answers
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 ...
- 9
0
votes
0
answers
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, ...
- 155
0
votes
0
answers
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
1
vote
2
answers
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:
...
- 11
1
vote
1
answer
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 ...
2
votes
0
answers
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 ...
- 1,062
2
votes
0
answers
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 ...
0
votes
0
answers
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?
- 101
0
votes
0
answers
37
views
Is $\{ 0^{a}10^{a}1 0^{a}|a \in \mathbb{N}\}$ a context free language?
I was thinking about whether $\{ 0^{a}10^{a}10^{a}|a\in\mathbb{N} \}$ is a context-free language, and I found this post. I am not sure if my understanding is correct or not, but I guess $R = \{ (a,1,a,...
- 101
0
votes
1
answer
71
views
T(n) = T(n-1) + T(n-1) vs T(n) = 2*T(n-1)
If I have 2 version of code
1.)
def T(n):
if n == 0:
return 1
return T(n-1)+T(n-1)
2.)
...
- 5
-2
votes
0
answers
28
views
C programming Code Blocks C syntax [closed]
Why is the following code not working in Code Blocks
#include<stdio.h>
#include<string.h>
void xstrrev(char *p);
int main()
{
char *arr[]={
"hello",
"goodbye",
"...
0
votes
0
answers
14
views
How is the physical address calculated in Page tables?
Taking an example, say we have Page size = 4KB, Page Table Entry = 4B, Physical Address Space requires 36 bits
In 3-level multi-paging, let's say the number of entries in the level 3 page table is 2^9 ...
0
votes
0
answers
30
views
Incompresensible about $w$ $x$+ $b$ = 0
I don't actually understand the meaning of $w$$x$ + $b$ = 0
when it is defined in support vector machine.
In my own understanding, in order for the equation to be true, the hyperplane would always ...
- 11
-1
votes
0
answers
41
views
Why does storing an $n$-element array require $O(n)$ space?
This may seem to be a trivial question, but I am a bit stumbled by why people claim:
$n$-element array requires $O(n)$ space
Under what assumption does this statement hold?
Is there an assumption in ...
- 789
0
votes
0
answers
29
views
Why in Edmonds Karp or Ford Fulkerson Algorithm the time complexity of BFS or DFS respectively is O(E) rather than O(V+E)?
For these algorithms, the time complexity of BFS and DFS is O(E).
I have gone through many websites and even the algorithm books, but I never got a clear idea of why it is O(E). It just says it's O(E) ...
3
votes
1
answer
80
views
How do I improve my problem-solving and creative thinking skills in Computer Science?
I am a CS undergrad trying to improve my problem-solving skills. I have noticed that I have a problem with theoretical computer science which I've been trying to fix largely unsuccessfully till now. I ...
- 31
0
votes
0
answers
37
views
What should I look to do in high school to prepare myself for college/jobs
I am a high schooler who has been programming for about 3 years now. My skill level is above what AP Comp Sci and especially what principles can teach me. What should I be doing to improve myself and ...
- 109
0
votes
0
answers
27
views
Does the following down-voted answer not answer the question "Why does Schaefer's theorem not prove that P=NP?"?
Does the following highly down-voted answer not answer the question "Why does Schaefer's theorem not prove that P=NP?"? If not, why not?
Marek, V. Wiktor. Introduction to Mathematics of
...
- 146
0
votes
0
answers
37
views
Progress towards a Polynomial time factoring algorithm?
This is probably insignificant, but I was messing around with polynomials, and found out that, if we have a number, n = pq that we want to factor, if we expand (k+1)^n -k^n - 1, mod n, the first ...
- 219
0
votes
0
answers
14
views
Current best output-sensitive algorithm for computing all maximal cliques of a graph
I am looking for a reference on the most optimal output-sensitive algorithm currently available for listing all maximal cliques in a graph.
I know the Bron-Kerbosch algorithm is highly utilized, but ...
0
votes
0
answers
37
views
Chore schedule with fair distribution of pairs and groups
I need to build a schedule that maps 7 people to 4 groups (3 pairs, 1 single) for each week.
An ideal schedule would be one where each person swaps pairs and groups in a round-robin style. If such a ...
- 101
0
votes
0
answers
29
views
What is the optimal resource to follow to learn Operating System?
I wanted to learn Operating System on my own. Although I have learned few basic things from here and there, but wanted to know the suggestions (books, any video lecture, etc.) from this community.
- 13
0
votes
1
answer
34
views
Regular expression for binary string containing no instances of 01
In order to enumerate such a regular expression, it's clear one can break down the language into the set $s =\{00,01,10,11\}$ and it is clear that we need to enumerate some expression that avoids the ...
0
votes
0
answers
23
views
Abstract models of parallel computing?
I am looking for literature on abstract models on parallel computing. I am mainly referring to models like Alternating Turing Machine, PRAM or NC-uniform equivalence (Boolean circuits) with some ...
- 1
0
votes
1
answer
41
views
Is a predecessor subgraph always connected?
Given an undirected graph $G$ with non-negative edge weights, how can we prove that the predecessor subgraph $G_{p}$ of $G$ is always connected?
Here's how the predecessor subgraph is defined: for a ...
- 33
0
votes
0
answers
15
views
Size of the page table
Question
Consider a system which has logical address is 7 bits, physical address is 6 bits , page size is 8 words, calculate the number of pages and no.of frames, size of page table.
Answer
Addressing ...
1
vote
0
answers
19
views
Toda's theorem without $\oplus P$
Toda's theorem says that the polynomial time hierarchy is contained in $P^{\#P}$, the class of problems solvable by polynomial time oracle Turing machines with access to an oracle in #P, which is the ...
- 413
1
vote
0
answers
18
views
Is it possible for a Linear bounded automaton to be a recognizer but not a decider?
So we know that LBAs have a finite number of configurations, which makes the task of detecting loops much easier. My proposition is that if a given LBA is constructed to recognize a language, it also ...
- 11