Questions related to design and analysis of algorithms

learn more… | top users | synonyms (1)

0
votes
0answers
10 views

(Asymptotics) Trouble understanding a why related statement holds after proving another statement for two functions

$f_1$, $f_2$, $g_1$, and $g_2$ are functions such that: $$f_1 = \Theta(f_2)$$ $$g_1 = \Theta(g_2)$$ I was able to prove that: $$\frac{f_1}{g_1} = \Theta(\frac{f_2}{g_2})$$ But I can't understand ...
-1
votes
0answers
14 views

Why does Peterson's Algorithm Work for Multiple Processors? [duplicate]

Peterson's Algorithm looks like: flag1=true; turn=threadNumber; while(flag2==true && turn==threadNumber); //critical section flag1=false; Why does this ...
-1
votes
0answers
27 views

An algorithm that increases probability by time [on hold]

I want to make a game for my school project. It's Speed Card Game. I need an algorithm for determining computers move time. It will make his move random time but i need to make it more human. I plan ...
1
vote
0answers
29 views

Iterative permutations, but favoring swaps of early elements

I'm familiar with the Steinhaus–Johnson–Trotter algorithm, which allows for the iterative yielding of permutations of a sequence by performing a single swap per iteration. It has the behavior, ...
0
votes
3answers
46 views

Count points enclosed by several planes in 3D space

I have for example 10 planes with their equation: Ax + By + Cz = D and a list of 3D points. Those plane can make regions, some of them closed, and others not, the task is to count the number of points ...
3
votes
1answer
45 views

Data structure for counting bits set on a table

I have a table that contains only bits. I would like to be able to do the following two queries: SET any bit to 0 or 1; GET the number of bits that are set to 1 from the beginning of the table up to ...
4
votes
3answers
102 views

Cutting equal sticks from different sticks

You have $n$ sticks of arbitrary lengths, not necessarily integral. By cutting some sticks, you want to get $k<n$ sticks such that: All $k$ sticks have the same length; All $k$ sticks are at ...
0
votes
2answers
67 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 ...
0
votes
0answers
41 views

Randomized algorithm to make a Binary Search Tree from an array of $n$ distinct elements

An array $\mathcal{A}$ of $n$ distinct integers $\{a_1,a_2,\ldots,a_n\}$ is given. I'm asked to design a randomized (esp. Las Vegas) algorithm to make a Binary Search Tree out of these elements, such ...
0
votes
0answers
39 views

smaller size approximation to minimum vertex cover

Does there exist a simple approximation to the minimum vertex cover problem that aims to find a smaller (or equal) set to the minimum? Usual algorithms seems to aim to find an approximation such that ...
6
votes
1answer
58 views

Implementing general vertex folding procedure in an undirected graph

I'm implementing the algorithm presented in "Improved Parameterized Upper Bounds for Vertex Cover" paper (PDF). I'm a bit stumped by the General-Fold procedure. ...
4
votes
0answers
16 views

Emulations of atomic registers and read-modify-write (RMW) primitives in message-passing systems

The well-known ABD algorithm in Sharing Memory Robustly in Message-Passing Systems can emulate atomic, single-writer multi-reader registers in message-passing systems, in the presence of processor or ...
0
votes
0answers
42 views

median of three quick sort and recurrence relation

How could we prove that median of three quicksort have a running time of \begin{equation*} T(n) = \mathcal{O}(n) + 2T ( n/2) \end{equation*} using induction when it is applied to a sorted array ...
6
votes
1answer
96 views

Scheduling Algorithm for aperiodic multiprocessor tasks

I've got a System, which is defined as follows: A limited number of stations is given (n), which can offer different services (for now there are two services). A station can either offer one of the ...
0
votes
1answer
72 views

Algorithm for finding best combination of elements

Say I have a very large, arbitrary number of variables, each of which I can assign to be type A, B, or C. The types come with expenses: Type A's are the least expensive, and C's are the most ...
0
votes
0answers
17 views

Fault-tolerant gates Problem [on hold]

