Questions related to design and analysis of algorithms

learn more… | top users | synonyms (1)

1
vote
1answer
11 views

Polynomial time

I was wondering if there is a polynomial time algorithm to test whether a DFA recognizes a star-closed language ( which is if $A=A^*$). I think that yes, but I do not have an idea to do it.
1
vote
1answer
9 views

Algorithm to determine Strongly Regular Graph(SRG)

I am looking for an algorithm/formula/theorem to determine whether a graph is Strongly Regular Graph(SRG) or not. I have an idea- Let $G = (V,E)$ be a regular graph with $ v$ vertices and degree ...
0
votes
1answer
26 views

Normalizing edge weights and the effect on Dijkstra's algorithm [duplicate]

If I had a graph $G$ with some negative edge weights, clearly Dijkstra's algorithm does not definitely halt, since it might get caught in a negative cycle (shedding infinite weight). However, would ...
1
vote
1answer
28 views

How to state a recurrence that expresses the worst case for good pivots?

The Problem Consider the randomized quicksort algorithm which has expected worst case running time of $\theta(nlogn)$ . With probability $\frac12$ the pivot selected will be between $\frac{n}{4}$ and ...
3
votes
0answers
24 views

Analysis of sorting Algorithm with probably wrong comparator?

It is an interesting question from an Interview, I failed it. An array has n different elements [A1 .. A2 .... An](random order). We have a comparator C, but it has a probability p to return correct ...
1
vote
0answers
26 views

Weighted, Acyclic Graph and Change Weights Problem?

I ran into a question as follows: We have a Code on Weighted, Acyclic Graph G(V, E) with positive and negative edges. we change the weight of this graph with ...
1
vote
1answer
330 views

What are the k characters which make the most complete words?

Given a word list of $N$ words formed from a language of $M$ characters, where each word is composed of $n \geq 1$ not necessarily distinct characters, how can I find the best set of $k<M$ ...
7
votes
1answer
92 views

Recoloring bipartite graphs

Given a bipartite graph $G = (A,B,E)$ where every vertex is colored either red or blue I am trying to minimize the number of blue vertices using the following operation: Choose a vertex $v_a$ in $A$ ...
2
votes
0answers
15 views

The set of all vertices, such that each vertex in the set has a path to exactly $k$ vertices

I need to find algorithms for both undirected and directed graphs, with no assumption on them being connected. Also the algorithms must be $O(V+E)$, where the undirected one should not depend on $k$. ...
1
vote
1answer
41 views

Variation on Insertion Sort

I'm writing insertion sort in scheme, but due to the difficulty of writing it recursively within the constraints of list processing of scheme, I made what seems like an insignificant change to the ...
0
votes
1answer
48 views

Given an amount of sets with numbers, find a set of numbers not including any of the given

Given an amount of sets with numbers (0-20 e.g) , we are asked to find the maximum set of numbers from 0-20 that doesn't include any of the given sets(it can include numbers from a set,but not the ...
1
vote
0answers
22 views

Sequence alignment with one to many characters

I'm trying to align a sequence of characters together, I found that sequence alignment algorithms which use dynamic programming like Needleman-Wunsch or Smith–Waterman only align one character with ...
1
vote
0answers
29 views

Comparison of matrix determinant in less than $O(n^2)$

I was reading this question and I think maybe somebody here could help. This is the idea: Given a matrix $M$ of integers, and a number $d$ is there a way to compare the determinant of $M$ and $d$ in ...
0
votes
1answer
44 views

An algorithm to compute a set of states that satisfy a specific CTL formula

Working through a past exam question and I'm unsure where to start or what form they want the answer in: Define an algorithm that receives as input a finite transition system TS defined over the set ...
0
votes
1answer
8 views

Placing a fixed number of points on a curve to make the finite second derivative constant

I am given a 1D curve $f(x)$ that starts at $a$ and ends at $b$. I have $n$ points I have to place on the curve, and I have to place two points at $a$ and $b$, respectively. Is there a way to place ...
4
votes
1answer
56 views

Algorithm to generate two diffuse, deranged permutations of a multiset at random

