# 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,546 questions
Filter by
Sorted by
Tagged with
19 views

### Number of distinct BFS, DFS trees in a complete graph

What is the number of distinct BFS, DFS in a complete graph? My approach is like this--> For DFS take a node, we have (n-1) possible tree edges, next we have all possible (n-2) tree edges,..........
9 views

### How to assign people to categories based on some voting rules?

Say in an election there are predefined categories users can be assigned to. Of the people who are assigned to a certain category, other users can vote for them. To compute the results, the following ...
53 views

### Min Fibonacci Heap - increase key

I have been trying to implementing heap data structures for use in my research work. As part of that, I am trying to implement increase-key operations for min-heaps....
45 views

### Does the Bellman-Ford algorithm find all the negative cycles?

The Bellman-Ford algorithm "can detect and report the negative cycle", but does it guarantee to find them or it may find some? The algorithm really focuses on the shortest paths, so I'm unclear if it ...
40 views

### Algorithm to save state of array as it changes

There's an array which changes with every iteration, i.e., an element is added or deleted in every iteration. I have to save the "state" of the array for every iteration, which would later be ...
18 views

### What is the difference between derivative free optimization and derivative optimization in terms of advantages/disadvantages?

I understand the basic operation of the algorithms however i'm unclear as to when to use one over the other and what advantages/disadvantages they offer over each other. Also as an aside, if anyone ...
25 views

### Looking for the name of this job scheduling algorithm

You have a list of jobs. Each job has a deadline and an associated profit if completed before the deadline. Also, each job takes 1 unit of time to complete, and only one job can be completed at any ...
16 views

### Comparison of constructive and local-search heuristics for TSP

In my high school class, we are currently looking at evaluating heuristic methods for intractable problems - especially TSP. My question is what is the advantages or disadvantages of using a ...
8 views

### Adding height to a minimum quantity of steps

I have a set of concrete steps. Each step has a height. I record the height of each stair, from first to last, bottom to top, as a list of heights: [1.3, 2, 3.5, 4.2]. There is an implicit first ...
7 views

### Count compound words with an ambiguous decomposition

I have a set of words $D$, and I make compound words by concatenating a fixed number $n$ of words from $D$ (repetitions are allowed). Let's call such words $n$-compounds. I want to know how many ...
35 views

### I am looking for an algorithm that can find the best possible combination of inputs, in order to determine the optimum output

So as the title poorly implies, I'm looking for an algorithm that can accomplish the following task (as an example): Given the inputs A(1:100), B(1:100), C(1:100), that can take on any value between ...
63 views

### Is there a formal definition for iteration?

I wanted know if there is a formal definition of iteration. In the sense that, this definition will say that after the 4th iteration is termination or the 5th iteration and not the 2nd iteration. ...
28 views

### Using Hoare logic to show an invariant holds or using induction?

I want to know if given a while loop: x = 0 while(x < 5){ x = x + 1 } I want to show that x (at the a ith iteration of the loop), the value of i is ...
18 views

### Is it interesting to make an FPT algorithm for a P-Space completer problems?

I have done a course on paramertized algorithms. For NP-Hard problem, Most of the researchers try to design an Fixed parameter Tractable algorithm. Let $P$ be a some P-Space complete problem. ...
27 views

### Non intersecting paths of graphs with obstacle number one

There are $N$ points inside a polygon. If two points are connected by an edge (a line segment) if the edge is completely inside the polygon. We could conclude finding a Hamiltonian path is NPC, but ...
59 views

### How to remove objects from an array most efficiently?

I am wondering if I can rearrange an array faster when I would like to delete more than one object. You are given a List: 1 2 2 3 4 5 7 And now you want to delete every "2" in the list. So what I ...
19 views

### Hamiltonian non intersecting path in plane

$N$ points are located in 2D plane. Some of the pair of the points are connected by line segments. What is the complexity of the problem of existence of Hamiltonian non intersecting path? What if we ...
52 views

### How to count all integers less than a given integer and having two contigous digits as $y$?

Suppose i have been given a number 54432 .How to count all numbers less than 54432 and having last two digits as 1 ? i.e all the numbers of form xxx11 and xxx11 < 54432 .Here x can be any digits ...
15 views

### Review of fast 2D strip packing algorithms?

It seems to me that strip/bin packing algorithms must balance between two criterion: 1) how long it takes to perform the packing 2) how area-efficient the packing is (i.e. how minimal wasted area is)...
19 views

### Algorithm for producing array of objects according to the given distribution

