Questions related to design and analysis of algorithms

learn more… | top users | synonyms (1)

2
votes
0answers
12 views

Minimal complexity for pairing two comparable sets with comparability restrictions

A project at university (whose deadline has passed by now) presented the following problem: Consider two finite sequences of (not necessarily distinct) real numbers $a_1,\ldots,a_n$ and ...
0
votes
0answers
20 views

Find a path in a complete graph with cost limit and max reward

I'm looking for an algorithm to solve this problem. I have a region in which there are several areas identify by its id and x,y,z position. I've made a graph in which each vertex identifies one ot ...
1
vote
1answer
13 views

What is the optimal strategy for filtering a large collection of items with multiple filter functions?

I have a large collection of items, and a list of independent filters (boolean functions). I want to find the collection of items that pass all of my filters as quickly as possible. This must involve ...
0
votes
2answers
43 views

Fast implementation of basic addition algorithm

Write code for a modified version of the Grade School addition algorithm that adds the integer one to an m-digit integer. Thus, this modified algorithm does not even need a second number being ...
8
votes
1answer
48 views

Determining the minimum number of edges to add in order to be 3-connected

A graph $G$ is said to be $3$-connected if it has no $2$-vertex cutsets (i.e., at least three vertices must be deleted to disconnect the graph). As far as I know, it is possible to determine if a ...
-3
votes
1answer
30 views

Complexity Analysis for a nested loop with two methods [duplicate]

Hey I am studying for my intro algorithms class final and I'm not sure if I'm understanding this question correctly (its from a sample final exam). If someone could explain this to me that would be ...
1
vote
1answer
27 views

Using A* search with different heuristic values

I am currently trying to use A* to create cyclical routes (for plotting driving routes of set distances). I want to find a driving route from my start location that is as close to my specified length ...
1
vote
2answers
44 views

How to enumerate minimal covers of a set

I have a set $S$ and a set $P = \{P_{1},...,P_{n}\}$ with $\bigcup P_{i} = S$. I want to find all the inclusion-minimal subsets of $P$ that are covers of $S$. What is the best algorithm for ...
4
votes
2answers
79 views

Do all greedy algorithm produce just the first solution, no matter how bad it is?

In all the exampls of the greedy algorithms I've seen so far, such as activity selection problem and unit-sized set coverage problem, the algorithm is usually very simple and intuitive and returns the ...
3
votes
0answers
61 views

Are there any algorithms where the recovery of a witness changes the time complexity?

In many algorithms, such as the solution to the longest-subsequence problem using dynamic programming, finding the length of an answer (or signaling the nonexistence of an answer) is easy, but ...
0
votes
1answer
14 views

Modified Bellman Ford to find minmum cost cycle in O(E²V) time?

I'm thinking about how you can modify Bellman Ford a bit to calculate the minimum weight cycle in an undirected graph with positive weights. Note that the constraint is that the algorithm must run in ...
2
votes
1answer
42 views

Time complexity of solving a set of 2-sat instances?

Suppose I have a set of 2-SAT instances, the set is of size $2^{3C}$ for some constant $C$. What is the time complexity of solving all instances using the fastest known 2-SAT solver?
1
vote
2answers
42 views

If algorithm runs $\theta(n)$ in time T, doubling input size has what effect on time T?

In other words, is there a relationship between the step size and the actual running time? Suppose that the algorithm is run on identical machine.
4
votes
2answers
45 views

Algorithms: Difference Constraints

I'm currently studying for my algorithms final and I came across a practice problem that I can't seem to figure out. Here's the problem: Consider the following set of difference constraints: ...
5
votes
1answer
68 views

Find set of points with maximum distance inside given intervals?

Let $A$ be a set of $n$ closed intervals, $I_i$, with both extremes positive integers. Is there an efficient algorithm to find a set of $n$ points $P_i$, with $P_i \in I_i$, such that the minimum ...
5
votes
3answers
174 views

How to choose the maximum number of nodes (with constraints) from a graph

Consider a connected undirected acyclic graph $G$ with $n$ nodes and $n-1$ edges. The nodes have non-negative integer weights less than $n$. A positive integer $x$ is given and you want to choose at ...
1
vote
1answer
74 views

LazyHeap data structure with $O(n)$ Insert, Delete, and Return operations

