Tagged Questions

Questions related to design and analysis of algorithms

learn more… | top users | synonyms (1)

-1
votes
0answers
4 views

Parallel CREW algoritm for sorting n numbers between 0 and logn-1

We are given n integers in the range [0,..,log(n)-1]. How can we sort the numbers? The algorithm doesn't have to be work-efficient.
1
vote
1answer
16 views

Round robin tournament scheduling using divide and conquer

I want to scheduling $n$ teams using divide and conquer method for $n \in \mathbb{N}$.My approach is that if $n$ is even divide it to to group $\frac{n}{2}$ and $\frac{n}{2}$ but if $n$ is odd, add ...
2
votes
1answer
37 views

Is there any algorithm can solve the following equations efficiently?

$$ x_1 + x_2 + \cdots +x_n = c_1 $$ $$ \frac{x_1^2}{2} + \frac{x_2^2}{2} + \cdots +\frac{x_n^2}{2} = c_2 $$ $$ \cdots $$ $$ \frac{x_1^n}{n!} + \frac{x_2^n}{n!} + \cdots +\frac{x_n^n}{n!} = c_n $$ ...
0
votes
0answers
29 views

Learn feature value range for a classification

Which domain does this problem belong to? Given a set of products some are classified as cheap and some not. The task is to determine the price range (probabilistic) for cheap products. Supervised ...
-3
votes
0answers
30 views

Mathematical problem but need to find a logic to write algorithm [on hold]

These are roman values - Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1,000 these are some rules associated to problem - Numbers are formed by ...
1
vote
0answers
42 views

Finding nearest of a list of points on Euclidian plane to a given reference point

Problem formulation: Given a list $L$ of $n$ points in the Euclidian plane and a reference point $R$ also in that plane, find a closest point $P\in L$ such that, for all $X\in L$, $|PR|\le|XR|$. ...
1
vote
1answer
16 views

Construction of graph with given Wiener Index

Given the sum of weights of shortest paths between all vertices in a graph, how can I construct a connected graph that satisfies the given sum? That is, how can a graph with a given wiener index be ...
0
votes
0answers
32 views

Camera Matching Algorithm

I am trying to understand how camera matching (or match moving) works. I need to build a program that can move the camera in a way to match a 3D object to its projection on an image. For eg. if I had ...
0
votes
0answers
26 views

Finding negative weight cycles in graph using BFS/DFS

I was learning about Bellman-Ford in CLRS and in the exercises, there is a question to find a way to list the vertices of a negative weight cycle if one exists. I was able to find one algorithm by ...
3
votes
1answer
41 views

Returning m greatest elements from k sorted array

We have $k$ sorted arrays, $A_1[1...n_1],...,A_k[1..n_k]$, where $n_1+n_2+...+n_k=n$. How can we get the $m$ greatest elements in running time $O(k + m\lg k)$? I have tried to use MIN-HEAP size of ...
-2
votes
0answers
16 views

Is search in database is always accurate? [closed]

Is search in database is always accurate ? From our IR course Exam: What is the difference between database management and information retrieval system ! The expected Answer: Database is structured ...
0
votes
1answer
56 views

I want to learn algorithms [duplicate]

I did study applied math and dealed almost exclusively with the creation of ode/pde solver code. Now, I want to increase my knowledge in some aspects and I want to learn some basic algorithms like A*, ...
1
vote
2answers
30 views

Sorting a sorted array after increasing several elements

I know that most of the efficient sort algorithms can run with a complexity of $O(n\cdot log(n))$, but this is given an unsorted array. However, given that the initial array is already sorted, is ...
1
vote
1answer
13 views

Hamming Weight to find the sum of 1 bits in the range between A and B inclusive [closed]

I am trying to find the sum of 1 bits in the range between A and B inclusive, where -2^31 <= A <= B <= 2^31 - 1 Input Format: The first line contains the number of test cases T ...
4
votes
1answer
125 views

Proof of Dijkstra Algorithm Optimality

Has it been proven that Dijkstra's algorithm is optimal for asymptotic worst case of single-source shortest path on directed graphs? (Assume no preprocessing) I became curious when Wikipedia ...
-1
votes
0answers
10 views

Algebraic form to code [closed]

I have a homework where we are supposed to implement a functional datatype for any generic datatype. The specifications for the class are given in algebraic form. I'm having problems interpreting it ...
2
votes
0answers
20 views

