Questions related to design and analysis of algorithms

learn more… | top users | synonyms (1)

0
votes
0answers
2 views

Find the 10 top most occurring strings in an input

Find the 10 top most occurring objects in a huge array of objects. I would also like to add that the array is huge and is itself divided into multiple arrays. My idea is to parse the arrays one by ...
-1
votes
0answers
4 views

Generate all different substring using suffix array and longest comman prefix array

We are given a string of length greater than 10000, we have to print total number of different substring present in the string. Please provide an algorithm using suffix array and longest common ...
5
votes
1answer
36 views

Algorithm to compose identity from a set of permutations

Given a subset P of all the possible permutations of a fixed set of elements, is there a non-exponential or optimized algorithm for computing the smallest composition of P that yields the identity ...
-1
votes
1answer
18 views

Fit stack of stone of varying length into a well of varying length

I have a stack of m stones of different Diameter. stack = [5,4,9,20,1] And a Well that is of depth n with varying diameter at different depths . ...
1
vote
0answers
15 views

Can smart recursive search find all optimal solutions for Closest String?

Consider the Closest String problem: Input: Strings $s_1, \dots, s_m \in \Sigma^n$ and $k \in \mathbb{N}$. Question: Is there $s \in \Sigma^n$ for which $d_H(s, s_i) \leq k$ for all $i ...
-1
votes
0answers
13 views

Strange tic-tac-toe board print in Java [on hold]

I am making a Java tic-tac-toe game and got really confused, because the console prints a really strange and big tic-tac-toe board, which is supposed to be 3x3, what is the cause? Here is the code: ...
0
votes
0answers
7 views

Change my visible IP from Java code in Http post [migrated]

For my thesis work I'm testing and trying to hack an online reservation platform. I am simulating some users that enter to the platform and perform hundreds of searches, at one time, in order to ...
-1
votes
0answers
14 views

network flow approach for maximizing number of jobs that can be scheduled

I'm curious to lean the network-flow approach to solve this problem. Hope someone here can take time to help me construct an appropriate and suitable graph for this problem. The constructed graph, ...
1
vote
1answer
18 views

Minimise simultaneous equation remainder

I'm not sure if this is the right place to ask, or what the right terminology to use is. The problem I have is this: I have a vector for example: v = [1,4,5,6,3,1,4,5,6,7,...7] and I have a set of ...
1
vote
1answer
63 views

Is this problem NP-hard?

Good day. Subset sum selection problem is NP-hard. I trying to solve following problem: Input: a grid NxN and subset size K and radius R. Every entry in grid contains a value. Solution: subset of ...
-1
votes
1answer
14 views

Checking a property of all of the cycles in a graph

Suppose $G= (V,E)$ is a directed graph with weights on the edges. I would like to check if $G$ has the following property: if $C \subset E$ is the set of edges in a cycle of length at least $3$, then ...
0
votes
0answers
20 views

Counter example to graph coloring heuristic using BFS [on hold]

I am considering the following heuristic for the graph coloring problem (i.e. to color a graph $G$ using a minimal number of colors so that no two adjacent vertices have the same color): Explore ...
3
votes
1answer
300 views

Algorithm to find all paths of length k

Consider the following definition of 3-friends: person 1 is 3-friends with person 2 if they are direct friends or person 1 is friends with a friend of person 2 or person 1 is friends with a friend ...
1
vote
2answers
66 views

Path optimization in a DAG: maximizing number of least cost arcs

I've got the following problem. I've a graph $G=(V,E)$ as in the picture and I have to calculate the optimal path from $R$ to $S$. The optimal path has to maximize the number of least cost arcs. In ...
3
votes
1answer
136 views

Does Ford-Fulkerson always produce the left-most min-cut

When using Ford-Fulkerson to find max-flow between s and t, the exact choice of flow-graph depends on which paths are found. However, if you then use the left-over residual graph to produce a min-cut ...
0
votes
0answers
27 views

A question about algorithm and code [on hold]

I am a very new user and I would like to know how to calculate the following operations in Mathematica. Honestly this is not a homework. I am an french architect and I would like to be back in Math ...
-1
votes
0answers
27 views

How quickly can we generate a random integer (asymptotically)? [on hold]

