Questions related to design and analysis of algorithms

learn more… | top users | synonyms (1)

0
votes
0answers
17 views

What are some approaches to solve these classes of problems efficiently

Good day, Please consider the following problem: 3 friends named Alice, Bob and Cindy have 3 food items (cheese, tomato, bread) in the fridge. Each person has a particular numerical preference ...
-2
votes
1answer
24 views

Why is Hamiltonian Path and graph coloring np complete and shortest path p when the former can also be solved using DFS recursively?

NP is a complexity class that represents the set of all decision problems for which the instances where the answer is "yes" have proofs that can be verified in polynomial time. But hamiltonian path ...
-2
votes
0answers
18 views

Find orientation graph of undirected graph that mimimizes absolute difference of in-degree and out degree

Here's a question from our uni's ICPC programming competition selections. I'm stating it in simpler terms here. Given an undirected graph, orient the edges of the graph in such a manner that the ...
0
votes
0answers
18 views

Generation of chords through a computer program [on hold]

This question is about generating chords through a computer program. Let us say we have generated C, E and G notes using a program. Now if we generate a new note by simply adding these 3 notes the ...
0
votes
0answers
23 views

Knuth Yao DP Speedup - Cutting Sticks

There's a problem called Cutting Sticks - we start with one stick and n points where it needs to be cut. Cutting a stick costs the length of that stick. Of course, we want to minimize the toal cost. ...
1
vote
1answer
24 views

Project to nearest point in convex polytope

Is there a reasonably efficient algorithm for the following task? Input: a point $x \in \mathbb{R}^d$; a convex polytope $\mathcal{C} \subseteq \mathbb{R}^d$ Find: a point $y \in \mathcal{C}$ that is ...
1
vote
0answers
25 views

calculate minimum wrapping surface area required for packing boxes

I can't get this question out of mind and can't come up with a algorithm to solve this Problem Given a set of N boxes, all of which have identical w x l x h dimensions, print the minimum ...
5
votes
0answers
47 views

Repeated point in polygon: preprocessing complexity given logarithmic query time?

I am interested in the repeated point in polygon problem, where one is given a polygon in a preprocessing phase and in the online phase, one is asked whether a point is in that polygon. The polygon is ...
-1
votes
1answer
31 views

A max-even subset problem

I want to know if there is any polynomial algorithm for the problem, or any NP-completeness result. Given a set $S$ and $m$ subsets $C_1, \dots, C_m$ of $S$, we want to find a non-empty set $X\...
0
votes
1answer
77 views

Cluster Edge Deletion on 2-trees

Definitions: Cluster Edge Deletion problem is a graph modification problem, in which we want to remove the minimum number of edges such that the resulting graph does not contain a $P_3$ as an induced ...
0
votes
0answers
42 views

Complexity of reductions of NP-complete problems [on hold]

Is there list of best known/possible algorithms (with minimal Big-O) for reductions of some of NP-complete problems to some other? If no, can you together make such list?
1
vote
3answers
40 views

More efficient vertex-labelling algorithm than BFS?

I am using the C++ boost library implementation of the push relabel algorithm to solve a max-flow problem. The output from that algorithm is a residual graph and in order to find the min-cut of my ...
2
votes
2answers
90 views

Finding perfect matchings with as few database queries as possible

I am trying to research a problem similar to the stable matching problem with a few different rules. The problem is as follows: There are an equal number of men and women. Each man has a perfect ...
3
votes
0answers
47 views

Maximizing pruned branches in an alpha-beta tree

Preliminary After doing some searches of similar questions posted here and elsewhere, i feel like this is the right place to inquire about, now let's get through some boring main notations... A ...
0
votes
0answers
77 views

How to choose between UC and PL when using the DPLL algorithm?

We know DPLL algorithm is backtracking + unit propagation + pure literal rule. I have an example. There is one example to solve following Satisfiability problem with DPLL. if assign of "0" to ...
1
vote
2answers
40 views

Describe an algorithm for painting cards in the following game