Assume we are given an infinite supply of two-input, one-output gates, most of which are OR gates and some of which are AND gates. Unfortunately the OR and AND gates have been mixed together and we ...
2
votes
1answer
43 views

Arranging tasks with specific constraints (scheduling)

I have the following problem: Given a set of tasks and their duration, i need to arrange them taking in consideration some constraints; Here's an example: Suppose we are scheduling talks in a ...
1
vote
0answers
19 views

Trying to find out how to deducing formulas in FCM algorithm

FCM algorithm or Fuzzy C-Means Algorithm is a clustering algorithm with a matrix with values between 0 to 1 to representing the membership function as membership function in K-means 0-1 approach. ...
2
votes
0answers
52 views

Optimal vehicle routing on map

Currently I am developing a piece of software that solves the vehicle routing problem. The task is the following: I have several vehicles along the town I have lots of destination points along the ...
-1
votes
0answers
37 views

Stable partition algorithm for Quicksort in linear time

I ran through this question in my exam. Was not able to solve it Write a pseudo-code for stable partition algorithm for Quick Sort in an array of n elements in linear time. Select the first element ...
1
vote
2answers
38 views

How to write regular expression excluding certain pattern aba from albhabet set {a,b}? [duplicate]

Often we are asked to write regular expression for the set of words that contain a certain string pattern, like $aba$. But what about the opposite? Is there any generic way to write a regular ...
4
votes
1answer
86 views

Maximum sum subset of an array with an extra condition

We are given numbers $n \leq 200$, $k \leq 10$ and an array of $3n$ positive integers not greater than $10^6$. Find the maximum possible sum of a subset of elements of this array, such that in every ...
1
vote
0answers
75 views
+50

Mini-Games for Artificial Intelligence Course

I am going to have Introduction to Artificial Intelligence in this semester & I know that our main resource would be "Artificial Intelligence A Modern Approach", since I want to learn deeply and ...
1
vote
1answer
17 views

Feasibility of linear inequalities with binomial variables

I have a system of linear inequalities of the form $A^t x <= b$ where each of the $x_i$'s is a binary variable in $\{0, 1\}$. Are there any known fast and practical algorithms that can find a ...
0
votes
0answers
48 views

A Fast Algorithm to Approximately Solve a Modified Version of The Thomson Problem

The problem I'm trying to solve is the same as the Thomson Problem except that the objective isn't to minimize $$ U(N) = \sum_{i < j} \frac{1}{r_{ij}}, $$ given $r_{ij} = |\mathbf{r_i} - ...
1
vote
2answers
60 views

Enumerate All Possible Strings Over Alphabet

I am given the following decision problem: A program $ \Pi $ takes as input a pair of strings and outputs either $true$ or $false$. It is guaranteed that $\Pi$ terminates on any input. Does there ...
0
votes
1answer
31 views

How to explain the steps in the implementation of hashing functions like SHA1

I was reading the article about the SHA1 hashing function (I know it is not secure anymore) and I've found a pseudocode implementation on Wikipedia. I can see that there are a lot of mathematical ...
1
vote
1answer
43 views

How to detect repeating random numbers?

What is the best way to detect repeating sequences of random numbers? For example, say I got two random number generators (RNG). One of them has been tampered with and is repeating the sequence of ...
1
vote
1answer
52 views

How many ways to find a sum totalling n using only certain Integers?

Using an infinite supply of integers of a set S, how many ways are there to reach a sum of n? Clarification: The Integers are arbitrary, positive, and may not include 1. At first I thought it was ...
3
votes
0answers
38 views

Efficient update to rational flow network?

Once we've computed the max flow in a flow network with integral capacities, we can change one of its edges' capacity by a unit and recompute a maxflow in linear time using BFS. Is there something ...
2
votes
0answers
26 views

algorithm to sample function so that integral is unaffected

I have an array with a hundred thousand entries representing the x and y values of a function. Since I frequently need to integrate this function (in a product with other functions) I am looking for ...
1
vote
0answers
17 views

Algorithm for the function “drop” in a binary random-access list

In the book Purely Functional Data Structures by Okasaki, exercise 9.1 asks: Write a function drop of type ...
0
votes
2answers
27 views

