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
12 views

Most efficient algorithm to determine whether a given finite sequence is mutually distinct

Let $a_1, \dots a_n$ be a finite sequence of elements of a set $X$. I'm wondering what is the most efficient algorithm to determine whether the number of elements of the set $\{a_1,\dots, a_n\}$ is ...
0
votes
0answers
23 views

Count the strings with n0 K zeroes together

Given a string of length N that is made of only 0 and 1's.But some positions of string are '?'.It means their we can put 0 or 1. Now , the problem is we need to count the number of ways to fill these ...
0
votes
1answer
31 views

searching a number in 2D matrix

I was looking for algorithm on searching a number in a 2D matrix, with property that the matrix is sorted both row-wise and column-wise. Finally i came across, this link ...
0
votes
2answers
22 views

Greedy Algorithm, Fewest overlaps

Hi I need help doing this problem. I've been working on it for like 2 hours now and I'm no where. I'm literally about to throw my computer. I've watched youtube videos, reread my notes. The homework ...
2
votes
2answers
23 views

algorithm to find the order of $a$ in $(\mathbb{Z}/n\mathbb{Z})^*$ where $n$ is not prime.

algorithm to find the order of $a$ in $(\mathbb{Z}/n\mathbb{Z})^*$ where $n$ is not prime. Now I know a naive algorithm where you just keep multiplying $a$ by itself until you find it equals $1 \mod ...
1
vote
0answers
29 views

Does a generalization of the Teichmuller-character for non-prime arguments exist?

Rereading an older article on Fermat-quotients in which I'd applied some p-adic-rationale I find now, that my method for the representation of bases $b$ which allow high fermat-quotients ...
1
vote
0answers
18 views

Algorithm to lay out orthogonal connector lines without overlap

I'm drawing a graph of nodes connected by orthogonal edges with corners. The nodes are laid out on a grid, and the edges (conceptually) follow the grid lines. The paths the edges take are laid out ...
0
votes
1answer
12 views

Linearly independent rows in a binay matrix

I need the algorithm to finding only the linearly independent rows in a binary matrix using XOR function. Example 1: The result: Example 2: The result: R4 is not included because:
0
votes
0answers
21 views

Identify regions in 3D space and assign a point to a region [on hold]

Sorry if the question is duplicated, I don't even know what to search for solve this problem. I have for example 10 planes with their equation: Ax + By + Cz = D and a list of 3D points. Those plane ...
0
votes
2answers
32 views

Is my method of computing the running time correct?

Okay, so this is the code for which I need to compute the running time: ...
2
votes
0answers
34 views

Algorithm to find the “optimal” path in a given graph

Assume that $G=(V,E)$ is an undirected connected graph and that $H: V \to \mathbb R$ is a function that assign at each vertex $v \in V$ its height $H(v)$. Think of the pair $(G,H)$ as an energy ...
2
votes
0answers
26 views

Find spacing of fence posts with minimal distance to fence posts of two other fences

Definition 1: A "fence" is a set of "fence post positions", where each pair of adjacent positions has the same difference (the spacing), e.g. $\{1,2, 3, 4\}$. A fence is described by three values ...
0
votes
1answer
13 views

Max no. of piece in k cut

Suppose I have large piece of rectangular sheet. Cutting is allowed only vertically and horizontally. My approach is if no. of cut is even then max. no of piece is (n/2)*(n/2) if no of cut is odd ...
0
votes
0answers
36 views

Find Good string in mimimum Moves

A string is called to be good if and only if "All the characters in String are repeated the same number of times" Now, Given a string of length n, what is the minimum number of changes we have to ...
1
vote
1answer
30 views

How to get the ratio from a function of N?

The exercise gave us a chart which showed the running time as a $N$ increases: \begin{array}{c|c} N & \text{seconds}\\\hline 256 & 0.000\\ 512 & 0.000\\ 1024 ...
5
votes
0answers
51 views

Traveling salesman problem: can a terrible strategy beat a good one?

Until yesterday, I was under the naive impression that constructing a weighted graph where the nearest-neighbour algorithm gives the worst possible route, would have the property that any other ...
3
votes
0answers
18 views

Looking for an algo to “sorta” diagonalize a similarity matrix.