Common subgraph isomorphism with K vertex

I'm looking for subgraph isomorphism of at least K vertex between Graph A and B. I only can come up with the dumbest algorithm, which is: Compute all combination of vertices with length K of Graph ...
0
votes
1answer
36 views

Evaluating Statements Using a Parse Tree

I'm building a compiler. I already have a parse tree which I built using Bison for a grammar similar to the ANSI C grammar in this link. I see that for multiplicative expression in my parse tree, ...
2
votes
1answer
20 views

Expressing pseudo-polynomial runtime solely in terms of the input size

In case we have an algorithm which is pseudo-polynomial and runs in $O(n^2C)$ for some $C$ that is encoded in binary. Is it correct to say that if $C=2^n$ then $O(n^2C)=O(n^22^n)$ and because ...
1
vote
1answer
40 views

Finding Triples that satisfy modulo equation in $O(n\log n)$ time

Given $n$, I am trying to count the number of values $(a,b,c)$ that satisfy the following equation in $O(n\log n)$ time. I do not need the values themselves only the number of total values that ...
-1
votes
0answers
15 views

Markov Chain Monte Carlo Simulator Not Working [closed]

I'm trying to run a MC simulator for a Markov Chain that is uniformly distributed among all 50x50 matrices that have no neighboring 1's. My algo is supposed to fill up the state space by running the ...
0
votes
1answer
27 views

How does the Earley Parser store possible parses of an ambiguous sentence?

I've got a pretty basic question concerning the Earley parser: In case of syntactic ambiguity ( S -> NP VP(V NP(NP PP)) vs. S -> NP VP(VP((V NP) PP) ), are both parses stored in one chart or in two? ...
0
votes
1answer
31 views

n-th non-decreasing sequence

I have a generator of non-decreasing sequences of numbers 0..M: ...
-1
votes
1answer
44 views

Calculating genus of graph

How to calculate genus of arbitrary graph? I am interested in any algorithm, even it based on full search.
1
vote
0answers
23 views

Combinatorics problem [migrated]

I am trying to solve this question, my solution involves solving a combinatorial problem as follows : Number of arrangements of exactly k distinct elements in n slots such that each one of the ...
1
vote
0answers
43 views

Approximation for fewest incompatibilities in a scheduling algorithm

Suppose you have a task selection algorithm to select the largest subset of tasks that do no overlap. The greedy algorithm that selects tasks based on their finish time will always produce an optimal ...
2
votes
0answers
119 views

Message protocol to probabilistically infer missing object from Union of two subsets of a larger set

This was a challenge problem I read some time ago and just remembered it: Say you have two people, $A$ and $B$, collect objects distinctly labeled $1,...,n$. They will each separately collect ...
-1
votes
0answers
46 views

Modify Johnson's algorithm

Let's say we modify Johnson's algorithm to use a different reweighing scheme. Let $w^* = \min_{(u,v) \in E} {w(u,v)}$. Define the new weight function as $w'(u,v) = w(u,v) - w^*$ for all $(u,v) \in ...
0
votes
0answers
25 views

A* cost implications of arbitrary/dynamic point on edge in navmesh

I currently have a working implementation of A* using navigation meshes. Agents are moving around a 3d navigation mesh, reaching their target, however often a sub-optimal path is chosen, when ...
-3
votes
0answers
24 views

Adding, deleting, increasing and decreasing edges of MST graph

