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.

0
votes
0answers
3 views

Flow Free as an integer programming

Flow Free is a popular mobile phone game where the problem is to connect the pieces . Wikipedia suggests this is equivalent to Number Link puzzles and as such is NP-complete. Supppse we wanted to ...
0
votes
1answer
17 views

Count the number of ways numbers 1,2,…,n can be divided into two sets of equal sum

count the number of ways numbers 1,2,…,n can be divided into two sets of equal sum. This is my recursive algorithm, what is wrong here?: ...
0
votes
0answers
15 views

For a collection $S$ of weighted sets $S_i$, find those $k$ elements that maximise the sum of weights of all sets $S_i$ covered by them

I have a collection $S$ of sets $S_i$. Each $S_i$ has a weight given by how many times this set was observed in some data. I now want to find the $k$ elements that maximize the cumulative weight of ...
1
vote
0answers
23 views

What is a contextual algorithm?

I've been around some research articles which talks about Contextual Algorithms. I want to know what is a contextual algorithm in computing in general.
0
votes
0answers
17 views

Exercise 11 of section 3.2.2(The art of computer programming)-part b

b) Let $f(z) = 1-a_1z-...-a_kz^k, G(z) =1/f(z)=A_0+zA_1+z^2A_2...$ Let $\lambda(m)$ denote the peroid length of $<A_n \operatorname{mod} m>$.Prove that $\lambda(m)$ is the smallest positive ...
1
vote
1answer
22 views

Simple algorithm to select separated points in closed intervals

Within the internal logic of a feature I'm working on, I've run into a need for a solution to essentially this problem: $S$ is a finite union of $K \geq 1$ closed intervals, $$S = [a_1,b_1] \cup \...
-2
votes
1answer
46 views

Calculating millisecond and avoiding float numbers [on hold]

I have a variable which increases/decreases from 0 to 255 every (X) millisecond. so: ...
0
votes
1answer
18 views

Learning Specific Topics In Machine Learning

I am a beginner in machine learning and I already have a good linear algebra/calculus background. I am interested in being able to eventually understand and implement convolutional neural networks, ...
0
votes
0answers
27 views

How to find the “odd one out” in a list of numbers

I have an array of numbers [x1, x2, x3, etc] that is size is over 20 elements and I'm trying to put together an algorithm to sort the elements based on the "oddness" they have relative to the rest of ...
0
votes
1answer
37 views

What is the name of this sorting algorithm?

I have typeset in a Wikipedia draft this sorting algorithm. It is a comparison sort, yet can handle only numeric arrays. Basically, it marches through the input array and for each new array ...
0
votes
0answers
39 views

Maximum independent set in a hypergraph

The problem is this, say you have a set $E$ of elements $e$, and you have a list of elements you want to remove from this set. But for an element to be removed, one of its dependencies must stay in ...
0
votes
1answer
31 views

How many combinations will be generated if below conditions are put?

I need a generalized formula for a set having size(s) having below restrictions, for ex. X = 2,7,11,17,26 I want only the first combination 2+7 & ignore all of the combinations that start from 2+...
0
votes
0answers
15 views

Prerequisites for Artificial Intelligence and Machine Learning? [on hold]

I am a beginner in the field of AI and ML. Before jumping into or learning something I have the habit of researching prior condition that has to be needed in my learning process and also I have to get ...
0
votes
0answers
7 views

What's a difference between Shape-From-Stereo and Shape-From-Motion approaches?

I am reading about different approaches for 3D facial reconstruction and can't get a difference between Shape-From-Stereo (SFS) and Shape-From-Motion (SFM) approaches.The SFS regresses a shape from ...
0
votes
1answer
25 views

How MO'S algorithm with update query works?

MO'S algorithm is used to answer queries related to a given array by dividing it into blocks(https://blog.anudeep2011.com/mos-algorithm/) .Though i understood general MO'S algorithm but i am facing ...
-2
votes
0answers
41 views

why is discrete maths needed to understand algorithms?

I am new to algorithms. I need to know is it necessary to study discrete maths to understand algorithms. If so, why? In particular, is it necessary for understanding algorithms or is it only necessary ...
3
votes
0answers
15 views

Normal colorings of cubic graphs (part 1)

Definition A normal $k$-coloring of a cubic graph (3-regular graph) is a proper coloring of the edges with $k$ colors such that each edge an its adjacent edges are colored with either five colors, or ...
1
vote
1answer
27 views

