Questions tagged [algorithm-design]

Questions related to general, high level, techniques for the design of algorithms.

23 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5 votes
2 answers
202 views

Decomposing an Algorithm into Local Transformations/Perturbations

Is it common to try to improve an algorithm by decomposing its action on a topological piece of data (e.g. graphs, geometric data) into a series of steps, each of which only makes a local change/...
Herng Yi's user avatar
  • 101
4 votes
0 answers
207 views

Arrange objects in space so that the outline takes the least surface/volume

Imagine you have a number of 2-dimensional objects. The question is how to fit them all in a rectangular space in such a way that this rectangle takes the smallest area possible. On the below image ...
alex's user avatar
  • 209
3 votes
0 answers
37 views

Suggestions for a source of algorithm design problems?

I’m finishing up Roughgarden’s two-part algorithms course on edx, and it was good, but I didn’t actually ‘design and analyze’ many algorithms, the questions mostly tested whether you understood the ...
Adam Tolnay's user avatar
2 votes
0 answers
40 views

Is it correct to say that there are similarities between CORDIC and digit recurrence algorithm for division?

I've been studying recently some variations of the CORDIC, and it seems to me that the logic behind at least the basic cordic or the redundant CORDIC is very similar to the logic used to design digit ...
user8469759's user avatar
2 votes
1 answer
57 views

Counting permutations whose elements are not exactly their index ± 1

This is a special case of the question: Counting permutations whose elements are not exactly their index ± M The $M=0$ case has already been solved, but no one was sure how to work out the non-...
PPenguin's user avatar
  • 327
1 vote
0 answers
34 views

How do I optimally fuse nodes in a tree structure?

I am trying to solve the following problem. I've tried to find the name of this problem, but could not really find what I was looking for. I assume there should be some graph-theory that covers it, ...
RunOrVeith's user avatar
1 vote
1 answer
43 views

Algorithm design: Model redundancy in tests

I've run across an interesting problem at work that I'm not quite sure how to grapple. Broadly, there is a suite of of $n$ tests to ensure the quality of a product. However, the tests are both time-...
lyberius's user avatar
1 vote
0 answers
105 views

Is the minimum spanning tree a minimum-altitude connected subgraph

I'm not sure if my solution to the following problem (adapted from Exercise 20, Chapter 4 of Algorithm Design by Jon Kleinberg and Éva Tardos) is correct. I would appreciate it if anyone could point ...
Eduardo Fernandez's user avatar
1 vote
0 answers
115 views

Sub-matrix with minimum size of $k$ and minimum sum

We have an $n \times m$ matrix whose entries are non-negative integers and we want to find a sub-matrix whose area (number of entries) is at least $k$ such that the sum of the entries in minimal. The ...
Pegi's user avatar
  • 111
1 vote
0 answers
61 views

Abstract algebra algorithms

Let’s make a big list of algorithms relying on abstract algebra. This will help us see how ubiquitous algebra is in algorithm design. I’ll start with two: one is the General Number Field Sieve, the ...
Zirui Wang's user avatar
1 vote
0 answers
160 views

Intersection of line segments induced by point sets from fixed geometry

I am reading up on algorithms and at the moment looking at the below problem from Jeff Erickson's book Algorithms. I solved (a) by seeing a relationship to the previous problem on computing the ...
spektr's user avatar
  • 453
1 vote
2 answers
157 views

Mutli-Path Collision Avoidance

I need an algorithm which can do the following: Given some finite number of particles (circles) each with the same radius, and a list of prescribed points for each particle, find paths in $\mathbb{...
JJJJJJJJJJJJJJJJ's user avatar
1 vote
0 answers
633 views

Non-deterministic Turing Machine recognizing a context-free Language

This question is taken from an exam of a Computer Theory Course. Describe how a NON-Deterministic Turing Machine with two tapes recognize the language generated from the grammar: $ S \rightarrow SS ...
Jack's user avatar
  • 175
1 vote
0 answers
826 views

Designing bidirectional search algorithm

Write down the algorithm for bidirectional search, in pseudo-code. Assume that each search will be a breadth-first search, and that the forward and backward searches takes turns expanding a node at a ...
Revolucion for Monica's user avatar
0 votes
0 answers
32 views

Understanding the step in given algorithm?

I am a newbie to the world of algorithms design and currently working on a algorithm which is related to cell-phone user associating with cell-phone tower. Let $\mathcal{K} = \{1,\dots,K\}$ be set of ...
chaaru's user avatar
  • 1
0 votes
0 answers
221 views

Algorithm question: Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1

Algorithm question: Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1. Example 1: Input: [0,1] Output: 2 Explanation: [0, 1] is the longest ...
ayuken's user avatar
  • 1
0 votes
0 answers
112 views

Counting number of sequences summing to target

This is a problem that I have been struggling to understand in a theoretical computer science book I've been reading: We call a sequence of $n$ integers $x_1, \dots, x_n$ valid if each $x_i$ is in $\{...
Satish Rao's user avatar
0 votes
0 answers
72 views

Doubt on integrality gap and LP relaxation

I have an exercise that tells me that, given a problem P (of which now I omit the description) there is no integrality gap between LP and ILP formulation of this problem, and for every fractional LP-...
bruce_springsteen's user avatar
0 votes
0 answers
19 views

How to divide services and capacities in a graph?

Given a graph where some nodes can provide some services with x,y,z... capacities. A node connected to multiple nodes needs to divide these services to the connected nodes and these nodes themselves ...
Ley Big's user avatar
0 votes
0 answers
42 views

Trouble Convincing Myself Algorithm Correctness

I'm having a tough time convincing myself right when coming up for some solutions to medium/hard leetcode.com problems. Take the following question for example. ...
Adam Thompson's user avatar
0 votes
0 answers
286 views

Implementing supplies in Coin change problem

I started an algorithm course in C two months ago, for the last weeks I've been trying to solve this problem , i ran out of time but I cannot find an acceptable solution. Basically It's a coin change ...
mark's user avatar
  • 1
0 votes
0 answers
18 views

Without sound synthesis, what is a good way of making a program that plays guitar notes from an array of stored sounds?

Without sound synthesis, what is a good way of making a program that plays guitar notes from an array of stored sounds? What I have in mind is to make note as a function of vibration speed such as N (...
Raed Tabani's user avatar
0 votes
1 answer
4k views

Is there Any difference between dynamic programming vs branch-bound vs delayed column generation

I was reading about cutting stock problem https://en.wikipedia.org/wiki/Cutting_stock_problem , this is best solved using dynamic programming but wiki page mentions 2 other techniques names Branch-...
Lalita Kumar's user avatar