Suppose we have found a MST of a graph. Then the graph undergoes some change. For each of the following changes to the initial graph, describe an efficient algorithm to update the MST (the ...
2
votes
2answers
44 views

Is single-source single-destination shortest path problem easier than its single-source all-destination counterpart?

Dijkstra's algorithm (wiki) and Bellman-Ford (wiki) algorithm are two typical algorithms for the single-source shortest path problem. Both of them compute distances for all nodes from source $s$. ...
1
vote
2answers
99 views

Brute force method to solve the 0-1 knapsack problem

I know that the brute force method is not the best way to solve the 0-1 knapsack problem. I'm not quite getting the dynamic programming idea, but would like to know the following: If the brute force ...
-1
votes
0answers
33 views

Scheduling N programs on two machines

Suppose we have 2 computers and N programs to execute .We want to run all N programs on both the computers but their are 2 conditions : We can't run two programs in parallel on a single computer. It ...
6
votes
2answers
54 views

Which measure of sortedness explains the phase transition in Quicksort's runtime?

I'm currently creating a program to analyse the pathological cases of Quicksort. Namely, the transition of complexity from $O(n^2)$ to $O(n \log n)$ as a data set gets less ordered. Since Quicksort is ...
1
vote
1answer
30 views

Equally distributed/packed spheres within a sphere

I need to equally distribute a variable number of spheres within a larger sphere (the volume of the spheres depends on how many there are). Are there any algorithms for doing this? An approximate ...
2
votes
1answer
71 views

Dijkstra's Algorithm with different color nodes

You are given a directed graph G = (V, E) and nodes s, t. Nodes are colored red, white, and blue. A path from s to t is called colorful if it contains both a red node and a blue node. The task is to ...
4
votes
2answers
53 views

Vertex cover in bipartite graph from Hopcroft-Karp Algorithm

Vertex cover in bipartite graph is polynomial algorithm: by König's theorem the number of edges in a maximum matching is the number of vertices in a minimum vertex cover. I've implementated the ...
3
votes
1answer
81 views

Does a greedy task selection algorithm find a c-approximate solution?

I was told this question may be better suited here. A scheduling problem can be stated as: Given a set $\{(s_i,f_i)\}_{1\le i\le n}\}$ of tasks identified by their start and end times, choose ...
1
vote
2answers
56 views

How to find an IP in overlapping ranges of IPs?

I have a large number (millions) of IP ranges which might overlap. An IP range should contain the start IP, stop IP and an range id. How can I efficiently find which ranges contain a given IP? I ...
2
votes
1answer
18 views

Are there FPTASs for the min cost flow problem?

In literature, one can find many approximation algorithms for the multicommodity min cost flow problem or other variants of the standard single-commodity min cost flow problem. But are there FPTASs ...
3
votes
1answer
30 views

Best sort method for median: median heap or insertion sort on a vector

I'm trying to decide between two methods of calculating a median, that will optimize the following operations: Add integer to data structure (insert) Get the median of all integer (getMedian) The ...
7
votes
1answer
452 views

Does a coin tossing algorithm terminate? [duplicate]

Suppose we have an algorithm like: n = 0 REPEAT c = randomInt(0,1) n = n + 1 UNTIL (c == 0) RETURN n (Assumuing the random number generator produces "good" ...
1
vote
2answers
40 views

Working out the connectives (And, Or, Not) in a Truth Table that has the outputs [duplicate]

I don't understand how to work backwards to work out a truth table that has been filled out already (I don't know the logical operators). E.g P | Q | Output 1 | 1 | 1 1 | 0 | 0 0 | 0 | 0 0 | 1 | 0 ...
1
vote
2answers
156 views

Dynamic programming to find the least possible balance of a full binary tree

I am given $n$ positive integers $x_1,x_2,\cdots,x_n$ as input. These are the weights of the leaves in a full binary tree, $x_1$ being the leftmost leaf and $x_n$ the rightmost leaf. The weight of an ...
1
vote
1answer
31 views

3-Coloring Problem Question [duplicate]

So I understand that finding a solution to the 3-coloring problem takes exponential time. However, say you had a friend who you could give a graph G to and he can say in constant time whether it is ...
1
vote
1answer
38 views

Finding optimal price in a sale

A furniture store is having a sale: purchase two items at the price of the more expensive one. John, having just moved to a new house, rushed into the store and chose $2k$ items of furniture, ...
0
votes
1answer
54 views

Longest Path in a directed rooted graph

A directed rooted graph is defined as graph for which there exists a vertex r such that to every vertex x there is a unique path (Equivalently dfs tree with source r has only back edges and has all ...
-1
votes
1answer
27 views

Bubblesort generalization [closed]

I was comparing and analyzing the sort algorithms thereby came across a machine which took 200 secs to sort 200 names but to generalize, in 800 secs wouldn't it sort 800 names?
1
vote
1answer
50 views

Hungarian Assignment Algorithm Implementation

I want to implement the "vertex similarity" algorithm described in the paper Graph Isomorphism Detection Using Vertex Similarity Measure. The algorithm is as follows: ...
-1
votes
1answer
27 views

Solving a Variation of knapsack [closed]

I'm working on a problem which to me, seems very similar to a knapsack problem: A furniture store is having sale: Purchase two items at the price of the more expensive one. David went to the store ...