Questions tagged [algorithms]

An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to design and analysis of algorithms.

Filter by
Sorted by
Tagged with
0
votes
2answers
37 views

Find the maximum number of contiguous occurrences of smaller string s in a larger string l

Say we have two strings s and l, and they only have characters 'a' through 'z' (lowercase English alphabet characters). The task is to find the maximum number of consecutive occurrences of s in l. Ex. ...
3
votes
1answer
137 views

Find a vector of non-negative integers $b$ that minimizes $\prod_{i = 1}^{D}\left(a_i + b_i\right)$ such that the product is a multiple of $c$

I'm trying to come up an efficient algorithm that, given a list of positive integers $a = \left(a_1, \ldots, a_D\right)$ and positive integer $c$, finds a list of non-negative integers $b = (b_1, \...
1
vote
0answers
12 views

What is spatial information in neural network? [duplicate]

The architecture of the CNN model contains several convolutional layers, non-linear activations, batch normalization, and pooling layers. The initial layers learn the low-level concepts such as edges ...
1
vote
1answer
16 views

On efficiency analysis of randomized divide-and-conquer median find

I read following explanation from Dasgupta's Algorithms book for Median finding, this is the same philosophy applied in randomized quick-sort. Here as per book terminology $S$ denotes array of ...
1
vote
0answers
14 views

What problem is this application of simulated annealing trying to solve?

I was reading about simulated annealing on its Wikipedia page, and was drawn to a particular example illustrating the annealing schedule. Below is the picture and its description: Example ...
0
votes
0answers
80 views

Devise Mont Carlo and Las Vegas Algorithms to Solve Maximum Independent Set

I am trying to devise a Las Vegas algorithm to solve Maximum Independent Set, but I don't know how to start. Also, I want to devise a Mont Carlo algorithm for this problem. I would appreciate any help....
0
votes
1answer
20 views

Distance transform with variable “impedance”

The distance transform gives the distance of each pixel in a mask to the nearest zero. E.g. lets take the Taxicab distance transform: ...
-1
votes
0answers
35 views

Finding a Spanning Tree Using other Spanning Trees of $G=(V,E)$

I am having trouble coming up with a polynomial time algorithm to solve the following problem: Let $𝐺=(𝑉,𝐸)$ be an undirected and unweighted graph with $𝑛$ vertices. Let $𝑇_1,𝑇_2,...,𝑇_π‘˜$ be $οΏ½...
0
votes
3answers
44 views

Finding a $g(n)$ so that $f(n) = O(g(n))$

I am having trouble on the following algorithms question: Given $f(n) = \sum^n_{y{=}1} (n^5\cdot y^{22})$, I am trying to find a $g(n)$ such that $f(n) = O(g(n))$. I know that this means I need to ...
1
vote
2answers
31 views

Efficiently enumerating all “good” strings given the ability to say whether a partial specification can be good

Suppose that I want to enumerate all English language words of length 5. If I've got nothing more than a check of whether an arbitrary string is an English word, I have to do 5^26 calculations. ...
-4
votes
1answer
31 views

Finding a clique in undirected graph is P or NP? (proof) [duplicate]

Finding a clique $C$ in an undirected graph $G= (V, E)$ such that $|C| > |V|/2$ is in P or NP-hard? How can I prove it?
0
votes
1answer
74 views

Each cycle in the graph, the edge with the minimum weight belongs to MST

Let $G=(V,E)$ be a weighted undirected connected graph and $w: E \to \mathbb{R^{+}}$ a weight function so that there are no two edges that have the same weight, and $T$ is an MST of $G$ . Then in ...
4
votes
3answers
166 views

Algorithm for solving a mixed integer programming problem in polynomial time?

I have the following mixed integer programming (MIP) problem: $$ \begin{array}{rll} \text{Maximize } & z=k \\ \text{subject to } & a_ik - m_i \geq 0 & (i=1,\dots,n) \\ & b_ik - m_i \...
2
votes
1answer
27 views

Algorithm to evenly distribute a hierarchical dataset

I am working on a chatbot designer interface. The dataset for the conversation flow consists of messages. Each message has a parent message and can have multiple possible next messages. The system ...
0
votes
0answers
27 views

Cycles of a multigraph with a property on the edges

Let $n$ be a positive integer. On a circle are arranged $n$ points $A_1$, $\ldots$, $A_n$. We put some arrows from $A_1$ to $A_2$, from $A_2$ to $A_3$, etc., from $A_n$ to $A_1$. On each arrow are ...
1
vote
2answers
52 views

