# 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.

7,340 questions
Filter by
Sorted by
Tagged with
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 ...
138 views

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 ...
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 ...
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 ...
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\...
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 ...
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 ...
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 "...
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 ...
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 ...
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 ...
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 ...
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....
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 ...
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 ...
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 ...
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?: ...
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 ...
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.
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 ...
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 \...
47 views

### Calculating millisecond and avoiding float numbers [closed]

I have a variable which increases/decreases from 0 to 255 every (X) millisecond. so: ...
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, ...
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 ...
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 ...
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 ...
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+...
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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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 ...
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 ...
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/...
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 ...
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?
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 ...
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 ...