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
0answers
4 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 &...
0
votes
0answers
11 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 ...
2
votes
0answers
27 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 ...
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 ...
0
votes
0answers
24 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. ...
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
23 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
0answers
27 views

Does the Two Generals problem assume messages are binary?

In considering the description of the Two Generals problem, what I found least intuitive is the common statement of Yes, we will both attack at the agreed-upon time.'' (or at dawn, or at a ...
3
votes
2answers
51 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
58 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 ...
1
vote
2answers
51 views

Divide two strings to form palindrome [on hold]

Given two strings, A and B, of equal length, 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.
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
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) ...
1
vote
0answers
60 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
67 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 ...
1
vote
1answer
45 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$. ...
3
votes
2answers
70 views
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 ...
2
votes
0answers
23 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
27 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. ...
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: ...
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)...
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 ...
0
votes
0answers
27 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
82 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
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 ...
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)$, ...
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
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 ...
16
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
27 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
88 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
19 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
34 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
18 views

Determining the best “approach” for an algorithm [closed]

I am trying to get better at algorithm design and was looking at questions on Leetcode and similar websites/textbooks. I was wondering what are some of the common phrases/semantics that could help ...
0
votes
0answers
60 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
64 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
37 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
44 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
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 ...
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%...
0
votes
0answers
132 views

Programming (java): Algorithm to find first even number [closed]

Before I'll ask my questions, I'd like to give You a few informations about my knowledge, so You might understand my problem better. I am an experienced Java developer, but I never had to go deeper ...
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 ...