I've got a big fat similarity matrix. The rows and columns represent people, and the values represent some positive measure of their closeness (0 meaning no connection at all). The n-th row and n-th ...
6
votes
1answer
60 views

Traveling salesman problem: a worst case scenario

For those not familiar with the problem, here is the Wiki article; it can be understood by anyone. I am in particular interested in the nearest neighbor algorithm, also known as the greedy algorithm, ...
0
votes
1answer
84 views

Cut squares from sheet

A rectangular paper sheet of M*N is to be cut down into squares. ...
0
votes
1answer
35 views

Big-Oh of exponent of exponent

How does one whether an exponent of an exponent is the big-Oh of the other? For example, if I have $a^{b^n}$ and $b^{a^n}$, how would i determine and prove which is a big oh of another? I'm thinking ...
0
votes
0answers
7 views

sufficient and necessary condition for specific dfs property

Let $G$ be a directed graph. I want to find a sufficient and necessary condition for the next property regarding dfs run- For each dfs run on $G$ the vertex with the latest finish time is a vertex ...
1
vote
0answers
37 views

Bride Groom Problem

Let's consider a system of $n$ men and women. Each woman is paired with one man (there are only pairings between a woman and a man in this system). There are $n!$ possible distinct pairings. I refer ...
0
votes
0answers
21 views

Modular nth roots, e.g. $x^5 \equiv 6 \pmod{31}$

I want to algorithmically solve the (large integer) modular root equation $$x^n \equiv a \pmod {p^k},$$ assuming for simplicity that $p$ is prime, $\gcd(a,p)=1\;$ and $n$ odd. If $q \equiv n^{-1} ...
0
votes
1answer
15 views

In the loop average computation

I want to compute the average of a set of number, which is constantly increasing. I guess it's simple, but I'm struggling here: Let's say: 1st iteration: m(i)=a+b/2 2nd iteration: m(i+1)=a+b+c/3 ...
0
votes
0answers
26 views

Sum of products of numbers in a list

For N numbers in a list, is there a formula to get the sum of products of the numbers in the list? Example: {3, 3, 2} = (3 * 3) + (3 * 2) + (3 * 2) Right now I'm ...
1
vote
1answer
38 views

“Job-scheduling” problem that minimizes the number of machines

In a graph, there are points that need to be visited. For each of these points, there is a certain time interval given by its start and ...
0
votes
0answers
30 views

Find two element $x_k$ and $x_l$

Let $S=\{ x_1, x_2, \dots, x_n \}$ a set of real numbers, where $n \geq 2$. Describe an algorithm, that has time complexity $o(n^2)$ and that finds and returns two elements $x_k$ and $x_l$ of $S$, ...
0
votes
0answers
21 views

To minimize surface area of integer cuboid of ​​the known volume

There is a cuboid (a * b * c), (a, b, c ∈ N). S (Surface area of a cuboid) = 2 * (ab + bc + ca). V (Volume of a cuboid) = a * b * c = n. I need to minimize S, provided that I specified the volume ...
0
votes
0answers
20 views

Adjust previous optimal solution to new assignment problem

Suppose I have an assignment problem with $n$ workers and $n$ jobs and its optimal solution. Now another worker and another job comes along and we are given all new costs. Is there an efficient ...
1
vote
0answers
9 views

Finding groups with minimum mean deviation

Is there any algorithm that groups consecutive elements in an array that gives the minimum mean deviation. For example we are given an array a=[1,2,3,4,8,2,3,5] There can be many "consecutive" ...
0
votes
0answers
47 views

Real roots of a quintic polynomial with constraints

This is a question on the edge of math and programming. I pondered about the best way to state the problem: should I provide context, or get straight to the point of the question? Given various ...
0
votes
1answer
26 views

Minimal disjoint chains covering graph vertex set

I'm looking for references on the following problem: Given a graph $G=(V,E)$, what is the minimum number of simple, disjoint paths that span all the vertices in $V$? i.e., let $P$ be the answer to ...
1
vote
0answers
24 views

Efficient algorithm to find a minimum spanning set for a given vector.

A few days ago a colleague proposed the following problem. Let $W$ be a finite subset of a vector space $V$, and let $v\in\langle W\rangle$ (the linear span of $W$). Is there an efficient ...
0
votes
1answer
39 views

