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.

6
votes
1answer
398 views

Finding Shortest Paths of weighted graph using stacks

I will be given some kind of this graph as in the picture below. I've searched some algorithms but it seams as if it is something impossible for me to figure them out. In fact using Floyd–Warshall ...
2
votes
2answers
60 views

Divide two strings to form palindrome [on hold]

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 ...
0
votes
0answers
10 views

About to find the maximum sum of transaction within a time window period

I received hundreds of transactions within one week. Each transaction has amount. I'd like to create an algorithm to find the maximum amount within 24 hour time window period. I know how to do that by ...
34
votes
6answers
46k views

The math behind converting from any base to any base without going through base 10?

I've been looking into the math behind converting from any base to any base. This is more about confirming my results than anything. I found what seems to be my answer on mathforum.org but I'm still ...
0
votes
2answers
71 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
0answers
32 views

Optimizing De Boor's algorithm

According to De Boor's algorithm, a B-Spline basis function can be evaluated using the formula: $$ B_{i,0} = \left\{ \begin{array}{ll} 1 & \mbox{if } t_i \le x < t_{i+1} \\ 0 &...
2
votes
0answers
30 views

Getting maximum consumption in a given interval

I propose to solve a scenario that is pretty familiar. I hope you can help me. I have a set of home appliances and their power consumption (in watts). TV: 250 W Oven: 2400 W Washing machine: 500 W ...
0
votes
0answers
14 views

Knapsack problem understanding a question

I don't understand this question and I would really appreciate it if someone could help. So it starts off with explaining the Knapsack Problem then it asks me to write a function that calculates the ...
1
vote
0answers
6 views

complexity of computing fractional edge-chromatic number of an edge-weighted graph

Let $(G,w)$ be an edge-weighted graph, where the weights $w(e)$ are assumed to be rational. My question is: What is the complexity of computing $\chi'_f(G,w)$, the fractional edge-chromatic number of ...
3
votes
2answers
53 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
0answers
27 views

Proof that this sorting algorithm sorts the input

I'm given this "sorting" algorithm and now I'm supposed to prove, that if given an array of integers of length $n$, sort(A,0,n-1) will sort it. ...
17
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
21 views

Algorithm for factoring elements of permutation groups?

You can solve a Rubik's cube by factoring its permutation into a sequence of "elementary" permutations (a subset of permutations that is sufficient to construct every other permutation in the group). ...
0
votes
0answers
12 views

Need help with automated data visualization algorithm [on hold]

The user uploads a collection of 100 points as x-y pairs. Output could either be a scatter plot that just plots the points or to show the user the points connected by a straight or curved line. What ...
0
votes
2answers
24 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 ...
7
votes
2answers
1k views

What is a Meta algorithm?

I am currently reading a survey paper on the multiplicative weight update meta-algorithm. I am not quite sure what they mean by "meta-algorithm". Is it simply a general algorithm that can be used for ...
0
votes
2answers
161 views

Algorithm for scheduling unit time tasks with arrival times and deadlines

Suppose we have $n$ tasks to order over $n$ days. Each tasks takes 1 day to be completed. Each task has a start date when the task becomes available and a deadline when the task must be delivered. ...
2
votes
1answer
78 views

Merging rectangles into rectilinear polygon

Having a set of adjacent rectangles, what would be the algorithm that gets the rectilinear polygon wrapping around them?
2
votes
1answer
37 views

Max sum cyclic path of fixed length in matrix

Given a matrix NxM of positive integer values and a starting position (that has value 0), determine the maximum sum path of length K that starts and ends at the aforementioned position. Legal moves ...
1
vote
0answers
61 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 ...
2
votes
1answer
70 views

Help with divide and conquer problem

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 ...
2
votes
1answer
60 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
16 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) ...
20
votes
3answers
14k views

Least number of comparisons needed to sort (order) 5 elements

Find the least number of comparisons needed to sort (order) five elements and devise an algorithm that sorts these elements using this number of comparisons. Solution: There are 5! = 120 possible ...
1
vote
0answers
66 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 ...
2
votes
1answer
42 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 ...
0
votes
1answer
203 views

Create a binary search tree from a sorted array: Space complexity reasoning

Here is the Python code. The solution is fairly common and is seen in most textbooks like 'Cracking the Coding Interview' and 'Element of Programming Interviews'. ...
1
vote
1answer
46 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
53 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$. ...
0
votes
0answers
10 views

Elevator algorithm with external and internal buttons [closed]

I have been asked to supply some pseudo code to implement elevator algorithm Event internal button: the man inside elevator Event ...
4
votes
2answers
79 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 ...
2
votes
0answers
24 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
28 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
34 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. ...
2
votes
1answer
84 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
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
16 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: ...
2
votes
1answer
224 views

Finding the longest path in an undirected node-weighted tree

I have a tree where each node is assigned a weight (a real number that can be positive or negative). I need an algorithm to find a simple path of maximum total weight (that is, a simple path where the ...
0
votes
1answer
43 views

What are possible uses for cross, back and forward edges after the DFS visit?

The depth-first search visit of a graph produces, in some implementations, a labeling of the edges as "Cross", "Back" and "Forward". I know "B" edges can be used to detect cycles. What are other ...
0
votes
0answers
21 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 ...
2
votes
1answer
40 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
27 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)...
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$
17
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
28 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^{...
4
votes
3answers
163 views

Are edges in a minimum spanning tree not heavier than respective edges in another spanning tree?

Let $G$ be an undirected connected weighted graph, and let $T$ be a minimum spanning tree of $G$ with edge weights: $w_1 \le w_2 \le ... \le w_{n-1}$. Now let $T'$ be some other spanning tree of $G$ (...
2
votes
0answers
12 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 ...
4
votes
1answer
38 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
1answer
14 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)$, ...