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
25 views

What is the underlying pattern/rule in this question?

I can't find a concise algorithm for the following coding problem: Given the mapping a = 1, b = 2, ... z = 26, and an encoded message, count the number of ways it can be decoded. For example, the ...
3
votes
0answers
138 views

Algorithm for answering queries of the type “largest interval contained in the given interval”

I have been wondering over the following problem: Given a set $S$ of intervals on the number line. We can do two operations on them: Add a new interval $[l_i,r_i]$ to $S$ Given an interval $[l_j, ...
2
votes
0answers
58 views

Algorithm or Method to reconstruct 3D world coordinates from 2D pixels with some known corresponding real-world dimensions

I have an algorithm than can recognize the 2d pixel locations of certain 3d points within a 2d image. Ultimately we are interested in computing a real-world horizontal distance between these points. ...
-1
votes
0answers
19 views

Starting and Finishing time of Tree Edge, Cross Edge, Back Edge [closed]

There is a certain relationship, when DFS search for a tree traversal occurred. Say if an UV traversed. Then relation between it's start time and end time is Now, my question is if u start early, ...
2
votes
1answer
24 views

Böhm-Jacopini theorem

I had a discussion with a friend developer and teacher. He told me about the Structured program theorem arguing that this theorem is one of the most important to know about. However, I have never ...
1
vote
2answers
47 views

When scheduling intervals across multiple resources, why sort?

I am reading this book and am at a point when the Interval Partitioning Problem is discussed. The pseudocode they provide for it is the following: ...
2
votes
1answer
50 views

Turing Machines proof notations

In context of "Computability", I have went over some proofs for Recursion Theorem using Turing Machine description. A TM $M$ stands for a single tape Turing machine and $\langle M \rangle$ is the ...
1
vote
1answer
51 views

Does any algorithm exist for computing the state of a non-trivial cellular automaton after an arbitrary number of time steps?

If have a cellular automaton, can I see the state of the board after something like $10^{{10}^{10}}$ time steps? For trivial cases, this is possible - for example, a cellular automaton where the state ...
3
votes
1answer
35 views

Min cut of at most k edges

I have been studying for my algorithms exam and whilst doing previous exams found this question for which I am not sure how to handle. Given a graph $G=(V,E)$ with integer capacities $C:E \rightarrow ...
0
votes
1answer
41 views

Express a number with a combination of arithmetic operations and a single number

Today I ran into a this relatively simple (At least from my perspective ) problem. Basically the task is to be able to express any number using only a single number an any combination of arithmetic ...
2
votes
0answers
15 views

Calculating diagonal of inverse of sparse band-like matrix

I'm trying find an optimization for an equation related to theorem 3.5.7 from "Finite Markov Chains" by Kemeny and Snell (1976). The theorem is: $$H=(N-I)N_{dg}^{-1}$$ Where $N_{dg}$ is a diagonal ...
0
votes
1answer
34 views

Analyze time series data to get min max over past period of time

The algorithm should analyze measured time series data in realtime and should check if all values of the specified last period lay inside a specified range. The range is calculated with max-min over ...
2
votes
2answers
38 views

How do we guess the recurrence relation from the given equation

In this book introduction to algorithms , i have been reading about a method named substitution method to solve the recurrence, the recurrence equation is \begin{equation} T(n)=2 T(\lfloor n / 2\...
1
vote
1answer
54 views

Select K columns from matrix and one element from each row that has maximum sum

Given matrix of size N x M (N- rows, M - columns), given integer value K(K < N and K < M). Select arbitrary K columns and create new matrix of size N x K after that select max element from each ...
0
votes
0answers
22 views

Max flow through a specific edge

What i'v tried doing so far is to find a simple path from s to t containing e as well as some "bottle-neck edge" of maximal value (i.e. a simple path from s to t, containing e, whose minimum ...
0
votes
0answers
20 views

How to update graph modularity in Louvain algorithm to find best community?

There is Louvain algorithm that searches communities in a graph using modularity metrics. As far as I know the most of the implementations of this algorithm use generalised metric version proposed by "...
7
votes
3answers
153 views

Separating numbers with a minimal difference

Given is a positive integer integer $n$, and integers $a_1,b_1,\dots,a_n,b_n$ with $ a_i\leq b_i$ for each $i$. What is the complexity of deciding whether there exist integers $c_1,\dots,c_n$ such ...
0
votes
1answer
38 views

Printing words starting with a given letter with the least amount of appearances with the print itself being an another appearance

I've had problems with this one and was unable to solve it on my Algorithms 1 exam: Input: -n words -k letters Problem: For each letter print out the one word which starts with that letter and has ...
1
vote
1answer
21 views

Questions about Randomized Median algorithm?

In textbook by Mitzenmacher and Upfal here, they write in page 62, the following: By repeating Algorithm 3.1 until it succeeds in finding the median, we can obtain an iterative algorithm that never ...
2
votes
1answer
16 views

Analysis of straight insertion

I'm currently reading through N. Wirths': Algorithms + Data Structures = Programs. I'm not sure, but I think there might be an error in the analysis of the provided straight insertion sort. Screenshot ...
1
vote
0answers
12 views

Structure Preserving Continuous Hash Function

This question was originally posted on super user, but redirected here based on some suggestions. I am completely new with computer science, and not only recently did I run into the notion of hashing....
0
votes
1answer
25 views

how to maximise the no of edges selected in the graph in form of cycles of unbounded length?

Recently i started looking the perfect cycle cover algorithm related to kidney exchange problem where it is considered as NP-Complete for cycles restricted to a length>2. However if cycles are not ...
0
votes
1answer
16 views

Scheduling algorithm with defined starting intervals and processing times

I need to design an algorithm for opening and closing some valves at regular times. The input schedule will look something like this: Every 5 minutes, open each of valves 1, 2, and 3 for 5 seconds ...
0
votes
0answers
19 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
34 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
20 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
27 views

What is a contextual algorithm? [closed]

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
22 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
27 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
47 views

Calculating millisecond and avoiding float numbers [closed]

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

Learning Specific Topics In Machine Learning [closed]

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
31 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 ...
1
vote
2answers
180 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
45 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
32 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
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
33 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 ...
0
votes
1answer
61 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 ...
4
votes
1answer
35 views

Normal colorings of cubic graphs (part 1)

Edit 2019 June 27 Question 3 is new ... 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 ...
2
votes
1answer
33 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
60 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, ...
4
votes
1answer
114 views

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 ...
2
votes
0answers
54 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
61 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
28 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
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
37 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
38 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
33 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 ...