How to calculate running time of code?

I'm finding great difficulty calculating runtime with loops. It's easy when there is one loop, especially when the counter is being incremented by one: ...
0
votes
2answers
22 views

Proving Algorithms

I'm trying to get down how to prove that something is $O(\cdots)$ or $\Theta(\cdots)$ but no matter what I look at, I don't get the reasoning as to how I can come to an answer. So here's a couple of ...
0
votes
1answer
42 views

How to prove the $\Theta$ notation?

I know that to prove that f(n) = $\Theta$(g(n)) we have to find c1, c2 > 0 and n0 such that $$0 \le c_1 g(n) \le f(n) \le c_2 g(n)$$ I'm quite new with the proofs in general. Let assume that we ...
0
votes
1answer
37 views

How many n-digit numbers can be formed using x single digit numbers? [on hold]

For instance, I have to form 4 digit numbers with the any 3 digits, say 1, 2 and 3. There are several possible numbers that can be formed by arranging these digits in various orders, but I am unable ...
2
votes
1answer
47 views

Using Big-O to analyze an algorithm's effectiveness

I am in three Computer Science/Math classes that are all dealing with algorithms, Big-O, that jazz. After listening, taking notes, and doing some of my own online searching, I'm pretty damn sure I ...
1
vote
0answers
14 views

Polynomial time algorithm for determining if there exists an ordering of subsets

Given n subsets of cardinality k of a set $S=\{1,2,...,m\}$. Is there a polynomial time algorithm to determine if there exists an ordering of subsets $s_1,...,s_n$ such that ...
0
votes
0answers
20 views

Factoring a quadratic residue modulo

Do apologize, wasn't sure where to ask this, but I was wondering how an algorithm would factor and show the square roots in a quadratic residue modolo when you're given N and a, which is a quad. ...
2
votes
1answer
23 views

find all continuous path segments in an undirected graph

I have an undirected graph, like the following: . C . / \ . B F . / / \ . A D E The edges are: ...
1
vote
1answer
41 views

Calculation of products of powers using Modular Exponentiation

I need to devise an algorithm that outputs $x^a * y^b$ (mod $m$) on an input of $m, x, y, a, b$ using the binary left to right modular exponentiation algorithm. It should be able to compute $x^{22} * ...
0
votes
1answer
32 views

Calculating running time for C code

The problem is this: How many array accesses does the following code fragment make as a function of $N$? ...
0
votes
1answer
20 views

Turing machine algorithm and Natural number

Let T be a deterministic Turing machine and let A be a set of all algorithms which is running on T. I know that there is an algorithm F which can transform an Algorithm $X$ into a Natural number ...
0
votes
1answer
18 views

Tight asymptotic upper and lower bounds

I have a equation: $T(n) = 4T(n/3) + n\ln n$ In this equation, I have to give tight asymptotic upper and lower bounds. What does that mean? I know I can apply Master theorem (which gives me theta ...
-2
votes
0answers
35 views

Minimise the expected value [closed]

Given an array A that contains n integers, namely $A[1], A[2], ..., A[n]$. A single action consists of performing one of two following operations: ...
1
vote
0answers
27 views

Definition of decidable sentence

Let $P(n)$ is a sentence which mentions natural number $n \in \mathbb{n}$ For example, "$n > 5$" or "There is no $n$ such that $3^n+4^n=5^n$ " can be $P(n)$. I want to define a set A as a set ...
0
votes
0answers
6 views

Pseudo-algorithm for most equals group size

Let's say I don't know how many (let's says person) will be present. I know I want to divise all those persons in group of 15. What king of algorithm could I use to create groups of person (the most ...
-1
votes
1answer
244 views

Finding winner of flipping game

Alice and Bob play a game with N non-negative integers. Players take successive turns, and in each turn, they are allowed to flip active bits from any of the integers in the list. That is, they ...
2
votes
1answer
29 views

Algorithm to determine if integer matrix is similar to symmetric integer matrix with nonnegative entries

Let $A\in M_n(\mathbb{C})$ be a matrix with integer entries (treated as a matrix over the complex numbers). Is there an efficient way to check if $A$ is similar to a symmetric matrix with nonnegative ...