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

UCT (Upper Confidence bounds applied to Trees)

For UCT (Upper Confidence bounds applied to Trees), why If given infinite time and memory, UCT theoretically converges to Minimax. ? Besides, I do not quite understand how UCT deals with the flaw of ...
-1
votes
2answers
46 views

Can data be compressed through this hash function technique?

I'd like to know if this data compression scheme would work or not, and why: Suppose we have a file. If we treat the bits that make up the file as the binary representation of a number n, we have n (...
1
vote
1answer
54 views

Can CYK Parsing algorithm generate the parsing tree in O(n^3)?

I found this question What is the usage of CYK algorithm in the real world considering we have algorithms with a much better Time complexity? saying CYK Parsing algorithm can compute any Context Free ...
3
votes
0answers
32 views

Modifying the JPEG compression to use custom block patterns

recently, while watching a video about machine learning, I had an idea about creating an image compression algorithm, that works similar to JPEG, but is based on arbitrary bitmaps as blocks. I should ...
1
vote
2answers
56 views

Permute an array in O(n) time with O(1) extra space with a given ordering function?

This question arises from a problem on a problem solving site (https://practice.geeksforgeeks.org/problems/-rearrange-array-alternately/0). Given a sorted (ascending order) array $A$ of $N$ ...
0
votes
0answers
28 views

Algorithm for comparing object dates and types

I'm looking for a good / efficient algorithm to compare classes of driver licences (or any type of similar objects) and their dates, so that they do not overlap and come in certain order. eg. We have ...
0
votes
1answer
38 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
142 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. ...
2
votes
1answer
25 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
49 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
54 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
55 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
47 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
17 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
42 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
39 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
21 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
179 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
39 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
14 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
38 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
21 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
30 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
23 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
30 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
34 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
188 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
46 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
2answers
51 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
48 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
63 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
120 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
56 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
62 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 ...