Computer Science Stack Exchange Community Digest

Top new questions this week:

Prove that $n$ is a time-constructible function

I am reading Arora and Barak's book: "Computational Complexity: A Modern Approach". On page 16, the authors wrote: A function $T: \mathbb{N} \rightarrow \mathbb{N}$ is time constructible if ...

complexity-theory time-complexity turing-machines  
user avatar asked by Wei-Cheng Liu Score of 4
user avatar answered by Bader Abu Radi Score of 1

Is this a potentially more intuitive approach to MergeSort?

I have read at least one other post (perhaps not on this stackexchange) that asks essentially: Why do we have to break up the array into successively smaller arrays until we finally reach the bottom (...

algorithms mergesort  
user avatar asked by releseabe Score of 4
user avatar answered by ratchet freak Score of 8

Are these two definitions related to strong NP-hardness equivalent?

Let $P$ be a computational problem whose inputs are integers. Consider the following properties: (a) There exists a polynomial-time reduction from some strongly-NP-hard problem $Q$ to $P$. (b) $P$ is ...

reductions np-hard integers polynomial-time-reductions  
user avatar asked by Erel Segal-Halevi Score of 4
user avatar answered by ttnick Score of 2

Is 3, 3 satisfiability trivial after all?

Tovey's paper from 1982 clearly states that: Theorem 2.1. Boolean satisfiability is NP-complete when restricted to instances with 2 or 3 variables per clause and at most 3 occurrences per variable. ...

np-complete satisfiability  
user avatar asked by nonsensical world Score of 4
user avatar answered by Noah Schweber Score of 8

Binary search tree with height of max 1.44 * log(n) is AVL tree or it's not an iff

Assume I have a binary search tree, and I managed to prove that its height is upper bounded by $1.44 \log(n)$. Now, can I say with confidence that it is, for sure, an AVL tree? or is this condition ...

data-structures binary-search-trees avl-trees  
user avatar asked by DaniDin Score of 3
user avatar answered by Ashwin Ganesan Score of 6

Is the definition of "computational problem" on Wikipedia correct?

In the https://en.wikipedia.org/wiki/Computational_problem, the first line states: "A computational problem is a problem that may be solved by an algorithm." However, I have doubts about the ...

algorithms complexity-theory computability decision-problem  
user avatar asked by pabloealvarez Score of 3

Proving that $T(n)=16T\left(\frac{n}{4}\right)+n! \in \Theta(n!)$

I am trying to prove that $T(n)\in\Theta(n!)$ for the following recurrence using the master theorem: $\qquad T(n) = 16T\left(\frac{n}{4}\right)+ n!$ My attempt We have that $f(n) = n! \in \Omega(n^{\...

time-complexity master-theorem  
user avatar asked by z.. Score of 3
user avatar answered by Chenyang Score of 3

Greatest hits from previous weeks:

Construct DFA accepting strings ending with '110' or '101'

Let the alphabet be $\Sigma=\{0,1\}$. I want to construct a DFA which accepts strings ending with either '110' or '101', additionally there should be only one final state. I have a solution with more ...

automata finite-automata  
user avatar asked by M.Usman Score of 2
user avatar answered by Yuval Filmus Score of 5

Longest path in an undirected tree with only one traversal

There is this standard algorithm for finding longest path in undirected trees using two depth-first searches: Start DFS from a random vertex $v$ and find the farthest vertex from it; say it is $v'$. ...

algorithms graphs trees  
user avatar asked by e_noether Score of 48
user avatar answered by Raphael Score of 25

What is the difference between user-level threads and kernel-level threads?

After reading several sources I'm still confused about user- and kernel-level threads. In particular: Threads can exist at both the user level and the kernel level What is the difference between ...

operating-systems terminology concurrency os-kernel  
user avatar asked by Sheldon Score of 34
user avatar answered by Gilles 'SO- stop being evil' Score of 30

Why is binary search faster than ternary search?

Searching an array of $N$ elements using binary search takes, in the worst case $\log_2 N$ iterations because, at each step we trim half of our search space. If, instead, we used 'ternary search', we'...

algorithms algorithm-analysis runtime-analysis search-algorithms binary-search  
user avatar asked by The Mean Square Score of 60
user avatar answered by DCTLib Score of 87

How to prove greedy algorithm is correct

I have a greedy algorithm that I suspect might be correct, but I'm not sure. How do I check whether it is correct? What are the techniques to use for proving a greedy algorithm correct? Are there ...

algorithm-analysis proof-techniques correctness-proof greedy-algorithms  
user avatar asked by D.W. Score of 50
user avatar answered by D.W. Score of 45

Mathematical benefit to use CPU/memory that increases by powers of 2 as 8-bit, 16-bit, 32-bit, 64-bit, etc?

Historically, processors often increase in bit-size by powers of 2, such as 8-bit, then 16-bit, 32-bit, 64-bit. Although this has not always been the case, it is a well known trend. One benefit is ...

cpu history  
user avatar asked by BipedalJoe Score of 10
user avatar answered by Peter Cordes Score of 11

Absorption Law Proof by Algebra

I'm struggling to understand the absorption law proof and I hope maybe you could help me out. The absorption law states that: $X + XY = X$ Which is equivalent to $(X \cdot 1) + (XY) = X$ No problem ...

boolean-algebra  
user avatar asked by user2635139 Score of 7
user avatar answered by Andrej Bauer Score of 10

Can you answer these questions?

Stuck reading "Optimal Biweighted Binary Trees and the Complexity of Maintaining Partial Sums"

I am reading the paper titled "Optimal Biweighted Binary Trees and the Complexity of Maintaining Partial Sums", and I am stuck on theorem 2.1, I believe it is wrong, the proof has a wrong ...

lower-bounds  
user avatar asked by Cecilia Chen Score of 1

Interactive Proof for Graphs with No Non-Trivial Automorphisms

I am looking for an interactive proof for the language $AUTO^C= \{𝐺∣\text{𝐺 is an undirected graph that has no non-trivial automorphisms} \}$. I am interested in a method similar to the interactive ...

complexity-theory graph-isomorphism interactive-proof-systems  
user avatar asked by user171912 Score of 2
user avatar answered by QuantumEnigma Score of 0

Equivalence of two approaches for sparsity

I am trying to understand whether the following two ways to achieve a sparse matrix are equivalent in Pytorch. Let me add some context: I am training Sparse Neural Networks with a specific structured ...

machine-learning neural-networks  
user avatar asked by Abhishek Tyagi Score of 1
You're receiving this message because you subscribed to the Computer Science community digest.
Unsubscribe from this community digest       Edit email settings       Leave feedback       Privacy
Stack Overflow

Stack Overflow, 14 Wall Street, 20th Floor, New York, NY 10005

<3