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.

Filter by
Sorted by
Tagged with
3
votes
1answer
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 ...
4
votes
0answers
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 ...
0
votes
0answers
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 ?
1
vote
1answer
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.
4
votes
0answers
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 ...
1
vote
1answer
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$ ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
-1
votes
0answers
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?
0
votes
0answers
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 ...
1
vote
0answers
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 ...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
0
votes
2answers
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 ...
2
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
0
votes
0answers
46 views

Does this algorithm sort in worst-case time-complexity $\mathcal O (n)$?

It has always buggered me that sorting in $\mathcal O (n)$ is not possible and I've been thinking about it from time to time. So, I've had an idea but am not really sure if it really can sort in $\...
-1
votes
0answers
28 views
+50

Selecting elements from two array to get the target sum

Let $A$ and $B$ are two arrays of size $n$ with positive integer values and let $k$ be any positive integer. Design an algorithm to solve the following problem. For each index $i$ ($1\leq i \leq n$)...
5
votes
1answer
134 views

Using decision oracle to solve optimization problem of maximum polyomino tiling

So, this problem is a kind of variant of polyomino packing which has been discussed frequently elsewhere, but I haven't been able to find anything on my particular problem. Suppose we have a list of ...
2
votes
1answer
21 views

Algorithm for creating n-multiset out of x?

I have a problem that can be modelled by 15 undistinguishable balls to 21 boxes. The state of a node is defined by indices from 1 to 21 and corresponding values from 0 to 15, with the constraint that ...
3
votes
1answer
54 views

Minimum XOR for queries

I was asked the following question in an interview. Given an array $A$ with $n$ integers and an array $B$ with $m$ integers. For each integer $b \in B$ return and integer $a \in A$ such that $a \...
2
votes
0answers
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 ...
2
votes
1answer
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 ...
3
votes
1answer
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(...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
8
votes
4answers
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 ...
0
votes
1answer
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 ...
1
vote
1answer
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. ...
0
votes
0answers
12 views

What is the answer for this recurrence? Is there a way to solve it? How? @

Solve the recurrence $T_n = 4T_{n+2} + n + 1$ where $T_1 = 0$ for $T_i = 1, 2 ... 16$
0
votes
1answer
26 views

Heap down - What is math logic and intuition behind $\sum_{i=1}^{log(n)}(logn - i).2^i $

In heap (bubble down) we have the formula : $\sum_{i=1}^{log(n)}(logn - i).2^i = logn\sum_{i=1}^{log(n)}2^i -logn\sum_{i=1}^{log(n)}i.2^i = log𝑛.2^{log𝑛+1}-(log𝑛.2^{log𝑛+1}-(2^{log𝑛+1}−2))=2𝑛−...
0
votes
0answers
16 views

Sort arrays with out merging

I have a data-set which contains more than two arrays. I would like to sort the data-set with out merging the arrays to a single array. Arrays may or may not be in same machine. I am looking for an ...
2
votes
1answer
24 views

Clarification about conclusion of $Θ(nlogn)$?

Why the first part of formula is equal to $2 * 2^2 + ... + 2^{log(n)} = 2^2 + 2^3 +...+ 2^{log(n)} = 2^3 +...+ 2^{log(n)} =... +2^{log(n)}$ What is the logic behind ($2^{log n +1} - 2{log n}$) ? I ...
0
votes
1answer
29 views

What is the time complexity in solving a polynomial equation of degree N in one variable?

How easy/difficult(in terms of big-O) is it to solve polynomial equations of high degrees of N? Do apps like Desmos actually solve equations to get roots or do they approximate roots by iterating ...
-1
votes
0answers
16 views

I want to create an unsigned 8-bit adder/substractor and implement it in a logic circuit [closed]

I am having a hard time trying to implement an adder for 8-bits unsigned numbers with 1's complement but without using VHDL since I am new to this kind of stuff. But I know that I should use 8 full ...
3
votes
1answer
87 views

Grover's algorithm on probabilistic classical machines

As a starting point for this question, I came across this question, which AIUI is citing a construction showing how to simulate quantum circuits with a $PP$ algorithm, i.e. implying quantum ...
2
votes
1answer
42 views

Is there a well-known algorithm for arranging inputs according to their category?

Background: (I’m a complete beginner in computer science in general, so I do apologise if my question is not formulated in a sensible way. E.g. I have avoided technicalities in formulating my ...
1
vote
0answers
16 views

Practice question on the applications of flows and cuts

This question is from Erickson's textbook on algorithms, p. 376, question 18. Faced with the threat of brutally severe budget cuts, Potemkin University has decided to hire actors to sit in ...
0
votes
0answers
14 views

Optimization problem (maximize output)

Problem I have an optimization problem, where I want to find the value of parameters X1, X2 ... Xn which will give the highest output Y. Variables Several X variables are dependant. For example, ...
0
votes
0answers
14 views

Inverse of Burrows-Wheeler

We can invert the Burrows-Wheeler with this method: The inverse can be understood this way. Take the final table in the BWT algorithm, and erase all but the last column. Given only this ...
0
votes
0answers
29 views

Weight of minimum spanning tree of G and T

We have undirected weighted connective graph $G=(V,E)$, We also have a minimum spanning tree $T$ of $G$. Let $v$ be some vertex. We have new graphs, $G'$ and $T'$. $G'$ and $T'$ are same $G$ and $T$, ...