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
1answer
10 views

Counting 3 chains

A 3-chain for an array is a subsequence of the array containing the first element of the array and the last element of the array. It also has the property that all consecutive elements of the ...
0
votes
0answers
5 views

Are there works on flows in networks with a dynamic structure?

I have a network that is initialized in some form, I am looking for a method to find feasible flows in it, the only problem is that, say I find an augmenting path, it could end up not just modifying ...
1
vote
1answer
15 views

What is the Number of epochs with no improvement after which training will be stopped.?

I am trying to make a Convolutional neural network. Training the images of different brands of Logos. Have 100 images per class and there are 40 classes. I have trained the model now want to check ...
0
votes
1answer
35 views

Possible unique paths to reach cell (0,n-1) from cell (0,0) given vector of must visited rows and allowed movement directions

I've been given a matrix path problem to solve and I need some hints / advises. You're given a $m \times n$ matrix where $m$ is number of rows and $n$ number of columns. When you're in a cell $(i,j)$ ...
0
votes
1answer
21 views

How does CNN deal with rotation invariant pictures?

I am trying to make a CNN model . Training the image . Want to know that When we apply kernel on image and take out the features of images. That features are rotation invariant or we have to apply ...
-3
votes
0answers
15 views

What is the network flow problem that corresponds to this project selection problem?

The problem in question is here https://www.chegg.com/homework-help/questions-and-answers/3-question-application-network-flows-project-selection-project-selection-problem-problem-s-q66506427 This ...
2
votes
1answer
45 views

Optimization problem over bidirectional connected graph

A company has several automatic vertical warehouses (called elevators). Each elevator have several trays and each tray has several slots. A slot contains a given quantity of a given article. Elevators,...
0
votes
1answer
18 views

Algorithm of split graph $G=(V,E)$ to 2 groups that at least half of the edges are between the groups [duplicate]

Can someone remind me the algorithm that split vertex of graph to 2 groups that at least half of the edges are external, I mean between the groups. As I remember it was a greedy algorithm, each time ...
2
votes
1answer
30 views

Group time series events into minimal amount of buckets

I'm trying to efficiently compute events in a time series by grouping them into buckets. My goal is to have as few buckets as possible. The constraint is that events within one bucket are all within a ...
1
vote
0answers
19 views

Using chebyshev polynomials to calculate LOG, EXP and TRIG functions

I originally posted this over on Software Engineering, but it was suggested that I repost it here. I am working on a BCD Floating point library and I'm a bit stuck on the EXP (antilog) functions. The ...
0
votes
2answers
27 views

Ω(f(x)) and worst case analysis

I'm currently reading The Algorithm Design Manual by Steven S. Skiena as my first book to algorithms. Something in the asymptotic part is kinda of confusing to me. Proving the Theta The analysis above ...
4
votes
2answers
51 views

How to make efficient path minimum queries in a tree?

Given a tree in which each node has a given value, I want to process "Path Minimum Queries": given two nodes, what is the minimal value of any node on the shortest path between them? My ...
1
vote
1answer
41 views

Analyzing the Runtime of Shuffling Algorithm

The following is psuedocode used to shuffle the contents of an array $A$ of length $n$. As a subroutine for shuffle, there is a call to Random$(m)$ which takes $O(m)$ time for an input $m$. Determine ...
1
vote
1answer
31 views

The Algorithm Design Manual - Working with the Big Oh