I'm looking for a RNG that either generates a random integer (from $-n$ to $n$) or generates $m$ random integers in this range. I'm mainly concerned with the speed of the RNG, although an even ...
0
votes
0answers
50 views

Design an algorithm to calculate the maximum amount of pairs $2a_i \le a_j$ that can be removed from a non decreasing sequence of n numbers

I am trying to solve the following problem: You are given a non decreasing sequence of $n$ unsigned integers $a_1 \le a_2 \le \ldots \le a_n$. You can modify this sequence using the following ...
2
votes
1answer
37 views

Efficiently enumerating all paths from i to j of given length in a graph

I've been trying to efficiently solve this problem : given a integer p > 0 and a directed graph whose nodes are 0, ..., N-1, enumerate (not simply count) all the paths (not necessarily elementary) ...
0
votes
0answers
37 views

Number of ways to connect sets of $k$ vertices in a perfect $n$ -gon [closed]

This is a copy of my post at Mathexchange.com, as my question is still not fully answered and I really wanna find a solution to this. Feel free to refer to there for useful comments and partial ...
1
vote
1answer
40 views

Dijkstra function for navigation for disadvantaged

Is there a way we can write a function for Dijkstra to determine which node to enqueue and which to discard. This is for a navigation solution for people with disabilities where path to stairs may be ...
1
vote
0answers
17 views

Find maximum scoring characters with non overlapping occurrences from a string

I have a problem related to Episode Mining in which I need to find the maximal utility of a episode given its occurrences in an event sequence.But I am presenting the question in a different form so ...
1
vote
1answer
47 views

Better algorithm for determining if a vertex is on any cycle in a graph

The problem I'm facing is the following: Given a simple undirected graph $G=(V,E)$ and a vertex $u \in V$, answer if $u$ is part of any cycle of $G$. The algorithm I can think of is to remove an ...
-2
votes
1answer
50 views

Dijsktra's algorithm example [on hold]

In the following example, how does Dijkstra's algorithm find the shortest path? I think we'll get abedz, while the shortest should be acedz.
1
vote
1answer
22 views

Optimizing iteration over all permutations of a bit array

edited for clarity: I have two functions–$f(x)$ which returns an integer and $T(x)$ which returns a boolean–that operate on a bit array of length $n$. I am trying to maximize $f(x)$ over all $x$ ...
3
votes
1answer
59 views

Maximum Flow with Binary Capacities

Consider the problem of finding a maximum flow from node $s$ to node $t$ in a directed graph where each link has capacity either $0$ or $1$. What is the state of the art regarding how fast this flow ...
0
votes
0answers
24 views

enumeration of all Maximal independent set on trees

what is the algorithm for enumerating all maximal independent set on trees (without the constaint of lexicographic order) . It 's very natural to find an algorithm faster than $ O(3^{n/3})$ on trees ...
0
votes
1answer
17 views

Order a list of edges to make the the complexity of searching for an edge O(lg E)

I was reading this article on how to represent graphs, and probably the simplest way to think about it is to have a list of edges, with an edget being usually a list of the vertices that are related ...
-1
votes
1answer
33 views

Deterministic processing on probabilistic input [closed]

I've designed an algorithm, is which responsible to process some samples from normal distribution under aegis of some deterministic steps. In other words, the algorithm generate unique response to a ...
1
vote
0answers
9 views

Algorithm for partial order width [duplicate]

I want to compute the partial order width i.e. the size of the maximum antichain in a given partial order. By Dilworth's Theorem this is the same as minimal chains required to decompose the graph, ...
-2
votes
0answers
20 views

How can we find a spanning tree with some nodes as leaves? [closed]

We have an undirected graph $G=(V,E)$ with $w_e$ the weight of edge $e \in E$ and $U \subset V$ a subset of the nodes. We are looking for a spanning tree where the nodes of $U$ are leaves. The tree ...
1
vote
1answer
20 views

Decreasing a digraph's edge-weights while keeping net weights of edges at each vertex constant

Given a directed weighted graph, is there an algorithm that does the following: Removes as many edges possible. Reduces as many weights as possible. Given the constraint that the net weight of all ...
1
vote
0answers
16 views

How do I apply a single iteration of Floyd's algorithm to an adjacency matrix? [on hold]

