Questions related to design and analysis of algorithms

learn more… | top users | synonyms (1)

0
votes
1answer
12 views

get time slots available in any of workshop

I have a list of Workshops, each having open_days (Monday, Tuesday etc.) and open_time and close_time (which will be same for each day). Now, Based on the current time, I need to find out next 7 days ...
2
votes
1answer
11 views

minimize $l_1$ distance between vectors

Given two vectors $a$ and $b$ I need to find $k$ such that $\sum_i|a_i - kb_i|$ is minimal. In other words, my goal is to find $k$ that minimizes the $l_1$ norm distance between $a$ and $kb$. How ...
2
votes
0answers
26 views

Smallest real root of a polynomial in a range

I'm trying to numerically find the smallest real root of a polynomial in a given range. My initial plan was to shift the polynomial so that the bottom of the range was 0, expand the resulting ...
0
votes
1answer
31 views

Are all problems approached and solved in fundamentally the same way?

This question might be a bit to vague, not make sense, or not developed enough yet to ask, but I thought I might give it a shot. This questions stems from a conversation a friend and I were having ...
-1
votes
0answers
15 views

Shortest path in a weighted graph with coloured edges

I have a weighted undirected graph with N veritces and M edges. Each edge has its weight and colour. There are at most 10 different colours in the whole graph. Each time I pass edges of different ...
-1
votes
2answers
55 views

Is there a bounded-time algorithm for Envy-free cake-cutting?

I am engineering student,i have doubts regarding the topic can anyone help me to find solution.
-1
votes
1answer
35 views

How to Modify SAT Solvers to Produce Resolution Refutations for Unsatisfiable Instances?

In recent SAT competitions, there is a Certified UNSAT track. The problem instances are all unsatisfiable and the solvers are asked to produce certificates for unsatisfiability. One way is to produce ...
-1
votes
2answers
70 views

Understanding Dijkstra's algorithms

As far as I understand, Dijkstra's algorithm always picks the nearest neighbour. But how does it work for the following graph? ...
1
vote
1answer
35 views

Is this special case of a flow problem solvable in linear time?