I'm reading The Algorithm Design Manuel and one part is kind of confusing to me The part that's confusing to me is how in the "Proving the Theta" section he proves that selection sort is Ω(n^...
0
votes
1answer
57 views

What is the minimum number of parts required to split the sequence S to in order to obtain sequence T?

Suppose a person has a sequence (S) consisting of integer numbers and would like to split the sequence into a number (possibly one) of continuous parts. For each part independently, I then choose any ...
1
vote
1answer
28 views

How to calculate the basic steps in Fibonacci sequences to get nFn and n^2

I am reading Algorithms by Sanjoy Dasgupta, Umesh Vazirani, Christos Papadimitriou and I am trying to understand how the number of steps $nF_n$ and $n^2$ were calculated. Here's the part of the book ...
1
vote
1answer
31 views

Is it possible to use an adjacency matrix for Bellman-Ford algorithm?

I have created a function that generates a complete, directed, and weighted graph, represented in an adjacency matrix but most Bellman-Ford implementations use an adjacency list. Is it even possible ...
0
votes
0answers
36 views

Most popular path in weighted cylic directed graph

Context I have a graph $G=(V,E)$ with weighted edges, all weights are positive integers $w(e)\in\mathbb{N}\setminus\{0\}$. The weights represent the popularity/count of each edge, for example $w(e) = ...
1
vote
1answer
22 views

How do these additional cases fit into this Theorem about the optimal substructure of a longest common subsequence?

Theorem 15.1 (Optimal Substructure of an LCS) Theorem Let the $X=(x_1,x_2,\dots,x_m)$ and $Y=(y_1,y_2,\dots,y_n)$ be sequences, and let $Z =(z_1,z_2,\dots,z_k)$ be any LCS. If $x_m = y_n$, then $z_k ...
1
vote
1answer
22 views

Approximate max weight path in directed graph

Context This question is related to the fact one can't use Bellman-Ford to find max weight paths in directed graphs with cycles. The reason is that giving a new graph $\tilde{G}$ with negative weights ...
1
vote
1answer
18 views

Producing a total or partial order from an inconsistent relation

Imagine I want to construct a total order from a set of elements, $E$, but the comparison function produces results that are non-deterministic. I produce a list of element pairs (e, e) through ...
-1
votes
0answers
20 views

What's the asymptotically lower bound of time complexity that iterate all r combinations of an arraylist length n?

Below is an example of algorithms that iterate all r combinations of an ArrayList of n elements. It read/write ...
4
votes
1answer
115 views

One-dimensional packing problem: Optimal decomposition of music structure

I am currently working on my Master thesis on the visualization of music structure and I'm looking to find an optimal description of repetitions found in a piece of music. Problem Description Given a ...
1
vote
1answer
24 views

What does it mean that a set of intervals is sorted by the right and left endpoints?

While reading a paper (On the k-coloring of intervals), I came upon the following description: "Input: An integer k, and a set of n intervals sorted by right and left endpoints. The intervals are ...
2
votes
1answer
29 views

Which graph partitioning algorithm can solve this problem?

In brief: Here I have a cyclic graph above. I want to partition the graph vertices into 3 clusters. (With the mindset of cluster-wise "load balancing") ...
2
votes
0answers
25 views

Can you give me insight into the time and space complexity of those pairing functions?

I am looking for a pairing function with linear time complexity. I found one in Steven Pigeon's thesis (p 115, §5.3.6.3) described in English on MathOverflow that works by bit interleaving. another ...
4
votes
1answer
47 views

Is there a computationally optimal point-in-polygon solution (for a dynamic scenario)?

I am approaching a problem where, among other things, I will have to repeatedly check if a point is within a (set of) polygon(s) in the 2D plane. the polygons are either convex or star-shaped with a ...
-1
votes
0answers
47 views

Find an minimum weight elementary path with a given constraint

I have a problem as below and I am really stuck with it as it run with more than the time I desired (about 1 second). I really want your help to build up a more efficient algorithms than mine Given ...
1
vote
2answers
26 views

Algorithm to schedule employees into days

I'm trying to build a scheduling app for a friend, but am stuck on how to sort the employees. I have three holidays each with their own employee_need: thanks_giving: 2 christmas: 3 new_years_eve: 2 I ...
1
vote
2answers
41 views

Is there an algorithm that can ensure everyone gets bussed to their destination on time, while minimizing the time spent on a bus?

Suppose I am a bus transportation company. I have n buses. I want to change the bus routes so that the "average" commuter spends as little time on the bus as possible, while being able to ...
3
votes
1answer
45 views

What's the average number of transistor switches needed to do an N-bit x N-bit multiply?

I want to know how switch-efficient a multiplier can be. If I need to do many $N$-bit by $N$-bit multiplies, and each bit is determined by flipping a coin, what's the average number of transistor ...
1
vote
2answers
88 views

What is the simplest algorithm to compress a string?

I need to compress a string in my application but I am very limited in the operations I can perform. In particular, I cannot store data in any file and I cannot query any database. Also, I cannot call ...
0
votes
0answers
27 views

Some nodes in binary search had broken.how we can fix it in-place by swapping nodes?

Given a binary search tree(can have any height) .Some nodes its value changed and violate bst property how we can recover binary search tree property in-place by just swapping a node with its ...
1
vote
1answer
37 views

Lexicographically Smallest String

Problem Statement: Given a string/pattern only consisting of '<' and '>' symbol, find the lexicographically smallest string that satisfies the pattern(made up of only lowercase english alphabets)...
-4
votes
0answers
22 views

Research the following [closed]

What does a web browser extension + plugin look like? What are the business and technology requirements to integrate an extension on a browser? What are the business and technology requirements to ...
0
votes
1answer
59 views

If i use other peoples code for my final year project does that come under Plagiarism?

I want to make a facial recognition project but my coding ability is very limited so I am going to be relying on other peoples code but if i use their code even if i change the variables and make ...
1
vote
1answer
49 views

What Makes an Algorthim Greedy [Graph Coloring Algorithm]

I have a simple graph G = (V,E) and each vertex has a range [a,b].Every two vertices are connected only if [a_1,b_1] and [a_2,b_2] have a common subrange. Each range of vertex is rV1 = [0,5] rV2 = [1,...
3
votes
1answer
101 views

Balanced Network max flow review

I would like a review for my algorithm for the following question: A flow network is a “balanced network” if for every $v∈V- {s,t}$ it holds that $c_in (v)=c_out (v).$ Let G be a balanced network in ...
0
votes
1answer
29 views

If $A$ reduces to $B$ and $B$ is NP-hard, is $A$ NP-hard?

Suppose there is a polynomial time reduction from problem $A$ to $B$. Why is the following false? If $B$ is NP-hard then $A$ is NP-hard. Can some explain this intuitively?
0
votes
0answers
12 views

Find optimal alignment between 2 strings with gap cost function

I have a homework question that I trying to solve for many hours without success, maybe someone can guide me to the right way of thinking about it. The problem: Given two strings S1 and S2, find the ...
1
vote
1answer
32 views

The probability that a person succeeds to pick the longest stick from a randomly ordered n sticks of distinct lengths following the optimal strategy?

To begin with, consider two persons(Px and Py) are playing a game. Px is the organiser of the game who has n sticks of distinct lengths and displaying them one by one to Py in a random order, with ...
0
votes
0answers
13 views

What's the best way to combine multiple A* searches?

I have a graph that looks like this The highlights nodes must be visited, and the blue node must be visited last, the stickman must be the start of the path. The weights are the Euclidean distance ...
-1
votes
0answers
12 views

Can artificial intelligence be used to create 3d models better than human modellers?

Imagine a set of points in 3d space. Can these points be organized and triangulated in such a way that identifiable 3d characteristics can be created based on input parameters ? Example : you input &...
0
votes
0answers
24 views

Subarray containing all integers from 1 to $m$

I have faced the following problem in an entrance examination, and need to verify a few results plus a question part that did not manage to get in time. Given an array $A$ of length $n$ which contains ...
0
votes
0answers
39 views

Find largest $k$ numbers in Max Heap in $O(n\log k)$

I have a data stream with $n$ numbers and I want to find the largest $k$ of them ($k \ll n$). I want to use a priority queue with max heap of size $k$, so I will have space complexity $O(k)$, which is ...
0
votes
1answer
47 views

Using A* path finding is giving me inaccurate results

So i am using A* path finding to find a path from a person, to a node on a graph. This person has a few 'must pass' nodes that they must go through. So my solution was to run the algorithm for each of ...
3
votes
1answer
36 views

Is the following Greedy algorithm to generate Gray Codes always correct?

I recently solved the basic problem of generating a n-bit Gray Code. The solution I used involved building larger-bit Gray Codes from smaller ones recursively (the solution I've seen on most websites)....
1
vote
1answer
29 views

Given an undirected graph, find an orientation such that every vertex has out-degree at least 3

Given an undirected graph $G=(V,E)$, describe an algorithm that computes an orientation of $E$ such that each vertex has out-degree at least 3. I know how to check if a vertex $v$ has at least $k$ ...
2
votes
1answer
131 views

Find optimal local alignment of two strings with restrictions

I have a homework question that I trying to solve for many hours without success, maybe someone can guide me to the right way of thinking about it. The problem: We want to find an optimal local ...
1
vote
0answers
30 views

Approximating the Levenshtein distance between two binary strings using the Fast Walsh-Hadamard Transform

I have come up with a simple technique of approximating the Levenshtein distance between two binary strings using the fast Walsh–Hadamard transform: given two binary strings $a,b$ with Walsh–Hadamard ...

1
2 3 4 5
184