Questions related to design and analysis of algorithms

learn more… | top users | synonyms (1)

0
votes
1answer
30 views

What is the min # of moves to sort an array from 1 to n?

Problem: You are required to sort an array with numbers from 1 to n. You can do a "move", which means choosing one element and moving it to any place you want (insert to any place, not swap). Prove ...
-2
votes
1answer
31 views

Determine if DFAs accept any word which contains bb

Let Σ= { a , b , c } . Describe an algorithm that takes as input a deterministic finite automaton M = ( Q , Σ , τ , s , A ) and determines whether or not M accepts a word containing bb (i.e. a word of ...
5
votes
0answers
21 views

Enumerate all non-isomorphic graphs of a certain size

I'd like to enumerate all undirected graphs of size $n$, but I only need one instance of each isomorphism class. In other words, I want to enumerate all non-isomorphic (undirected) graphs on $n$ ...
-1
votes
1answer
31 views

Enumerate all N-bit bitstreams

I am trying to figure out an algorithmic way to generate all bitstreams with $N$ bits . So for example you input 2 and the output will be: 00 01 10 11 I am doing research on data compression and ...
1
vote
0answers
57 views

RMQ with $\sqrt{n}$ space?

I'm asked to design an RMQ data structure (Range Minimum Query) for an array that has $<=\log(n)$ local minimums (a local minimum is an index $i$ such that $A[i-1]>A[i]<A[i+1]$). There are 2 ...
3
votes
2answers
74 views

match an array with a given set of arrays

We have a set of 24 distinct arrays, each array has 36 elements and each element can have one of 13 possible values. Then we're given an array X (this array is certainly part of our set) and we have ...
-1
votes
1answer
37 views

Distributing values of an array into smaller arrays with bounded sums

Take the following array of integers: [60, 45, 30, 45, 45, 5, 60, 45, 30, 30, 45, 60, 60, 45, 30, 30, 60, 30, 30] They need to be sorted into pairs of sub-arrays. The first sub-array in each pair ...
-1
votes
0answers
14 views

Reading an image from same directory? [on hold]

Suppose I have been given an image called in.png in the same directory as my main.cpp. I have to read that image and put it into b i created in the main body. I have been given a class PNG, and the ...
-1
votes
0answers
17 views

complex python problem [on hold]

Write a program that reads n digit number. after reading the number, compute and display the sum of odd positioned digits,multiply all even positioned digits and add the two numbers. I have attempteed ...
-1
votes
0answers
13 views

Simple proof of the polynomial smoothed runtime of k-means?

The k-means algorithm has exponential worst-case runtime but its smoothed runtime can be shown to be polynomial. Is there a simple proof of this?
0
votes
0answers
13 views

Is k-means parallelizable (other than the data parallelism of the distance function computation)

The k-means algorithm is known to be NP-hard. While the distance function computation in the algorithm loop is data parallel, the algorithm is iterative and may become exponential in the number of ...
1
vote
2answers
27 views

Counting inversion using D/C

This is a homework. It looks easy, but not really. A list of integers $a_n$, for every $i<j$, if $a_i>2a_j$, then it is an inversion. Count the inversions in the list, and return the count and ...
1
vote
2answers
84 views

Finding the max XOR of two numbers in an interval: can we do better than quadratic?

Suppose we're given two numbers $l$ and $r$ and that we want to find $\max{(i\oplus j)}$ for $l\le i,\,j\le r$. The naïve algorithm simply checks all possible pairs; for instance in ruby we'd have: ...
2
votes
1answer
15 views

How do I measure the reliability of a confidence value in a predictive algorithm?

Supposing I have some algorithm that is able to provide me with a confidence value for some event occurring. Let's say on day 1 it tells me that there is a 80% chance it will rain, on day 2 it tells ...
35
votes
16answers
4k 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 ...
10
votes
1answer
96 views

Efficient algorithms for vertical visibility problem

During thinking on one problem, I realised that I need to create an efficient algorithm solving the following task: The problem: we are given a two-dimensional square box of side $n$ whose sides are ...
1
vote
1answer
41 views

Finding all partitions of a set s.t. each block contains exactly one subset from a given set of subsets - how hopeless?

Hello and apologies if my question will be too elementary. My background is from arithmetic geometry, but I have been recently faced with certain computational problems of combinatorial nature, where ...
0
votes
1answer
42 views

Propagating node labels upwards in a tree

I am trying to think of an efficient way to synchronize a tree's nodes with the following rules. Consider for instance this tree: so the top of the heap is always ...
0
votes
1answer
53 views

Binary tree traversals reversed

Am I correct in saying that traverse(node): if node is null, return print node traverse(node's right subtree) traverse(node's left subtree) would ...
2
votes
1answer
36 views

Algorithm for approximation with sum or difference of 2 unit fractions

Let $U =\{\frac{1}{n}: n\in \mathbb{N}\} \cup \{-\frac{1}{n}: n\in \mathbb{N}\}$ be the set of positive or negative unit fractions. Given positive integers $m<n \in\mathbb{N}$, how do you find ...
-1
votes
0answers
26 views

Can anyone tell me what is the time complexity of particular code [duplicate]

int fun(int n) { int count = 0; for (int i = n; i > 0; i /= 2) for (int j = 0; j < i; j++) count += 1; return count; } I ...
-2
votes
0answers
47 views

Comparing two gcd algorithms

Consider the two following possible algorithms, gcd1 (a,b) { if b =0 then return a; else return gcd1 (b, a mod b); } ...
0
votes
0answers
29 views

Proof of Asymptotic Fact [duplicate]

I was trying to prove the next exercise 1 It's not look so hard, but with some tries, I couldn't find out a way to show it, I was supposed wrong assumptions. To convince myself if that relation ...
4
votes
0answers
60 views

Rate Pooling Optimization Algorythim

I have thousands of wireless LTE hotspots. Each month I need to assign each hotspot a rate plan. Each hotspot uses some amount of data in a month (represented in megabytes). Each rate plan has some ...
-3
votes
0answers
21 views

Performance difference between quick sort ending at empty subarrays and length-1 subarrays

I'm wondering how much difference an implementation to quicksort that terminates loops at length-0 subarrays has as compared to one that terminates at length-1 subarrays? Any way to quantitatively ...
4
votes
0answers
47 views

Complexity of Pythagorean triples

We define a Pythagorean triple as a triple $\langle a,b,c\rangle$ such that $a,b,c\in \mathbb N$ and $a^2+b^2=c^2$. In order to avoid duplicates, we say that a triple $\langle a,b,c\rangle$ is legit ...
3
votes
1answer
43 views

Optimal way for grouping events

I am creating an event notification system. Each event has a user and a subject, such that, 'user did event to the subject'. Now while presenting these the events need to be grouped. All the events ...
1
vote
1answer
51 views

Divide self-intersecting polygon into simple polygons

My question is similar to question here Divide self-intersecting polygon I have points of self-intersecting polygon, its edges and also I am able to find points where it intersects. I have to divide ...
-2
votes
1answer
89 views

How to calculate $24!$ modulo $107$ with complexity as $O(n)$? [closed]

How to calculate $24!$ modulo $107$ with complexity as $O(n)$? I tried expressing $24!$ as a product of primes but that wasn't doing me much help. Can someone suggest me a better method to solve the ...
-3
votes
1answer
47 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 ...
-4
votes
0answers
31 views

What do you thing will the job market be like for complexity theorists in 5-6 years? [closed]

Is this an active growing field worth getting into? I have been reading stuff like UGC, PCP and spectral graphs and quantum complexity and such topics and I was finding it very exciting. I talked ...
4
votes
3answers
73 views

Most time-optimal parallel algorithms to calculate the determinant and inverse of a matrix

I am writing a numeric library to exploit GPU massive parallelism and one of the implemented primitives is a matrix class. Naturally I require a determinant and inverse function for this class and I ...
-1
votes
0answers
20 views

Worst case scenario perform better than average case for Heap Sort [closed]

I am using Heapsort to sort two different list of numbers List ( random selection of numbers from 1 to 9999 ) List 2 ( descending order of numbers from 9999 to 1 Heapsort algorithm ...
-1
votes
1answer
52 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 ...
1
vote
0answers
34 views

Places to find problems that are complex enough in algorithms [closed]

I have been finding a place having problems where I can start thinking about that is not so simple that the pseudo code can be explained in one or two English sentences. In my opinion, those are ...
1
vote
0answers
81 views

Boyer-Moore with Don't Cares

I have been doing a lot of research into pattern matching algorithms. For some background I am searching a long binary alphabet text consisting of considerably more 0s than 1s. The individual ...
3
votes
1answer
112 views

Minimum distance between start and end by going through must visit points in a maze

So, suppose i have a maze, which has a start point and an end point, marked with Orange and red respectively and my goal is to find the minimum distance between them. The blocked path is represented ...
6
votes
2answers
81 views

Are there ways to automatically (no human testing) measure a $9 \times 9$ Sudoku puzzle's average hardness for a human to solve?

So most resources providing Sudoku puzzles assign a difficulty category to each puzzle, even some I've seen with 15 or more difficulty categories. But what is a good way to assign these difficulty ...
-1
votes
0answers
22 views

Asymptotic runtime of Apriori and Fp Growth

What is the asymptotic runtime of apriori and fp growth? I have been searching from on internet for a week for results but have been unable to find any proper reference.
1
vote
1answer
156 views

Deciding if a finite automata accepts strings of any length

Question is you're given a DFA. Give an algorithm which tells you whether strings of all lengths $n\in \mathbb{N}$ are acceptable or not. What I doing was, I have algorithm to count the number of all ...
2
votes
1answer
24 views

Check whether it is possible to turn one BST into another using only right-rotations

Given two binary search trees T1 and T2, if it is possible to obtain T2 from T1 using only right-rotation, we say that T1 can be right-converted to T2. For example, given three binary search tree T1, ...
-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 ...
-4
votes
1answer
53 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 ...
3
votes
0answers
52 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
86 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 ...
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
91 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
54 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?