Questions related to design and analysis of algorithms

learn more… | top users | synonyms (1)

-2
votes
0answers
9 views

Help with linked list [migrated]

As i have had no formal education with computer science, please pardon if my question seems trivial. I was reading on linked lists, and the only good source i could find was one from stanford ...
-3
votes
1answer
29 views

Linear-time algorithm for solving a set of inequalites

We have a set $A$ of $n$ distinct numbers. We want to determine for all $x,y,z \in A$ whether the following relations hold. $$ x+y>z\qquad x+z>y\qquad y+z>x $$ Anyone could describe ...
2
votes
0answers
19 views

Algorithms that are similar to Dynamic TIme Warping

Dynamic time warping (DTW) is an algorithm in time series analysis for measuring similarity between two temporal sequences which may vary in time or speed. Here are some explanations of DTW: Dynamic ...
3
votes
0answers
79 views

Sorting with gaps

Suppose we have a directory containing $N$ files whose names are numerals, but not necessarily contiguous numerals. Let's say for concreteness that each file contains an email message, each of which ...
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 ...
-5
votes
0answers
38 views

program to print a series which result in zero [on hold]

write a program in c that takes in input any digit N(1<=N<=9)and print all the possible series starting from 1 and ending in N with either "+" or "-" in between the digits so that the resultant ...
4
votes
1answer
53 views

Algorithm to find most nodes in distinct cycles

I am trying to design a program where people trade objects within a fixed set of objects. They offer a single product, and designate a set of products they are willing to accept for that product. ...
-2
votes
1answer
80 views

Sorting when there are only O(log n) many different numbers

We have $n$ integers with lot's of repeated numbers. In this list, the number of distinct elements is $O(\log n)$. What's the best asymptotic number of comparisons for sorting this list? Any idea or ...
-1
votes
1answer
52 views

Board cutting problem

To cut a wooden board, a sawmill charges proportional to the length of the board. The cost of cutting a single board into many smaller boards will thus depend on the order of the cuts. As an example, ...
-2
votes
1answer
32 views

LSD and MSD sorting - which requires fixed length keys?

I am studying these sorts, but it is still unclear to me which one of these two would require fixed length keys?
0
votes
1answer
38 views

Why BFS is source vertex specific? [on hold]

Take a graph $G=(V,E)$ . As we know both DFS and BFS are graph search algorithms . But why the algorithm for BFS is designed in such a way that it does not cares about the vertices that are not ...
1
vote
0answers
43 views

Massively parallel unconstrained minimization; f is a black box

My objective function, f, is complicated and embodies several disparate constraints I want my simulation to optimize simultaneously. So I can't really even assume it's continuous; it is probably ...
0
votes
0answers
30 views

Can the Sieve of Eratosthenes be adapted to find twin primes

The Sieve of Eratosthenes is an algorithm generate the prime numbers, $2,3,5,7,11,13,...$ by drawing a list of numbers crossing out multiples of the smallest number in the list. Is there anyway to ...
0
votes
4answers
148 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
votes
1answer
50 views

Implementability of a (abstract) data structure/type? [closed]

Do people consider the implementability of a (abstract) data structure or a data type, just like people do for implementability/computability of an algorithm? By implementability, I mean if a ...
1
vote
1answer
45 views

What's the difference between Clock and Second Chance Page-Replacement Algorithm?

I know that they both have reference bit, but I only understand the Second Chance but not the Clock Page-Replacement algorithm. could anyone help me understand?
1
vote
2answers
54 views

Fast checking Matrix multiplication in mod 10

I recently faced this problem in a programming contest: Given 3 square matrices N x N of size N up to 1000. All elements in 3 matrices are from 0 to 9. Check if matrix A x B equals to C, mod 10. In ...
1
vote
1answer
35 views

Strictly speaking do the Hoare and Lomuto partitioning algorithms work on the same algorithm: quicksort?

For Hoare's partitioning algorithm quicksort is implemented as such ...
0
votes
1answer
37 views

Connection of “modern” runtimes and number of steps on a Turing machine

Why an evaluation of Turing machine efficiency is equal to the algorithm which is implemented by this machine and vise versa? For example, we can say that efficiency of merge sorting algorithm is ...
1
vote
0answers
22 views

Detect bad acceleration deceleration of car [closed]

I am working on aggressive driving behavior android application. This will be implemented via supervised learning, wrong actions will be recognized and added while driving the car. To check ...
0
votes
1answer
60 views

Can I use breadth-forst search for topological sorting?

Can I use Breadth first Search for finding topological sorting of vertices and strongly connected components in a graph? If yes how can I do that? and If not why not? I tried with a simple acyclic ...
1
vote
1answer
39 views

Bit distance and disruption [duplicate]

Earlier, I asked a question defining disruption in Genetic Algorithms. Given that definition, I'm still confused on how to answer the following question. True or false? For 1-point and 2-point ...
-1
votes
0answers
31 views

testing parallelity/perpendicularity of two 3D vectors of lengths close to zero using dot product [closed]

