# 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.

7,857 questions
Filter by
Sorted by
Tagged with
17 views

### Dynamic length of union of segments (1d Klee's measure problem)

Finding the length of union of segments (1-dimensional Klee's measure problem) is a well-known algorithmic problem. Given a set of $n$ intervals on the real line, the task is to find the length of ...
16 views

### Rectangle Packing with Constraints

I am aware that the general rectangle packing problem is NP-hard. I am trying to form an estimate for a version of the problem with constraints. Consider fitting rectangles of smaller size into a ...
12 views

### When do we would like to use array as the data structure in Dijkstra’s algorithm instead of heap for perfmance

When do we would like to use array as the data structure in Dijkstra’s algorithm instead of heap for performance gain ?
17 views

### Subset sum to 0/1 knapsack

How can I translate (i.e. reduce) an arbitrary instance $(S, t)$ of Subset Sum into an instance of 0-1 Knapsack? I'm also given a hint: you may assume that all members of $S$ are positive integers.
39 views

### Assign n people to m rooms of different sizes, such that noone is alone

I'm looking for an efficient way to assign n people to m rooms in a very specific way. INPUT: The program receives two sets of people (set of males and set of females), as well as a set of available ...
24 views

### NP Complete Clique Variation

I have the following problem I am trying to prove NP Complete. Tutors have two jobs- grading exams and homework help. Suppose we have a set of $n$ tutors. Each of them can tutor any amount of $m$ ...
37 views

### How do I use message passing to find the maximum of all values in a grid?

I am working on a problem. I have been tracing much more simple problems by hand, but I got this one and I am truly at a loss. I do not know how to research this to help me figure it out. I am truly ...
16 views

### How to maximize the number of filled grid squares in a partially filled grid with Tetris shapes

So here's the problem: -You are given a partially filled grid of size mxn (represented by a matrix of 1s and 0s where a 1 signifies that grid square is occupied by a block and a 0 signifies that grid ...
72 views

### Using a polynomial-time Boolean formula program to evaluate Boolean circuits [closed]

I'm new to learning about NP-Completeness. While it is very interesting to me, I am stuck on this exercise. Suppose your friend gives you a program they wrote which solves a Boolean formula in ...
38 views

### Which sort algorithm to choose given two specific arrays?

Interview question: Given array A which contains only odd numbers and array B which contains only even numbers, explain which sort algorithm would you choose. I said merge sort. I thought that ...
14 views

### Why maximum-matching algorithm falls into the category of fill-reducing algorithms?

My understanding is that "maximum matching" (or "maximum transversal") are algorithms to pre-order matrix to increase the numerical stability. In Timothy Davis' book Direct Methods for Sparse Linear ...
25 views

### Difference between a skiplist and an Indexable skiplist

Can someone please help me understand the main differences between a simple skiplist and an indexable skiplist? How does an indexable skiplist work in comparison to a normal skiplist (maybe a little ...
46 views

### Why is IDA$^*$ faster than A$^*$? Why does IDA$^*$ visit more nodes than A$^*$?

I used IDA$^*$ for optimally solving the 8-puzzle and my friends used A$^*$ for it too (with same manhattan distance heuristic). I calculated the average running time and number of nodes of my ...
33 views

### Finding a vertex coverage that is also an independent set

Given a graph $G$ and integer $k$, find a vertex coverage set of size $k$ that is also an independent set. I need to either prove this problem is np-complete or find a polynomial solution. Any idea?
24 views

### Deciding whether CFG generates the empty word

Give an algorithm to decide the following problem: given a CFG $G$, does $G\Rightarrow^\star \epsilon$? That is, given a grammar can it generate the empty word? How can I make sure my algorithm is ...
25 views

### Hanoi towers recursive expression for EVERY algorithm

What the recursive algorithm for moving $n$ disks says, is: If $n > 1$, move $n-1$ discs from A to B. Move the $n$th disk from A to C. If $n > 1$, move $n-1$ discs from B to C. Let $T_n$ be ...
34 views

### Network Flow - Minimum flow in a network

I have a directed graph G=(V,E) with a source s$\in V$ and a sink t$\in V$. There is a minimum capacity (lower bound) l $_{e}$ for each edge in G. There are no upper bounds on the edges. In a course ...
25 views

### Imperfection in randomness in VLC shuffle playlist - why?

Whenever I play a playlist of music using VLC (possibly other software too), I notice that some songs never get played while others get played repeatedly (even for a playlist of just 8 songs). I know ...
42 views

### Shortest path from $s$ to $v$ in unweighted simple directed graphs

Let $G=(V,E)$ be an unweighted simple directed graph. Some of the edges are colored red. Let $E'⊆E$ denote the set of red edges. Given a vertex $s∈V$,suggest an efficient algorithm for finding the ...
28 views

### How to check whether given $k$ vertices make a $k$-clique in an undirected graph $G$ efficiently

Let $G=(V, E)$ be an undirected graph with vertex set $V$ and edge set $E$. Let $V'=\{v_1, v_2, ..., v_k\}$ be a subset of $V$ where degree of each $v_i$ is bigger than or equal to $k$. Is there a way ...
28 views

### Which Graph Algorithm should I use to find all possible groups in a graph?

I have the following situation: (Alex, Bob) (Alex, Charlie) (Debra, Erika) Imagine that each row in the list represents a friendship. Alex is friends with Bob. Alex is friends with Charlie. And ...
19 views

### Build a histogram from a very large data sample

I want to calculate a histogram from an array of size N. N is very large. I know 2 ways to do so: The naive approach is to ...
25 views

### Upper (or lower) envelope of some linear functions

Given some single variable linear functions $y_1=m_1x+b_1$, $y_2=m_2x+b_2$, $\ldots$, $y_n=m_nx+b_n$, the upper envelope is the function $f(x)= \max \{y_1, \ldots, y_n\}$. We know that this function ...
46 views

66 views

### Given undirected and connected graph G=(V,E). Prove for any DFS run: for any u,v∈V if u.d>v.d then u.d−v.d≥δ(u,v)

Given undirected and connected graph $G = (V,E)$. Prove for any DFS run: for any $u,v \in V$ if $u.d>v.d$ then $u.d − v.d ≥ δ(u,v)$ $δ(u,v)$-distance of a shortest path (not necessarily unique) in ...
25 views

### Determine aproximation factor in a greedy algorithm

Suppose we have n food dishes associated to a cost c, and we have i guests such that each one of them has a certain number of preferences. We want to choose a menu such that we minimize the cost and ...
62 views

### Hausdorff distance between two binary images according to distance maps

I want to compute the Hausdorff distance between two (very large) binary images X and Y, which is: $$H(X,Y) = \max\left\{\,h(X,Y), h(Y,X)\right\}\!$$ with h(X,Y) = \sup_{x \in X} \inf_{y \in Y} d(...
106 views

### How do I reduce subset sum to another problem in NP?

I'm trying to solve the following problem about arranging pens on rows. The problem goes as the following. Given $n$ integers $l_1, \dots l_n$, the lengths of the pens, r rows and a goal G. Is it ...
19 views

### What is a non-procedural algorithm?

I have heard a term "procedural algorithm" before so I'm curious what would constitute a non-procedural algorithm? Are there any examples? As far as I understand, there are maze generation algorithms ...
20 views

### What's the correct algorithm to filter accumulating string concatenations?

I have a function that is receiving messages with the following pattern: (In this picture, "string" and "message" are synonymous.) I'm only interested in the largest messages, such as these: over a ...
45 views

### Traversing the edges of a labeled 2-regular graph based on a binary string

Let $G$ be a $2$-regular graph. Each edge of the graph is labeled with either 0 or 1. Given a such a graph and a staring vertex $u$ and $l$ length string of 0 and 1, we have to follow the edges of the ...
200 views

### Stack Permutation Algorithm

I was recently designing a Forth stack machine. I have an atomic instruction which rotates the top N elements. For example if the top of the stack is on the left, then say the N=3 rotate instruction ...
49 views

### Divide and Conquer a problem into a sub-problem to solve it efficiently

Assume that problem A cannot be solved in O(n^2) time. However, we can transform problem A into a problem B in O(n^2 log n) time, and then solve B, and finally transform the solution of B into the ...
28 views

### Converting non-deterministic algorithm to deterministic

I was thinking about an non-deterministic algorithm to generate all the subsets of the $\{1..n\}$ set. ...
Solve the recurrence $T_n = 4T_{n+2} + n + 1$ where $T_1 = 0$ for $T_i = 1, 2 ... 16$