Questions related to design and analysis of algorithms

learn more… | top users | synonyms (1)

0
votes
0answers
4 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
27 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
15 views

Constrained maximum sum sub array [on hold]

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
16 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
24 views

Olympiad practice for 14 year old [on hold]

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
24 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
33 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
40 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 [on hold]

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
81 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
79 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
46 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, ...
4
votes
1answer
86 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, ...
2
votes
0answers
31 views
+50

Is it possible to boost the error probability of a Consensus protocol over static network?

Consider the binary consensus problem in a synchronous setting over static network (thus, there are $n$ nodes, and some of them are connected by edges). Given a randomized $\delta$-error protocol for ...
1
vote
1answer
71 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 ...
1
vote
0answers
32 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
35 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
50 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
77 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
56 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
36 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
0answers
34 views

Please help me understand the reason behind an Infinite Loop [closed]

Problem: Find all numbers uptill $10^7$ such that the sum of the $factorials$ of each $digit$ is divisible by the number itself. As an example, consider $145$: $$5!=120, 4!=24, 1!=1\Rightarrow ...
2
votes
2answers
92 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
39 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
188 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
46 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
82 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
35 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 ...
0
votes
0answers
45 views

Most frequently auto-tagging algorithms for text documents

Please if it's possible introduce the newest and most frequently auto-tagging algorithms for auto-tag text document. I want to get one text document and export tag for that. I also saw TF-IDF but it ...
7
votes
1answer
92 views

How do you determine the number of errors in the Welch-Berlekamp algorithm?

In the Welch-Berlekamp algorithm for decoding Reed-Solomon codes, one is given a list of points $(a_i, b_i)$ representing a message with $e$ errors on the $b_i$ in unknown locations (and $e$ is given ...
2
votes
0answers
21 views

Difference b/w a drawn 2d path and a sample

Background: I'm working on an application which is supposed to teach users how to write Japanese kanji. Each kanji is represented as an array of strokes. Each stroke is an array of 2d points. Strokes ...
0
votes
0answers
48 views

Aliens to the Moon

$N$ Aliens want to reach their Moon ($D$ meters away), but they can only put on each other, making a vertical chain. Every $Alien(i)$ has an height $X(i)$ and a lenght of their arms $Y(i)$. ...
2
votes
2answers
97 views

Find the number of values between i & j(given as input) in an unsorted array in O(1) time

Given an unsorted array $A$ of $n$ numbers and inputs $i$ and $j$, can we find the number of values $i<k<j$ in $A$ in O(1) time complexity by doing some preprocessing? An additional requirement ...
1
vote
1answer
22 views

Creating a list of minimum-distance pairs from two lists

Let's say there are two lists of objects, list1 and list2, and that there is a function that can generate the "distance" between an object in list1 and an object in list2. What I would like to do is ...
2
votes
1answer
55 views

I want to figure out whether my problem described below is reducible to the set cover problem

I have a collection of non-empty sets $S_i$, where $1 \le i \le n$, which are constructed from elements of a universe $U$. I need an algorithm that gives me a set $T$ of minimum cardinality ($T ...
3
votes
0answers
51 views

The runtime of a neural net with given numbers of observations, features, and neurons

If I have $n$ training observations, $m$ number of features per observation, and my neural network has $x$ neurons in the 1st layer, $y$ neurons in the 2nd layer, and 1 output neuron, what is the ...
1
vote
0answers
22 views

Does the vehicle routing problem and variations have approximation ratios or a PTAS?

This is a somewhat big question since there are many variations on the VRP. The most studied seems to be the capacitated version, the CVRP, but variations considering time windows, backhaul/linehaul, ...
1
vote
0answers
34 views

Sort graph nodes by density [closed]

Imagine villages (or Internet Routers) scattered all over the world (or World Wide Web) connected by roads or shipping lanes (or Cables). All villages (nodes) has the same amount of villagers which ...