Questions related to design and analysis of algorithms

learn more… | top users | synonyms (1)

3
votes
0answers
36 views

Computing the “at least k friends in common” graph

Suppose we have the graph of a social network with symmetric connections (e.g. Facebook or LinkedIn). Suppose we would like to find all pairs of people who have at least k friends in common, in order ...
4
votes
3answers
174 views

Why is the addition function exponential for k-bit integers providing only zero, equality and the successor functions?

I'm currently reading the elements of programming book and have come across a section I don't quite understand A computational basis for a type is a finite set of procedures that enable the ...
0
votes
0answers
49 views

Dynamic Programming problem: A number as a sum of squares

Following is the problem I am trying to solve: Problem Statement Find the number of $n$-tuples $(a_1,a_2,a_3,\cdots,a_n)$ such that ...
-2
votes
1answer
32 views

Using dynamic programming to find the number ofl increasing subsequences

I got this question today and I'm nowhere near the solution, Given a sequence of real numbers (X1, X2, ..,Xn). write an algorithm as efficient there is, that finds the number of strictly increasing ...
2
votes
1answer
33 views

Find the subset of k element between n that maximize the total distance

Given a set $Q\subset \mathbb{N}^m $ of $n$ points, we want to find the subset $S_{max}\subset Q$ of $k$ elements that maximize the total distance between them, according to the $\ell^1$ norm. ...
1
vote
1answer
37 views

Shortest Path problem(Single Source&Destination)

Given: A completely connected directed acyclic graph. What would be the most efficient(Least Time complexity) way to find a shortest path among a very large number of nodes? Constraint: 1)The result ...
0
votes
1answer
102 views

Why is O(n log n) the best runtime there is?

