# Questions tagged [algorithm-design]

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

25 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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

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