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.

0
votes
2answers
25 views

Quicksort Algorithm with Pivot element as Median

I have read that when pivot element is choosen as Median, then QS Algorithm gets nearly balanced splits and have time complexity of O(nlogn), but my doubt is what if all the elements of the input are ...
3
votes
2answers
61 views

Minimize number of DFS searches in a graph

I got a weird homework question about graph. A helicopter is going to land on an island to check the n houses after an earthquake. Some of the two-way roads connecting the houses are destroyed ...
0
votes
2answers
86 views

Why run -time of N-Queens using backtracking algorithm fluctuates?

I have tested and measured the running time of a backtracking algorithm for solving the $N$-Queens problem. When $N=7$, the run time is $0.773$, but for $N=8$, the run time is $0.492$. I think the ...
2
votes
2answers
91 views

Divide two strings to form palindrome

Given two strings, A and B, of the same length $n$, find whether it is possible to cut both strings at a common point such that the first part of A and the second part of B form a palindrome. I've ...
18
votes
4answers
5k views

Time complexity of an algorithm: Is it important to state the base of the logarithm?

Since there is only a constant between bases of logarithms, isn't it just alright to write $f(n) = \Omega(\log{n})$, as opposed to $\Omega(\log_2{n})$, or whatever the base might be?
1
vote
0answers
20 views

How to Track Connected Components in a Graph when Deleting Nodes

Suppose you have a graph G, and you want to support the following operations: addNode(Node n) addEdge(Node n1, Node n2) ...
1
vote
0answers
65 views

Approporiate algorithm for a graph theory problem

So I have recently ran into a graph theory problem and was unable to find a matching algorithm for the problem or reword the problem to match some existing algorithm. The problem is pretty ...
3
votes
1answer
88 views

How to understand the recurrence relation and time-complexity of StoogeSort?

I have the following problem of recurrences and divide-and-conquer. Consider the algorithm, called StoogeSort in honor of the immortals Moe, Curly and Larry. The swap operation $(x,y)$ exchanges the ...
1
vote
1answer
50 views

why is $O(n^2)$ equal to $n^{1.5}$?

I am learning this MIT course, which gives this formula $$O(n^2) = n^{1.5}$$ is there a table to calculate this? like $O(n^{1.5})$, $O(n^{5})$ ? what x takes would have O(x) give $c \cdot n$ where ...
1
vote
1answer
85 views

Shortest Path in Layerwise Complete Graph

Consider a directed $k$ partite graph $G$ with a source node $s$ and a sink node $t$. Each vertex in the graph is labeled with a positive integer value. Both the source and sink are labeled with $0$. ...
3
votes
2answers
95 views
2
votes
0answers
27 views

What does it mean by “consistent view of memory” in lock-free dequeue implementation?

I am currently reading this paper by Chales-Lev. This paper explain an implementation of work-stealing dequeue. The part where I don't understand is in the implementation of steal operation. ...
3
votes
0answers
35 views

DCEL with dynamic graph

Is doubly-connected edge list a good data-structure for planar graph which vertices can be moved freely? I experienced DCEL as a very good structure when it comes to add/delete some vertex or edge. ...
2
votes
1answer
35 views

Running time for Breadth-First-Search vs Depth-First-Search

Can someone explain why BFS is $O(V + E)$ whereas DFS is $\Theta(V + E)$. I understand the definitions of both notations, but I just don't see why the bound for DFS should be tighter than that of BFS. ...
0
votes
0answers
17 views

How to make schedules so that each team plays every game?

There are g games (checkers, chess, Monopoly, ...) and there are t teams. t is odd. Each ...
1
vote
1answer
18 views

Tarjan's Algorithm failure case, what am I missing?

I'm having a little trouble with Tarjan's Algorthm. So here's my problem: I have a graph such that these nodes are directionally-connected as shown: ...
0
votes
0answers
28 views

Finding negative cycle using Bellman Ford

Given a graph with |V| vertexes and |E| edges, I have to find a negative cycle, if there is one, in a graph. The wanted complexity is O(|V|*|E|). I was thinking about using Bellman-Ford to solve the ...
3
votes
2answers
73 views

Single-source shortest paths with even weight

I need help to find an algorithm that calculates the single-source shortest paths in a graph, with an extra condition that the weight of the path has to be even. In another words, we have to find the ...
1
vote
2answers
32 views