It's my first question out here, so please don't judge me too strictly. I heard of the following game: there's set of cards with different set of objects (but the same number of them on every card) ...
0
votes
0answers
18 views

What are some quadratic run time tasks (algorithms)? [duplicate]

Are there problems, for which best algorithms have worst run time O(input_length^2) and it is proven, that this worst time cannot be substantially improved (better algorithms do not exist). EDIT: ...
-4
votes
1answer
139 views

Algorithm to find liars and truthtellers

This is the exercise 2.18 from Introduction to Bioalgoritms of Neil Jones. It says: We have a mix of 100 participants: some are honest while others are not. The honest ones always tell the truth, ...
3
votes
1answer
107 views

Meaning behind 1/ϵ in FPTAS

I am currently learning about FPTAS and PTAS but do not understand what the definition of FPTAS. A fully polynomial time approximation scheme (FPTAS) for problem $X$ is an approximation scheme ...
-1
votes
1answer
70 views

Cost Minimizing

A man has to travel for given number of days by bus. He can buy either: $1$ day ticket for $2Rs$ (valid for 1 day) $7$ days ticket for $7Rs$ (valid for 7 consecutive days) $30$ days ticket for $25Rs$...
2
votes
2answers
88 views

Dijkstra with bitwise OR of edge costs

Given a graph $G$ where loops and multiple edges are allowed. A path {$e_1, e_2, ..., e_k$} (a sequence of edges) has a cost $$ cost = e_1 | e_2 |...|e_k$$ where $|$ is the bitwise OR. Assume for all ...
3
votes
1answer
33 views

Generalized sorting algorithm on partially ordered set generated by a relation

Assume we have a finite set $X$ of elements and any relation $\preceq$ on $X$. Such a relation may or may not generate a reflexive transitive anti-symmetric relation $\leq$ on $X$ (a partial order). ...
12
votes
2answers
229 views

Is there any study or theory behind combining binary search and interpolation search?

I just read Can this algorithm still be considered a Binary Search algorithm? and recalled that a few years back I wrote an indexer/search for log files to find log entries in large plain text files ...
-4
votes
1answer
36 views

python, learn from users erros// multiple choice quiz [closed]

I am making a multiple choice quiz however I am finding difficulty on how to impletement a machine learning algrithm of somesort where by it can see which questions the user gets wrong and make a ...
3
votes
2answers
49 views

How to match two sets of points based on the closeset distance?

I have a set of points (tiny triangles) $K=\{1,2,\ldots, k\}$ and a set points (tiny circles) $N=\{1,2,\ldots, n\}$ and a matrix of positive real values $\mathbf{D}=\left[d_{ij}\right]$ for all $i\in ...
1
vote
2answers
36 views

Community detection in weighted directed graphs for fixed number of communities

I have a weighted directed graph $G=(V,E)$ with positive weights. Say these vertices represent cities and the weight $w : V_1 \rightarrow V_2$ represents number of students moving into other cities ...
11
votes
2answers
2k views

Can this algorithm still be considered a Binary Search algorithm?

While doing the second code kata (which asks you to implement a binary search algorithm five times, each time with a different method), I've come up with a slightly different solution which works as ...
2
votes
1answer
46 views

Equality of cardinality of maximum matching and minimum vertex cover in general

I'm preparing for exam and I came across this problem: We say that a graph is König's graph when the sizes of its minimum vertex cover and maximum matching are equal. Find a polynomial time ...
2
votes
1answer
227 views

Is this probability distribution data structure already discovered?

Problem formulation I have implemented an interesting probability distribution data structure: having $n$ elements $a_1, a_2, \dots, a_n$ in the data structure with respective positive weights $w_1, ...
2
votes
3answers
87 views

Why do we use multiple data structures? [duplicate]

I'm studying elementary data structures like Linked List, Doubly Linked List and Binary Trees like Binary Search Trees. Both runs in worst case O(n) in the same operations, so why don't we use only ...
0
votes
2answers
26 views

Is there a standard recently-used algorithm based on time and usage count?

