Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

4
votes
0answers
67 views

Overlaying Two Matrices So That Sum Of Squared Differences Is Minimized

I have a question about my solution to a problem from Hackerrank. The problem is, given $R,C,H,W$ with $1\le R,C\le 100$, $1\le H\le R$, $1\le W\le C$, an $R\times C$-matrix $L$ and an $H\times W$-...
1
vote
1answer
28 views

Longest common sequence matrix giving wrong answer

I am trying to find longest common sequence for these two strings SHINCHAN NOHARAAA The common sequence is NHA of length 3 ...
3
votes
1answer
72 views

Global indexing of shared nodes in parallel

Consider a tiling of quadrilaterals in 2D that provide complete coverage of a particular region. N quadrilaterals are distributed across many parallel threads, typically in a way to keep groups of ...
2
votes
1answer
74 views

Are there algorithms with proven upper bounds but no proven lower bound (above constant time)?

One of my professors mentioned such algorithms exist but could not think of any offhand. Obviously any algorithm will be at least $\mathcal{O(1)}$, but are there algorithms not yet proven to have a ...
1
vote
1answer
36 views

Devising a way to spot a contradiction given a set of statements using graphs

If we had statements like: John is as tall as Mark, Mark is as tall as Sally, Chuck is as tall as Sally, Chuck is shorter than John. Would there be a way to figure out that there is a contradiction ...
4
votes
2answers
72 views

Find maximal subgraph containing only nodes of degree 2 and 3

I'm trying to implement a (Unweighted) Feedback Vertex Set approximation algorithm from the following paper: FVS-Approximation-Paper. One of the steps of the algorithm (described on page 4) is to ...
1
vote
1answer
49 views

Probabilistic r-way cut set algorithm

I am reading Probability and Computing, by Mitzenmacher and Upfal, and the exercise 1.24 asks for a generalized algorithm for finding the cut-set of a Graph. In this generalized version, instead of ...
7
votes
2answers
461 views

Find a point shared by maximum segments

Given: $N$ segments (arrays) of ordered integers, integers could be from $-K$ to $K$. Example: ...
2
votes
0answers
33 views

Check if a matrix over finite fields is superregular

Is there any practical, efficient algorithm to check if a matrix over $\mathbf{F}_{p^n}$ is superregular? It need not be theoretically polynomial, just roughly be implementable for $n=32$ and for ...
2
votes
1answer
168 views

Finding the largest possible area covered by M rectangle under a given histogram

Finding the largest rectangular area possible in a given histogram is a well-known problem and have linear solution. I have a similar but different problem. In my problem, we have $M$ rectangles ...
1
vote
1answer
24 views

A tree edge $uv$ with $u$ as $v$’s parent is a cut edge if and only if there are no edges in $v$’s subtree that goes to $u$ or higher

Referring to these notes regarding DFS - Click Here They refer to the following claim that follows Definition 0.2. as observation: A tree edge $uv$ with $u$ as $v$’s parent is a cut edge if and ...
6
votes
1answer
109 views

Finding a negative cycle in a bipartite graph

The Bellman-Ford algorithm can be used to find a negative cycle in a general graph, in time $O(|V||E|)$. Is there a faster algorithm for finding a negative cycle in a bipartite directed graph, where ...
4
votes
1answer
95 views

Maximum subarray of bounded length

I'm giving an array $A[0..n-1]$ and an integer $w$. The goal is to find indices $i,j$ that maximize $$\Phi(i,j) = A[i] + A[i+1] + \dots + A[j-1],$$ subject to the requirements that $0 \le i \le j \...
9
votes
2answers
163 views

Find an optimal ordering

I came across this problem and am struggling to find a way to approach it. Any thoughts would be greatly appreciated! Suppose we are given a matrix $\{-1, 0, 1\}^{n\ \times\ k} $, for example, ...
2
votes
1answer
21 views

Name of double sided search algorithms

I modeled the function double_sided_breadth_first_search after the ideas in "improving Dijkstra" in Cormen et al, and the OCW course on algorithms. Note that I expand the smaller boundary, in an ...
0
votes
1answer
48 views

Distance function such that we visit every “color region” once [closed]

Consider the following image: Starting at (0,0) top left, the objective is to find a dijikistra path to the bottom right. We must go through each color exactly once, and once we go outside a color, ...
0
votes
0answers
41 views

