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.
11,567
questions
0
votes
0
answers
10
views
Livout analysis of control flow graph of a program
I just started reading about data flow analysis in compilers and I am trying to understand the concept of live-out variables. For this I read the algorithm to compute live-out variables in each bloc ...
- 101
3
votes
0
answers
46
views
Is the definition of "computational problem" on Wikipedia correct?
In the https://en.wikipedia.org/wiki/Computational_problem, the first line states: "A computational problem is a problem that may be solved by an algorithm." However, I have doubts about the ...
2
votes
0
answers
39
views
Decomposing a general polygon into simple ones
This is a question about splitting a very general kind of polygon
into a list of simple polygons.
Let me introduce some notions: Let an 'edge class' $E$ be a set of
homeomorphic images of the unit ...
- 161
4
votes
3
answers
2k
views
Is this a potentially more intuitive approach to MergeSort?
I have read at least one other post (perhaps not on this stackexchange) that asks essentially: Why do we have to break up the array into successively smaller arrays until we finally reach the bottom (...
- 141
0
votes
1
answer
32
views
Which course is more beneficial for studying undergraduate computer science: Multivariable Calculus or Number Theory
I want to major in computer science for my undergraduate degree. I want to take one of the mathematics courses offered by Stanford ULO (https://ulo.stanford.edu/mathematics). I am unable to choose ...
1
vote
1
answer
20
views
Rule-Based Link Prediction for Social Network
Relevance to Site
I believe this question is suitable for the Computer Science Stack Exchange as it pertains to the implementation of a graph algorithm. According to this widely accepted answer, such ...
- 11
-1
votes
0
answers
16
views
Sequencing swaps with constraints
I have an array of N numbers, and M swaps. Each swap has an index i and amount it subtracts from the ith number, and an index j and amount it adds to the jth number. It can only be applied if the ...
- 99
2
votes
2
answers
53
views
Sorting Algorithm that accounts for relative difference to reduce comparisons (sorting paint samples)
I have a scenario where I want to sort a list of objects where the process of comparing two a <= b is very slow, and so I wish to minimise comparisons. My ...
- 121
-1
votes
0
answers
11
views
Algorithm_A-Res problem
https://en.wikipedia.org/wiki/Reservoir_sampling#Algorithm_A-Res
A-RES calls for the selection of m distinct random items out of a population of size n, each item with weight.
but my case is:
a huge ...
2
votes
1
answer
29
views
Algorithm for finding the minimum factorization of a tensor product expression
I originally asked a question on the Mathematica stack exchange on a similar topic here.
But it seems like my question actually extends beyond Mathematica. The issue is the following. Let $a,b,d$ be ...
- 125
2
votes
5
answers
783
views
In-Place Reordering of Doubly Linked List Nodes to Ensure Memory Contiguity
I am addressing an optimization problem involving a doubly linked list, where nodes are allocated within a contiguous memory block of fixed size $N$. Initially, the spatial locality of nodes in memory ...
0
votes
5
answers
719
views
Classification of efficient and inefficient algorithms and the scientific reasoning behind them
I've been struggling with the commonly accepted notion in computer science that exponential algorithms are inefficient. The standard explanation is that they "grow exponentially in the size of ...
- 119
1
vote
1
answer
26
views
Given arrays A & B and an element-wise distance function f between them, minimize the sum of f over A & B by reordering B?
I have a problem I think I've managed to distill down to the following problem:
Given two arrays $A$ and $B$ of length $n$ and a pair-wise distance function $f(a_i, b_i)$, where $a_i \in A$ and $b_i \...
- 245
0
votes
0
answers
23
views
SSA Construction: DFS of CFG vs Traversal of Dominator Tree
According to Engineering a Compiler Cooper, K. and Torczon, L. the SSA transformation algorithm is divided into two parts
Inserting $\phi$ functions. For each existing definition of a variable ...
- 133
0
votes
0
answers
21
views
What is the fastest algorithm for generating all non-isomorphic unlabeled free trees for n-vertices, and also for caterpillar trees of n-vertices?
I'm aware of some algorithms for each problem such as the WROM algorithm for unlabeled free trees and the algorithm from this page for all caterpillar trees of n-vertices.
However, I haven't been able ...
