Questions related to design and analysis of algorithms
1
vote
0answers
12 views
FPT algorithm for point line cover
In the "Covering Things with Things" paper from Langerman and Morin, they mention the BST-Dim-Set-Cover, which is a FPT algorithm for point-line-cover, at page 666.
The algorithm chooses each point p ...
0
votes
0answers
10 views
A bot to cleanup a map
We're given a robot that's able to sense its immediate surroundings on the north, south, east and west, has space to store its state 0-100, and a room for the robot to cleanup, with obstacles in it. ...
0
votes
0answers
21 views
Using an older version of data structures and algorithm in java [on hold]
Has data structures and algorithms changed during the pass 13 years in java? Would i be able to learn the concepts from a textbook published in 2002 called Data Structures and algorithms in java by ...
-1
votes
0answers
25 views
What is the best book for a 15 year old to start algorithms, and wants to go to the IOI 2017? [on hold]
I am currently 15 and I want to go to the ioi, in order to go to the ioi I need to learn about algorithms and data structures. I tried the CLRS book but sadly the maths in it was too hard. I am ...
2
votes
2answers
46 views
Minimising sum of consecutive points distances Manhattan metric
I have set of points (two dimensions, $X, Y$).
Coordinates are floating point numbers.
Objective is to sort them in such way that sum of differences in distances of consecutive sorted points is ...
0
votes
0answers
18 views
What is the best-case and worst-case Time complexity in terms of n,in the form “O(…)” of the following code? [duplicate]
I've Asked this question .....
What is the best-case and worst-case Time complexity in terms of n,in the form "O(...)" of the following code
...
2
votes
0answers
36 views
Algorithm to group two-dimensional data points
I feel like there should be a known algorithm to the following problem, but I am short of ideas how to construct or search for it.
Suppose as an input you have a list of two-dimensional data points ...
0
votes
1answer
34 views
Raptor Algorithm: Differences between trip and route
I'm reading Microsoft's paper about algorithm in public transit named Round-Based Public Transit Routing, short name is ...
1
vote
1answer
23 views
Algorithm for Filling Regions with Small Gaps
I am looking for an algorithm that fills a region with one color, but the edge of the region is not completely closed (i.e. one or more gaps are being left). The result is like the use of the Paint ...
0
votes
0answers
9 views
Minimum path cover problem to maximum bipartite matching [on hold]
I read this link http://stackoverflow.com/questions/10303800/minimum-number-of-days-required-to-solve-a-list-of-questions
But I couldnt understand how to transform the graph for which minimum path ...
0
votes
1answer
27 views
CPU influence in speed of a task with inefficient Algorithm [closed]
If CPU power doubles how much will iecrease time for solving a problem? If the relationship between time and number of steps that the algorithm does be: T = 2^n
i.e:
A PC with 2GHz processor takes 4 ...
1
vote
0answers
15 views
How to find an axis-aligned hyper box whose set of integer points minimizes Jaccard distance to a given finite set of points $X \in {\mathbb Z}^d$?
So I saw this question posed on math.se for $d=3$. Suppose we are given a finite set $X \subset {\mathbb Z}^d$ of $n$ points. The goal is to find a hyper box of integer points $ B = [k_{1,1},k_{1,2}] ...
3
votes
1answer
32 views
Finding the number of $L\leq j\leq R$ such that $a[j] \leq a[i]$
I have recently encountered the following problem which I heard can be solved by using BIT (binary indexed trees) but I am not sure how:
Given an array $a[1, 2, \ldots, n]$ and $Q$ queries of the ...
0
votes
0answers
17 views
Constrained maximum sum sub array [closed]
How would I find the maximum sum of an array of unique positive integers (not necessarily sorted, but associated with an index) given that some indices cannot be paired.
For example we have an array: ...
1
vote
0answers
18 views
Edge Covering with different colored edges
I have a graph with the edges already assigned colors and there are edges of the same color as well as different colors incident to each vertex. I would like to find an edge cover (does not have to ...
0
votes
0answers
30 views
Olympiad practice for 14 year old [closed]
I am currently 14 years old and I am interested in programming, I Am currently learning Python but recently I heard about the ioi (international Olympiad for informatics). I read that in order to get ...
1
vote
0answers
26 views
Dividing/Multiplying Numbers Stored in two memory locations
I have two numbers x and y.
The upper bits of x are stored at location m, while
the lower bits of x are stored at location n.
The upper bits of y are stored at location i, while
the lower bits of y ...
0
votes
1answer
34 views
How to “properly” handle incorrect values in a random walk?
I'm performing a simple one dimensional walk to create sample interest rates. Whilst I know there are lots of options for encouraging values to oscillate around a mean etc. I'm yet to find a simple ...
1
vote
1answer
47 views
Improve minimum spanning tree with new edge, with better running time than O(|V|)?
The problem gives a MST $T$ and a series of $Q$ queries, each one with a new edge $e = \{u,v\}$ such that no edge between $u$ and $v$ exists in $T$. For every query, we have to improve $T$ with $e$ ...
-2
votes
0answers
22 views
Villagers move to a safe location in a catastrophe [closed]
Assume there are n villages on a straight line.
Each village has a population p located at a distance d from a base location (0,0).
During a catastrophe, all villagers are requested to move to a ...
1
vote
2answers
88 views
Sort deck of cards with least no of moves
We have n cards with each card numbered from 1 to n.
All cards are randomly shuffled but all cards are visible
We are allowed only operation MoveCard(n) which moves the card with value n to the top ...
4
votes
0answers
85 views
Paxos consistency
I'm looking at the paxos family of protocols for solving consensus in a network of unreliable processors. I'm working through scenarios where processors fail, and I know I'm wrong, but I don't know ...
0
votes
1answer
47 views
O(n) time algorithm for maximum earnings
There are $n$ plates $p_1$ to $p_n$ each filled with money of value $a_1$ to $a_n$. You can take the money from one or more plates if the sum of the money in them is divisible by three. I need a ...
0
votes
0answers
22 views
How to calculate runtime for FOR and WHILE loops? [duplicate]
While there have been many questions/answers around this on stackoverflow and wikipedia, I would like to have a clearer understanding on how to calculate it in layman's terms. I will say that, yes, ...
5
votes
1answer
89 views
Efficient algorithm for 'unsumming' a set of sums
Given a multiset of natural numbers X, consider the set of all possible sums:
$$\textrm{sums}(X)= \left\{ \sum_{i \in A} i \,|\, A \subseteq X \right\}$$
For example, ...
4
votes
0answers
70 views
Is it possible to boost the error probability of a Consensus protocol over dynamic network? [migrated]
Consider the binary consensus problem in a synchronous setting over dynamic network (thus, there are $n$ nodes, and some of them are connected by edges that may change round to round). Given a ...
1
vote
1answer
76 views
Sorting an already k-sorted array
Can anybody give me some hint on how to do this? I'm not really sure where to start. The problem says:
We say that an array $A[1...n]$ is $k$-sorted if it can be divided
into $k$ blocks, each of ...
2
votes
0answers
41 views
Finding the n-best items in a 0/1 Knapsack
I'm trying to understand why an alternate formula for finding the best $p$ items in a 0/1 knapsack with $n$ items isn't working. The formula was proposed by @Carlos Linares López in this answer: ...
-1
votes
2answers
36 views
Parallel Algorithms for matrix multiplication
Are there any parallel algorithms designed for fast matrix multiplication? If so, can someone suggest me some online sources to read about them or could possibly brief it out here in their answer.
-1
votes
1answer
39 views
Algortihm for path existence in a N by N board moving with a chess knight
I have a problem which goes like this.
There is an $N$ x $N$ board in which some squares are maked with $x$. The upper left and lower right corner squares are also marked. You have a chess knight ...
1
vote
1answer
51 views
Tools for practicing problem solving and expression of algorithms
I'm involved in a university course which is a crash course in the basics of problem solving and common concepts in computer science. The course contains a number of practical assignments and ends ...
1
vote
2answers
21 views
How does one generate a list of size N of all possibilities using a dictionary of size D?
Say that we have a list of size $N$ to fill with elements of a dictionary of size $D$. So we would have in total $D^N$ elements/possibilities.
It makes sense to me how to write an algorithm for this ...
2
votes
1answer
78 views
Do we want largest or smallest priority in the A* algorithm?
On this site http://algs4.cs.princeton.edu/25applications/ is described A* algothihm this way
The A* algorithm is a problem-solving process where we put the start
configuration on the priority ...
0
votes
2answers
58 views
Schedule two trains whose tracks overlap so they don't crash
I've encountered scheduling problems in my algorithms class before like the type we use vertex cover to solve.
Recently I was asked this question and did not even know what algorithmic technique to ...
0
votes
1answer
42 views
Comparison between IDA* and Recursive best first search
How does IDA* compare to recursive best first search (RBFS), in terms of (a) the number of nodes expanded, and (b) space complexity?
Both algorithms are intended to be memory-efficient heuristic ...
-3
votes
0answers
10 views
recurrence relation complexity analysis [duplicate]
I want to find time complexity of recurrence relation without using masters theorem : T(n) = 3T(n/2)+n^2.could you please help me to do so without using master theorem?
2
votes
2answers
95 views
Delivery Algorithm - Find shortest paths
Given -
A center(lat=x,lng=y) 'C' from which a delivery boy makes a round
trip.
A delivery boy has a bag which may contain at the most 10
boxes to deliver.
A set of points Di (lat=xi,lng=yi) ...
-1
votes
0answers
40 views
Find number in Young tableau in $O(n+m)$
Give an $O(n+m)$-time algorithm to determine whether a given number is stored in a given $m\times n$ Young tableau. An $m\times n$ Young tableau is an $m\times n$ matrix such that the entries of each ...
3
votes
0answers
53 views
Complexity for finding zeroes of sum of cosines
Consider the following equation with variable $n \in \mathbb{N}$:
$$\sum \limits_{i=1}^{k} \cos(n\theta_{i}) = 0.$$
Given $\theta_1,\dots,\theta_k$, I'd like to determine whether there exists $n \in ...
2
votes
1answer
41 views
Move tokens from s to t as fast as possible
Let $G=(V, E)$ be an unweighted and undirected graph, and $s, t \in E$.
The problems starts with $n$ tokens on $s$.
The goal is to move theses tokens to $t$ in a minimum of rounds with these rules ...
0
votes
0answers
20 views
How to find close match of levenshtein distance [duplicate]
Let's say we have some function,
float distance(String a, String b) { /*...*/ }
to find the Levenshtein distance between two strings, and we have a large array ...
0
votes
0answers
37 views
Find the index of minimum number that is greater than key given of a sorted array, does these two functions return same result?
Give an array of integer has been sorted (non-decreasing order), we need find the index of minimum number number that is greater than key given, I wrote two functions, they're identical except the ...
3
votes
3answers
1k views
Why does this sort algorithm work?
The following O(n^2) sorting algorithm works but I can't figure out why.
...
3
votes
1answer
197 views
Why does a color video compress better than a black and white video?
It was asked in an exam why a color video compress better than a black and white (grayscale) video using MPEG but can't find anything explaining it.
In other words, we would apparently get a better ...
4
votes
2answers
86 views
Efficiently partition tree into clusters of similar diameter
I am looking for a way to split a tree into $k$ clusters so that the cluster with largest diameter is as small as possible. All edges have the same length. I'm hoping for an algorithm that can handle ...
-1
votes
0answers
47 views
Will my solution work? Interview Question
So there is an interview question on interview cake. The question is given an array, how can you get the product of all the numbers except for the listed value. So let's say the array is [4,7,13,9]. ...
0
votes
0answers
14 views
Set distance as similarity metric for MinHashing algorithm
I am currently working on document clustering using MinHashing technique. However, I am not getting desired results as MinHash is a rough estimation of ...
0
votes
1answer
86 views
Help needed with lesson on recursion
I'm studying CS online, and I'm reading this lecture on recursion, see "3.2. A Mathematical Example".
I understood the beginning and I even made a program that calculates $X$ to the power of $N$ ...
1
vote
1answer
84 views
Name of Bomberman algorithm?
Last couple of days I've been pulling my hair trying to find the name of a
bomberman-esque algorithm which finds solutions to the question of where to place a single bomb so as to blow all targets ...
1
vote
1answer
36 views
Algorithm Design Manual Question
In the book, Algorithm Design Manual by Steven S. Skiena, he states "Becoming familiar with many different algorithmic graph problems is more important than understanding the details of particular ...
