# Questions tagged [algorithms]

An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to design and analysis of algorithms.

8,837 questions
Filter by
Sorted by
Tagged with
30 views

### Median of distribution with memory constraint

Task I want to approximate the median of a given distribution $D$ that I can sample from. A simple algorithm for this, using $n$ samples, is: ...
47 views

### Dynamic Programming - Tiling Question

I came across the following question while practising for my final algorithms exam, but I am unsure how to get a linear time complexity for this problem. I assumed it would require checking which ...
68 views

43 views

### How to answer the following queries on a tree?

Given a tree of "N" nodes(each node has been assigned a value A[i],node-"1" is the root of the tree), and a constant "K" , we have Q queries of the following type : [w] (...
14 views

### Encoding a arbitrary stack trace into a fixed length value

Background I would like to store the nodes of a Calling Context Tree using in a key value store. I need to be able to directly access a node by it's method name and complete stack trace. In addition ...
34 views

### Reconstructing an Array via Time-Intensive Subset Queries

I am trying to design an algorithm for a problem, and the following is an auxiliary problem for which a good solution would imply a faster algorithm for the original problem. I am given access to an ...
38 views

### How do you convert an NP problem which runs in O(f(x)) time in a SAT instance with O(f(x)*log(f(x))) variables in O(f(x)*log(f(x)))

I looked at the Cook's theorem at Wikipedia which presents a way to convert any NP problem to SAT but it seems to require O(f(x)^3) variables. Is it possible to remove some of the checks in the ...
15 views

### Interval scheduling problem implementation

I am learning the Interval scheduling problem, and I came up after some reading with an implementation. I'll list my steps and the code, please let me know if this is correct or there is a more ...
67 views

### Algorithm to compute average length of a simple path

Given a connected graph and two nodes s and t, there can be many different simple paths (without cycles) from s to t. Is there an efficient algorithm to find the average length of these paths?
104 views

### Time taken by virus to reach all nodes

Given a connected graph, with weighted edges, a virus starts from a given node. It takes x seconds for the virus to travel from a node to one of its neighbours where x is directly proportional to the ...
40 views

### I'ld like a better algorithm for scheduling tutors to fill a set of shifts

My problem is as follows: I have a set of shifts at various locations that need to be filled by tutors. A simple example would be basic math in room A on M, W, F from 9-11am and Sa from 12-3 pm. ...
61 views

### Is there a way to determine whether a list of integers can be a prefix function?

Say you had (0,0,0,1,2,3,4,5,6,7,8,9,10) or (0,1,0,1,0,1,2,3,0,1,0,0,1) Could you use, for example, the KMP algorithm to deduce the validity of the above lists as prefix functions? I know there is a ...