Consider a data structure called LazyHeap that supports the following operations: INSERT(x): Given an element $x$, insert it into the data structure. It has no cost. DELETE(x): Delete $x$ from the ...
0
votes
1answer
17 views

Devise a backtracking algorithm to allocate $p$ projects to $s$ students

There are $p$ projects and $s$ students where $p \le s$. Multiple students can work on the same project but the same student cannot work on multiple projects. All projects must be allocated and all ...
2
votes
1answer
42 views

Picking an $m$ which minimises the sum $\sum_{i=1}^{i=n} |x_i-m|$ where $x_i$ is an element of the list $[x_1,x_2,…,x_n]$

I've got the following problem: Tommy has a toy consisting of wooden posts and in each move he can either hit one post (which decreases its height by 1) or pull out a post (which increases its height ...
1
vote
1answer
37 views

Particular techniques for NP-complete problems

Is it possible to show particular classes of techniques (for instance dynamic programming) cannot produce polynomial time algorithms to any NP-complete problem?
2
votes
1answer
29 views

ANN - Backpropagation with multiple output neurons

Can I utilize the backpropagation algorithm in a layered, feed-forward ANN in instances where there are multiple output neurons? If so, how? Links to (somewhat) comprehensible resources would be ...
2
votes
1answer
19 views

Creating a one-to-one mapping between a N-length list and M workers?

I have a list of length N, and I have M workers. I want each of my workers to independently select a contiguous section of the list, with the property that every element of my list is selected by ...
-1
votes
0answers
16 views

Why do comparison-based sorting algorithms have a lower bound of Ω(n log n) for their worst-case running time? [duplicate]

I get that any comparison-based sorting algorithm has a lower bound of Ω(n log n) for its worst-case running time, but why is it so? Is there anyway I can prove it?
-1
votes
0answers
16 views

Load .bmp file to Borland Pascal [closed]

Can someone, please, help me with loading bmp file into (Borland, Free) Pascal? I have decided to encrypt bmp file but I am still struggling with loading bmp, reading the file header etc. Thank you ...
13
votes
2answers
180 views
+150

How many cookies in the cookie box? — Tiling stars

With holiday season coming up I decided to make some cinnamon stars. That was fun (and the result tasty), but my inner nerd cringed when I put the first tray of stars in the box and they would not fit ...
1
vote
1answer
29 views

How to find a 2-wise independent hash family that is not 3-wise independent?

I'm trying to find a family of hash functions mapping $\{1, 2, ..., 2^n\}$ to $\{0, 1\}$ that is 2-wise independent but not 3-wise independent. Any ideas on that? I know two 2-wise independent ...
0
votes
1answer
24 views

Finding three factors of a number with minimal sum

Suppose that we have a number $x \in \mathbb{Z}^+$. I am seeking an algorithm to find three numbers $a, b, c \in \mathbb{Z}^+$ such that $a \times b \times c = x$ and $a + b + c$ is minimum. Is this ...
2
votes
2answers
72 views

How to go about proving an algorithm correct?

The algorithm (called as rmax(1,n)) finds the maximum of a list of numbers contained in an array S[1..n]. ...
2
votes
2answers
42 views

Counting inversion pairs - $n^2$ results in $n \log n$ time?

The number of possible inversions in an array is bounded by $\binom{n}{2}$, i.e $\frac{n(n-1)}{2} \in O(n^2)$. How it is possible to calculate $O(n^2)$ results in $O(n\log n)$ time using something ...
4
votes
4answers
124 views

How again do certain sorting methods use $o(n \log n)$ time?