First of all you may need to be reminded that $ \vec v . \vec w = \left\lVert \vec v \right\rVert \times \left\lVert \vec w \right\rVert \times \cos\theta = (v_x \times w_x+v_y \times w_y+v_z \times ...
7
votes
1answer
78 views

Guessing Number Game

I was solving this question. It is as follows Joe picks an integer from the list $1,2,\cdots,N$ with a probability $p_i$ of picking $i$ for all $1\leq i \leq N$. He then gives Jason $K$ attempts ...
3
votes
0answers
93 views

computing permanent of a 0-1 rectangular matrix

I need to compute the permanent of a 10*100 matrix. All the entries are either 0 or 1. All I know is that I can compute the permanent of all 10*10 submatrices and then sum it to get the desired ...
1
vote
1answer
41 views

Compute sums of all subsets of some words

We have $16$ words of given length, let's say $W_1,...,W_{16}$ and and i want to make an one dimensional matrice that will contain all the possible sums of $W_i$'s, for example: $W_1,W_2,...,W_{16}$ ...
1
vote
1answer
30 views

Algorithm for designing a binary code with predefined distance

Suppose I have a matrix $A$ with its entry $A_{ij}$ denoting some kind of distance between class $i$ and $j$, is there a feasible algorithm for computing a binary coding for all the classes, such that ...
0
votes
1answer
33 views

How to write all $r$-tuples with a certain property in a list [closed]

I have the following question: Let $a,b,c,d$ be four natural numbers with $a \leq b$ and $c\leq d$. I have written a program that produces a list, which has as entries all 2-tuples $(x,y)$ with ...
4
votes
4answers
88 views

Interleaving algorithm for 2 stacks

Suppose I have two stacks $<a_1,a_2,...a_m>$ and $<b_1, b_2,...b_n>$ and a third stack of size $m+n$. I want to have the third stack in the following manner, ...
-1
votes
1answer
104 views

Mininun changes required in a directed graph to make path from 1 to n

i have a directed graph. Basically, i have to find how many edges i need to change to opposite direction to make a path between 1 and n. So, i tried solving it by making the graph undirected and ...
3
votes
0answers
81 views

Maximum local edge connectivity [migrated]

For a simple graph, the local edge connectivity of vertices $x,y$ where $x\neq y$ is $\lambda(x,y)$ and defined as the maximum number of edge disjoint paths from $x$ to $y$. One can find this by a ...
0
votes
0answers
35 views

What is the best approach to implement custom rules on lists of integers? [on hold]

Suppose we have a list of all possible integers ( a custom sample space) like so: S = [200,300,400,500,600,700,800,900,1000]. Using S above, you can create your own subsets like: set1=[200,300] ...
2
votes
2answers
27 views

Algorithm to partially sort list into equal-sized buckets

Suppose I have a large list of numbers that I want to divide into equal-sized buckets so that every bucket contains only larger numbers than buckets to its left. Numbers within each bucket don't need ...
1
vote
0answers
48 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 ...
4
votes
3answers
125 views

counting arithmetic progressions $a, a+r, a+2r$ in a list

I have a large list $L$ of numbers and I need to count instances of elements $a,b,c \in L$ such that $a +c = 2b$. A brute-force approach would be to check all possible triples $(a,b,c)$ and this will ...
1
vote
1answer
54 views

How can we design an efficient warehouse management program?

Assume that we want to develop a warehouse management system, which picks up plastic boxes and stacks them on a pallet. A pallet has a maximum of 5 vertical box stacks and the maximum height of a box ...
4
votes
1answer
122 views

Finding an element in a sorted array with at most three queries to larger elements

Given a sorted array A, we have to find the position of an element m in it. (It is also given that the element exists in the array.) However there is a constraint. Like in a game you have 3 lives. If ...
3
votes
1answer
49 views

Bellman-Ford and zero-distance cycle

Problem statement: Given a graph G(V,E) which is not acyclic and may have negative edge weights (and thus may possibly have negative-length cycles), how does one detect if the graph has a zero-length ...
1
vote
1answer
49 views

Feasible solution existence

I wonder what is the fastest way to check whether the intersection of a set of half-spaces is empty. Right now I'm using a linear programming formulation (with Gurobi as solver) to check if there is ...
2
votes
0answers
76 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
43 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
21 views

What is the Big O of this algorithm? [duplicate]

I'm having trouble working out what the Big O is of this piece of code, any in particular how to analyse it for recursive functions. Could someone explain step by step how to calculate the complexity ...
0
votes
2answers
88 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
vote
1answer
37 views

Algorthm: Given a set of points, width around line, find line to capture maximum points

I want to know if there is an algorithm for this problem. I have a list of points given as (x,y) values and a given distance. I want to draw a line through the set of data points so that the size of ...
5
votes
1answer
108 views

Are there current benchmarks for algorithms solving Travelling Salesman?

I'm researching the travelling salesman problem and looking for data regarding the current state of affairs regarding solutions and performance. So far the only data I've states that the current ...
6
votes
4answers
606 views

Infer number of comets, based upon observations of their periodic visits to Earth

Can we algorithmically infer the number of comets that orbit the Earth, based upon periodic observations of them, if we cannot tell the comets apart? In more detail: The problem There is an ...
3
votes
2answers
93 views

Pick a subgraph that maximizes the total cost of min-spanning tree among all subgraphs of the same size

There is a complete graph $G$ with $n$ vertices and each edge has a distinct weight. Is there an efficient (not necessarily optimal) algorithm to select $k$ vertices from the graph $G$, such that the ...
1
vote
1answer
57 views

Name for class of algorithms preserving accuracy/confidence

I am considering the following class of algorithms: The algorithm has access to some probabilistic oracle (procedure) $f$ in addition to input. The answer of procedure $f$ (we may assume it is ...
2
votes
1answer
29 views

Choice of algorithm for hierarchical clustering for minimizing network communication costs

Suppose I have a large distributed task running on a cluster system where part of the workload is compute bound and part depends on network performance. Data transfer is not completely homogeneous ...
2
votes
2answers
129 views

Is my simplified explaination of the XOR swap correct?

The XOR swap is a well-known in-place algorithm to swap two values, by XOR:ing them bitwise. It goes as follows: a = a ^ b b = a ^ b a = a ^ b Now, I was ...