What does “bounded above” mean in Family of Bachmann–Landau notations?

Per wiki |f| is bounded above by g (up to constant factor) asymptotically with this concrete example, $$f(n) = \log n$$ $$g(n) = n^c = n^{0.000001}$$ Does "bounded above (up to constant factor)...
1
vote
0answers
67 views

Maximum size of BFS open set on a grid

I have a 2D grid of infinite size that can either be 4-connected or 8-connected (as defined in https://en.wikipedia.org/wiki/Pixel_connectivity). I am implementing breadth-first search on this grid ...
0
votes
0answers
29 views

how to compute $O(n^{0.000001})$ [duplicate]

this MIT course gives a formula about Big O $$n^{0.999999} \log n = O(n^{0.999999} \cdot n^{0.000001})$$ going through wiki, i cannot find a similar Big O properties or usages. how to compute $O(n^{...
2
votes
1answer
86 views

Subtree with minimum sum of nodes' costs

Let's consider a tree with root $r$ ( not necessary binary) and to each node $i$ we associate a cost $\sigma(i)$ that can be negative, positive or zero. We want to select the set of nodes that ...
0
votes
1answer
27 views

Solving using the master theorem: T(n)=T(n/2)+n⋅log n and T(n)=T(n/8)+2.n [closed]

Could someone help me with these 2 questions? I do not understand the case 3 $T(n) = T(n/2) + n \log n$ $T(n)=T(n/8)+2 n$
2
votes
0answers
17 views

Regex NFA construction: Why use Glushkov over Thompson? Pros/Cons

In what circumstances should we prefer Glushkov's algorithm or Thompson's construction for the building of regular expression NFAs? I understand the difference between them, and can follow the ...
0
votes
1answer
16 views

Orthogonal range reporting with fixed upper rectangular corner

Consider the following special case of orthogonal range searching: Given a set $S$ of $n$ points in $d$ dimensions, and rectangular queries with a fixed "upper-left" rectangle corner $(0,0,...0)$, ...
4
votes
1answer
39 views

How to approach analysis of randomized algorithm

Let us suppose we have a sequence of values $C(i)$ that represent some counter for a given $i$ for $i \in \lbrace 1, \cdots, n \rbrace$. Let us assume some uniform distribution $U$ where selecting any ...
0
votes
0answers
32 views

Algorithm to change order of tree

I'm looking for an algorithm name to change the order of the levels of a tree. I've done something that works but there's a lot of code and the $ O(n) $ is very bad. Here's an example, let say there ...
19
votes
9answers
6k views

Is it a good idea to teach algorithm courses using pseudocode instead of a real programming language? [closed]

I am a young professor teaching a data structures course for the first time. I'm teaching at an engineering college that provides an academic degree, but the focus is preparing future computer ...
0
votes
0answers
34 views

Job scheduling with minimum makespan

You are given n jobs, m workstations and an n × m two-dimensional task matrix T of the time each job will spend at each workstation. Each job becomes available at a specified time and may be processed ...
4
votes
1answer
95 views

Scheduling algorithm to minimize the number of late jobs

There are $n$ (non-recurring) jobs where each job $i$ has an arrival time $a_i$ and a duration $t_i$. All the jobs share a deadline length $d$ (deadline for each job is $a_i + d$). The problem is to ...
1
vote
1answer
22 views

Number of ways of tiling a 3*N board with 2*1 dominoes problem

I came across this problem, Tiling with Dominoes and initially I faced difficulty in understanding the logic behind recurrence relation, but after reading it from here , I understood it. But I had a ...
2
votes
1answer
36 views

k-enclosing rectangle in two-colored point set

I was asked to write an algorithm for the following problem, and discuss complexity: There are p points of two colours, black and white, in an n*m grid. Any cell in the grid can contain 0 or ...
0
votes
0answers
62 views

Find longest path in minimum spanning tree

Given an undirected MST with positive weights how can the longest path be found? Based on the accepted answer in this question Longest path in an undirected tree with only one traversal I've ...
2
votes
2answers
69 views

Converting a number from N to 0 in binary

Trying to solve this problem since 2 days. Still unable to figure out even a basic approach. Given a number $N$ in binary ($1$ to $10^5$), we need to convert it to $0$ using only 2 operations. ...
1
vote
2answers
38 views

Running time correct with Omega?

I have the following statement. I would say it's correct as it's either equal or higher than $\Omega(\log^{10}(n))$. Because: I know $\log(2^n) = n$. By that I would guess the same goes for $\log(n^{...
0
votes
1answer
49 views

Help with graph search problem

For the next problem I can not think of how to find a solution with graph searches (I thought it was backtracking but my college professor told me that I should use graph searches, which I do not know ...
2
votes
1answer
45 views

Distributed MST Construction in O(log log n) Rounds in a Clique

I'm reading the paper MST Construction in O(log log n) Communication Rounds in a Clique and trying to understand the correctness analysis, in page 5. It shows by induction on k (phase number), that ...
2
votes
1answer
68 views

Understanding Correctness of Bidirectional Dijkstra

I'm trying to understand the correctness of the bidirectional version of Dijkstras algorithm as mentioned here on slide 10: https://www.cs.princeton.edu/courses/archive/spr06/cos423/Handouts/EPP%...
1
vote
0answers
28 views

How to justify using available code (in different language) for comparing algorithms [closed]

I have proposed an algorithm for a scheduling problem in a submitting paper. In the revision, the reviewer asked us to compare with another algorithm in the literature. Our algorithm is in MATLAB, and ...
0
votes
1answer
24 views

Proof Big Theta (sum of a geometric)

Here sum of a geometric, where c is a positive real number. $g(n)=1+c+c^2+...+c^n$ $\theta(1)$ if $c<1$ Any idea to solve this?
0
votes
0answers
22 views

Implementing binary arithmetic encoder

I have set integers that are normally distributed, and I'm trying to implement binary arithmetic encoding, as suggested in this post: Compressing normally distributed data I'm running into trouble ...
2
votes
1answer
46 views

Can we find a computable function which cannot be calculated faster for any given time?

Define $T\colon \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}$ by: $T(k,n) = 2^{T(k-1,n)}$ $T(0,n) = 1$ $T(1,n) = 2^n$ $T(2,n) = 2^{2^n}$ And denote the W.C. (worst case) time of computing $...
2
votes
1answer
31 views

Minimize shipping cost based on weight and price constraints

I'm trying to determine the least shipping cost when you have a number of items (each with a weight and a price) that can be combined into the same package. The constraints are as follows: There is a ...
3
votes
1answer
53 views

Reductions between LIS and LCS

Given an oracle that returns both the length and the subsequence for the Longest Increasing Subsequence of a given input $A$ of $n$ elements $\text{LIS}(A,n)$, can one use a polynomial number of calls ...
2
votes
0answers
52 views

What algorithm should I use for the following problem?

Suppose we have 2 lists: List $G$: the goal, contains goal items each comes with a specific amount, $$G = \{i_1 \times Item_1, i_2 \times Item_2,\dots, i_n \times Item_n\}$$ List $I$: a list that ...
0
votes
1answer
36 views

Non consant size alphabet

Sometimes I read that an algorithm works on constant size alphabet and it is clear for me but what means that an algorithm works with a non constant size alphabet? I would like to see an example.
3
votes
4answers
105 views

How to select best k fractions out of n fractions (k<=n) so as to have (numerator sum / denominator sum) maximum?

For example, given 4 fractions $\frac{4}{2}$, $\frac{2}{3}$, $\frac{1}{2}$, $\frac{10}{20}$, I have to select 3 fractions out of these 4 so that the value of $\frac{\text{numerator sum}}{\text{...
0
votes
0answers
32 views

Vertices/segments graph to polygons

On a 2D plane there is a set of vertices V and segments S. Each segment has 2 vertices, and each vertex knows segments that use it. That creates a kind of a graph. I would like to find all polygons ...
0
votes
0answers
25 views

Draw lines according to a specific condition

We have an infinitely planar cartesian coordinate system on which $N$ points are plotted. Cartesian coordinates of the point $i$ are represented by $(X_i,Y_i)$. Now we want to draw $(N−1)$ line ...
2
votes
1answer
86 views

Proving NP hardness in Puzzle with SAT reduction

Introduction I have created an algorithm that generates n^2 x n^2 Sudoku Grids. Out of those grids I remove elements to give only one solution. The algorithm follows an infinite language based on ...