Computer Science Stack Exchange Community Digest

Top new questions this week:

Is there a faster way to solve the following problem?

$A$ is an array of length $n$ $B$ is an $n\times n$ matrix \ I want to return an array C of size n such that: $$C_{i} = \sum_{j=1}^{n} \max(0, a_i - b_{ij}) $$ In pseudocode it could be like ...

algorithms time-complexity  
user avatar asked by Macosso Score of 3
user avatar answered by D.W. Score of 28

Optimal algorithmic complexity of stack varient?

I'm wondering about the optimal complexity - or at the very least, some way of achieving non-terrible complexity - of a particular stack variant, that I'm calling a 'nonrepetitive stack'. A ...

time-complexity data-structures asymptotics  
user avatar asked by TLW Score of 2

Dijkstra as a greedy algorithm

I'm preparing some material for students about greedy algorithms, and there is one point that confuses me: how Dijkstra's algorithm fits into the greedy framework. I would like to say that we have ...

optimization greedy-algorithms dijkstras-algorithm  
user avatar asked by Dmitry Score of 2
user avatar answered by John L. Score of 2

How can we prove that Extract almost minimum operation in a priority queue cannot be done in o(logn)

Given a data structure with 2 operations: insert and extract almost min. Extract almost min operation outputs either the first minimum or a second minimum item from the current structure randomly. How ...

algorithms complexity-theory algorithm-analysis runtime-analysis priority-queues  
user avatar asked by JsonResponse Score of 1
user avatar answered by D.W. Score of 0

Having a 2D matrix with three typed elements, how to efficiently cover one of the types and NOT cover the other one?

I have a matrix with three possible elements: A, B and C. The size of the matrix could be a maximum of 15x16. $$ \begin{bmatrix} A & A & C & A\\ A & C & B & C\\ A & C & ...

algorithms matrices python  
user avatar asked by Predicate Score of 1
user avatar answered by D.W. Score of 0

Efficiently find the distance from a point to the decision boundary for assigning points to a particular $k$-means cluster

I have run $k$-means on a large set of high-dimensional data, and now I want to find the distance from a point $x$ to the Voronoi cell associated with one of the $k$ centroids. (In a previous version ...

algorithms computational-geometry clustering  
user avatar asked by gmr Score of 1
user avatar answered by V.V. Score of 1

Automatic differentiation - Upper bound time

Is there any proof or reference or intuition for the following theorem related to AAD: Any function f of n variables f(x1,...,xn) can be differentiated with respect to every variable xi at a ...

algorithms time-complexity  
user avatar asked by Glork Score of 1
user avatar answered by Glork Score of -1

Greatest hits from previous weeks:

The convoy effect in process scheduling

As I understand the convoy effect, in the context of vehicular traffic in a road system. A slow moving group of vehicles passes through the system, slowing traffic even in areas which were not ...

operating-systems process-scheduling  
user avatar asked by jsj Score of 7
user avatar answered by Ugnes Score of 9

What is most efficient for GCD?

I know that Euclid’s algorithm is the best algorithm for getting the GCD (great common divisor) of a list of positive integers. But in practice you can code this algorithm in various ways. (In my case,...

algorithms recursion arithmetic  
user avatar asked by Jonathan Prieto-Cubides Score of 33
user avatar answered by Gilles 'SO- stop being evil' Score of 28

Why is it best to use a prime number as a mod in a hashing function?

If I have a list of key values from 1 to 100 and I want to organize them in an array of 11 buckets, I've been taught to form a mod function $$ H = k \bmod \ 11$$ Now all the values will be placed ...

data-structures hash hash-tables primes  
user avatar asked by CodyBugstein Score of 99
user avatar answered by Mario Cervera Score of 116

What is the exact difference between a latch & a flipflop?

From what I have understood : A Flip Flop is a clocked latch i.e. flip flop = latch + clock Latch continuously checks for inputs & changes the output whenever there is a change in input Flip Flop ...

computer-architecture sequential-circuit digital-circuits  
user avatar asked by avi Score of 8
user avatar answered by Ran G. Score of 7

How do computers keep track of time?

How are computers able to tell the correct time and date every time? Whenever I close the computer (shut it down) all connections and processes inside stop. How is it that when I open the computer ...

computer-architecture clocks  
user avatar asked by Soham Score of 79
user avatar answered by D.W. Score of 113

Why is quicksort better than other sorting algorithms in practice?

In a standard algorithms course we are taught that quicksort is $O(n \log n)$ on average and $O(n^2)$ in the worst case. At the same time, other sorting algorithms are studied which are $O(n \log n)$ ...

algorithms sorting  
user avatar asked by Janoma Score of 369
user avatar answered by Sebastian Score of 254

What is the average turnaround time?

For the following jobs: The average wait time would be using a FCFS algorithm: (6-6)+(7-2)+(11-5)+(17-5)+(14-1) -> 0+5+6+10+13 -> 34/5 = 7 (6.8) What would the average turnaround time be?

algorithms operating-systems process-scheduling scheduling  
user avatar asked by Sheldon Score of 7
user avatar answered by Gilles 'SO- stop being evil' Score of 10

Can you answer these questions?

Sort array of 3D points to maximize number of tetrahedra in the array

Let $P$ be a indexable set(array) of points in $\mathbb{R}^3$ s.t. $P = \{p_0,p_1,p_2,...,p_n\}, p_i \in\mathbb{R}^3$. I want to sort $P$ so that every 4 consecutive points forms a non-coplanar ...

algorithms computational-geometry simplex  
user avatar asked by yosmo78 Score of 1
user avatar answered by Yves Daoust Score of 0

acceptance of non-recursively enumerable language by the Turing machine

I'd like to know if there's a non-recursively computable language that can be accepted by the Turing machine. From the following definition of the recursively enumerable language: and from the fact ...

turing-machines recursively-enumerable  
user avatar asked by obolenskaya00 Score of 1

Is this problem NP-hard ? (about arithmetic progressions)

Suppose there are n Arithmetic Progressions : Example : $$ AP1: a_1 = 1, d = 14 \\ AP2: a_1 = 8, d = 21 \\ :\\ :\\ APn: a_1 = X, d = X \\ $$ a1 = first term d = common difference and for each AP'...

np-complete np-hard np  
user avatar asked by uccu1573 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, 110 William Street, 28th floor, New York, NY 10038