Sum duplicates in array problem

I get $n$ numbers, where every number is an integer between 1 and 1000. If within given numbers are duplicates, I sum all of them to one number. I repeat it until I have only distinct elements. As a ...
-1
votes
1answer
48 views

Kohonen, 1 dimension, SOM, puzzle

We consider training one-dimensional open map of Kohonen with neurons in one-dimensional input space. We assume it is completed the phase of the device and the weights $w_i$, $i = 1,2, \dots, N$, are ...
1
vote
1answer
21 views

How do i make sure i get the correct Bellman Ford path?

I was studying shortest path algorithms and was met with an issue regarding Bellman Ford for the image below. Following the graph, i see that node 3 has a length of 1 while node 2 has a length of 2. ...
3
votes
1answer
73 views

Completing tasks on a graph

Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. The graph $G$ is complete, which means we can traverse $(i, j)$ for all $i, j \in V$. At each vertex $v \in V$, there is a task that ...
1
vote
1answer
15 views

Sorting in computing longest increasing subsequence

I am currently reading the paper On computing the length of longest increasing subsequences by Michael L. Fredman. I'm struggling to understand parts of the proof of Theorem 3.5, especially this bit: ...
0
votes
3answers
89 views

Computing square vs computing square-root? Time complexity

I am working on something that requires checking a very large natural number $x$ to determine if it is the square root of an even larger natural number $y$. So I am wondering what are the fastest ...
1
vote
0answers
22 views

Even distribution of weighted sums across a period of time

I want to automatically&optimally split and distribute a number in several buckets as evenly as possible across a period of time. Example: 5000 across 12 months, in 6 buckets, with weights 15%, ...
1
vote
0answers
26 views

Binary ↔ Gray permutation matrix

Generating a Gray code representation of a binary number can be thought of as mapping one binary number onto another binary number. Therefore, $n$-bit Gray code is a permutation of $2^n$ elements. ...
2
votes
1answer
38 views

Algorithm to sample high-dimensional parameter space of expensive cost function

I am looking for recommendations for algorithms (apparently this is the right SO site for that) that efficiently scan the high-dimensional parameter space of a cost function that is very expensive to ...
0
votes
0answers
13 views

Finding time complexity of a depth first traversal algorithm with a depth limit to get all node traversals starting from the root node

What would be the time complexity of a depth-first traversal algorithm on a graph, that is simply trying to retrieve all nodes being visited from starting node up until a depth limit is reached (i.e. ...
1
vote
1answer
22 views

Notations for dealing with generators in algorithms

This question is about generators, which are functions that return an item from a (usually very large or infinite) set on demand, an example from Python is: ...
1
vote
0answers
27 views

Dijkstra's algorithm - additional properties

Say we let $R$ denote the set of currently chosen vertices in Dijkstra's algorithm, $d$ be the currently stored path-length estimates, and $s$ be the source. The standard property that we know is true ...
0
votes
0answers
27 views

kth smallest element using Randomized select

I have recently started studying Randomized algorithms on my own. I am refering to Rajiv motwani - randomized algorithms book. Objective - find kth smallest element using radomized select in $O(n^\...
1
vote
1answer
53 views

Finding “entrance” points in a set of d-dimensional points. Can I do better than O(N^2)?

I am given a set of d-dimensional points, and need to find the set of entrance points in them. Definitions: A point p1 captures p2 if 1) All dimensions of p1 is smaller or equal to p2; and 2) At ...
1
vote
0answers
45 views

Turning an unsafe state into a safe state - Banker's Algorithm

I have included an example in my question. I know this state is unsafe as there are no full sequences in the process. However, is there a way to arrive at a safe state from it at all?
0
votes
0answers
18 views

What is a good approach to deciding which jobs (from a list of HPC jobs) should be ran locally vs. on the cloud given time & cost constraints?

Cloud computing has transformed the landscape of compute operations. Of course, there are still many labs/businesses with local, large-scale compute clusters. For those businesses who keep the ...
1
vote
0answers
35 views

Optimal order to traverse a grid with caching

Let's say I want to evaluate a two-argument function using all possible combinations of elements from sets A and B as arguments. For example, if the function is addition, we get this grid: ...
1
vote
1answer
65 views

Time complexity and upper and lower bounds

