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.

Filter by
Sorted by
Tagged with
3
votes
0answers
36 views

Hardness of an instance of a problem independent of algorithms?

The paper “Where the really hard problems are” (https://www.ijcai.org/Proceedings/91-1/Papers/052.pdf) and others that cite it provide evidence that lots of algorithms for many NP complete problems (...
1
vote
3answers
44 views

Is $n \log n$ in $O(n^{1.46-\varepsilon})$?

I am trying to figure out the solution of the recurrence relation $$T(n) = 5T(n/3) + n \log n$$ using the Master Method. I am guessing that $f(n) = O(n^{1.46 - \varepsilon})$, but I am confused in the ...
-2
votes
0answers
67 views

Use magic-pivot as a black-box to obtain a deterministic quick-sort algorithm with worst-case runningtime of O(nlogn)

Suppose we have an array A[1 :n] of n distinct numbers. For any element A[i], we define the rank of A[i], denoted by rank (A[i]), as the number of elements in A that are strictly smaller than A[i] ...
0
votes
2answers
18 views

Sorting an interval

Given that array has $k$ elements (all distributed uniformly). Its length is exactly $3$ somewhere in $[0, k)$. For example, if $k=100$ then, we have $100$ numbers and they can be in $[10,13)$, but ...
3
votes
1answer
59 views

Justifying a claim in the proof of the master theorem

I am trying to understand the proof of the master theorem and I came up with my own proof for why (4.23) is true. My argument is as follows: Claim: $g(n)=O\left(\sum_{i=0}^{\log_{b}(n)-1}a^i(n/b^i)^{\...
-1
votes
0answers
33 views

Assignment of Nodes to Multiple Queues

You are given $n$ customers at $n$ nodes and each node is at a variable distance away from all queues. Also each customer is processed in a constant amount of time $c$ when it is in a queue. Assuming ...
-2
votes
0answers
81 views

Why do delta x is multiplied in bresenhem line drawing algorithm

In derivation of bresenhem line generation algorithm( https://getsetcg.blogspot.com/2018/10/bresenham-line-drawing-derivation.html?m=1 ) why do they multiplied delta x or in some they use dx to ...
0
votes
0answers
77 views

$O(n)$ algorithm to find a sequence of 3 or n tennis players with ratings in decreasing/increasing order [closed]

This problem is a follow up from this. At a certain (unrealistic) event, we have infinitely many tennis players lined up who are conveniently numbered $(P_1,P_2, \cdots)$. Each player has a certain ...
0
votes
0answers
14 views
1
vote
1answer
28 views

Determine saving moves for a checked king

In my chess code I explore the whole tree of possible movements to find saving moves for a checked king. That is, for every one of the checked king's side pieces I search their whole tree of moves and ...
0
votes
2answers
77 views

Average case running time of quick sort

How to show that the quick-sort algorithm runs in $O(n^2)$ time on average ? Because on average, the expected running time is in $O(n\log n)$. The algorithm should not be in exponential time.
1
vote
1answer
29 views

What is a “negative function” withing algorithms?

I am currently studying the book 3rd edition CLRS Algorithms textbook, Chapter 3. I had the exact same question as this post but I have one more question now: What is a negative function? These ...
1
vote
0answers
69 views

Covering Variation of Longest Common Substring

Given three binary strings, find the maximum possible length of a contiguous block of 1's formed by shifting and overlapping the strings. This may be interpreted as finding the maximum window size $k$...
2
votes
0answers
54 views

What algorithm to use for substractive machining RT simulation?

For a CAM (Computer Aided Manufacturing) software, and more specifically, for the simulation of the subtractive manufacturing, I would like to understand how to design the representation. In ...
2
votes
0answers
28 views

Relationship between proof and algorithm of Ramsey's Theorem

The following is a problem statement from "Introduction to Theory of Computation" Chapter 0 Problem 0.14: Let $G$ be a graph. A clique in $G$ is a subgraph in which every two nodes are ...
1
vote
0answers
172 views

Total running time expressed in O notation of a word ladder program all words same length

I am trying to figure out a big O expression for the running time given $V,E,F$ for a word ladder or word chain program that I have written in Java. I am using undirected graphs with BFS. What is ...
0
votes
0answers
20 views

Empirical (Computational) Analysis

how to write a program that display the total running time of a given algorithm based on different situations such as processor speed, input size, processor load, and software environment?
0
votes
2answers
40 views

Insertion sort on small arrays in Merge Sort

Quick question on the wording of the question from CLRS Ch2 Problems. The question goes as follows: Although merge sort runs in $\Theta(n\lg n)$ worst-case time and insertion sort runs in $\Theta(n^2)...
1
vote
1answer
40 views

Solving the recurrence formula $T(n) = 3T(n/2)+n^2$

What is the solution of the following recurrence? $$ T(n) = 3T(n/2) + n^2, \quad T(1) = 0. $$ I cannot use the master theorem since I need to know the exact final expression, not just it's big O, ...
0
votes
0answers
28 views

Gale-Shapley Stable matching where one man's preference list changes

Given $n>1$ women and men. Let $M$ be the stable matching given by the Gale-Shapley algorithm with men proposing. Is there a stable matching instance such that: changing one man's preference list ...
1
vote
1answer
34 views

Loop invariance insertion sort algorithm

I have the following pseudo code for a insertion sort algorithm ...
1
vote
0answers
72 views

Prove the correctness of divide algorithm

This is the pseudocode for the algorithm: function divide($y,z$) comment Return $q,r \in \mathbf{N}$ such that $y=qz+r$ and $r<z$ where $y,z \in \mathbf{N} $ $r:=y$, $q:=0$, $w:=z$; while $w \...
0
votes
0answers
18 views

I need good book about algorithms, which explains recursion, backtracking and depth first recursion for beginners [duplicate]

I'm learning programming, Python 3 in particular, and I have a good book "Beginning Python - From Novice to Professional" by Magnus Lie Hetland, but the book doesn't explain algorithms at ...
1
vote
1answer
52 views

Algorithm to check that one sum is less than another

Suppose that we have two sums: a1+a2+...+an, b1+b2+...+bm We can perform only two binary operations on operands of these sums: lt (less than) eq (equal) These operations can return 3 possible ...
1
vote
1answer
49 views

Partitioning list into two parts of almost equal sum

I was given this problem in class, and I have no idea how to solve it. The problem is: "Given a list of positive integers, divide the numbers into 2 groups such that the difference between the ...
1
vote
0answers
68 views

Multiplication algorithm I wrote - slower than I expected

Recently I thought of an algorithm for multiplication and decided to stop dreaming and start writing on paper my ideas, and even implement this to code (in this case - Python 3.9.1). I do not know if ...
1
vote
1answer
35 views

Proving big-theta complexity with constants in $f(n)$

I am working through a problem in which I have to prove that a particular $f(n) = \Theta(g(n))$. I know that for this to be true there need to exist positive constants $c_1$, $c_2$, and $n_0$ such ...
0
votes
1answer
34 views

Create Shortest Path tree for every node after Floyd Warshall in O(nm)

Right now I am stuck with the problem, how all shortest path trees can be created in O(n*m) given G = (V,E,c) with negative and positive costs without negative cycles and n =|V| m = |E| after ...
1
vote
1answer
66 views

What happens to the running time of an $O(n \ln n)$ algorithm if you double $n$?

Problem: Suppose the running time of a certain algorithm is $O(n \ln n)$. We happens to the running time of the algorithm if $n$ doubles. Answer: Let $R_1$ be the running time of the algorithm when ...
1
vote
1answer
68 views

Proof of algorithm correctness

I am studying about algorithm correctness and have enctountered this problem. ...
0
votes
0answers
23 views

Test data for tasks that communicate over network

I am working on a load balancer that schedules tasks that communicate over network. I want to test its performance, but I'm struggling to find test data for it. Currently I try to extract relevant ...
0
votes
0answers
20 views

Resources on DS and algos

I am new to this forum as I want to explore data structures and algorithms in depth. I want to know from experts here what books or other resources would be best for someone like me who can be ...
0
votes
0answers
13 views

Looking for a evolution/timeline algorithm

I am trying to draw a presentable timeline and I am doing some research about available algorithms al Here are the timelines of interest I already found a great article by Bill Mill Drawing ...
1
vote
0answers
16 views

Equally optimal nodes during minimax with alpha-beta pruning

Alpha-beta pruning is an optimization for minimax that reduces the number of nodes visited without changing the final result. However, both minimax and alpha-beta only return the optimal node value (...
5
votes
0answers
78 views

Scheduling tasks on a graph with assistance

This is a follow-up to a question that I recently posted here: Completing tasks on a graph. In that question, I posted the following: Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. ...
1
vote
1answer
16 views

Tips on speeding up hierarchical linkage clustering algorithm

I implemented a hierarchical linkage algorithm for a set of 5,000 points. Each point is defined with a longitude and a latitude. I read about this algorithm here. These are the steps: Compute ...
-2
votes
1answer
40 views

Condition in the Dependent Loops

I'm stuck with nested for loops that are dependent on the previous loop: for (i=1; i<=n; i++) for (j=1; j<=i; j++) x = x+1 the part that is confusing ...
0
votes
0answers
14 views

How to do -8 x -8 in a 4 bit booth multiplier?

In the general case of an n bit booth multiplier, the maximum negative value is -2n-1. So with 4 bits we can represent -8 x -8 (M=1000, Q=1000). Now if we follow Booth's algorithm for multiplying n-...
0
votes
1answer
39 views

AVL-tree insertion complexity proof

I tried to figure out the proof of insertion operation in AVL-tree is O(log n), but I do not know how. I also tried to find it somewhere on the Internet, but I could not find any good results. Do you ...
1
vote
0answers
122 views

Minimum Degree Spanning Tree Without Restricting Vertices Searched [closed]

I am currently self studying approximation algorithms from The Design of Approximation Algorithms (Williamson and Schmoys; page 50 here), specifically the minimum-degree spanning trees (MDST) problem. ...
1
vote
2answers
35 views

Maximum matching for general graph

I am studying the maximum matching problem and I was trying to understand why the classical augmenting path algorithm does not work for the general graph (i.e. for non bipartite graph) and you must ...
0
votes
2answers
48 views

Need help finding/writing an algorithm to reassign items to groups with minimal changes

I have some users in groups, like this (groups are letters, users are numbers): { a: [1, 2, 3], b: [4], c: [5], d: [6], e: [7, 8, 9, 10] } I receive a ...
1
vote
2answers
63 views

What mathematical guarantees gives alpha-beta pruning?

In the alpha-beta pruning version of the minimax algorithm, when one evaluates a state p with $\alpha$ and $\beta$ cutoff and gets a ...
0
votes
0answers
35 views

Having trouble understanding Red-Black trees

Exam question: Draw the Red Black Tree that results from inserting the following values in the given order: [10, 20, 30, 4, 5, 50] Draw the red connections with a dotted line and the black ones with ...
1
vote
0answers
21 views

What algorithm for feedback control to maintain heart rate

I am writing an application that will maintain heart rate within a specified range by adjusting the resistance on a turbo trainer. I could cobble together something that would gradually increase ...
1
vote
1answer
61 views

Which data structure can be used to determine most experienced person in a shift?

Problem Statement: There are $n$ hours in a day and you have $w$ workers. For each worker $i$ you will be given $x_i$ (work experience), $s_i$ (shift start time) and $e_i$ (shift end time) on a ...
1
vote
1answer
24 views

Sum of products over k-permutations

Let $A$ be a matrix of size $K \times N$, $K \leq N$. Let $n_1...n_K$ denote a $K$-permutation of integers $1...N$ (understood as a unique assignment of a column to every row in the matrix). How to ...
1
vote
2answers
39 views

Selecting connected subgraph that exceeds value c, with least possible weight

Given a graph $G$ where each node has a value $c$ and weight $w$, I want to select a connected subgraph $V^*$, such that, Sum of all values in $V^*$ crosses threshold $t$. Sum of all weights(say $w^*...
1
vote
0answers
22 views

Finding s-t min-cut of undirected graph

Given an undirected graph with non-negative edge weights, and two vertices $s,t$ in the graph. I would like to find the minimal cut such that $s$ and $t$ are on different sides of the cut. For example ...
1
vote
0answers
28 views

Equivalence of two approximation algorithms for min Steiner tree

I learned two approximation algorithms for the min Steiner tree: The first algorithm: 1- Compute the metric closure G' of G. 2- Compute a min spanning tree T' of G' 3- Construct the union U of the ...