Questions related to design and analysis of algorithms

learn more… | top users | synonyms (1)

0
votes
0answers
2 views

Expectancy of the number of interval flippings needed to sort random array

This question is inspired by the Bogo-Sort algorithm and the discussion of whether there are any worse sorting algorithms than Bogosort. Assume that $A$ is an array initialized by a random ...
0
votes
2answers
30 views

Is there a way to find path length to a node from root in a binary tree?

I went through the algorithm’s for finding the LCA of two nodes in a binary tree (let’s say the values are random – not a binary search tree) and I chose the method where the path to root is stored in ...
0
votes
0answers
16 views

Optimizing a generator of strings that satisfy a two dimensional regex

I have a program that fills a matrix with characters such that all words formed by each row satisfies one regex and all the words formed by each column satisfies a second regex. How can I use ...
0
votes
0answers
22 views

Is there a way to tell a picture has been resized?

I need to evaluate if the picture was resized (upscaled). Are there any approaches to that already? If not, what do you recommend me to start with?
1
vote
0answers
20 views

Finding all “smooth” numbers up to 10^6 — problem with nested loops [duplicate]

A [smooth number] is one whose factors are all "small". For a computational problem, I would like all smooth numbers up to $10^8$. I think it's unfeasible to factor a billion numbers. Instead, I ...
4
votes
1answer
45 views

Parallel algorithms on a fixed number of processors

Usual parallel algorithms require a number of processors that grow with the size of the input, usually $O(\log n)$ or $O(n)$. This is great from a theoric point of view, but strange from a practical ...
0
votes
1answer
27 views

undirected graph without weights and DFS [on hold]

following question on undirected graph without weights can be solved by using DFS and in O(|V|+|E|) times. check that G is ...
2
votes
0answers
34 views

Algorithm for a special case of SAT/#SAT

