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
1
vote
1answer
38 views

Solving/mitigating the free rider problem without requiring identification?

Is there any algorithm/protocol out there to solve/mitigate the free rider problem without requiring identification? In a web system, I want to distribute exactly one virtual dollar per day to each ...
1
vote
2answers
39 views

Time complexity of finding predecessor for a dictionary implemented as a sorted array

I'm currently reading "The Algorithm Design Manual" by Steven Skiena. On page 73, he discusses the time complexity of implementing $ Predecessor(D, k) $ and $ Successor(D, k) $ and suggests that it ...
1
vote
2answers
56 views

Verifying connectivity of a graph in O(n^2)

I trying to solve the following problem in $O(n^2)$: We have vertices which represents cities and a textfile containing an edge on each line. How many roads do we need to build to make the graph ...
0
votes
0answers
18 views

Can anyone provide proof of second equation of rod cutting problem in CLRS section 15.1

While going through ROD CUTTING problem of DP from CLRS, I noticed the optimal structure of the rod cutting problem is : 𝑟𝑗=max{𝑝𝑛,𝑟1+𝑟𝑘−1,𝑟2+𝑟𝑗−2,...,𝑟𝑗−1+𝑟1} In overhead approach, ...
1
vote
0answers
23 views

How to implement minimization of maximum regret?

We run a report, but for one of our big clients, it is taking too long. There is a loop where it loops for a list and fetches it upstream 1by1. We're making this a bulk operation now, but some items ...
1
vote
1answer
32 views

What is the meaning of uniform distribution of elements in an array?

I was going through the concept of Interpolation search and it stated that when the elements are "uniformly distributed", it takes O(loglogn) to search an element using interpolation search. Can ...
2
votes
1answer
25 views

How to prove an implication about an upper bound mentioned in the proof of master theorem?

How can we prove rigorously the proposition "Suppose the if in case 1 is true, the equation 4.23 is true"? For given constant b and j, the implication in green makes sense. If the upper bound of j ...
2
votes
2answers
44 views

Big-O Notation and Calculus?

I was wondering if there are any calculus relationships implicit in Big-O notation. For example, an algorithm linear according to Big-O notation reduces the size of the problem by a constant amount ...
3
votes
1answer
142 views

Merging nodes of a DAG

I would like to merge connected nodes with a specific attribute of a directed acyclic graph. The purpose is to detect max connected clusters of blue nodes and merge them. After each merge operation, ...
1
vote
1answer
25 views

Is there a way to modify Kadane's Algorithm such that we know the resulting subarray?

Kadane's Algorithm is an algorithm that solves the maximum subarray problem by clever dynamic programming. Is there a way to further modify the algorithm so that we would get to know the resulting ...
3
votes
1answer
67 views

Problem in downvote system

Problem For my game, I'm building a system where players have power/weight, and they can downvote each other, players with 66% of downvote weight are banned. The weight of the votes is calculated ...
1
vote
1answer
29 views

Student Course Allocation Problem with Many Constraints [closed]

Problem statement In an university, there are $t$ course categories, $m$ courses, $n$ sections, $p$ students. $i$-th section has: A student capacity: $cap_i$. Two lecture timings. (Formally, each ...
5
votes
1answer
81 views

Intersection of O(n) expanding circles with line from the origin

I am interested resolving a programming challenge problem, but I'm struggling obtaining an efficient solution. Consider yourself as a point located on the origin $(0,0)$ of an infinite two-...
1
vote
1answer
25 views

What is the time complexity of a binary multiplication using Karatsuba Algorithm?

My apologies if the question sounds naive, but I'm trying wrap my head around the idea of time complexity. In general, the Karatsuba Multiplication is said to have a time complexity of ...
0
votes
0answers
20 views

Design a greedy algorithm by intermingling two sequences [duplicate]

I find myself solving problems for a test and the next problem I still can't solve it. There are n ordered sequences, $S_1$ to $S_n$. It is requested to intermingling them to obtain a single sequence,...
0
votes
0answers
19 views

How well do multi objective optimization algorithms such NSGAii scale when there are many objectives (for example 10 or more)?

What I'm trying to figure out is what happens when using a multi objective optimization algorithm such as NSGA-ii and instead of trying to find the usual 2/3 objectives, I use 10 or many more ...
0
votes
0answers
43 views

Counting number of apples in an apple tree with given number of layers

This problem comes from a competitive programming question, and it seems to require dynamic programming. There are several layers of apples arranged in a formation with each apple having a value ...
0
votes
2answers
71 views

how to prove that log(n!) >= c n log(n) for some c >0?

as reading the book Algorithms by Dasgupta, C.H Papadimitriou. on Page 63. And it is well known that $\log(n!)≥c\cdot n\cdot\log n$ for some $c > 0$. There are many ways to see this. The ...
0
votes
1answer
33 views

What is meant by a preemptive algorithm?

The definition on Google says 'serving or intended to pre-empt or forestall something, especially to prevent attack by disabling the enemy.' So, how does this relate to an algorithm, especially the ...
1
vote
1answer
48 views

Algorithm for the complete parenthesization of n factors

Is there an algorithm that can list all possible parenthesizations of a given set of commutative factors? This is related to the Catalan number. It, however, merely determines the number of such ...
-1
votes
1answer
17 views

Recurrence Relation of Ternary search and the number of comparisons with binary search

i was reading the binary search and ternary search algorithms. But i had a doubt with recurrence relation of ternary search as somewhere it is T(n/3)+c and T(2*n/3)+c. I want to know which one is ...
0
votes
0answers
21 views

Disjoint Set Connected Components With Weighted Graph

I have been trying to solve this HackerRank problem (link). The basic premise of this problem is that there is a tree with undirected, but weighted, edges. The cost of a path in this tree is taken ...
0
votes
0answers
19 views

A deterministic finite state automata for finding all (potentially overlapping) regular expression matches?

I was working on a bioinformatics practice problem named Finding a Protein Motif on rosalind.info. In essence, I was given a particular regular expression ...
0
votes
0answers
16 views

Find the asymptotic time complexity of the following [duplicate]

while(n>1){ n = sqrt(n); } Where sqrt returns the root of n. n = 2^k and k is a power of 2.
1
vote
1answer
38 views

Minimize cost of recursive pairwise sums: how to prove the greedy solution works?

The problem is in this other question. Why does this always work? It's not clear to me how one would use induction. For $n = 3$, a quick calculation shows it works, however, I don't think it ...
0
votes
0answers
18 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,..........
0
votes
0answers
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 ...
4
votes
1answer
50 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....
1
vote
1answer
43 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 ...
1
vote
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
1answer
34 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 ...
2
votes
2answers
62 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. ...
0
votes
0answers
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 ...
0
votes
0answers
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. ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
14 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)...
1
vote
2answers
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: ...
0
votes
3answers
91 views

Time Complexity To find Kth smallest element in a min heap [on hold]

In a min heap of n elements, the Kth smallest element can be found in? O(n) O(nlogn) O(logn) O(1). According to me ans should be O(n), say we can have a case ...
2
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
2
votes
1answer
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 ...