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

10,499 questions
Filter by
Sorted by
Tagged with
1 vote
36 views

### Is there a method for information transfer without copying the data?

What I mean is, if in real life I had an object and I gave it to you, I would not have it anymore. I did not give you a copy of the object. Is there a way to do that with information?
110 views

### Is there an efficient algorithm to find GCD of all cycles' lengths in directed multigraph?

I have weighted connected directed graph with cycles which can have multiple edges and loops (edge from vertex back to itself). Weight of each edge is its length (always positive integer). There ...
27 views

### Which algorithm would be most suitable for finding a minimum subgraph that connects all vertices in a graph and has the smallest weight?

Which algorithm would be most suitable Kruskal, Prims or Steiner tree algorithm ?
1 vote
20 views

### Algorithmic ideas to multiply two tall & skinny matrices into one large square matrix?

This problems comes from AI, and it looks something like this: I am supposed to multiply two floating-point matrices A * B. A ...
1 vote
41 views

### Find a perfect matching with weights as close as possible to each other

Given a set of jobs $J$ and a set of machines $M$, where the link between machine $i\in M$ and job $j\in J$ has a positive weight $w_{ij}$. The problem is to select a perfect matching between the jobs ...
1 vote
53 views

### Find max of all trees resulting from single edge removal in generic tree in linear time

Given a generic tree with $n$ weighted nodes, there are $n-1$ edges. Removing any of the edges will partition the tree into two distinct trees, hence we can construct $2(n-1)$ possible trees in this ...
1 vote
26 views

### Redistricting algorithm

Here in the USA there is a lot of controversy over the practice of gerrymandering. Every ten years the states are divided up into new congressional districts and whoever is in charge creates bizarrely ...
27 views

### finding a hemisphere that contains all points of a given set S

Let $S$ be a finite set of points on the unit sphere $\mathbb{S}^2$. My question would be: is there an easy way to either find a great circle $C$ such that all points in $S$ are inside one of the ...
1 vote
50 views

### Summation of asymptotic notation the

How can we solve summation of asymptotic notations like given below: $$\langle 2^0 + 2^1 + 2^2 + \dots + n^{k}\rangle = \Theta(n\log n)$$
25 views

### Where is external sorting used beyond databases?

