Tagged Questions

Mathematical questions about Algorithms, including the Analysis of Algorithms, Combinatorial Algorithms, proofs of correctness, invariants, and semantic analyses

learn more… | top users | synonyms (1)

0
votes
0answers
23 views

True or False Time complexity questions

Here is my go at them and any help is appreciated: If $f(n) = \Theta(n^2)$ and $g(n) = \Theta(n^2)$ then $(f - g)(n) = \Theta(n^2)$ where we define $(f-g)(n) = f(n) - g(n) \forall n$ TRUE? If $f(n) ...
1
vote
1answer
25 views

Time complexity of algorithms

I am having some trouble figuring out the time complexity in big theta notation of the following algorithms. Any help is appreciated. ...
0
votes
1answer
22 views

Resolve $Ay=b$ with fast method

I am looking for method that resolve equation $$Ay=b$$ I read the paper "Wiedemann's algorithm" that is one solution for fast way to find the solution instead of Gauss-Elimination. Could you suggest ...
0
votes
1answer
26 views

complex root finding

I have a problem of root finding. Format of the function can be arbitrary whereas I want to solve the following one: $$f(x)= a+e^{-x^2}(b+cx+dx^2)$$ where a,b,c and d are given parameters, not ...
1
vote
1answer
18 views

Find the sum of all the multiples of 3 or 5 below 1000 (Break down)

I know that this has been posted before but I can't grasp how it actually works. I'm a 16 year old in the 10th grade and am interested in algorithms. I've looked in multiple places on the web but am ...
1
vote
2answers
29 views

Split cab fare proportional to saving made across the board

Interesting dilemma. I've figured out how to split a cab fare 3 ways (proportional to time, mileage and equally) but I've found that when the cab fare is split proportional to time and mileage, the ...
0
votes
1answer
24 views

Split a cab fare proportional to the time everyone has spent in taxi

How would you split a cab fare proportional to the time everyone has spent in the taxi? Total journey time = 19 min Fare = $17.25 ...
0
votes
0answers
11 views

How to approximate the formual of combination function with large number element in set

I am implement the function to get the value of W with input are $k, \epsilon,\Omega$. The function W is defined as Please don't worry about the complex of equation. It is very easy with three known ...
-3
votes
0answers
18 views

Problem related to substitute [on hold]

These are roman values - Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1,000 these are some rules associated to problem - Numbers are formed ...
-1
votes
1answer
25 views

Prove that the sieve of Eratosthenes crosses off all composite numbers on the list but retains all the primes. [on hold]

Prove that the Sieve of Eratosthenes crosses off all composite numbers on the list but retains all the primes. I don't know where to start and how to strictly prove this statement.
1
vote
1answer
29 views

Find all Combinations of 1 and 2 which sums up to k.

I have two numbers $1$ and $2$. I have to print all ordered combinations which sums up to $k$. For example: $k=1$ Its only $1$. $k=2$ It's ${1,1},{2}$. $k=3$ Its ${1,1,1},{1,2},{2,1}$ What ...
0
votes
0answers
20 views

Evaluation a function of degree of vertices in a graph

I have a function $f(d)$ which takes in the degree of a vertex of a node in a graph $G$ and outputs a number between 0 and 1. The function is specified as follows. ...
0
votes
0answers
8 views

looking for an algorithm for nonuniform timing series

If we have a nonuniform timing series t1,t2,t3.... and every timing point means an event. A time interval T is given. Then n events can happen in T. Once T is given, how to calculate the maximum ...
0
votes
1answer
22 views

Select K numbers from N numbers fairly

I want to fairly select K numbers out of an array of N number. I know that this problem can be solved using Reservoir Sampling but I want to know if this approach is correct too? ...
1
vote
0answers
16 views

Formula for number of tiles needed to fill up predefined space?

I've been bashing my head all day with this problem, there is no way I could figure it out by myself. Here's a detailed explanation, any help will be much appreciated: We want to fill up the room ...
0
votes
1answer
16 views

Running time for algorithms

Suppose i have a set $\{1,2,...,n\}$ and i know that the solution to my problem is a subset $S \subseteq \{1,2,...,n\}$. Clearly trying out all subsets in an exhaustive approach is far too time ...
0
votes
0answers
26 views

Algorithm Generate all labeled graphs

I'm trying to find an algorithm which will generate all labeled graphs with $n$ nodes and $n-1$ edges. It must cover trees and graphs with cycles with one unconnected node, but without multigraphs. ...
0
votes
0answers
24 views