I am taking a course on Coursera about algorithm design. The course said that a time of $O(n \log n)$ is considered to be good. However, there are faster runtimes such as (from now on just assume it ...
-1
votes
0answers
18 views

How to port forward? [on hold]

how can I port forwand on my modem if I have lost my password. It is a Netgear DGN2200v4. I need to host a minecraft from home and I need to port forward on port 25565 to let other people join my ...
3
votes
1answer
40 views

Since we need space for recursive calls, is the space complexity of the recursive factorial is n?

As Wikipedia says, quickSort needs O(log n) extra space when the following conditions are met: In-place partitioning is used. This unstable partition requires O(1) space. After partitioning, the ...
1
vote
2answers
78 views

Exercise on Divide&Conquer's technique

I need help on this exercise: You are given an array of n elements, and you notice that some of the elements are duplicates; that is, they appear more than once in the array. Show how to remove all ...
-1
votes
1answer
36 views

Divide-and-Conquer Exercise [closed]

I need help on this question: Given a sorted array of distinct integers A[1, . . . , n], you want to find out whether there is an index i for which A[i] = i. Give a divide-and-conquer algorithm that ...
-2
votes
0answers
135 views

Find out maximum number of K’s possible for given number of keystrokes [closed]

Imagine you have four operations. ‘K’ (types k on screen), ‘select all’, ‘copy’, ‘paste’. Find out maximum number of K’s possible for given number of keystrokes. e.g ...
3
votes
1answer
29 views

Algorithm(s) for creating balanced 5-a-side teams?

I play 5-a-side soccer twice a week. 10 people play each game out of a pool of about 30 people who are giving the opportunity to play as it's first come first serve. Some people play more often than ...
0
votes
0answers
11 views

Simple Path to Route Algorithm [closed]

I'm currently conducting research into subway paths, but stand in front of a problem, with no programming knowledge and an extremely short time-limit. Probably the question I am asking is trivial, ...
6
votes
1answer
378 views

Given an array of size N, if you know that all of the elements are white except for one, how to find the index of that element efficiently?

Yesterday while returning home, I walked past a house that had a camera. For some reason I started thinking about how these cameras work, and how you would use them in case of robbery. While thinking ...
2
votes
0answers
49 views

KMP Algorithm, Pratt's Minimisation/optimization of Knuth's original DFA based algorithm

The Original Knuth's Algorithm is based on DFA and it depends on the alphabet size. And Then, Pratt optimised it to be independent of Alphabet Size. But, All the ...
0
votes
2answers
26 views

Constructible enumerable set

We suppose that the sets $S_1$ and $S_2$ are constructible enumerable, that means that there is an algorithm that enumerates them. Show that the sets $S_1 \cup S_2$ and $S_1 \times S_2$ are also ...
2
votes
1answer
24 views

Selecting k “special” nodes in a graph such that the min distance is maximized?

Lets say we have a graph $G$ with $|V|$ nodes. We wish to select $k$ such nodes while optimizing the following attribute: maximize: for each $i$ and $j$, where $i \neq j$, $min(distance(v_i, v_j))$ ...
0
votes
0answers
64 views

Looking for an algorithm to solve this optimization problem

I have a set of constants $C = \{c_1, c_2, \ldots, c_n\}$ and a set of variables $V = \{v_1, v_2, \ldots, v_n\}$, each element in $V$ is somewhere between $0$ and some maximum limit $U$. Let $S = c_1 ...
1
vote
1answer
25 views

How would you implement truly random hash functions in practice?

Suppose that $[U] = [0,...,U-1]$ is the universe from which all elements will be taken, and $A$ a hash table of size $m$. A hash function $h:[U]\rightarrow[m]$ is truly random if For any set of ...
1
vote
0answers
33 views

Better Alternatives for Canny algorithm in Edge Detection?

Canny edge algorithm has 5 stages, from here ...
1
vote
3answers
72 views

Why would a function be tabulated in advance and then retrieved?

Given some function and assuming no concern for the time to compute the co-domain for its domain, when might it be preferable to compute and tabulate in advance the co-domain results of the function, ...
11
votes
3answers
229 views

Finding a pair of non-overlapping bit vectors

I give you a list of $n$ bitvectors of width $k$. Your goal is to return two bitvectors from the list that have no 1s in common, or else to report that no such pair exists. For example, if I give you ...
-2
votes
0answers
70 views

Find the city that is farthest away from its nearest police station

It is given an undirected graph $G = (V, E)$ and a weight function $w : E \rightarrow\mathbb{Z} ^{+}$, which we interpret as distance between vertices. The vertices of the graph are cities, and in ...
1
vote
1answer
61 views

Why does Kadane's algorithm solve the maximum sub-array problem?

I've tried to solve a exercise 4.1-5 in algorithm book "Introduction to algorithms". it is about Maximum sub-array problem, which is an algorithm that determines the greatest sum of sub-array A[i], ...
0
votes
0answers
15 views

Time varying handshaking problem with memory: optimal matching

I have to analyse the following problem. I have a set of users $M = [m_0,m_i,\ldots,m_n]$. Between each pair of users I there is a certain Temporal Affinity $F$ defined as $F(m_i,m_j,t_k)$ that is: ...
0
votes
0answers
6 views

How to implement this test case in python? [migrated]

Q. Suppose that our banking system requires the ability to make joint accounts. Define a function make_joint that takes three arguments. A ...
3
votes
1answer
66 views

Succinct bounded-sum array with $O(1)$ access

Assume we have a $n$ sized integer array $A$, and that we know that $\sum_{i\in[n]}A[i] \le M$. Assume we are using the RAM model with $\Theta(\log n)$ sized memory words (which can be read / written ...
3
votes
0answers
35 views

Voronoi Diagrams with L∞ Metric

I've recently become interested in randomly generating Voronoi diagrams to create "territory" maps (similar to this) for a project I've been working on. Traditional Voronoi diagrams using an ...
0
votes
2answers
87 views

Find all the paths from node A to node B

You are given a bunch of nodes evenly spaced in a rectangular shape. The rectangle is M nodes long and N nodes wide. Node A is in the upper left hand corner and node B is at the bottom right hand ...
2
votes
0answers
27 views

Delete $2^{k-1}$ numbers from $(0, 2^n+1)$ interval; the maximum distance between deleted numbers at step $k$ must be $2^{n-k}$

The problem I have two integers, $n$ and $p$: $n \ge 1$ $1 \le p \le 2^n + 1$ Consider the sequence of numbers: $0, 1, 2, ..., 2^n, 2^n + 1$. $0$, $p$, and $2^n + 1$ in the sequence are marked as ...
0
votes
1answer
79 views

How can I prove algorithm correctness? [closed]

How can I prove algorithm correctness ? when i face a problem and come up with a solution the only way to know if this a valid solution or not is by trying some test cases. if they pass through the ...
2
votes
1answer
22 views

Turning a simple polygon with holes into exterior-bounded only

I am converting cartographic objects, which have an exterior boundary (simple polygon) and zero or more interior boundaries (also simple), into a less sophisticated format that specifies exterior ...
1
vote
0answers
9 views

Multiple sequence Progressive alignment example using five sequences

I tried to find sources that explain multiple sequence alignment with an example using progressive alignment, but I couldn't find one. I actually know till creating a guide tree, after creating a ...
3
votes
1answer
39 views

Algorithm for automatic/optimal database joins?

I'm curious if there is existing literature or well known algorithms out there for a problem I am working on. Given a normalized relational database with valid foreign key constraints and a list of ...
2
votes
1answer
40 views

Fast algorithm for interpolating data from polar coordinates to cartesian coordinates

I have a set of solution nodes generated over a polar grid. I would like to convert / interpolate these solution nodes onto a Cartesian grid: That is, using the image above, for each node in the ...
6
votes
3answers
147 views

When did polynomial-time algorithm become of interest?

I would like to understand why and when polynomial algorithms became of interest. When did people realize the role and importance of efficient versus non-efficient algorithms? Did that happen when ...
3
votes
1answer
17 views

Learning a small disjunction using an input distribution of our choice

I have a boolean function $f: \{0,1\}^n \to \{0,1\}$ that I know takes the form $$f(x_1,\dots,x_n) = x_{i_1} \lor x_{i_2} \lor \dots \lor x_{i_k}.$$ I don't know the values of $i_1,\dots,i_k$, but I ...
0
votes
1answer
64 views

Complete examples of program correctness proofs

Does anyone have any complete example of a proof of program correctness? I'm talking about something that includes the usual predicate, base case, inductive hypothesis, and inductive step. But also ...
2
votes
1answer
18 views

Learning a small disjunction

I have a boolean function $f: \{0,1\}^n \to \{0,1\}$ that I know takes the form $$f(x_1,\dots,x_n) = x_{i_1} \lor x_{i_2} \lor \dots \lor x_{i_k},$$ but I don't know the values of $i_1,\dots,i_k$. ...
-1
votes
1answer
29 views

Printing the array elements sorted by repetition [closed]

I just can't figure this question out: Given an array of N elements, its values range are from 0 to 100. Write a function that prints the array's elements sorted by repetition. Time complexity : ...
0
votes
1answer
15 views

What is the order of this traversal method?

Please see below pseudo-code for finding the max-height of a b-tree ...
1
vote
1answer
29 views

Do compression tables exist and where are they used?

Let's take the zip compression for example, from what scraps I can gather on the Internet, the 2 major simplified ways it works is by looking for arrangements of bits that repeat throughout the file, ...
2
votes
3answers
86 views

Algorithm for finding all the combinations on a boolean array

I have to design an algorithm to do the next task: I have one array of booleans. For example: Array: [0 1 0 0 1 0 1 1] I want to obtain all the existing combinations of 1's, having in mind that ...
9
votes
0answers
101 views

size of maximum matching in a bipartite graph

I've been wondering if there's a way to determine the size of a maximum matching in a non weighted bipartite graph without paying the full price of actually computing the matching itself. It's a long ...
0
votes
1answer
16 views

Most Efficient Method To Determine Triangle Fill Values Based On Corner Values

I have a triangle and the value of the pixel intensity at each of the three corners of the triangle. I want to interpolate to find interpolated pixel intensities for a set of points inside the ...
-1
votes
0answers
17 views

What is an efficient algorithm to find the factorial of huge numbers which lie in the range 100000-1000000? [duplicate]

I need to know, What is an efficient algorithm to find the factorial of huge numbers which lie in the range 100000-1000000? please kindly help me this
1
vote
1answer
24 views

Enumerating connected subgraphs [closed]

Is there an efficient algorithm to visit/enumerate all unique connected subgraphs of a labelled graph? E.g., when the graph is a path, $v_1v_2\dots v_N$, there are $N(N-1)$ unique connected graphs: ...
4
votes
2answers
70 views

Algorithm to find sequence of minimum moves to sort 13 card hand

Just for fun I am trying to write a program to sort the 13 cards (from a standard pack of 52) in a Bridge hand by performing human-like moves on the hand. A sorted bridge hand is arranged by suit, ...
1
vote
1answer
64 views

Computing the k shortest edge-disjoint paths on a weighted graph

Looking for k shortest paths that do not share edges. i.e if the paths were represented as sets of edges, their intersection has to be empty. We could use Dijkstra to find the 1st "disjoint" (edge ...