Everyone is familiar with most recently used files lists in software and in OSs like Windows. Some programs just sort by time. I've always been fairly annoyed at this. Others like Windows take usage ...
4
votes
1answer
41 views

Two recurrences for the change-making problem with repetition

The change-making problem with unbounded repetition is: Input: Unlimited quantities of coins with values $x_1, \ldots, x_n$; and an amount $v$. Output: Can the given $v$ amount of money be ...
-3
votes
0answers
28 views

What is the amortized time complexity of inserting an element to this heap?

Assume you implement a heap using an array and each time the array is full, you copy it to an array double its size. What is the amortized time complexity (for the worst case) of inserting elements ...
3
votes
0answers
41 views

Orient edges in a mixed graph to minimize the critical path

A mixed graph is a graph that has directed and undirected edges. Is there an efficient algorithm that allows the orientation of undirected edges in a mixed graph in such a way that no cycle is ...
2
votes
2answers
129 views

Computing maximum-cost subtree that uses at most k edges

I'm looking for an efficient algorithm for the following problem: Input: a binary, complete tree with a cost on each edge, an integer $k$ Output: the maximum-cost subtree containing $\le k$ edges ...
2
votes
1answer
45 views

Why isn't a binary counter used for generating $k$-combinations?

I have been looking at algorithms that allow you to generate $k$-combinations of a given string. My question is that why isn't the algorithm used to generate power sets used to generate the ...
3
votes
1answer
40 views

Single-source shortest path algorithm for graphs representing stacked behavior

I am trying to compute a single-source shortest path in an interprocedural control flow graph (iCFG). That is a directed, unweighted, cyclic graph with edge labels. Some of these labels represent ...
7
votes
1answer
189 views

Binary rooted tree isomorphism

My trees are rooted and have at most two children at every vertex. I need references that help me solve any or all of the questions below: How many isomorphism classes of trees with n vertices are ...
4
votes
2answers
137 views

How do I do sum of first k elements of a row of a Pascal's Triangle efficiently?

More specifically, I want to: $^nC_0 + ^nC_1 + ^nC_2 + ..... + ^nC_k$ I tried doing it linearly by calculating $^nC_{j+1}$ by multiplying $^nC_{j}$ with (n-j+1)/j. The answer it gives is correct ...
3
votes
0answers
43 views

Can we create the level graph from sink to source in Dinitz?

One of the steps of the Dinitz algorithm for computing maximal flows is to create a level graph. It is created from source to sink using BFS. Could we create the level graph from sink to source ...
-1
votes
1answer
60 views

Convert between IEEE 754-2008 decimal64 and IEEE double precision floating point number

I need to know the algorithm for converting between IEEE 754-2008 decimal64 and IEEE 754-1985 double precision floating point number. I have been working on this for the past 2 days and I match the ...
1
vote
2answers
35 views

Why should small o notation has to satisfy the equation for all values of the constant

Big-O of a function i.e. f(n) = O(g(n)) is such that both c and $\textbf{n}_0$ can be assigned values depending upon the function f(n). If such is the case for Big-O, then why for small-o, the ...
0
votes
0answers
47 views

Checking for 4-cycles in a graph

I was reviewing some selected problems on algorithms and time complexity and the notes had the following exercise (ex. 4.3 from book Algorithms by Dasgupta, Vazirani, Papadimitriou): Design and ...
3
votes
2answers
145 views

Efficient algorithm for getting from 1 to n with 3 specific operations

The question: Given those 3 valid operations over numbers and an integer $n$: add $1$ to the number multiply the number by $2$ multiply the number by $3$ describe an efficient ...
0
votes
0answers
34 views

Complete set of basic circuits for McLane's Theorem

I was assigned a project in which i had to implement some algorithms concerning graphs. The last one is the one described in the title. I have to make an algorithm that uses McLane's theorem (https://...
2
votes
0answers
37 views

Does the Longest Common Subsequence problem reduce to its binary version?

I am working on a problem regarding the Longest Common Subsequence (LCS) of two strings, and I was wondering if there is any reduction from the general case of LCS to its binary version, i.e. by ...