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
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?
2
votes
2answers
39 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
39 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. <...
3
votes
2answers
38 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
124 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
31 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
87 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
56 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-...
0
votes
1answer
32 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
53 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
48 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
56 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
24 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
128 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
22 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
33 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, ...
1
vote
1answer
25 views

What are the best ways to find errors in a sequence of messages (strings)?

I am currently working on a thesis, where the main goal is to find errors (like a missing message, wrong sequence) in message sequences. The messages are distinguishable by their name, have further ...
1
vote
2answers
86 views

Algorithm for generating random incrementing numbers up to a limit

I'm trying to write a code to generate incremental sequences of numbers such as: 0 + 1 + 3 + 5 + 1 = 9 0 + 5 + 1 + 1 + 1 = 8 0 + 1 + 1 + 2 + 1 = 5 I have 3 ...
1
vote
2answers
87 views

How do you write a diff algorithm given limited amount of RAM?

Say you have two large files (100 TB each) and only 1 MB of RAM. What's an efficient algorithm that will print the missing lines (diff)? The files don't necessarily contain duplicates. The two files ...
1
vote
1answer
46 views

Shortest path in a incomplete graph

I know the Dijkstra algorithm to solve the "single source shortest path" problem in a graph. And I've seen people discuss solutions in a dynamic graph where edge/vertices are subject to change. ...
3
votes
0answers
68 views

Assign weights to the edges in a DAG so that, for all S and T, all paths from S to T have equal weight

I have a DAG, and on each edge, I have a minimum and maximum weight. I would like to assign (or determine it's impossible to assign) exact weights to each edge so that Each edge's weight is between ...
5
votes
1answer
75 views

Searching a Treasure

I was selected for a UG interview for computational natural science program and the following was one of the questions asked: "Suppose we have an $8 \times 8$ grid. Under one of the blocks, I (the ...
1
vote
0answers
23 views

Find the m-th largest separation

The m-th largest number in a list of n numbers can be found in $O(m \log n)$ using a max-heap. This avoids sorting. Suppose I'm interested not in the actual numbers, but separation between adjacent ...
0
votes
0answers
39 views

$\Omega$-notation for insertion sort [duplicate]

I'm reading the CLRS book and there is a statement for instance, the running time of insertion sort is not $\Omega(n^2)$, since there exists an input for which insertion sort runs in $\Theta(n)$ ...
0
votes
0answers
20 views

Class timetable generation program in C#

As a "fun" project for school, I am attempting to create a timetable generation program which will automatically assign students and teachers to lessons and those lessons to one of 5 periods within a ...
4
votes
2answers
65 views

Count paths of length $n$ that a player can take

I'm writing a video game, and I'm trying to find an efficient way of calculating this. The goal is to count the number of paths of length $n$ that a character can take, where the character can move ...
3
votes
3answers
311 views

Is time complexity more important than space complexity?

I've noticed quite a few cryptographic algorithms speak mainly of the time complexity of an algorithm. For example, with a hashing function h, find x given y = h(x). We normally speak on how long it ...
1
vote
0answers
21 views

Is there an algorithm to partition a set of points into two disjoint polytopes far away from the origin?

Suppose I have a finite point set $P = \{p_1,\ldots, p_K\} \subset \mathbb R^D$ and all $p_i \ne 0$. What I would like to do is partition $P$ into two disjoint pieces $A \cup B$ so the convex hulls $\...
1
vote
0answers
25 views

time complexity of k-bubble sort [duplicate]

I'm a student. today I answered a question wrong, the question is this: Spouse we have a k-bubble sort, which means except sorting 2 elements each time, it has a magical function that can sort $k$ ...
1
vote
1answer
156 views

how to find total paths in a graph which have only one vertex common with a given path

Assume I have a undirected graph $G$ without cycles (i.e., a forest) and I am provided with pair of nodes $a$ and $b$. How can I find the total number of paths in the graph that do not share any edge ...
1
vote
0answers
32 views

How is the modular multiplication matrix unitary in Shor's Algorithm?

I have been reading papers about the construction of this matrix in Shor's Algorithm all night. The behavior of the controlled modular multiplication matrix is described as $$C U_{a^{2}}(|c\rangle|y\...
0
votes
1answer
29 views

Speed Up Access to Fractal-Like Array

I'm trying to speed up the following function in c++: ...
4
votes
0answers
38 views

Algorithm for Unique Selections

Suppose I have $k$ sets with $n$ elements in each. Define a selection as one element taken from each set. A selection is unique if there's one and only one way it can happen—that is, one and only one ...
2
votes
0answers
22 views

Algorithm to select elements from a ranked list of lists

I have a list of lists of objects. Each of the lists of objects is ranked according to a numeric field of the object. The big list is ranked according to the highest numeric value of the field of all ...
2
votes
1answer
28 views

Does Google's PageRank count as a sorting algorithm?

Is it correct to assume that PageRank is a sorting algorithm or does it fall in any other category?
5
votes
1answer
262 views

Data structure for selection of K elements and taking sum

The problem: We are given an array $A$, an integer $Z$ and a value $Q$. The goal is to maximize the sum of $A$, by performing following operation any number of times: We can select exactly $Z$ ...
0
votes
0answers
28 views

Choosing algorithms and/or data structures at runtime based on input characteristics

I've been reading about Adaptive Computing, i.e. the idea of computer programs taking feedback from the environment at runtime to improve the output in some way. More precisely, my current focus is in ...
2
votes
1answer
137 views

Algorithm for fewest number of moves with artificial minimum

I asked a question recently, but I need to be able to add an artificial minimum number of steps that can be larger than the Dijkstra minimum. To summarize, I built an undirected graph with edges ...
1
vote
0answers
24 views

Goemans' Extended Formulation of the Permutahedron And Comparator Networks that are not Sorting Networks

I am interested in using Michel Goemans' extended formulation first developed for the permutahedron to study comparator networks that are not sorting networks. In his paper "Smallest Compact ...
1
vote
1answer
44 views

Analysis of Basic Recursive Functions

I'm trying to understand the contrast between run-time for this function ...
1
vote
1answer
108 views

Can I simplify successive XOR operations?

I'm doing an online programming challenge where successive XOR operations are used (from codewars.com, if you don't want to create an account, here are the instructions). We have a rectangle of known ...
1
vote
1answer
24 views

How to put elements in allowed bags?

Let's say I have a list of "Items" I also have a list of "Bags". Each bag is a set of "Items" which gives what item can be placed in that bag. But only one item can go in each bag. I want to place ...
2
votes
1answer
48 views

Exercise 11 of section 3.2.2(The art of computer programming)

I'm asking about its part a. a) If $f(z),\space a(z),\space b(z)$ are polynomials with integer coefficients, let us write $a(z)\equiv b(z) (\operatorname{mod} f(z)\space and\space m)$ if $a(z) =...
1
vote
2answers
82 views

Find axis-aligned rectangle with maximum area in a point set in the Euclidean plane

On the plane $n$ points $(x_i, y_i)$ are marked. Select 4 points so that they define a rectangle with the greatest area and sides parallel to the axes. Time limit for python is 10 seconds, for other ...
0
votes
1answer
36 views

Finding the maximum disjoint weight in a weighted node graph

I have a graph of nodes that reflect resource allocation. Each node has a weight to reflect this. A well formed graph is disjoint, so there will be no edges, and the weight of the graph is just the ...
0
votes
0answers
24 views

Solving a modular equation programmatically

Consider that I've a mathematical equation of the form: $$ (6+4\times x)\text{ } mod\text{ } 22 = 0 $$ How can I solve this modular equation by using a program, efficiently? By trial and error, one ...