Show that for each even n, there exists a graph with n vertices, such that the 2-approx VC alg returns a VC which is exactly twice the Minimum-VC

Question: Show that for each even n, there exists a graph with n vertices, such that the ALG(algorithm) returns a vertex cover which is exactly twice the size of minimum vertex cover. Define ALG: ...
2
votes
1answer
80 views

Can all $O(n)$ problems be solved without nested loops?

There are examples of algorithm implementations that contain nested loops but are of complexity O(n), and some of them have corresponding implementations that contain no nested loops. So here comes a ...
21
votes
2answers
5k views

If I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?

Let us say there is a program such that if you give a partially filled Sudoku of any size it gives you corresponding completed Sudoku. Can you treat this program as a black box and use this to solve ...
2
votes
1answer
48 views

How to partition a set in order to minimize the number of the elements and their interactions?

Given two sets $S_1$ and $S_2$ of $n$ elements each. Each set $S_1$ (resp. $S_2$) has a revenue $R_1$ (resp. $R_2$). Each element $i$ of $S_1$ (resp. $S_2$) has a gain $g_{i1}$ (resp. $g_{i2}$). From ...
0
votes
0answers
72 views

Brute Force Approach for LCS and its Time Complexity

I have read several Algorithm books where it is been told brute force approach of Longest Common Subsequence takes 2^n which is exponential time complexity. Whereas, I've noticed that while I am ...
2
votes
1answer
257 views

Implicit nil checks in algorithms

I am reading algorithms in a CS book where a potentially nil value is passed to a function, but neither the caller nor the callee check if the value is nil. Is this a common practice in algorithms? ...
6
votes
2answers
142 views

Can this system of polynomial equations be solved in polynomial time?

I have these $n$ equations, with $n$ variables. Variables are first $n$ positive integers, constants can be any rational number including zero. Given that there is always a solution, how do we find a ...
0
votes
1answer
40 views

Expected value of the distance between nodes in a binary tree

If there are 16 leaves in a full binary tree and two nodes $a$ and $b$ chosen at random, then what is the expected value of the distance between $a$ and $b$ in T? My question here is, how do I ...
3
votes
2answers
32 views

Minimizing catastrophic risk in Gale-Shapley matching

In the hospital-resident assignment problem we have to match a large set of med students with a small set of hospitals. Hospitals may accept multiple students, but the number of students is much ...
0
votes
0answers
12 views

Proving k-partition problem is NP [duplicate]

For any integer k ≥ 2, the k-Partition problem is said to be a sequence of positive integers (w1, w2, . . . , wn), is it possible to partition them into k groups having equal sums? I'm confused on ...
1
vote
2answers
48 views

Can someone explain why the MAX-CUT problem is in NP?

Given an undirected graph $G = (V, E)$ and an integer $k$, is there a partition of the vertices into two (nonempty, nonoverlapping) subsets so that $k$ or more edges have one end in each subset? I'm ...
3
votes
1answer
123 views

3SAT instance with EXACTLY 3 instances of each literal