Thorup : What is the meaning of super distance?

While reading Thorup's Algorithm to solve SSSP problem, I have one point that I can't understand: super distance. It says: "For each vertex we have a super distance $D(v)\geq d(v)$" $d(v)$ must ...
3
votes
1answer
55 views

Forcing an edge to be in S-T min-cut

Given a flow-network $N=(G,c,s,t)$ and an edge $e=(u,v)$, I am trying to build an algorithm that finds a minimum $(S,T)$ cut in the given network, that includes e. So, I tried couple of steps, first, ...
3
votes
1answer
88 views
+50

Mistake in a proof of termination phase of Simplex algorithm in CLRS?

There is a pseudo-code for Simplex algorithm in CLRS: The proof consists from three-part loop invariant: Proof We use the following three-part loop invariant: At the start of each iteration ...
0
votes
0answers
32 views

How to prove that extended euclidean algorithm has time complexity log(max(m,n)) ?'

I tried to search on internet and also thought by myself but was unsuccessful. Intuitively i think it should be O(max(m,n)). can someone give easy explanation since i am beginner in algorithms.
-1
votes
0answers
27 views

How do i make a percentage based loot system C# [closed]

so i have been trying to figure this one out on my own for a little while now for my game i am creating, but i am not able to get my head around it. I basically would like too know how to create a ...
2
votes
0answers
48 views

Maximum weighted matching for directed (non-bipartite) graphs

This post concerns mainly non-bipartite graphs. Edmonds (1961) have proposed the Blossom algorithm to solve the maximum matching problem for undirected graphs. The best implementation of it is due ...
2
votes
2answers
57 views

Binary search uneven split number of queries?

For even split binary search (repeated halving) number of queries is log with base 2. According to Skiena's Algorithm Design Manual, if the split in binary search is by ratio 1/3:2/3 instead of 1/2:1/...
0
votes
1answer
23 views

Multiway Cut question

I am trying to understand Multiway Cut, and basically how the Multiway Cut works. I am searching google many hours to find a good example to understand. A good example that I am trying to understand ...
0
votes
0answers
23 views

Efficient algorithm to prune a graph [closed]

I'm faced to a problem I don't know the name, and for which I'm searching an efficient algorithm. From two list of nodes (without shared elements), the aim is to remove edges between element of the ...
0
votes
1answer
19 views

In a Turing machine, what is the difference between the instruction table and the algorithm?

In a Turing machine, what is the difference between the instruction table and the algorithm? The instruction table seems to be an algorithm for completing the task no?
0
votes
2answers
24 views

How to find the nearest point in the coordinate system

There are so many points in the coordinate system. When a specific point is given in the coordinate system, I want to find the closest point to the straight line distance. For example, if you have 800 ...
2
votes
1answer
35 views

Maximum Flow in a Network

Let $N = (V, E)$ be a network in which the capacity of each edge is either $12$ or $18$. Prove or disprove: The value of a maximum flow for $N$ can’t be $56$. I'm trying to figure out how to ...
1
vote
0answers
37 views

How to solve 2 variable recursion?

T(m,n) = T(m-1,n) + T(floor(m/2), n-1) Base conditions T(m,n) = 1 when n = 0 T(m,n) = 0 when m < n Edited: Below is the code for which I want to know the time complexity in terms of m and n. <...
0
votes
0answers
32 views

Reversible shuffle function

I would like to implement this algorithm with a minimum memory use: ...
0
votes
1answer
33 views

Who studied the algorithms through the Cousera. Tell me whether to take a subscription? [closed]

It is very difficult for me to learn algorithms. And so I think how best to start learning. And I also think whether I have enough material from the platform where I want to purchase a subscription. ...
0
votes
0answers
44 views

Is Travelling salesman problem with dikstra's algorithm the optimal solution?

I've tried solving the travelling salesman problem using dynamic programming and Dijkstra's algorithm to find the optimal solution in Dijkstra's algorithm is always correct(in the test data i used). ...
3
votes
2answers
30 views

Solving the min edge cover using the maximum matching algorithm

To solve an instance of an edge cover, we can use the maximum matching algorithm. Edge Cover: an edge cover of a graph is a set of edges such that every vertex of the graph is incident to at least ...
0
votes
1answer
66 views

What is the space complexity of Dijkstra Algorithm?