Maximum flow problem with both minimum and maximum capacities

I'm trying to develop an algorithm for a variant of the st-Maximum Flow problem where each edge has a maximum capacity $c_{max}$ and a minimum capacity $c_{min}$. The output should be a maximum ...
0
votes
0answers
12 views

HMM - forward algorithm (Part-of-Speech Tagging)

In order to understand the Forward algorithm for Hidden Markov Models, I created a Little example of Part-of-Speech Tagging. Consider the Hidden Markov Model with states $N$ (Noun), $V$ ...
1
vote
0answers
36 views

A list of numbers and

I have a real life problem that math may be able to solve. I am no mathematician so if you have any insight please use the simplified version. This problem is way beyond me. My gut tells me there is ...
-3
votes
0answers
21 views

What are the best data structure implementations for each of Kruskal’s and Prim’s algorithms [closed]

What are the best data structure implementations for each of Kruskal’s and Prim’s algorithms?
1
vote
0answers
24 views

Some doubts regarding decidable sets

I've been working at one of the problems, related to the decidability. Let's denote $ f: \mathbb{N} \rightarrow \mathbb{N}$ as a computable increasing function, $A \subset \mathbb{N}$ is a ...
0
votes
1answer
11 views

Interpolation in quadtrees/octrees

I'm looking for an interpolation algorithm for quadtrees and octrees that is derived from bi(tri)linear or bi(tri)cubic interpolation. I'm mostly interested in the case where: the interpolant is ...
0
votes
2answers
24 views

Directed acyclic graph problem

Love some guidance on this problem: G is a directed acyclic graph. You want to move from vertex c to vertex z. Some edges reduce your profit and some increase your profit. How do you get from c to z ...
0
votes
0answers
37 views

Grover's algorithm

Any help is appreciated! I've read over a bunch of sources but still I don't get the question. Consider a function $f \colon \{0,1\}^n\to\{0,1\}$ such that the number of $x\in\{0,1\}^n$ such that ...
0
votes
1answer
13 views

Explanation of division/reduction in a binary Galois Field using bit-shifts

I've seen a lot of algorithms reducing the result of a multiplication in a Binary Field by using only bit-shifts and XOR. The number of positions to shift seems to be derived from the polynomial, but ...
0
votes
1answer
21 views

What is the formal name of this problem?

I'm doing an assignment and I'm having trouble with this question, could anyone give me the formal name of the problem described so I can research it better? The task is to move a player along a path ...
0
votes
2answers
21 views

Help with algorithm

How can I prove that is true/false $$ f(n)+g(n)=O(f(n)\cdot g(n)) Where f(n),g(n) > 0 $$ I think that if $f(n)=\frac{1}{n}$ and $g(n)=n$ it can't be true but I don't know how to prove it.
0
votes
0answers
12 views

Find an algorithim for parallel time sharing

I am trying to come up with an algorithm to calculate the time spent on multiple tasks, where there is the potential that they can run in parallel. The problem can be summarized as follows: A CPU is ...
1
vote
1answer
22 views

Combinatorics problem

I am trying to solve this question, my solution involves solving a combinatorial problem as follows : Number of arrangements of exactly k distinct elements in n slots such that each one of the ...
0
votes
0answers
39 views

Approximation for fewest incompatibilities in a task scheduling selection algorithm

Suppose you have a task selection algorithm to select the largest subset of tasks that do no overlap. The greedy algorithm that selects tasks based on their finish time will always produce an optimal ...
1
vote
1answer
17 views

Trying to find polynomial-time algorithms for knapsack-like problems

Consider two related problems: You have $n$ cannisters that must go into $m$ trucks that can each carry $k$ cannisters. You require that no truck becomes overloaded, and for each cannister, there is ...
0
votes
0answers
19 views

How can we show that 3-dimensional matching $\le_p$ exact cover?

In exact cover, we're given some universe of objects and subsets on those objects, and we want to know if a set of the subsets can cover the whole universe such that all selected subsets are pairwise ...
0
votes
1answer
15 views

Calculating nCr mod M using inverse multiplicative factors

The method used for calculating nCr mod M is: fact[n] = n * fact[n-1] % M ifact[n] = modular_inverse(n) * ifact[n-1] % M And then nCr is calculated as ...
0
votes
0answers
3 views

Will postorder traversal on a reversed graph provide the same result as a reversed postorder traversal on a usual graph

Will postorder traversal of a reversed graph provide the same result as a reversed postorder traversal on a usual graph? I am trying to understand strong components search algorithm (on coursera) and ...
0
votes
2answers
23 views