I hope this question isn't too 'soft' for here. It's been a while $\tiny{\text{an eternity for some people's standards}}$ since I've touched this stuff, and I had a convincing explanation to this ...
-2
votes
0answers
40 views

Sorting aray of $-1$, $0$, $1$ in $O(n)$ time [duplicate]

I'm trying to come up with an algorithm to sort an array where each element is a $-1$, $0$, or $1$ in $O(n)$ time, where $n$ is the length of the list. Here is my solution (written in Python): ...
0
votes
0answers
25 views

Use binary indexed trees to find the number of increasing sub sequences in an array [closed]

I want to find the numbers of increasing subsequences in an array and I came across a Binary index tree which provides us with an $O(\log n)$ solution. I can't understand the code used for BIT: ...
0
votes
1answer
35 views

Resolution refutation [closed]

This is an assignment so I don't want the answer, just maybe a push in the right direction. The question is: Suppose you are given an algorithm $R$ that can test for any propositional formula in ...
0
votes
1answer
22 views

Voronoi diagram algorithm with non-euclidean metric

Do you know any easy to implement algorithm for construction Voronoi diagram from given set of points on a surface, using some different metric (taxicab, for instance)? It can be some modification of ...
0
votes
3answers
53 views

How can I keep track of the state of a sequence after rotating parts of it multiple times?

Given a sorted array 1 2 3 4 5 6 7 8 and an operation that takes the N-th element out the array and puts it in front (or rotates the first N elements to the ...
0
votes
0answers
7 views

Java: Incorrect Output [Code placement / Reading from a file] [migrated]

Today I am working on a program that reads in a copy of the constitution, allows a user to input three words and have those three words checked in the file and output how many times those three ...
2
votes
1answer
27 views

What is With High Probability on Probabilistic Algorithms?

I watched lecture from MIT about Skip List. Overall, I understand the material, but one thing. What is "with-high-probability"? I really don't get it at all. I've seen the lecture notes but still ...
2
votes
1answer
117 views

task scheduling optimization problem

I'm interested in such problem. I have a set of $n$ tasks ${T_i}$ and directed acyclic graph, which nodes correspond to tasks and edges correspond to order of execution two tasks. In other words if I ...
0
votes
2answers
43 views

Genetic Algorithm Minimum Population Size

Is there a minimum limit to a pool (population) size when using the genetic algorithm to solve an optimization problem? For example a population of size 2.
0
votes
1answer
54 views

Approximate the order of summation of two vectors

Assume we are given two vectors $A,B$ that each contains $c$ numbers: $A=[a_i>0]_{1 \times c}$. We want to see the weighted summation of which one is larger. In other words, given two vectors $A$ ...
2
votes
2answers
39 views

Difference between edges in Depth First Trees

I have a directed graph, where each node has an alphabetical value. The graph is to be traversed with topological DFS by descending alphabetical values (Z-A). The result is $M,N,P,O,Q,S,R,T$ (after ...
0
votes
0answers
23 views

Algorithms for verifying and solving three-coloring [duplicate]

I found the following problem that I am trying to answer: Consider the three color problem where V, vertex set of a bipartite graph. can be partitioned into three subsets such that there is no ...
1
vote
0answers
27 views

Getting ALL negative weight cycles of a graph using Bellman-Ford

I'm doing a min cost assignation problem to assign doctors to their working days for a hospital. After correctly getting the max flow with Ford-Fulkerson algorithm, I would like to use the cycle ...
-1
votes
0answers
31 views

Dynamically weighted priority queue? [closed]

Elements are stored in a single dynamic data-structure $D$ Element ranks are computed by: $\forall i \in n\quad f(i,\ x_i+1) : x_i \in \mathbb{Z^+}$ The function $f$ is weighting based on the value ...
1
vote
2answers
71 views

Find the coins required which sum to S

Given a list of $N$ coins, their values $V_1, V_2, \cdots , V_N$, and a parameter of a total sum $S$. Find the coins the sum of which is S (we can use each coin at most once). I was recently studying ...
0
votes
1answer
40 views

FM-index - print all patterns

How is it possible to print all patterns, of length k, contained in a string using FM-index and burrows-wheeler transform? PROBLEM DETAIL: I think it's better to leave more details regarding my ...
-1
votes
1answer
25 views

Vertex degree in De Bruijn graphs

How can I find the degree of a vertex in a De Bruijn graph? Also, given a vertex, is there an easy way to find which other vertices it is connected to?
5
votes
2answers
99 views

Is Dijkstras algorithm used in modern route-finding systems?

Is Dijkstra's algorithm used in modern route-finding systems such as Google maps or the satnav in your car? If not, then what is?
3
votes
1answer
39 views

Listing integers as the sum of three squares $m = x^2 + y^2 + z^2$

I would like to write an algorithm that lists all the ways a natural number $m \in \mathbb{N}$ can be written as the sum of three squares $m = x^2 + y^2 + z^2$ with integers $x,y,z \in \mathbb{Z}$. ...
0
votes
2answers
48 views

find the optimal combination [closed]

Suppose I have these values with weights -- $$ x_1 = 2\\ x_2 = 4\\ x_3 = 5\\ $$ There is no negative or $0$ value. I need to find $2$ element subset with maximum value computed from a function ...