Questions tagged [algorithm-design]
Questions related to general, high level, techniques for the design of algorithms.
94
questions
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-...
D.W.♦
- 152k
2
votes
2
answers
61
views
The awkward status of Mersenne Twister
Random number generators generally fit into 3 categories IMO:
ad-hoc designs serving as stub to be replaced by something else if this ever happens,
considerate designs aiming at achieving statistical ...
- 20.3k
0
votes
2
answers
129
views
How can I find 2 median values of an array which is an union of 2 arrays in O(log n)?
So I have 2 sorted arrays which will have the same length and what I need to do is sort the union array (the union of the two sorted arrays) and then find two median values, I need to do this in O(log ...
- 136
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{...
CommunityBot
- 1
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=...
CommunityBot
- 1
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
1
vote
1
answer
36
views
Beginning Algorithm Design and Proving
I know this is a general question, so you can address this by giving some examples that are specific to your field.
I want to start learning algorithm design and consequently prove its convergence. ...
D.W.♦
- 152k
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
1
vote
1
answer
23
views
An algorithm to evaluate the strength of Quiz Participants
As a side-project, I had the idea to write some kind of an algorithm that would evaluate all participations in our weekly Pub quiz, to then calculate the average strength of the participants.
This is ...
D.W.♦
- 152k
0
votes
2
answers
51
views
Are there any guidelines on how to decide algorithm strategy when approaching a problem?
There are many different general strategies when designing algorithms for a problem like divide and conquer, greedy, dynamic programming, etc. I understand that it is not always obvious which to use ...
-2
votes
1
answer
37
views
How to design algorithm
I am a newbie to algorithm designing. I am working on user association and load balancing algorithm designing in millimeter wave wireless communications.
In this topic I am able to formulate the ...
- 27.4k
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
1
vote
1
answer
89
views
3-colouring with a bounded amount of colors
The topic of 3-colouring is often talked about, but what happens if we limit the amount of times we can use one color? Take a graph $G=(V,E)$ with $k$ being the number of vertices, is it possible for ...
- 12.1k
3
votes
1
answer
69
views
Fast algorithm for computing minimal closure of a set of sets under intersection?
A step of an algorithm I’ve designed requires computing the minimal closure under intersection of a set of sets of arbitrary size. By the "minimal closure (of a set $S$) under intersection", ...
D.W.♦
- 152k
1
vote
1
answer
38
views
Fingerprint functions for set equality checks?
Given I have two sets of objects $A =\{a, b, c\}$ and $B = \{a, b, c, a\}$
Based on the set equality, I want the fingerprint of these sets to be the same $F(A) = F(B)$.
Additionally I want to be able ...
D.W.♦
- 152k
0
votes
1
answer
49
views
Queue for two types using 2 queues?
I'm reading the book Cracking the Code.
The answer for this question suggests a solution using timestamps and two separate queues. This is straightforward and involves simply enqueuing into the ...
- 376
1
vote
1
answer
48
views
What are the reasons for solution assumptions behind the longest subsequence problem?
All O(N^2) solutions that I have seen for the longest increasing subsequence problem, as their first step, state something like this "Let L[i] be the length of the LIS ending at index i...":
...
- 38.3k
1
vote
1
answer
1k
views
Josephus Problem - A faster Solution
I came through Josephus problem a little while ago. Problem is stated as follows :
"People are standing in a circle waiting to be executed. Counting begins at a specified point in the circle and ...
CommunityBot
- 1
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 ...
0
votes
2
answers
606
views
no of times partion is called in quick sort, assuming array is always halved
In the most even possible split, PARTITION function produces two subarrays, each of size no more than n/2. since one is of size floor(n/2) and one of size ceil(n/2)-1.
The recurrence for the running ...
- 26.5k
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 ...
- 274k
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 ...
- 5
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 $\{...
- 274k
0
votes
1
answer
64
views
Algorithm for sorting within windows
I am writing an app which displays speeches on various topics, with each speech having a number of attributes. I want to give the user the choice to sort a list of speeches by an attribute, even ...
- 4,491
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
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
6
votes
2
answers
1k
views
How to Match Socks
When I do my laundry I tend to make a pile of unmatched socks, putting new socks on the top of the pile and matching off pairs if two of the same sock are near the top of the stack. Since eventually ...
CommunityBot
- 1
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
1
answer
205
views
Partition the indices of 2d array to minimize sum of sub-matrices
Given an $n\times n$ Matrix $M$, and the indices $[{1,2,3,4,...,n}]$ are divided into several intervals : $[1,x_1],[x_1,x_2],...[x_k,n]$, which further extract several squared sub-matrices along the $...
- 450
1
vote
1
answer
75
views
Multi-Path Length Minimization
I've been thinking about path planning and am trying to make good heuristics for cases with multiple agents.
Suppose there are sets $S_i$ of coordinates in $\mathbb R^2$ or $\mathbb R^3$, each of the ...
1
vote
1
answer
86
views
"Searching and sorting" algorithm to find the natural logarithim of a number?
Yeah, this is for a homework assignment, but I hope that you'll humor me anyway. I am asked to design an algorithm that finds the natural logarithm of a number. This would be straightforward, but I'm ...
- 12.5k
1
vote
1
answer
70
views
Finding lost bottle (algorithm problem)
The question is as follows:
A scientist creates a new compound, called compound A, that will explode 10 days after being mixed with compound B. This compound A was stored in a label-less bottle on ...
- 4,358
2
votes
1
answer
1k
views
Maximum number of similar groups of a given size that can be made from a given array
I am given an array of numbers, not necessarily unique, and the size of a group. Let the array be denoted by $B$ and the size of the group be $A$.
I need to find the maximum number of groups with the ...
- 4,358
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-...
1
vote
1
answer
93
views
Is it possible to estimate the step size and walking velocity of different person with the x-y-z acceleration data from 6 axial accelerometer sensor?
I have a 6-axial sensing device used to record the acceleration data. There is an algorithm used to count the number of step and walking distance of the user, but I want to further increase the ...
- 3,443
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
1
vote
1
answer
61
views
design cache system using queuing theory
If we have data from a random population, a 3d histogram of throughput and current cache size of DRAM (intersection of a IOPS & a cache size will have a count). How can one use queuing theory to ...
CommunityBot
- 1
1
vote
2
answers
126
views
Lexicographic permutation list
Does anyone have an algorithm for stepping through all permutations of n given arbitrary objects in lexicographic order?
Thanks.
2
votes
1
answer
151
views
Given an array of size n, create a sub array with given conditions using dynamic programming
We are given an array of integers of size n, which is not necessarily sorted, and we want to create a sub array. We are allowed to do one of 3 tasks below in each level:
1. skip the number in original ...
- 38.3k
3
votes
1
answer
543
views
Can a greedy algorithm have more than one subproblems to solve after making greedy choice?
For example:
s = <s1 s2 s3> is my problem,
I make greedy choice s2 and solve s1 and <...
CommunityBot
- 1
2
votes
1
answer
606
views
Greedy algorithm for even item distribution
I have this problem where I need to design a greedy algorithm. The problem is as follows:
A chocolate factory owns $n$ stores, which are connected by a single road. Each store has a limited supply $...
- 38.3k
4
votes
1
answer
60
views
Finding max value algorithm with subset comparison
I have a set of $N$ different values, and my goal is to find the biggest one in the least number of comparisons. Comparing subsets (using the sum of each) is also allowed, and counts as one comparison....
- 274k
7
votes
1
answer
19k
views
Implementation of QuickSort to handle duplicates
I have this past year question based on the following scenario:
When the list of items to be sorted contains a lot of duplicate values, we can improve QuickSort by grouping all the values that are ...
- 38.3k
3
votes
1
answer
296
views
Longest substrings of common length with the same parity
Given two sequences $a$ and $b$, find largest $x$ such that in $a$ there is substring $A$ and substring $B$ in $b$ meeting those conditions:
length of both $A$ and $B$ is equal to $x$;
sum of ...
- 71.8k
1
vote
1
answer
434
views
Algorithm to organize a tournament where the team componentes change each round
So, I was tasked with creating an app that generates the schedule of a doubles tennis tournament (i.e., teams of two) in a way that, by the end of it, everyone would have played against the rest of ...
- 81.1k
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
2
votes
1
answer
156
views
Avoiding correlated values and reduced collision resistance in multiple hash states
I need to design a hash function that fits this criteria:
Limited to 32-bit integer operations (for compatibility with JavaScript bitwise operations, my target system)
Produces an n-bit hash digest, ...
D.W.♦
- 152k
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
1
vote
1
answer
91
views
How to create an algorithm when given the invariant
I am given the following invariant:
Invariant The greatest $i$ keys of an Array are always in sorted order on the last $i$ indices of the Array.
I am supposed to ...
CommunityBot
- 1
3
votes
1
answer
70
views
Develop a winning strategy for a game
Okay so I've been going crazy about this problem I was given. It is as follows:
Given a pile of N matches, 2 people take turns removing matches from the pile. When it is your turn you are allowed ...
- 274k