I have a set of objects, and each object has (let's say) a color. Given a distribution such as: ...
45 views

### Divide grid so that each box has only one object

Is there an efficient algorithm to divide a 2D space, which contains several different sized rectangles, such that each partition has only a single object. Please see the attached image. I have come ...
14 views

### How can I match handwritten character segments (including the direction they are written)? [closed]

I am trying to test Chinese character production by having users draw the characters on their device. There are plenty of data models that include the character information already, so I will have ...
31 views

### Given a system in $\mathbb{F}_2$ in RREF, how do I find a solution of minimal norm?

I have a $12 \times 12$ (so not really large) system of linear equations in $\mathbb{F}_2$ which I got to RREF through the usual row reduction. Suppose the system has multiple solutions, and call the ...
50 views

### How do I minimize the cost of some algorithm that performs some operation on a list?

I stumbled upon this problem whilst studying the complexity of a simple algorithm. I used set-theoretic notation, but all the $S_i$'s are lists (I couldn't think of a better way to write the problem ...
46 views

### How to cover given entries in a matrix with minimum number of rows and columns?

We have a matrix of 0 and 1. We want to cover all the 1's. We can cover a raw or a column with a plate. We want to use the minimum number of plates. example 0 0 1 0 0 1 0 1 0 0 1 0 0 0 1 0 ...
39 views

109 views

### Is there a solution set for Knuth's The Art of Computer Programming series? [closed]

Is there a solution set for the books in The Art of Computer Programming series written by Donald Knuth? I've found solutions for Concrete Mathematics using Google, but not the above series.
50 views

### Range of each building in array

I have two arrays, X and H, where X is sorted. X[i] represents the coordinate of building i. Y[i] represents the height of building i. If building i collapses, all buildings in the interval [ X[i]+1, ...
71 views

### Efficient algorithm to simulate dealing cards from a large deck of cards?

In shedding-type card games, the dealer starts by dealing a shuffled deck of cards to the players (if there are N players, card i...
43 views

### largest subset of pairwise intersecting intervals [closed]

Given a set of intervals on the real line, compute the largest subset of pairwise intersecting intervals (an interval in the subset must intersect with every other interval in the subset). Design a ...
11 views

### Mapping every character to its next occurrence based on the number of unique characters between the occurrences

To optimize my LF mapping, I was asked to do the following. Given a string, say $abaxyxwxbx$ I need to encode it in a way where every index stores the value of the number of unique characters ...
10 views

### Processing RSS content from different providers based on priority

I have multiple RSS provider URLs. Each RSS provider posts articles from time to time. Each article has a published date. Some RSS providers post more often than others. I have to go through the list ...
33 views

### When does knowing the number of solutions help (improve the running time)?

Combinatorics equips one with methods to find the number of solutions to discrete problems. While this is obviously an important tool for accurate gauges on the average running of an algorithm, I'm ...
48 views

### Given n sets of points in the plane find the shortest path which passes from exactly one point from each set

I am trying to find an algorithm for this. You can imagine each set $(S_1, S_2, \ldots, S_n)$ as points with different colour. Also it isn't necessarily $|S_1|=|S_2|=\cdots=|S_n|$. For $n=1$ we ...
34 views

### Any array takes at least log(n!) compairs to be sorted [duplicate]

I have to prove that there is no comparison based algorithem that can sort a randomly given array in less than log(n!) steps. Lets say the array has 5 elements, it is impossible to sort it (using ...
86 views

### Time complexity of Sieve of Eratosthenes [closed]

Wikipedia states that the Sieve of Eratosthenes runs in time $O(n\log\log n)$. Why is that so?
56 views

### Is there an O(1) solution to find the kth-smallest element in an implicit min-heap?

I know this would be an O(k log n) operation on a traditional heap, and I know there are ways to maintain Kth-smallest over a stream of inserts/deletes for constant-time access... My question though ...
50 views

### Number of nodes in Van-Emde-Boas tree of universe size u?

The universe size $u$ in vEB trees is square rooted at each level until $u = 2$. So, unlike search trees, the branching factor is different at each level. The height of the tree is $h = \lg \lg(u)$ ...
37 views

### Maximum Pairwise GCD of an even subsequence

I am trying to solve a particular problem, where I have been given an array of integers and an integer X and I need to choose a subsequence of the array whose pairwise gcd is maximum given that the ...
51 views

### Gas Station problem : Fixed path variation

Given a set of cities where you need a certain amount of fuel to travel from one city to another, each city has a different fuel price and you can only load K amount of fuel to the vehicle. The path ...
17 views

### Solving sequential multi-knapsack problem

Suppose I have $n$ items, each with value $v(j)$ and weight $w(j)$, and $m$ knapsacks each with capacity $c(i)$. If I make the assumption that $w(j-1)$ evenly divides $w(j)$, then there's a nice ...