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

11,347 questions
Filter by
Sorted by
Tagged with
1 vote
94 views

### Greedy Algorithm and Proof of Correctness for Minimum Denominations of US Coinage System Problem

I've come up with a greedy algorithm proof for the minimum denominations problem, and I'm curious if someone can verify the correctness of the proof for me. I have simplified the problem by ...
2k views

### Time complexity for count-change procedure in SICP

In famous Structure and Interretation of Computer Programs, there is an exercise (1.14), that asks for the time complexity of the following algorithm - in Scheme - for counting change (the problem ...
1 vote
24 views

...
7 views

### How does this partitioning problem map to studied problems?

I have a real-world (see background below) problem wherein a set $S = \{A,B,C,D...\}$ needs to be partitioned into set $P = \{ \{A,B\},\{D\},\{E,F\},\{C,G,H\},...\}$ where $P$ is required to have the ...
109 views

### Suggest good books for Advanced Data Structure and Algorithms

I don't really need hands on coding help, I need to clear my concepts of some of the more complex topics of DS and Algo like NP-Completeness, Computational Geometry, String Matching, Multithreaded ...
28 views

### Find multiple order-statistics of an array

Given array $a$ of size $n$ and array $p$ of size $m$. How we can for every $i < m$ find $p_i$-th order statistics of array $a$ in $O(m log(n) + n)$? We can find order statistics separately, but it ...
1 vote
57 views

### How do I find time complexity of while loops?

I am designing a simple algorithm to be used at hardware level. And I want to find its time complexity. i=1 while(i<=n) { i=i*2; } How I'd go about finding ...
7 views

### Confusion on the use of the chain-rule for the total derivative of the NLL Loss function

So my question is about when we want to find the total derivative of the NLL Loss function $L$ w.r.t. $w_i$. So the "pipeline" is often expressed as: \frac{\partial L}{\partial w_i} = \...
1 vote
423 views

### Find the smallest subarray with sum larger than a threshold

Given a set of $n$ positive numbers $\{a_1,\ldots,a_n\}$ and a positive target $T$, find a subset $S$ from $\{a_1,\ldots,a_n\}$ of contiguous elements, that is $S=\{a_i,a_{i+1},a_{i+2},\ldots\}$ for ...
72 views

### A version of Bareiss algorithm or similar for symmetric matrices

A linear equation $Ax=b$ can be solved by reducing the matrix $A$ to upper triangular form by using Gaussian elimination or LU decomposition. If $A$ is symmetric and positive definite one can use ...
37 views

### Binary search calculating complexity big o

I'm studying recursion and a i have a doubt about the running time complexity of the binary search. I didnt understand this passage in my book : ...
44 views

1 vote
46 views

### Time complexity of algorithm with three loops and if statement

Suppose I have this c++ code: ...
65 views

### The three elevator problem

There are three elevators in a building that has twelve floors. Find an algorithm that needs to find the best possible way for the elevators to stop at any particular floor considering the traffic ...
1 vote
37 views

### How do i make a 2d array as same as i possibly can with another one?

Say i have an 2d array A of nxn size, int values already given for each item.these values can be the same or different. There's gonna be another nxn array B being input. I can only interchange one row ...
2k views

### Proof that median of an array is the number that minimizes the sum of manhattan distance to all points

Given a sorted array A, the problem is to find a number that minimizes the sum of Manhattan distance to the numbers in the array. I found that the median of A is the solution, but was not able to come ...
37 views

### Find combination of elements, one element from each list, whose average is the closest to a target number

Problem: There are L lists of positive integers, say L_0, L_1, L_2 ... L_|L|-1. The lists have equal length. There is a target number T. Find what is the combination of elements, one element from each ...
193 views

### Could this novel algorithm be qualified to be published in Nature or Science

I recently designed an algorithm for single-source shortest paths in graph structures, which can limit the number of edges as Bellman-Ford while approaching the performance of SPFA. Of course, it also ...
36 views

### Round-robin tournament scheduling, with teams that may share their home field

I need to implement an algorithm to create schedules for round-robin tournaments (where each team faces each other team exactly once), but with the constraint that up to 2 teams – that may play in ...
713 views

### calculating the string similarity of an optimal alignment

description of the algorithms behavior I have two strings s1 and s2, with $len\_s1 <= len\_s2$. I would like to find the ...
12 views

### Dynamic programming problem for minimum cost tower placement

I have an algorithmic problem in which I have a highway that is a straight line of length n and a set of unique respective costs for construction of a radio tower for each mile on the highway. I am ...
1 vote
465 views

### Find all polygons from a set that overlap a given polygon (convex case)

Problem: Given a set of $N$ non-overlapping convex polygons $\{S_i | 1\leq i\leq N\}$ defined by their vertex coordinates $(x,y)$ and a convex polygon $P$, also defined by its vertex coordinates, ...
1 vote
85 views

### Can we compute most significant digit of a binary number in O(1) on RAM model?

Consider we use a RAM model with word length w (or if you really want a more exact model, you can use Knuth's MMIX instructions with w-bit numbers). Given a number n, we want to compute the most ...
We are given two cyclic $\{0,1\}$ strings $X$ and $Y$ with both length $n$, containing $k$ 0s and $n-k$ 1s. Suppose positions of 1 in $X$ are $x_0,\dots,x_{k-1}$, for $Y$ are $y_0,\dots,y_{k-1}$. We ...