All Questions

Filter by
Sorted by
Tagged with
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 ...
achhainsan's user avatar
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, ...
Hugh Mann's user avatar
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 ...
PerseP's user avatar
  • 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, ...
Nicholas Humphrey's user avatar
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.
Splendid Digital Solutions's user avatar
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 ...
Almog David's user avatar
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. ...
Akash Ram's user avatar
-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 ...
Cerise's user avatar
  • 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 ...
emily-cs's user avatar
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 ...
Sam's user avatar
  • 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 ...
silass0's user avatar
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 ...
Kong's user avatar
  • 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 ...
meeeeee's user avatar
  • 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} = \...
Zeeshan ahmed's user avatar
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 ...
Jeff's user avatar
  • 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 ...
Kingdom Mutala Akugri's user avatar
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{...
Zeeshan ahmed's user avatar
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 = ...
carlos palma's user avatar
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-...
user's user avatar
  • 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 ...
tistorm's user avatar
  • 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 ...
user877329's user avatar
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) ...
Zagatho's user avatar
  • 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 ...
MNM LOLO's user avatar
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, ...
Barney's user avatar
  • 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 ...
phuck's user avatar
  • 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: ...
user163191's user avatar
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 ...
Daniël van den Berg's user avatar
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 ...
alim's user avatar
  • 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 ...
Edward Shanahan's user avatar
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?
Yandle's user avatar
  • 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,...
wsz_fantasy's user avatar
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.) ...
IamA's user avatar
  • 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", "...
Kaarthik Ananthanarayanan's user avatar
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 ...
parsingstreet's user avatar
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 ...
ABC's user avatar
  • 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 ...
Fraïssé's user avatar
  • 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) ...
CaptainHow's user avatar
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 ...
kaddy's user avatar
  • 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 ...
Pixeled's user avatar
  • 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 ...
Geremia's user avatar
  • 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 ...
Colonizor48's user avatar
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 ...
pyridoxal_trigeminus's user avatar
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 ...
Juraj Fiala's user avatar
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.
enerneo's user avatar
  • 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 ...
bipartite's user avatar
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 ...
Eduardo's user avatar
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 ...
Hugh Mann's user avatar
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 ...
Saket Singh's user avatar
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 ...
user6767509's user avatar
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 ...
Aland Ameer's user avatar

15 30 50 per page
1
2 3 4 5
948