I have the following adjacency matrix for a graph with nodes {a,b,c,d}: \begin{bmatrix} & & a& b& c& d\\ & & & & & \\ a& & 0& ...
1
vote
1answer
18 views

Updating the MST of a graph G = (V,E) when decreasing the weight of one of the edges that is not part of the MST

You are given a weighted undirected graph G = (V,E). You have run Prim's algorithm and found the MST of this graph. Now you pick one edge that is not part of the MST and reduce its weight by some ...
1
vote
0answers
25 views

TSP heuristics for limited distance information [closed]

this is my first question on ComputerScience beta. :) I've posted a similiar question on Mathoverflow and a friendly user advised me to post my question on this site. Problem: I'm looking for ...
1
vote
2answers
70 views

Why are syntax trees used in genetic programming?

Reading a course on genetic programming, the first chapter describes the syntax tree as the basic representation of programs in genetic programming. What are the reasons leading to the choice of a ...
0
votes
1answer
24 views

Sub-Array with a unique element [closed]

You have an Array of length n. If you pick a sub-array from the array, it must contain at least one unique element. The sub-array could be of any length but must contain consecutive/successive ...
2
votes
1answer
111 views

How to improve my these specific math skills? [closed]

I am student of CS. Problem is, I feel that I don't have enough math knowledge to solve mathematical problems. When some programming problems arises which needs some math skills to solve then despite ...
-1
votes
1answer
34 views

Best pathfinding algorithm for undirected unweighted graph [on hold]

I have an unweighted undirected graph with every node connected with an average of two hundred other nodes (nodes are people from social network). What will be the fastest algorithm to find the ...
0
votes
1answer
26 views

What makes an MILP problem solvable?

Knapsack problems, Assignment problems can all be expressed as (MILP) mixed integer linear programs. MILP is NP-complete. But Knapsack problem is solvable in pseudo-polynomial time using dynamic ...
0
votes
0answers
10 views

Why can't fractional cascading be used on two unrelated arrays?

According to both Wikipedia and my professor (see question 5.1), fractional cascading has to be done on arrays with related data. The specific question: A fellow student wants to compactly store ...
2
votes
1answer
166 views

Mergesort with $O(n^2 \log n)$ runtime

I have a task where i need to find a problem in which mergesort has to have a runtime of $O(n^2 \log n)$. In our lecture we said that the runtime is $O(n \log n)$ assuming that every comparison is ...
1
vote
0answers
13 views

A query regarding the Max3SAT Approximation Algorithm's Application

Its known that a polynomial time Approximation Algorithm that satisfies 3MaxSAT in 7/8+e clauses implies P=NP. If given that the given 3MaxSAT is satisfiable, it is still difficult to find a 7/8+e ...
-2
votes
1answer
17 views

It is possible to implement insertion sort for sorting linked list ?

it is possible to implement insertion sort for sorting linked lists ? will it have the same O(n^2) efficiency as the array version ?
0
votes
1answer
23 views

Integer Knapsack Problem - No duplicates Allowed

In the bounded Integer Knapsack problem, we are given N items of sizes S1 through SN, having values V1 through VN. The problem requires us to find the maximum value that can be attained for a given ...
0
votes
0answers
29 views

a way to get shortest path tree

Given the shortest path tree of a directed graph $G=(V,E)$ and $w\colon E\to R$, source vertex $s$ and an assumption that there are no negative cycles in the graph. In the homework assignment we need ...
3
votes
1answer
101 views

Algorithm to search substring in a circular string?

I need an algorithm to search for substrings. I checked different resources, and it seems that the most known algorithms are the Boyer–Moore and the Knuth–Morris–Pratt. However, as far as I ...
2
votes
1answer
27 views

Counting the nodes in a network in a distributed way

There is a network with $n$ nodes. Each node can contact only the neighbouring nodes (the degree of each node is bounded, if that matters). One of the nodes, say $s$, wants to know $n$. How can it do ...
-3
votes
1answer
16 views

worst case of insertion sort

what is the worst case of insertion sort ?
3
votes
1answer
28 views

Minimum Length Hamiltonian Path Pair in O(n^2) or better

A friend and I have been discussing turning a $O(n^2)$ graph problem's algorithm into $O(n\log n)$, or at least less than $O(n^2)$. And no - this is not a homework question. We've narrowed it down to ...