Partitioning graph edges into two cycleless sets

Given a directed graph $G=\left(V,E\right)$, provide an algorithm that partitions $E$ into two disjoints sets $E_1,E_2$ such that $E=E_1\cup E_2$ and $G(V,E_1)$, $G(V,E_2)$ have no cycles. The ...
-2
votes
1answer
27 views

What is the most efficient way to evalaute the function $f(N, R) = F(N)/(F(N-R)*F(R))$ where $F(N) = 1^1*2^2*…*N^N$? [on hold]

In particular goal is to find $f(n,r)\mod(m)$ for given values of n, r, m and m is a prime number. $f(n,r) = F(n)/(F(n-r) * F(r))$ where F(n) = $1^1 * 2^2 * 3^{3} *... * N^N $ Here is the python ...
-1
votes
0answers
30 views

Adjacency and incidence matrix, algorithms for finding connected components (breadth/width search, matrix approach), Dijkstra's algorithm.

(5pts) Consider the graph C5 (cycle with 5 vertices). Let A be its adjacency matrix. Calculate A^4, the fourh power of the matrix. Draw the graph corresponding to the adjacency matrix A^4. (5pts) ...
3
votes
2answers
111 views

Need formal mathematical definition of this concept

Assume we have a function $y=f(x)$ that is $\textit{C}^\infty$ and the function has a number of local maximums. Assume there are $k$ such maximums $\{m_1, m_2, m_3, \ldots , m_k\}$ where $f'(m_i)=0$. ...
1
vote
2answers
67 views

Algorithm: Scheduling of Overlapping Intervals

I'm reviewing algorithms, and I've come across this problem. At first, it seemed like an interval scheduling problem to me, but now I think it is a dynamic programming problem. I'm not sure how to ...
0
votes
1answer
24 views

search algorithms performance

A company database has 10,000 customers sorted by last name, 20% of whom are known to be good customers. Under typical usage of this database, 60% of lookups are for the good customers. Two design ...
0
votes
0answers
117 views

Devise an algorithm that find all terms of a finite sequence of integers that are greater than the sum of all previous terms in the sequence.

Devise an algorithm that find all terms of a finite sequence of integers that are greater than the sum of all previous terms in the sequence. I'm not sure how to approach this.
0
votes
1answer
18 views

How to find the largest connected component of an undirected graph using its incidence matrix?

Usually, finding the largest connected component of a graph requires a DFS/BFS over all vertices to find the components, and then selecting the largest one found. Suppose I only have an incidence ...
0
votes
1answer
27 views

Why does .NET's Array.Sort method use Heapsort instead of Quicksort when the number of partitions exceeds 2 * LogN? [closed]

As per MSDN doc for Array.Sort, If the partition size is fewer than 16 elements, it uses an insertion sort algorithm.If the number of partitions exceeds 2 * ...
1
vote
2answers
60 views

Big theta proof [closed]

a) Show that $3x+7$ is $\Theta(x)$. b) Show that $2x^2 +x -7$ is $\Theta(x^2)$ c) Show that $⎣x+.5⎦$ is $\Theta(x)$ d) Show that $\log_{10}(x)$ is $\Theta(\log_2(x))$ My professor gave the ...
1
vote
1answer
52 views

Increase by one all edges, Min-Cut, changes or not?

My Friends, as i ask a new question recently, Increase by one, Shortest path, changes the edges or not? i want to ask a related question as a new post Suppose we have a Graph G in which weight ...
1
vote
2answers
26 views

Increase by one, Shortest path, changes the edges or not?

as i read the following text : "Let P be a shortest path from some vertex s to some other vertex t in a graph. If the weight of each edge in the graph is increased by one, P will still be a shortest ...
-2
votes
0answers
117 views

Devising Algorithms

a) Describe an algorithm that uses only assignment statements that replaces the triplet (x,y,z) with (y,z,x). What is the minimum number of assignment statements needed? b) Devise an algorithm that ...
0
votes
1answer
28 views

Simple Turing Machine

Having a bit of trouble designing a turing-machine which recognizes the following language. The alphabet is $\Sigma$ = {a,b,c}. $$ L_2 = \{wcw^R | w \epsilon \{a,b\}^*\} $$ The part which messes ...
0
votes
1answer
22 views

cubic integral roots

I am trying to find the integral roots (if they exist) of the following polynomial. Additionally, it would be helpful if someone could explain an algorithmic approach to solving this. $$ f(x) = 2x^3 ...