Questions about the science and art of determining properties of algorithms, often including correctness, runtime and space usage.
0
votes
0answers
16 views
Asking for help with this Therac 25 bugged code. I don't understand the explanation
Therac 25 is a radiation therapy machine that lead to 3 deaths and 3 injuries in 1980s. That's the worst accidents in history which are caused by software bugs. In 1993, Leveson and Turner did a ...
-1
votes
0answers
19 views
About a program that might help the Windows 7 Operating system [on hold]
I use the Windows 7 Home Edition and one BIG weakness seems to be the Windows Installer or the M.S.I. Installer. 1,000,001 things seem to be able to go wrong with it and I'm not a programmer or a ...
1
vote
0answers
38 views
Influence of edge number and priority-queue implementation on the runtime of Dijkstra
When we try to find the shortest path of a directed weighted graph using Dijkstra’s algorithm, is there a relation between the number of edges/vertices of the graph and the different implementations ...
0
votes
0answers
59 views
stuck on proving the optimality of a greedy algorithm [on hold]
I'm Ph.D. student doing research in wireless networks. My past projects are more oriented to systems than theory. For my current project, I devised a greedy algorithm for an optimization problem. ...
0
votes
0answers
34 views
Ranking in complete binary trees
I have a binary tree, the node has two subtrees, every node except the the leaves, has 2 children and all the leaves are at the same level.
I want to know the worst and best case complexities when I ...
0
votes
0answers
24 views
analyzing moving pseudorandom sieve algorithm
the following is a rough simpification or "toy" version/ abstraction/ model (but still quite nontrivial) for/ inspired by a famous open math problem (which for now will remain nameless & may be ...
0
votes
1answer
38 views
Maximum value a variable can hold without documentation [closed]
Suppose we work with some particular programming language (like C++) on some particular computer. Furthermore, we want to know which values are minimum and maximum for some particular numeric data ...
6
votes
1answer
60 views
Etymology of time and space “complexity”
The word choice of "complexity" in analysis of algorithms to describe temporal and spatial resource requirements has always struct me as an odd one. These are certainly useful and meaningful concepts. ...
-5
votes
0answers
18 views
Proving the correctness of Fibonacci by induction when using arrays [closed]
f(n):
A = [0, 1]
for i in range(2,n+1): # from 2 to n
A.append( A[i-1]+L[i-2] )
// invariant: last element of A is A[i]
return A[i]
prove the invariant.
...
0
votes
1answer
16 views
Understanding when to count key comparisons
I understand that for something like Linear search, this would be the key comparison:
if(itemToFind == a[i])
return i;
If I put this method into another ...
0
votes
1answer
26 views
Comparing Big O Complexity [duplicate]
I'm trying to compare two functions, such as f(n)=n^n and g(n)=n^10^10. I'm unsure if f(n) is O(g(n)) or vise-vera where g(n) is O(f(n)). From my understanding, n^n can be worse than n! and although ...
0
votes
2answers
69 views
How to show that this algorithm for evaluating polynomials works?
I'm having trouble showing how to solve this problem in particular the part where it asks "To Show that the following pseudo-code fragment finds the value of the polynomial..."
How do I exactly show ...
3
votes
0answers
18 views
Pruned FFT runtime
Pruned fast Fourier transforms compute only a specified subset of the result indices in faster time, although sometimes with a slower implementation constant (because FFT is generally so optimized). ...
0
votes
1answer
40 views
Showing that tournament sort requrires O(n log n) comparisons
I wish I could think of a better way to word my question. Maybe some one here could offer s suggestion for that, as well.
On to my question. Before I do, this is a class question that has been asked, ...
2
votes
1answer
35 views
Why is Ibarra Kim for 0/1 knapsack an fully polynomial time approximation scheme (FPTAS)?
According to one of my CS lectures, there is an fully polynomial time approximation scheme for the 0/1 Knapsack problem. A first version was developed by Ibarra and Kim, but there are several improved ...
27
votes
3answers
5k views
Why is binary search faster than ternary search?
Searching an array of $N$ elements using binary search takes, in the worst case $\log_2 N$ iterations because, at each step we trim half of our search space.
If, instead, we used 'ternary search', ...
1
vote
1answer
40 views
What Can We Say Complexity of Solving the Weighted Pool Ball Problem with a Variable Scale?
Background:
The pool ball weighing problem is a classic CS question thrown at students, typically to demonstrate a binary search (alternative to ripping phonebooks in half).
Pool Ball Problem: Given ...
-1
votes
1answer
30 views
Proving number of calls made in cut-rod algorithm [duplicate]
I was reading dynamic programming chapter from famous book Introduction To Algorithm
In rod cutting problem it gives simple algorithm as follows:
...
1
vote
1answer
63 views
Creating a binomial heap from an array in �?(n) time
I'm studying binomial heaps. A book tells me that insertion of a node to a binomial heap take $\Theta(\log n)$ time. So given an array of $n$ elements it would take $\Theta(n \log n)$ time to convert ...
41
votes
11answers
5k views
How to fool the “try some test cases” heuristic: Algorithms that appear correct, but are actually incorrect
To try to test whether an algorithm for some problem is correct, the usual starting point is to try running the algorithm by hand on a number of simple test cases -- try it on a few example problem ...
-2
votes
0answers
30 views
Writing recurrencies for run time? [duplicate]
Given a function;
derp( x, n )
if( n == 0 )
return 1;
if( n % 2 == 0 )
return derp( x^2, n/2 );
return x * derp( x^2, (n - 1) / 2);
a) I ...
-3
votes
1answer
56 views
Probabilty that quicksort partition creates an imbalanced partition
I have come across this question:
Let 0<α<.5 be some constant (independent of the input array length n). Recall the Partition subroutine employed by the QuickSort algorithm, as explained in ...
-1
votes
1answer
55 views
Quick Sort Algorithm When Partition is Constant Time
I ran into a question about Quick Sort Algorithm.
Suppose in Quick Sort, Partition procedure take C times, (need constant time). if we use random data as input, what is the order (time complexity) of ...
0
votes
0answers
20 views
Programming and evaluating sorting algorithms based on its complexity [duplicate]
I need to program and evaluate two sorting algorithms: insertion sort and merge sort
I know that the complexity of insertion sort is O(n^2) and for the merge sort is O(n·log n)
In this case I have a ...
0
votes
0answers
19 views
How to conduct time complexity analysis for an implemented algorithm [duplicate]
Main task
In my bachelor degree's thesis I've developed an algorithm for recommender systems which uses personalized PageRank with some particular features as nodes.
In the recommender systems' ...
1
vote
2answers
44 views
Why comparison is dominant time consumption for comparison-based sorting algorithms? [duplicate]
Comparison-based sorting algorithms does a number of different operations to accomplish the sorting, why comparisons are the dominant time consumption? While I understand the standard analyses of ...
0
votes
1answer
39 views
tightest upper bound on binary search tree insertion? [closed]
The upper bound on the runtime of binary search tree insertion algorithm is O(n) which is if it is not balanced
What will be the tighter upper bound on this,will it become O(logn)
I have read that ...
0
votes
0answers
10 views
How to calculate the complexity of Uniform Binary Search algorithm [duplicate]
I was studying the Uniform Binary Search algorithm authored by Donald Knuth which is an optimization of the classic Binary Search algorithm. Can someone explain the complexity analysis for Uniform ...
-1
votes
4answers
201 views
Proving Quicksort has a worst case of O(n²)
I am sorting the following list of numbers which is in descending order.
I am using QuickSort to sort and it is known that the worst case running time of QuickSort is $O(n^2)$
...
1
vote
1answer
84 views
Space complexity analysis of binary recursive sum algorithm
I was reading page 147 of Goodrich and Tamassia, Data Structures and Algorithms in Java, 3rd Ed. (Google books).
It gives example of linear sum algorithm which uses linear recursion to calculate sum ...
-1
votes
1answer
73 views
How the below program is taking O(n!) time? [closed]
The complexity of the below program is given to be O(n!)
...
5
votes
2answers
77 views
Choosing error rates for probabilistic algorithms
Probabilistic algorithms often have a parameter that allows one to tune the error rate, typically by running the algorithm repeatedly. This often gives an error rate of something like $2^{-k}$ for $k$ ...
3
votes
0answers
29 views
Monograph or survey paper on smoothed analysis of algorithms
The paper by Spielman and Teng, Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time (JACM 51(3):385–463, 2004), won a Gödel award in 2008.
Since then, has ...
1
vote
0answers
49 views
How come computer science books are so relaxed about specifying which set variables/values belong too? [closed]
How come computer science books are so relaxed about specifying which set variables/values belong too ?
I've read several books on algorithms like CLRS's Introduction to Algorithms, Sedgewick's ...
0
votes
1answer
40 views
If x operations cost O(x) amortized then how much xy operations cost?
True or False?
Say some data structure can perform $x$ operations in amortized $O(x)$ time.
Then for a big enough $y$ it can perform $xy$ operations in worst case $O(xy)$ time.
My attempt:
$x$ ...
3
votes
1answer
109 views
How to sort using $\texttt{SQRTSORT}$ as a subroutine which sorts $\sqrt{n}$ of consecutive elements?
I am teaching myself algorithms with the online lecture notes by Jeff Erickson and fails to solve the following problem (Problem 21 of Lecture 1).
(a) Describe an algorithm that sorts an input ...
4
votes
1answer
48 views
Optimal Algorithm for Finding Maximal Number of Colinear Points
Given a set of $n$ point in a plane, find the maximal number of colinear points (the points residing on the same straight line).
The crudest algorithm is to compute the slope and intercept of each ...
3
votes
0answers
102 views
Complexity of a naive algorithm for finding the longest Fibonacci substring
Given two symbols $\text{a}$ and $\text{b}$, let's define the $k$-th Fibonacci string as follows:
$$ F(k) = \begin{cases} \text{b} &\mbox{if } k = 0 \\
\text{a} &\mbox{if } k = 1 \\
F(k-1) ...
0
votes
2answers
96 views
Check if an array is a substring of another array
Given two sequences $A$ and $B$,
we want to check if $A$ is a subsequence of $B$ where the elements of $A$ appear in $B$ consecutively and in the same order.
Example 1.
input: $A = (4 , 6 , -5), B ...
-1
votes
1answer
35 views
difference between multilayer perceptron and linear regression
What is the difference between multilayer perceptron and linear regression classifier.
I am trying to learn a model with numerical attributes, and predict a numerical value.
Thanks
1
vote
1answer
56 views
Understanding Property Testing with a toy example
I am newbie with this property testing and I am trying to understand it with a few examples. I first dealt with a toy example.
I did not understand the first step of the test in the following slide. ...
0
votes
1answer
27 views
Hashing and number of comparisons [duplicate]
Say, I want to put N objects into a hash table. How do I figure out how big the size of the table needs to be to have K comparisons on average when the table is: half full? three quarters full? all ...
-1
votes
1answer
39 views
How to find the run time of this algorithm to find if a binary tree is balanced?
This is the algorithm
...
2
votes
2answers
114 views
Where does the lg(lg(N)) factor come from in Schönhage–Strassen's run time?
According to page 53 of Modern Computer Arithmetic (pdf), all of the steps in the Schönhage–Strassen Algorithm cost $O(N \cdot lg(N))$ except for the recursion step which ends up costing $O(N\cdot ...
7
votes
2answers
106 views
Why is the transform in Schönhage–Strassen's multiplication algorithm cheap?
The Schönhage–Strassen multiplication algorithm works by turning multiplications of size $N$ into many multiplications of size $lg(N)$ with a number-theoretic transform, and recursing. At least I ...
1
vote
1answer
35 views
Runtime analysis of sorting an array with known number of inversions
I'm having difficulties with analyzing the worst-case runtime of this following case:
I'm given an array that has $n$ natural numbers. Out of all $\binom{n}{2} = \frac{n(n-1)}{2}$ possible pairs ...
3
votes
1answer
61 views
Computing the complement of a set
Suppose I have a set $A$ of elements in $\{1, \ldots, n\}$, given as an unordered list.
I would like to compute the complement of $A$, i.e., I would like to produce an unordered list of entries in ...
4
votes
1answer
147 views
Complexity of Hopcroft-Karp
I have a rather basic question about the number of operations taken by the Hopcroft-Karp algorithm for finding a maximum matching in a bipartite graph. It is commonly reported as $O(m \sqrt{n})$ where ...
3
votes
1answer
106 views
Master Method to solve recurrences is 'a' related to 'b'?
The master method allows us to solve certain recurrences of the form
$$T(n) = aT(n/b)+f(n)\,,$$
where $a\ge1$ and $b>1$ are constants and $f(n)$ is a positive function with some further ...
1
vote
2answers
69 views
Don't understand one step for AVL tree height log n proof
I came across a proof that the an AVL tree has O(log n) height and there's one step which I do not understand.
Let $N_h$ represent minimum number of nodes that can form an AVL tree of height h. Since ...