Consider the following algorithm: (the print operation prints a single asterisk; the operation x = 2x doubles the value of the ...
0
votes
1answer
35 views

Algorithm chalenge: find minimum range to cover all houses with light

N houses are located on a straight street which has K streetlights. Each streetlight has range R. Given N and K how to find minimum value for R? N is an array containing location of each house. K is ...
0
votes
0answers
19 views

Software for triangulation flip graphs?

I need to generate flip graphs on around 10 points (more would be nice). Specifically, I would like flip graphs on subsets of the integer lattice, so the coordinates of each point are integers. Is ...
1
vote
1answer
51 views

Can't wrap my head around on building a suffix table for Boyer Moore

My resources were the following video, as well as this video. Basically, in one of the videos they state that the good suffix table for the pattern "ABCBAB" is the following: k suffix d2 1 ...
2
votes
2answers
126 views

Shortest path including all nodes in a subset

Given a directed graph $G=(V, E)$, two nodes $s, t \in V$ and a subset of nodes $U \subseteq V$. Provide an algorithm that determines if there is a shortest path from $s$ to $t$ that passes via all ...
1
vote
1answer
83 views

What does Dijkstra's algorithm become, when you replace path cost with edge cost?

Consider a variant of Dijkstra's algorithm (for a directed graph) where nodes are visited not in order of total path cost, but in order of incoming edge cost. (Assume here that all edge costs are ...
1
vote
1answer
32 views

Bellman Ford Source & Negative Cycles

I’m having some troubles with Bellman Ford Algorithm in the following exercise My guess is that at the end the algorithm should detect the negative cycle BD DF FG GB since B is decreasing at Vth (i.e. ...
0
votes
0answers
18 views

How to find diffrenet ways to implement merge and delete_min operation in binomial heap?

I have searched on the internet to find different ways to learn binomial heap operations. What I have found is not quite helpful for me.For example, for delete min operation the algorithm says: ...
2
votes
1answer
39 views

Find the set of all edges which there is a cycle such that for every $e' \in C, e'\neq e$ : $w(e')\leq w(e)$

Given an undirected graph $G=(V,E)$ and weight function: $ w: E \rightarrow \{1,2,...,10\}$. Describe an algorithm that finds the set of all edges $e\in E$ for which there is a cycle $C$ in $G$ that ...
1
vote
1answer
21 views

Is transfer learning applied on only similar datasets only?

I am trying to make a CNN model on different brands of logos . Firstly , I wrote a CNN from scratch and trained it on which I got 70% accuracy, I have total 40 classes and each class has 100 images . ...
1
vote
0answers
46 views

Best algorithm/model to establish relevance between events utilizing mixed data type (Tags, Time, x_coordinate, y_coordinate)? [closed]

I'm building a relevance ranking system for incidents occurrence and prevention. My goal is to use four attributes to establish relevance: tag (About 500 tags), x_coordinate, y_coordinate and time. ...
1
vote
1answer
60 views

Counterexample to greedy solution for set cover problem

I am looking for the answer to the exercise 1-6 in "The Algorithm Design Manual" book. it is stated as follows: 1-6. The set cover problem is as follows: given a set of subsets $S_1,\dots,...
1
vote
2answers
29 views

Given a list of vertices in a binary tree output minimal sublist with the same lowest common ancestor

The input: a binary tree and a list $L$ of vertices in that tree. The output: a sublist of $L$ of minimal length that has the same lowest common ancestor as $L$. If there is several sublists of ...
2
votes
0answers
29 views

find zero weight cycles in a directed graph [duplicate]

I need to plan an algorithm that decides if a directed weighted graph $G = (V,E)$ has a zero weight cycle. the graph has no negtive cycles the algorithm needs to be in $O(|V| \cdot |E|)$ time my ...
0
votes
1answer
18 views

How to position images within a canvas while avoiding overlapping

I have a canvas. On this canvas, I want to position 1, 2 or 3 images. The images can be positioned anywhere on the canvas just as long as they're within the canvas. The images move by their top-left ...
0
votes
0answers
24 views

Characteristics of max-heaps

I have just reached the priority queue section where the book I am currently reading about algorithms talked about max-heaps and min-heaps. As a part of its structure, the book would ask the reader a ...
0
votes
1answer
53 views

Algorithm for sorting within windows

I am writing an app which displays speeches on various topics, with each speech having a number of attributes. I want to give the user the choice to sort a list of speeches by an attribute, even ...
0
votes
1answer
40 views

2-3 tree: Sum of leaves in a given range

I am implementing a 2-3 tree, where every leaf has a unique key and a value, and I need to write an algorithm which finds the sum of values of the leaves which ...

1 2
3
4 5
…
186