Alice, a student, has a lot of homework in over the next weeks. Each item of homework takes her exactly one day. Each item also has a deadline, and a negative impact on her grades (assume a real ...
2
votes
0answers
22 views

Vertex Disjoint Path Covers of Hypercube-Like Graphs

This is a followup question relating to an older question I posted, namely: Decomposing the n-cube into vertex-disjoint paths. Given a graph $G = (V, E)$ and sets of distinct vertices $S = \{s_1, ...
-3
votes
0answers
20 views

Can one use BFS to obtain a MST for a weighted undirected graph?

Can one use BFS to obtain a MST for a weighted undirected graph ?
1
vote
1answer
18 views

Reconstruct the minimal path cost from the delta-stepping algorithm?

I was coding the delta-steppping algorithm from this paper. They describe almost everything about the algorithm but not how to get the path. As an output I am getting the dictionary tent where ...
0
votes
1answer
19 views

Levenshtein distance cabable working with (large) vectors - not strings

Long version: Is there any algorithm similar to Levenshtein distance which can compare vectors? I will post several examples with desired inputs/outputs and then I will also show that it is not the ...
1
vote
1answer
11 views

Length of an Edit Script and the Number of Deletions

I am reading the 1989 paper called "An O(NP) Sequence Comparison Algorithm" by Wu, Manber, Myers, and Miller. The algorithm sounds like a good fit for a project I'm doing at work. I have found some ...
0
votes
0answers
24 views

Find cheapest path from 1st city to the $n$th city

The title may be a bit misleading, but this is essentially a DP problem. The problem is that we have $n$ cities labeled from $1, ... n$ and we are trying to find the cheapest way to travel from 1 to ...
2
votes
1answer
20 views

TSP problem with a benchmark data

I've got a test Travel Salesman Problem's data with known optimal solutions. It's in a form of set of 2D points. Particularly, this is a tsplib format; sources are here and here. I'd started a ...
1
vote
0answers
17 views

Trying to understand a way to split an AVL tree in O(log n)

I'm trying to understand a presentation about AVL trees. It says that the way to split AVL trees in node x is as follows: You search for the node x and mark every left son of every node when you turn ...
3
votes
0answers
41 views

Branch and Bound running time and golden ratio

This is a follow up question to When does Branch and Bound exactly stop giving solutions for the bin packing problem After testing many instances I found out that when r = V / Vtotal <= ϕ (Golden ...
-1
votes
1answer
22 views

Maximum flow with Edmonds–Karp algorithm

I am learning Edmonds–Karp algorithm , I formed following flow network, (capacity is described above arrow, where s is source and t is sink.) If we first follow path S - A - C - T , we will get ...
2
votes
0answers
58 views

Finding all cycles of length <=5 in a directed graph?

I was wondering if there's an efficient way to find all cycles of a graph of length <= 5 in a directed graph. I've read up on Johnson's algorithm that takes ...
0
votes
0answers
13 views

Finding patterns in data over time

My problem domain is: I have a large number of bins numbered from 0 - X. Each bin has a size of 1. Each bin can either be empty or full. They all start out empty. If a bin is full, it can be ...
1
vote
1answer
23 views

Efficient algorithm for finding weakly connected components

We recently studied Tarjan's algorithm at school, which finds all strongly connected components of a given graph. I was curious however how one would find all weakly connected components (I had to ...
1
vote
1answer
42 views

Algorithm to find a path connecting given nodes in a graph

Suppose I have $n$ nodes in a graph and I identify $x$ nodes in the graph (where $x < n$). I would like to find a path to connect all those $x$ nodes I have identified. Is there any algorithm for ...
3
votes
1answer
21 views

Algorithm for grouping identical neighbors in a list

I have a list that I want to reduce to a smaller list by grouping identical neighbors. This list has many many redundant entries. Example list: ...
2
votes
1answer
44 views

Hash function which is invariant under small changes

I am looking for a hash function which is invariant under small changes. E.g., if I have two strings MyString and MySttring ...
0
votes
0answers
12 views

Progressive distribution for set of items

I need to come up with progression formula / distribution algorithm. My global data is Amount of baskets S, amount of balls B, net size N. Example: B= 100 balls, N=10 balls in each Net, S=3 baskets. ...
0
votes
0answers
23 views

Get all possible combinations of distributing x*n balls into n boxes

I'm trying to figure out how to get all combinations of putting x*n balls into n boxes. ...
0
votes
0answers
39 views

Simple Way to Convert an Adjacency Matrix to a CSR Graph and Vice Versa

Let's say for the following weighted, undirected graph: I am given the adjacency matrix A[5][5]: ...
5
votes
2answers
307 views

Difference between algorithm and procedure

I came to know that the important difference between algorithm and procedure is that the algorithm halts and procedure doesn't halts(stops). But i am not able to understand the concept. Please can any ...
3
votes
1answer
17 views

Is there an alternative to full factorization for testing the Polya conjecture?

The Polya conjecture is a disproved conjecture that states over half the numbers less than any number has an odd number of prime factors. It first fails at $n = 906,150,257$, thus being a good example ...
1
vote
0answers
18 views

Can anyone give an example for worst case of quick sort if we employ median of three pivot selection?

If we employ quicksort by selecting the pivot as the median of three elements viz., the first element, the middle element and the last element, then when will the algorithm hit worst case? and also ...
0
votes
0answers
29 views

How to simulate a parallel computer (with certain number of processors) on a serial computer

I am a novice to parallel computing. I would like to solve the traveling salesman problem (TSP) using a parallel genetic algorithm (GA). I need to write a simulator of a parallel computer (for ...
1
vote
0answers
43 views

What is the difference between this bin packing problem and the knapsack problem?

I have these two problems: Problem 1 (Bin packing problem) Instance: A set of $n$ items where each item $i$ has weight $w_i$. A set of $k$ bins where each bin $j$ has capacity $W_j$. Question: Find ...
2
votes
1answer
73 views
+50

Finding pairs of points that have a given offset

Problem: Given a set of points $S = \{x_1, x_2, x_3, ..., x_n\}$ from $\mathbb{R}^m$ and an offset vector $v \in \mathbb{R}^m$, find a set $Z \subseteq S \times S$ containing $k$ pairs of points ...
6
votes
1answer
574 views

How to identify when to use Genetic Algorithm/Programming

I have been reading/studying on genetic algorithm/programming, and have implemented Traveling salesman problem. TSP is basically a permutation/combination problem, and I can understand how GA helps ...
-4
votes
0answers
24 views

Q: What is an NP-complete in computer science? [duplicate]

what is its importance in computers?What are P, NP, NP-complete, and NP-hard?
0
votes
3answers
116 views

Find a weighted median for unsorted array in linear time

For days, I'm trying to figure out, whether it is possible to find an item in array which would be kind of weighted median in linear time. It is very simple to do ...
4
votes
1answer
36 views

Maximize function over a set with a transitive and antisymmetric relation

Let $\mathcal{R}$ be a transitive and antisymmetric relation defined over a finite set $X$. For any set $S\subseteq X$ define $\Gamma(S)=\left\{y\in S \mid \not \exists x\in S . ...
-3
votes
0answers
21 views

Recursive Definition, Sum of Nodes at Level K, and how many leaves for a given Algorithm [closed]

I have an exam tomorrow and one half of the points on the exam has to do with analyzing a given algorithm that's in pseudocode and answering certain questions on the runtime and recursion trees ...
0
votes
0answers
19 views

RMQ with single index update in array

Range Minimum Query (RMQ) can be solved in (O(n), O(1)) if the array is known to be static by dividing it into blocks and then using Cartesian tree numbers to detect "similar" blocks. Link: ...
-3
votes
0answers
37 views

How to master the following Computer Science Subjects [closed]

1.Probability 2.Discrete Maths 3.Algorithm 4.Python 5.Artificial Intelligence 6.DBMS 7.Operating System(linux) 8.Networking
9
votes
7answers
2k views

How to find middle element of linked list in one pass?

One of the most popular question from data structures and algorithm, mostly asked on telephonic interview.
-3
votes
0answers
15 views

cryptography basics [closed]

I need to fill this table.Can anyone help?
0
votes
2answers
50 views

Longest substring with consecutive repetitions

I want to find the longest substring which is repeated without any gap between the repetitions. That is, given a string $x$, I want to find the longest $y$ such that $yy$ is a substring ...
0
votes
1answer
21 views

Would incrementing the min cut edges by 1 increase the max flow by 1 as well?

Given the theorem that max flow <= min cut, Would incrementing the min cut edges by 1 increase the max flow by 1 as well?
-1
votes
0answers
20 views

3-Sum Algorithm Recursion

HOW can we implement the 3-sum problem where the sum of the 3 numbers of the array is zero using only recursion.I figured that there are 3 recursive calls but I have not figured out the base case and ...
-1
votes
1answer
44 views

How to Convert a Directed Graph to an Undirected Graph (Adjacency Matrix)

Given an adjacency matrix, what is an algorithm/pseudo-code to convert a directed graph to an undirected graph without adding additional vertices (does not have to be reversable)? similar question ...
1
vote
0answers
14 views

Bounded pairwise distance on moving points

Suppose you're writing a video game that takes place on a large rectangle (2d). You have a large list of entities (monsters, spells, and so forth, represented as points) living on this rectangle, and ...
5
votes
1answer
65 views

A* graph search time-complexity

Some confusion about time-complexity and A*. According to A* Wiki the time-complexity is exponential in the depth of the solution (shortest path): The time complexity of A* depends on the ...
2
votes
1answer
53 views
+100

Find all non-isomorphic graphs with a particular degree sequence

I have a degree sequence and I want to generate all non-isomorphic graphs with that degree sequence, as fast as possible. The only way I found is generating the first graph using the Havel-Hakimi ...