As per my understanding. The space complexity will be O(V). An array of V nodes will be created which in turn be used to create the Min heap. But this link is stating that It is O(V^2)? I don't ...
0
votes
0answers
27 views

How do i solve this task about the the Reservoir Sampling algorithm?

Hello I have the following task (no homework). You are using the Reservoir Sampling algorithm. You process the 2000th element in the data stream and are maintaining a sample of size 500. What is ...
0
votes
2answers
59 views

Reducing Graph Reachability to SAT (CNF)

So I came across this problem in my textbook. I was wondering how to develop a reduction from the Graph Reachability problem to SAT (CNF) problem. (i.e. formula is satisfiable iff there exists a path ...
1
vote
0answers
55 views

Inverting a function

I posted this question on mathoverflow two years ago but got no answer: Let $w = a_0 \cdot a_1 \cdots a_{n-1} $ be a word from $ \{0,1\}^n $, $|w| = n$ Let $m = \sum_{i=0}^{n-1}{ a_i \cdot 2 ^ {n-1-...
-1
votes
0answers
34 views

Need assistance in running Tarjan algorithm for this test case ? references :gfg and Tushar roy's tutorial [closed]

The test case is : There are 3 vertices 1,2,3 such edge: source-destination 1-2 1-3 2-3 As dfs proceeds from 1 to 2 and then to 3 . Following are the discovery ...
0
votes
1answer
25 views

Algorithm for selecting a sample that's as spread out as possible?

I have a large database of data with dates. There are large gaps and large chunks of data without gaps. I want to get a sample of this data such that the dates are as spread out as possible (i.e. as ...
1
vote
1answer
37 views

How to find Maximum perimeter of rectangle in a grid with obstacles? (Dynamic Programming)

Can someone tell me what am I doing wrong? Problem: https://codeforces.com/contest/22/problem/B Editorial: https://codeforces.com/blog/entry/507 ( I followed the DP solution O((n*m)^2) ) Eg: ...
0
votes
0answers
38 views

What is a uniform algorithm?

what is a uniform algorithm? I see some definitions based on running time, but also contradictory uses of slower uniform algorithms.
0
votes
0answers
14 views

Is there an algorithm that provides the highest possible “sum of satisfaction” for a priority based distribution problem?

Let's say we have n (e.g. 6) children and a box of candy. The box has k (e.g. 8) different flavours, and m (e.g. 4) piece of candy in each flavour. This question is specifically about the cases where ...
1
vote
1answer
43 views

Given n standard C++ STL maps, can I merge them? [closed]

I was wondering if it is possible to merge standard STL maps in O(log(n)) using DSU trick. For example, Map a={{1,2},{3,2},{4,3}}, Map b={{2,3},{3,2},{4,1}} and Map c={{2,1},{3,2},{4,4}} Then the ...
2
votes
1answer
49 views

Thought process for the following problem?

We are given a 1-d array and we have to return the smallest array attainable after removing all the continuous same numbers. We can only eliminate those numbers which repeat continuously more than or ...
1
vote
0answers
19 views

Determining the DP subproblem given a problem

I'm reviewing DP and I was wondering the intuition behind determining the subproblems for some DP problems. For example, consider 2 similar problems. Given a set of 1, 2, and 3 steps you can take, ...
4
votes
1answer
104 views

Matching Algorithm - How to maximize matched quantity with unique matching rules?

Given a set $S=\{A,B,\cdots,H\}$. Elements in $S$ can be matched according to the following rules: $$\begin{aligned} A\leftrightarrow B\\ C\leftrightarrow D\\ B+C\leftrightarrow F\\ D+A\...
2
votes
0answers
21 views

Permutation to maximise strings' common prefix

Is there a good algorithm for finding a permutation which, applied to all the strings in a set, maximises the weight of those with a common fixed length prefix. Given a set $S=\{(s,w)\}$ of pairs of ...
1
vote
0answers
32 views

Is There A Difference Between Search And Optimization?

Is one a subset of the other? Two differentiable processes? The same thing? In the textbook "AI: A Modern Approach", the terms seem to be used interchangeably.
0
votes
0answers
9 views

Is it possible to compute a whole convolution layer at once?

I have an input of 32×32×3 and I want to feed it to a convolution layer that output 32×32×16 feature maps. I know that I can compute a single feature map as matrix multiplication. But my question is, ...