I'm trying to solve a question which requires me to prove that an instance of 3SAT where each literal appears in exactly 3 clauses (positive and negative appearances combined) and each clause ...
3
votes
1answer
65 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? (...
3
votes
3answers
903 views

Algorithm to convert a fixed-length string to the smallest possible collision-free representation?

I have a US-based telephone number (in the format 000-000-0000) and need to convert it to a "shorter" representation. Using base32/64 produces too long of a string. I've discovered CRC-16, which ...
1
vote
0answers
22 views

Given a subset of numbers $1, \dots, n$, find the minimal subset of numbers $1, \dots, n$ sums of every subset of which cover all sums of first subset

Given a subset $A = \{a_1, a_2, \dots, a_k\}$ of numbers $\{1, 2, \dots, n\}$, find another subset $B = \{b_1, b_2, \dots, b_t\}$ of numbers $\{1, 2, \dots, n\}$ of minimal size (that is, minimise $t$)...
1
vote
1answer
23 views

Amortized time complexity for double stack emulated queue

Assume that we have a data type $stack$ which has two operation $push$ and $pop$, both operations' time complexity is $O(1)$ in worst case. The $stack$ also has a property $size$ indicate how many ...
1
vote
2answers
36 views

Find m smallest elements in an array of size n where m = n/2

So we have an unsorted array, we need to find the first $m$ elements in ascending order (or $m$ smallest elements) where $m = \mathrm{array.size}/2$ (or $n/2$). How would we do this in linear $O(n)$ ...
2
votes
1answer
44 views

Generalizing Knuth's $O(\log_2 n)$ Fibonacci algorithm to linear homogenous recurrences

Knuth has a neat algorithm that uses matrix exponentiation to compute the $n$th Fibonacci number in $O(\log_2 n)$-time 1. However, there doesn't seem to be a lot of resources on generalizing his idea ...
0
votes
1answer
54 views

Condensed Nearest Neighbor Explanation

I have a question regarding the Condensed Nearest Neighbor algorithm from ...
2
votes
1answer
72 views

How to best maintain a sorted list from a stream of integers?

If I have an incoming stream of integers how can I best maintain a sorted list of them? The only way I can think of is to binary search for the position and shifting the remaining elements to the ...
1
vote
2answers
111 views
1
vote
2answers
65 views

Putting as many items as possible with weight and size limit

I am trying to design a greedy algorithm that has to take in multiple factors when making a greedy choice. Any item has an item weight of Iw and item size of <...
0
votes
0answers
35 views

Correctness of algorithm and its complexity

I am trying to solve problem of generation of so called activity-on-edge (activity-on-arc) network graph given based on given activity-on-node network graph. So, I found this paper proposing an ...
2
votes
1answer
23 views

Interpolate on a cylic x axes

Let's assume you are in 2D space and you have a set of fix points FIX_POINTS = [(x1, y1), (x2, y2)]. I want to interpolate the y ...
0
votes
0answers
23 views

What is the complexity of an algorithm that ensures 2 “aggregate graph properties”?

Background Let $G(V,E)$ be a graph. Let $S$ be the set of all combinations of $|V|$ edges. Let $A$ & $B$ be two subsets of $S$, where: each subset is a collection of all elements of $S$ that ...
6
votes
1answer
56 views

Can one count the number of n points in m triangles in less than O(nm)?

We have n points given as $(x,y)$ coordinates and m triangles given as triples of $(x,y)$ coordinates, and want to count the number of times that one of the points is inside one of the triangles. The ...
4
votes
0answers
91 views

Subset Sum Search Problem for Input with At Most One Solution [closed]

Edit: This question has been reasked on TCS. We first consider the search version of the subset sum problem: Given a set $S$ of $n$ naturals, find a subset of $S$ that sums to exactly $W$. My ...
0
votes
1answer
40 views

QuickSort of linked lists optimised for duplicates

This is an past year question for a school exam that I do not suggested solutions for. Problem Description Quick Sort is not stable because of need to swap values in array when partition is done. If ...
6
votes
2answers
117 views

Find a $\log_2(|V|)$ long cycle where each node is of different color

Here's a question from an algorithms exam by Prof. Noga Alon that I just can't wrap my head around. Let $G=(V,E)$ be a directed graph where $|V|=n$. Let $k=\lfloor \log_2(n)\rfloor$. Each node in ...
2
votes
2answers
39 views

Calculate the number of distinct permutations of length n in the closure of a language

I am studying a distance CS course, but there is no tutor available, so I would appreciate your help... Consider the language $S = \{a, aa, ab\}$ How many distinct words of length $n$ will appear in $...
0
votes
0answers
16 views

how can I write an algorithm in python that converts a natural number n into base b? [duplicate]

I only know simple python but I'm not sure how to write an algorithm that takes values n and b, where n is a positive integer and b is the base, and converts n into base b. Note b<=10.
0
votes
1answer
41 views

Can Dijkstra's algorithm be modified to return paths with ascending edge-id's?

Say that each edge in a directed graph is labelled with an ID. I want to run Dijkstra on the graph to find the shortest path between $source$ and $destination$, with the additional restriction that ...
0
votes
2answers
85 views

Interview Questions for Minimum Cost of Tasks

I got this problem as an interview questions and I was blank all the way, I thought it was pressure but as I try to do it now I am still blank, anyway to solve this problem, I am blank so a solution ...
1
vote
1answer
30 views

Get all factors of a word in linear time or constant time

I have the following problem : I have an algorithm which takes a word $w$ as entry. The problem is that my algorithm is doing a lot of things on the factors of $w$ and I am representing $w$ as an ...