# 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,443 questions
Filter by
Sorted by
Tagged with
0answers
11 views

### Number of swaps and comparisons in sorting algorithms

i was reading the comparison algorithms(bubble,insertion and selection). i followed this linklink1,but if someone asks what is the number of comparison and swap in these algorithms, what should i say ?...
0answers
5 views

### Solved “Generate Parentheses” using Bit Manipulation - is my algorithm faster than other known solutions?

It's a famous old question, LeetCode #22 "Generate Parentheses": Given an integer n, generate all valid permutations of n pairs ...
1answer
16 views

### Binary Search Symbol Table

Hi I'm attempting to self teach myself from Algorithms (Sedgewick) and ran across the following problem: ...
1answer
22 views

### Algorithm for commonalities across related objects

I am making early forays into the application of algorithms to best solve a problem and I am finding it difficult to choose the best application. The problem is give the data below (two columns) ...
0answers
13 views

### How to know a specific coordinate on Google maps is in a road or a building?

Is it possible to know if a specific coordinate is located in road or a building? For example, if I take this coordinate 52.5047252, 13.3569516 do I need to type it on Google and verify it's position ...
0answers
10 views

### Recurrence Formula for Bitonic Sorter Runtime

A Bitonic sorter takes a bitonic sequence as an input and the output is a sorted list. I want to analyse Bitonic Sorter by knowing its depth/runtime. Can anyone give an idea on its recurreence formula?...
1answer
56 views
+50

### Merging nodes of a DAG

I would like to merge connected nodes with a specific attribute of a directed acyclic graph. After each merge operation, the graph should remain acyclic. Let's say my graph contains blue nodes and ...
1answer
41 views

### Are every problems in EXP karp reducible to any EXP-Complete?

According to wikipedia and other references there exists complete language $L \in EXP$ such that for every languages $L'$ in $EXP$ there exists a polynomial reduction $f$ that converts instance of $L'$...
1answer
36 views

0answers
12 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, ...
0answers
611 views

0answers
20 views

### How to create a square root program without using math library in c++ [on hold]

I need help to finish my activity in data structures and algorithms. Need help 😅
1answer
791 views

### Compression of domain names

I am curious as to how one might very compactly compress the domain of an arbitrary IDN hostname (as defined by RFC5890) and suspect this could become an interesting challenge. A Unicode host or ...
2answers
2k views

### Time Complexity analysis for Map-Reduce model

I am trying to redesign my algorithm to run on Hadoop/MapReduce paradigm. I was wondering if there is any holistic approach for measuring time complexity for algorithms on Big Data platforms. As a ...
1answer
18 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 ...
1answer
65 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-...
1answer
19 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 ...
2answers
35 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 ...
1answer
52 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 ...
1answer
32 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 ...
1answer
10 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 ...
1answer
27 views

### Student Course Allocation Problem with Many Constraints [on hold]

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 ...
1answer
164 views

### Predicting next action to take to reach a final state

Does anyone know of an algorithm that could be used to determine the next action to take to reach a desired state when trained on time-series data? For example, a robot starts at a certain state, ...
1answer
84 views

### Building maze to maximize shortest path, may be given waypoints and teleports

How would you go about solving this problem? Is it something that could be expected to be computed/solved within a couple of hours of given a starting area with (32) threads on 3.0GHz Xeon cores? (...
1answer
20 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 ...
0answers
11 views

...
1answer
95 views

### Minimizing sum of recursive pairwise sums

What is the best algorithm for this? We are given an array of positive integers and we want to minimize the total cost of recursively adding together all the integers to one integer, two integers at ...
0answers
40 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 ...
1answer
23 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 ...
1answer
117 views

### Find variance within one pass

Given a list of real numbers. Is it possible to find the variance with no more than 1 iteration with constant space complexity?
0answers
15 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,...
0answers
18 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 ...
2answers
59 views

### What is the best way to avoid using goto statements in the pesudocode for an algorithm?

What is the best way to avoid using goto statements when writing the pseudocode for an algorithm? I want to avoid it and use another way to replace it.