## 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
 asked by Macosso Score of 3
 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
 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
 asked by Dmitry Score of 2
 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
 asked by JsonResponse Score of 1
 answered by D.W. Score of 0

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  asked by Predicate Score of 1  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  asked by gmr Score of 1  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  asked by Glork Score of 1  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  asked by jsj Score of 7  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  asked by Jonathan Prieto-Cubides Score of 33  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  asked by CodyBugstein Score of 99  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  asked by avi Score of 8  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  asked by Soham Score of 79  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  asked by Janoma Score of 369  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  asked by Sheldon Score of 7  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  asked by yosmo78 Score of 1  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  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
 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, 110 William Street, 28th floor, New York, NY 10038

 <3