Questions tagged [algorithm-design]
Questions related to general, high level, techniques for the design of algorithms.
25
questions with no upvoted or accepted answers
5
votes
2
answers
201
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/...
- 101
4
votes
0
answers
161
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 ...
- 209
3
votes
0
answers
34
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 ...
- 153
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 ...
- 693
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-...
- 327
1
vote
1
answer
33
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-...
- 11
1
vote
0
answers
92
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 ...
1
vote
0
answers
66
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 ...
- 111
1
vote
2
answers
68
views
Comparing Registers with 16-bits
I am given with this information:
"CMP OP1,OP2 will compare registers OP1 and OP2 if they are equal,
flag values will be ZF=1, CF=0,
if the first
operands value is greater flag values will be ZF=...
1
vote
0
answers
44
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 ...
- 940
1
vote
0
answers
120
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 ...
- 453
1
vote
2
answers
137
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{...
1
vote
0
answers
598
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 ...
- 175
1
vote
0
answers
798
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 ...
0
votes
0
answers
222
views
Divide and conquer problem
Problem:
Given a set of n intervals I = [a1, b1],[a2, b2], . . .[an, bn]. Here ai < bi for all i = 1
to n. Devise a Divide and Conquer algorithm to compute the length of the biggest
overlap between ...
- 1
0
votes
0
answers
21
views
Is there a design pattern or an algorithm for working adaptively to the load?
I want to make a program which is adaptive to CPU load.
For example, My program A works in state a which uses resources in best ...
- 11
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 ...
- 1
0
votes
0
answers
97
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 ...
- 1
0
votes
0
answers
77
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 $\{...
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-...
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 ...
- 1
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.
...
- 155
0
votes
0
answers
276
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 ...
- 1
0
votes
0
answers
17
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 (...
- 131
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-...
- 101