Does anyone know of an algorithm that can solve the following special case of SAT in polynomial time? Are there any algorithms that can solve the counting (#SAT) version of it in polynomial time? ...
0
votes
1answer
20 views

What is the name for this … (alerting when threshold is exceeded, but only if dropped enough below threshold first)

Imagine: you are monitoring a system, and want an alert when certain measured value goes over a threshold value X. But perhaps the measured value is constantly fluctuating close to X, and you get a ...
2
votes
1answer
39 views

Shortest path in a mutable graph

I have an acyclic edge-weighted graph and have used Dijkstra's Algorithm with topological sort to find all shortest paths from a root $s$. This is performed in time proportional to $V + E$, where $V$ ...
-1
votes
0answers
23 views

Multivariate optimisation data-structure / algorithm? [on hold]

Based on constraints given at runtime, is there an efficient way of finding the answer? Given $n$ rows with $k$ columns. To exemplify, with $n=3$ and $k=3$: ...
-3
votes
0answers
37 views

is there an algorithm to calculate the sum of two egyptian fractions? [on hold]

I would like to create a programm of egyptian fractions and the sum and substraction of them
1
vote
1answer
31 views

Rubik Cube Algorithm for general n

I am not sure if this is the right place , but: Is there an algorithm for solving $n\times n \times n$ rubik's cube (non-trivial one)? If so how efficent is it? Now say I have a $n \times \ldots ...
0
votes
0answers
24 views

Finding Contextual Nodes in a Knowledge Graph

I'm currently participating in developing a knowledge graph that uses ConceptNet and a few others as its data sources. It uses the same architecture as ConceptNet namely it is stored as a hypergraph ...
0
votes
1answer
41 views

Example of worst case input for Build-Max-Heap

Is there a worst-case inputs for Build-Max-Heap? I know there is but I just couldn't paint a clear picture of it in my head.
0
votes
1answer
44 views

Set Intersection with asymmetric set sizes

I'm looking for an algorithm to perform set intersection where set $N_1$ is very small and set $N_2$ is very large. Due to the constraints of the problem I am solving, I cannot rely on an algorithm ...
-1
votes
0answers
16 views

Running time of algorithms [on hold]

Suppose for all integers $0 ≤ m$, $n < N$, Algorithms $A$, $B$, and $C$ compute the following: Algorithm $A$ computes $n + m$ in time $O(A(N))$ Algorithm $B$ computes $m · n$ in time ...
0
votes
1answer
45 views

Build-Max-Heap vs. HeapSort

I'm not sure whether my definition for these 2 terms are correct. Hence, could you help me verify that: HeapSort: A procedure which sorts an array in place. Build-Max-Heap: A procedure which runs in ...
1
vote
0answers
30 views

Network clearance algorithms

In the network clearance problem, we are given a simple undirected graph with a capacity assigned to each edge (and/or to each vertex). Each edge can transport up to its capacity each time step (i.e., ...
2
votes
1answer
42 views

What type is this sorting algorithm?

I needed to sort vertices into buckets as an optimization for collision detection later. I came up with this: go over all the verts and count the size that each bucket needs to be to contain them ...
6
votes
4answers
121 views

Finding the two largest of five small integers as quickly as possible

I use a variation of a 5-cross median filter on image data on a small embedded system, i.e. x x x x x The algorithm is really simple: read 5 unsigned ...
3
votes
1answer
55 views

Set the parameters of a Erdos-Renyi graph generator to get a specific mean degree

I'm trying to reproduce the synthetic networks (graphs) described in some papers. The topic is the same as a previous question of mine, but with a different focus. It is stated that the Erdos-Renyi ...
4
votes
1answer
43 views

Parameters for Barabasi-Albert graph generator

I'm trying to reproduce the synthetic networks (graphs) described in some papers. It is stated that the Barabasi-Albert model was used to create "scale-free networks with power-law degree ...
0
votes
0answers
11 views

Regarding number of iterations in Value Iteration

In value iteration for single goal problem, does the number of iterations it takes for the convergence to terminate dependent on grid world size, or discount factor or threshold set or none of the ...
2
votes
1answer
105 views

What is the name for this search algorithm?

A colleague came up with the following search algorithm: We have an array of sorted, distinct integers [$i_0$ < $i_2$ < ... < $i_n$] We are looking for the index of $i_k$ (for simplicity ...
2
votes
1answer
60 views

Computing a Sequence of People Entering and Leaving a Room

I've been working on a problem for my Algorithms class, but I've found myself stuck. The prompt is as follows. You start with an empty room and a group of n people waiting outside. At each step, ...
0
votes
0answers
10 views

Help on previous question (Truthteller and Liar problem) [duplicate]

There is a hint for part B, but I do not get which ones are the right cases to get rid of both goblins. Thanks! How can I tell who is a truth teller and who is a liar?
3
votes
2answers
110 views

How can I generate first n elements of the sequence 3^i * 5^j * 7^k?

How can I efficiently generate the first N elements of the sequence $3^i 5^j 7^k$, where $i,j,k \in \mathbb{N}$? I've googled around a bit and found the sequence in OEIS, but I don't really see a ...
2
votes
1answer
59 views

Find the shortest string that is not a sub-string of a set of strings [duplicate]

Alphabet: abc Sample input: abc cba aabbcc ...
2
votes
1answer
55 views

Should one learn proofs for the correctness of algorithms? Why? [closed]

I'm reading Introduction to Algorithms and would like to know if learning the proofs is worthwhile.
-1
votes
0answers
16 views

Distance Increment in Graphs [closed]

Question: Let G be a direced graph with non-negetive weights and to speciall nodes S and T,find the smallest group N (group of edges) that will increase the distance form S to T. Time ...
5
votes
2answers
39 views

Algorithm to generate all planar graphs

Is there an algorithm which provides a sequence of all simple planar graphs, unique by graph isomorphism? For instance: first all planar graphs with 1 node, then all planar graphs with 2 nodes, etc. ...
-1
votes
0answers
19 views

Data Structure for efficient distribution [closed]

Suppose I have a train with $N$ wagons. Each wagon $i$ has $n_i$ cells, while each cell has 6 seats. Now suppose $0<x \leq 6$ passengers entered wagon $i$ of our train and want to sit in the same ...
2
votes
0answers
27 views

A fast algorithm for a simple multi-objective minimization?

I have a set $S$ of $n$ (arbitrary) integers which I want to partition into subsets $S_1, \dots, S_k$, each of size $n/k$ (you can assume that $k$ divides $n$). Let $A$ be the arithmetic mean of ...
-2
votes
0answers
26 views

Understanding the following structure for an edge in a Graph [closed]

I am going through a solved example of Dijkstra's algorithm and I cam across the following structure being defined in C++. ...
0
votes
2answers
53 views

Finding the lightest simple path in trees with integer weights

A tree with integer weights (positive, negative or zero) is given. We want to design an efficient algorithm for finding a simple path with lightest weight in this tree. That is, we look for shortest ...
-1
votes
0answers
6 views

Java Programming Method Overloading Help [migrated]

First time posting here sorry about the format. public static void main(String args[]) { ...
2
votes
1answer
35 views

Applications of Lamport's Distributed Mutual Exclusion algorithm

I'm trying to understand the relevance of the Lamport distributed mutual exclusion algorithm (or any of its variants), where a group of processes cooperate to gain exclusive access to a resource ...
0
votes
1answer
26 views

Collecting and combining data from iterative DFS on read-only trees

I am iterating over a tree through an API. This API provides a list of nodes sorted in post order DFS. I need to gather data for each node in the tree, combine that data with the parent's data ...
3
votes
1answer
35 views

Efficient way to calculate sum in sliding window?

Assume you have a grid as below: The square is the sliding window. I want to slide this window over all the possible position such that the window is contained in the grid (i.e the edges of the ...
4
votes
0answers
26 views

Parallel algorithm to find if a set of nodes is on an elememtry cycle in a directed/undirected graph

I'm looking to find / develop a simple parallel algorithm that does this: Input: vs: list of root vertices max_length: max cycle length max_dist: max distance to root Variants one variant of ...
5
votes
1answer
99 views

Subgraph isomorphism in planar graphs

I'm a computer engineer trying to understand this Eppstein paper for matching subgraphs in planar graphs. I'm trying to find subgraph matches to map an application graph (the subgraph) to a ...
0
votes
1answer
33 views

Time-complexity of recursive defined code [duplicate]

How would I set up a recursive formula for time-complexity for this code: ...
1
vote
0answers
16 views

Modify one element and find out which surounding elements are affected

I want to know if there is an algorithm which does the following: Imagine you have a point cloud and the points affect each other but the action from each point to an other is only valid in some ...
0
votes
1answer
24 views

Update all nodes in a graph in a way that at any step all chosen nodes are disconnected

There are N nodes in a graph and some of them are connected with edges. All nodes are of type T1. The goal is to update all nodes to type T2. At any step you can choose any set of nodes and change ...
1
vote
6answers
184 views

Computer Program vs. Algorithm

It's said that a program include algorithms, however if we refer to their definition, an algorithm is a sequence of instructions written to perform a specified task and a computer program is also a ...
1
vote
0answers
26 views

Reference for approximation algorithms [closed]

what is the best book to gain an introductory understanding of approximation algorithms? I'm looking for something along the lines of the Sedgewick, that has examples written in a well known language ...
1
vote
1answer
15 views

Unification — removing equations and updating the solution

This question is concerned with the first order unification. Suppose I have a set $D$ of equations and a solution to these equations. Let this solution be a set $S$ of substitutions. Now, suppose I ...
0
votes
1answer
172 views

A partition algorithm

I have encountered the following problem that I found very interesting to solve: Given an array of positive integers $\{a_1, a_2, ..., a_n\}$ you are required to partition the array into $3$ ...
23
votes
7answers
6k views

Is it a problem to be a programmer with no knowledge about computational complexity?

I've been assigned an exercise in my university. I took it home and tried to program an algorithm to solve it, it was something related to graphs, finding connected components, I guess. Then I made ...