I am trying to find applications/systems that use external sorting techniques or avoid external sorting by using other methods to achieve a task. I know most relational databases (like PostgreSQL or ...
87 views

### Consistent Hashing Algorithm Without Distribution / Load Balancing

I need some help finding or creating a consistent hashing algorithm with the following properties: Given N buckets, only distributes keys to bucket N. When number of buckets are increased from N to N+...
24 views

### Algorithm to generate unique suggestions for creating an ID

Let's say I have a service where I provide user registration. The user chooses a ID. Now if I already have someone who is registered against that ID, I will inform the user that this ID is already ...
22 views

### An electronic book is made up of 500 pages there are 16 lines of 2400 bits lines of each page. computer space it will ocuppy on a computer in GB

An electronic book is made up of 500 pages and there are 16 lines of 2400 bits lines of each page. compute the space it will ocuppy on a computer in GB
28 views

### scheduling with profits and deadlines clrs

The following problem is on page 1104 of the CLRS textbook: I was wondering how to show that the problem is NP-hard (i.e. part b)? Like subset-sum, this problem is weakly NP-complete; it has a ...
1 vote
23 views

### compute shortest distance to a different sink

Given a directed graph G=(V, E) and a sink vertex t. Edge costs may be negative, zero, or positive. consider d(v) contains the length of the shortest path from v to t Given a new sink t2 in the graph, ...
71 views

### Longest common subsequence of two permutations

Given two permutations $\pi_1$ and $\pi_2$ of numbers $\{1,2,\dots,n\}$, can we find $\mathrm{LCS}(\pi_1,\pi_2)$ in $O(n\log n)$? I think we can use LIS but I get stuck.
22 views

### a generalized job assignment problem

The following problem is from a past algorithms course exam and I'm using it to test my knowledge. There are m machines and n jobs. Each machine can doing a subset of jobs. Each machine i has a ...
60 views

### How we can solve two lines of this algorithm in $o(n^2)$?

Given $n=2k$ pairs of points $P=\{(p_1,q_1),(p_2,q_2),\dots,(p_k,q_k)\}$ in the plane. Also, let $d(.)$ return distance between two points. Now, our goal is to act as bellow: For each $(p_i,q_i)$ ...
1 vote
38 views

### Given T(1)=1 and $T(n) = 3T(n/4) + cn^2$, does it make sense to yield $T(2)=T(1)+c2^2$?

Section 4.4 of "Introduction to Algorithms, 3rd Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein" illustrates how a recursion tree provides a good guess ...
43 views

### Efficiently finding range from ordered list of ranges with preprocessing

Say we have a list of ranges like so: ranges = [(0, 100), (101, 200), (201, 300)] The ranges will always be ordered, never overlap, and perfectly align. We want to ...
1 vote
11 views

### Finding overlapping time under distance condition

I have a set of records (2 or more for each person) on multiple peoples locations (latitude and longitude) with timestamps. each record has: person ID, latitude, longitude, timeStamp. for each 2 ...
25 views

1 vote
35 views

### Where does 2^32 come from with bitcoin?

Several months ago I was doing research into calculating mining revenue for several crypto currencies. When trying to calculate BTC revenue I found this value 1/2^32 which was described somewhere ...
50 views

### How do these Crypto terms relate to each other and what do they all mean?

Alright this is another day of my pursuit to learn about how crypto works. I have several terms that I have found linked together. I was trying to do research on how the Target Hash is determined and ...
55 views

### Store strings which have same start, but different end

I need to store a list of strings in some files. In this moment, there are too many strings in too many files, which is a problem for me. Here is an example of strings: ...
25 views

### 3-term arithmetic progression

I am a computer science student, I am studying an algorithm course independently. In the course I got stuck with this question: $A$ 3-term arithmetic progression is 3 integers ${a < b < c}$ such ...
1 vote
20 views

### K-Modes Clustering with Partially-Overlapping, Variable-Length Data?

I'm working on a project that's attempting to cluster books using machine learning. I'm using the K-Prototypes algorithm for clustering data that has both numerical and class-based data. Under the ...
1 vote
20 views

### Algorithm Complexity Question

this is my first question on this site and I would like to preface this by saying I am not very savvy when it comes to Computer Science. So, I will try to ask this the best I can. I was doing some ...
63 views

### Binary search with mid index equals to $\frac{(right + left )}{2}$

I have tried to implement traditional binary search on an array. Now, if I set the mid index to be $mid = \frac{(right + left )}{2}$, my code does not run within time quota specified already, however, ...
1 vote
35 views

### T(1)=1 is a boundary condition of the recurrence $T(n)=2T(\lfloor{n/2}\rfloor)+n$. Does there exist any other boundary condition of the recurrence?

Section 4.3 of "Introduction to Algorithms, 3rd Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein" uses the following recurrence as an example to ...
1 vote
37 views

### Why DFS transversal without the duplicates is a valid cycle?

So I am studying apporiximation algorithms for TSP problem and there is a step that I don't get. Essentially trying to solve TSP means we are looking for a minimum cost Hamiltonian path. The well-...
39 views

### Is there an algorithm for determining the identity of an individual, based on their genome and the genome of distant relatives?

I've been thinking recently about the Golden State Killer case, in which a crime was solved by comparing a killer's DNA sample with known samples in a public genetic database. The cousin of the killer ...
1 vote
54 views

### Recursive algorithm for adding numbers from 1 to n with O(1) time complexity

So I have a recursive algorithm which sums up the numbers from 1 to n plus one (hence the return 1): ...
19 views

### Algorithm to Detect Disjunctive Relationships

I'm working with logic formulas of the form '0 & 2 | 0 & 3'. I was wondering if anyone knew of an algorithm that would take in such a formula, detect existing disjunctive relationships, and ...
1 vote
31 views

### How to prove that if Eternal Vertex Cover is Polynomial it's possible to detect its vertices and edges

EVG is defined as EVC = { <G,m,k>| G is an undirected graph and there is as et of m edges in G that are covered by at most k nodes} If EVG was decidable in polynomial time how could we find the ...
1 vote
60 views

### How to use the step count method correctly for binary search?

I've tried to use the step counting method to get the worst-case time complexity for binary search. But I seem to mess it up, as my final result would be O(n) and ...
21 views

### GPU compute parallel radix sort optimizations

I'm looking at this paper that describes a GPU parallel radix sort algorithm. They describe multiple optimizations but in section 3 where the whole algorithm is described some things elude me. First, ...
1 vote
36 views

### Text Justification problem of "Introduction to algorithm"

The problem that I currently went through is kind of text justification problem. The problem is given that there is a paragraph and a some blank lines. We want to print this paragraph neatly on the ...
1 vote
75 views

### Why are these two recurrence relations that compute the shortest path equal?

Given a directed graph $G=(V,E)$ with positive weight function $w$, source $s$, destination $t$ and a nonnegative integer $\ell$, we want to find shortest path $\pi$ from $s$ to $t$ such that $\pi$ ...
1 vote
92 views

### Given a sequence of strings how can you find the maximum number of strings so that if you concatenate them you have a dominant letter?

The naive approach, which is the first thing that came to my mind, is to use some sort of backtracking to generate all subsets of the given set of strings and then to find the subset with the maximum ...
52 views

### Non adjacent sum: Why do we need to include or exclude the current element?

The problem goes like this: Write a function, nonAdjacentSum, that takes in an array of numbers as an argument. The function should return the maximum sum of non-adjacent elements in the array. There ...
11 views

### How much faster would a semantic segmentation model be with just 2 classes compared to 100 classes?

Let's say I have a semantic segmentation model that distinguishes between 100 classes of objects, and the speed of running the model is 1 image per second. Now let's say I take the same model ...
1 vote