Algorithm for generation of Canonical represented integers [closed]

Is there a way to get canonical representation of an integer by algorithm? I can get primes, but I don't know how to represent, for example, 1000 as 2^3×5^3. How ...
4
votes
2answers
75 views

Decremental reachability in a grid graph

Consider an $n$ by $n$ grid graph. For example, the following. You can of course reach the top left corner from the bottom right. Now consider the graph dynamically with an arbitrary number of ...
2
votes
0answers
81 views

Fastest algorithm for shortest path with atmost k edges on a DAG with non-negative edge weights?

(Please note, this is not a duplicate to Shortest path with exactly $k$ edges OR Shortest path with a fixed number of edges. What I want is a better algorithm) The problem under consideration is to ...
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', ...
7
votes
0answers
89 views

Change in the distances in a graph after removal of a node

Given an undirected unweighted graph $G=(V,E)$ and a node $s \in V$, we are looking for a vector $\operatorname{diff}[]$, such that, $$\operatorname{diff}[v] = \sum_{u \in V \setminus \{v\}}{(d^{G ...
2
votes
1answer
23 views

connected components - determining “groups” in Go

I would like to write an analysis of go positions. Part of it requires me to determine the "groups" on the board and count their "liberties". Any Go "position" is a collection of black ...
-4
votes
2answers
70 views

Sort doubly linked list efficiently

How efficiently can a doubly linked list be sorted? The minimum I could get is $O(n^2)$. Can anyone suggest something better?
0
votes
0answers
26 views

Asymptotic Complexity of the following two functions [duplicate]

Let $f(n) = n^{1.01}$ $g(n) = n(log(n))^2$ Now I need to figure out whether $f = O(g(n))$ or $\Theta(g(n))$ or $\Omega(g(n))$. I tried taking the ratio $f(n)/g(n)$, apply L'Hospital's rule ...
11
votes
2answers
217 views

Algorithm to distribute items “evenly”

I'm searching for an algorithm to distribute values from a list so that the resulting list is as "balanced" or "evenly distributed" as possible (in quotes because I'm not sure these are the best ways ...
1
vote
1answer
52 views

maze solving algorithms (pledge algorithm)

I saw this maze, and tried to apply pledge algorithms to it. But I am not able to solve this maze using this algorithm. What am I missing/doing incorrectly? PLEDGE ALGORITHM: in both cases we don't ...
1
vote
1answer
63 views

Why can't we detect infinite loops in the busy beaver problem?

I was reading about the busy beaver problem the other day and I'm confused as to why we can't keep an array of Turing machine states that the machine has been through and simply iterate through it at ...
0
votes
1answer
38 views

Find pixel mapping matrix with minimum iterations

The Situation I am an electronics engineer and on a volunteer team that have built a prototype eye that has 200*200 sensors that are mapped to the optic nerve, the connection to the optic nerve is ...
-1
votes
1answer
27 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
37 views

Algorithm to merge two incomplete lists of symbols (strings) into a complete one

I initially considered this problem trivial, but then looked with more attention, I could not find an easy solution. Let's say we have two ordered lists of symbols (strings): ...
0
votes
0answers
87 views

Dynamic distance from source in a directed graph (only incremental or only decremental)

At the beginning we have a directed unweighted graph of $n \leq 10^3$ vertices, and $m \leq 10^5$ edges, with some vertex being a source, and we perform updates and queries on it. An update is adding ...
1
vote
2answers
49 views

For each vertex of a tree count vertices closer than a specified value

We have a weighted tree of $n\leq 10^5$ nodes, and for every node $v$, value $L(v)$. The goal is to calculate, for every vertex $v$, number of vertices $u$ such that ...
1
vote
1answer
72 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 ...
-4
votes
1answer
42 views

Determine if DFAs accept any word which contains bb [closed]

Let $\Sigma=\{a,b,c\}$. Describe an algorithm that takes as input a deterministic finite automaton $M= (Q,\Sigma,\tau,s,A)$ and determines whether or not $M$ accepts a word containing $bb$ (i.e., a ...