Background $\newcommand\ms[1]{\mathsf #1}\def\msD{\ms D}\def\msS{\ms S}\def\mfS{\mathfrak ...
2
votes
3answers
64 views

Can any recursion implementation be written as tail-recursion?

Can any method that uses recursion be written as tail-recursion?
0
votes
0answers
16 views

optimal minimum set cover problem [on hold]

I am implementing optimal set cover problem but I am facing problem. Can anyone help me regarding optimal algorithms related minimum set cover problem such as Linear programming, Primal dual, brute ...
-4
votes
0answers
27 views

Dijkstra's algorithm

can we use dijkstra's algorithm here to find the shortest path from A to H? or use bellman-ford algorithm. i think using dijkstra's algorithm but I am not sure about that.
6
votes
2answers
107 views

Maximize distance between k nodes in a graph

I have an undirected unweighted graph $G$ and I want to select $k$ nodes from $G$ such that they are pairwise as far as possible from each other, in terms of geodesic distance. In other words they ...
1
vote
0answers
18 views

Clock variant of the Second-Chance page-replacement Algorithm vs. standard Second-Chance Algorithm

A sample question for my upcoming Operating Systems exam is: Under which circumstances would the clock variant [of the second-chance algorithm] be preferred over the standard second-chance ...
0
votes
0answers
24 views

Algorithm for scheduling timetable for student management system

I am developing the timetable module for a student management system. I am finding it difficult to design/develop it. It can be assumed that a given teacher is capable of teaching any standard whether ...
4
votes
2answers
69 views

How does one formulate a backtracking algorithm for generating all permutations of n bits

I am new to learning algorithms. I was reading backtracking algorithm for generating all strings for n bits. If I dry run the program I know the program is giving right result. But I didn't understood ...
8
votes
1answer
148 views

What type of algorithms are faster with a quantum computer?

I am a beginning CS student and I am learning algorithms. I heard that even with quantum computers, that general sorting algorithms can never have better than $n\log n$ time. However, I also know that ...
0
votes
1answer
63 views

Does every problem in NP have an exponential time algorithm?

I am not sure that every problem in NP have an exponential time algorithm. Since NP does not mean "not polynomial.", I think the answer is false. But I have no concrete reason about that.
3
votes
0answers
33 views

Complexity of clustering lattice points

[Note] I have completely rewrited the question after Yuval's comments. I hope it makes more sense now! $\newcommand\ZZ{\mathbb Z}$$\newcommand\dist{\operatorname{dist}}$Consider the $d$-dimensional ...
0
votes
1answer
41 views

Algorithm analysis of nested loop [duplicate]

so I have this code: for (int i=1; i < n; i=i*5) for (j=i; j < n; j++) sum = i+j; And I'm wondering, what's the time complexity of this for ...
7
votes
3answers
1k views

Efficient algorithm for this optimization problem? Dynamic programming?

I've created a diagram that depicts what I'm trying to accomplish. Full-size Image In the input sequence, the nodes are as close together as possible. But I want the white nodes to be as close to ...
2
votes
1answer
35 views

A little confusion with the Knapsack problem (a worked example)

I'm going through a worked example on the Knapsack problem: My problem is that I don't understand quite follow the last bulletpoint. Where does the $x_4 = 4/5$ comes from? I know $x_4$ has to be a ...
3
votes
0answers
18 views

Algorithm to find piecewise circular curve around object made of non-overlapping circles

Introduction I have an object which consist of loosely packed, non-overlapping circles, of radius r. Part of such an object is seen below, the object consist of the bold blue circles, and it ...
-1
votes
0answers
5 views

Finding Data Maxima Using Excel / MatLab / Mathematica [closed]

I'm having trouble figuring out a way to analyze some simple data. When graphed, the data I have make a somewhat sinusoidal curve. What I want to do is to find the x-values of the maximum peaks of the ...
3
votes
1answer
35 views

Are there algorithms with non-convex and non-concave computational complexity?

If I am not mistaken, an algorithm that runs in time $\Theta(f(n))$ also runs in $\Theta(f(n) + a\sin(bn))$ where $a,b$ are conveniently chosen constants. Therefore I believe that the computational ...
2
votes
1answer
43 views

TSP polynomial Time [closed]

How can it be proved that TSP cannot be solved in polynomial time ( Please bear that I don't have a hardcore computer science background).
0
votes
0answers
9 views

Effect of mismatches on string matching finite automata

I am contemplating a string matching FA algorithm (not KMP). The complexity of its transition function calculation ie the preprocessing is m(length of pattern )* (the language of the FA) . What effect ...
6
votes
3answers
168 views

Find the minimum range

Given a list of numbers as L, how do you find the minimum value m such that L can be made ...
3
votes
1answer
47 views

What is the worst case running time for an algorithm that combines insertionsort and mergesort?

Suppose that we have an algorithm "combination" that uses insertionsort for $n < 100$ and mergesort for $n \geq 100$. Is the worst case running time of "combination" then $n^2$ or $n\log n$? I was ...
0
votes
0answers
24 views

Matrix array problem [on hold]

Create an algorithm named Moon. This algorithm should take a p by q matrix ...
2
votes
1answer
41 views

If p(n) is a polynomial in n, then is 1/p(n) polynomially bounded?

This is part of a homework exercise. Given is an algorithm that errs with probability $\frac{1}{2}-\frac{1}{p(n)}$ for some polynomial in the input size $n$. I'm trying to prove that a polynomial ...
-4
votes
1answer
80 views

Write an algorithm that finds array elements that sum up to some value [closed]

The following is a pseudo-code named PractOne. It takes a finite list A of real numbers and gives the pair ...
1
vote
1answer
24 views

Number of submatrices with a particular sum- Answer Explantion

I read Evgeny Kluev answer on this and was not able to understand the mechanism. Now let us understand using an example. let us say we have this matrix. ...
1
vote
1answer
19 views

Solving cycle in undirected graph in log space?

Setting Let: $$UCYLE = \mathcal \{ <G> ~:~ G \text{ is an undirected graph that contains a simple cycle}\}.$$ My Solution we show $UCYLE \in L$ by constructing $\mathcal M$ that decides ...
-1
votes
0answers
26 views

Prove correctness of algorithm - how to show the properties

Give an algorithm that finds the MST (maximum spanning tree) of a graph G=(V,E). Prove that the algorithm you gave finds the MST. I tried the following: I applied the Kruskal algorithm, but ...
0
votes
0answers
20 views

Complex 0/1 Backback Problem

Say I have 3 compartments in my backpack: red, green, blue and 3 sets of items: red items, green items and blue items which all have a weight and benefit. I also have a requirement around the total ...
0
votes
0answers
22 views

Proving that a simple algorithm is $\Omega(n^2)$ for all inputs [duplicate]

I am given the following algorithm, which checks whether a given matrix is symmetric: ...
1
vote
2answers
71 views

Reachability matrix in time $O(|V| \cdot |E|)$

Suppose that we are given a directed graph and we want to find out if a vertex $j$ is reachable from another vertex $i$ for all vertex pairs $(i, j)$ in the given graph. Reachable mean that there is a ...
6
votes
1answer
142 views

Optimize binary search on Segment Tree by storing past result

Goal Let $A[n]$ be an arbitrary array of integers of length $n$. Let $S$ be a segment tree, represented by an array of records: each record containing the left and right bounds ($[l,r]$) of the ...
1
vote
1answer
50 views

What sorting algorithm should be used for this array?

I am given an array {1, 2, 3, 5, 4, 6} and I am asked What sorting algorithm might you want to use to sort the given list, and why? Initially I think using ...
1
vote
0answers
29 views

How does a minimal DFA ensure minimal computational cost?

I just went to read wikipedia to check a point on FA minimization, and I read there the following sentence: The minimal DFA ensures minimal computational cost for tasks such as pattern matching. ...
2
votes
1answer
22 views

Partitioning planar graph cycles based on chords

Given a cycle of length > 3 in a planar graph, I'm looking to partition it into 4 sublists of length 2 or more such that: No sublist contains two vertices with a chord between them The last element ...
1
vote
1answer
22 views

The Fundamental and Essential Matrix

Could someone, in plain english, explain the distinction between the fundamental matrix and the essential matrix in multi-view computer vision? How are they different, and how can each be used in ...