0
votes
1answer
28 views

Number of configurations in a constrained nested loops and configuration back from serial

Consider 4 counters looping the digits 0, 1, 2 to form the various "configurations", like in : ...
0
votes
0answers
42 views

How can nested for-loops be expressed in mathematical notation?

Apologies if this is an obvious question; I'm not very familiar with mathematical notation for algorithms. I was coding a solution for Project Euler #4, and I came up with an interesting way of ...
0
votes
1answer
61 views

efficient algorithm to place people in a specific order

You are preparing a banquet where the guests are government officials from many different countries. In order to avoid unnecessary troubles, you are asked to check the list of international conflicts in ...
0
votes
0answers
39 views

Need suggestions for this real world problem

I have a real-world optimisation problem. Following is the problem. At last have the hope for mathematics. Problem: One person Mr. X works as supervisor for a home appliances repairing company. Mr. X ...
3
votes
1answer
59 views

Placing n points in a MxM square grid

I am facing an apparently well-known problem: placing $n$ points in a discrete grid so that the points are 'evenly' distributed. By evenly I mean that I would like the density of points to be nearly ...
1
vote
1answer
28 views

steps by Euclidean algorithm back tracing

integers x and y such that gcd(2689 , 369) = x 2689 + y 369 I know the answer is x = 94 and y = -685 But I really want know how can I trace it back by Euclidean algorithm if I know the gcd is 1. My ...
14
votes
1answer
168 views

Minimum number of operations (divide by 2/3 or subtract 1) to reduce $n$ to $1$

This question is inspired by a Stack Overflow question which involves the task to find an algorithm to solve the following problem: Given a natural number $n$, what is the least number of moves ...
1
vote
0answers
32 views

Josephus problem extended

Suppose there are $2n$ people in a circle; the first n are good guys and the last n are bad guys. If we go around the circle executing every $m$-th person, all the bad guys are first to go. How to ...
2
votes
1answer
112 views

How to solve this recurrence relation with Sigma notation (f(n, m) = f(n - 1, m) + f(n, m- 1) + c?

This recurrence relation was inferred from the function $f(n, m) = f(n - 1, m) + f(n, m-1) + c$. After expanding the latter, I ended up with the following: $$f(n,m)=\begin{cases} 0,&\text{if ...
1
vote
1answer
31 views

Proof that such a Turing machine cannot be constructed…

Prove there can be no Turing machine $M^*$ that takes input $n$ and: i. halts printing 1 if $M_n$ halts on input 1 ii. halts printing 0 if $M_n$ doesn't halt on input 1 Intuitively I can see why ...
-1
votes
1answer
166 views

how to determine the largest n for which one can solve within one second using an algorithm

So I am confused on this problem for my discrete math class, I didn't know if there was a specific formula you were supposed to use or what. The question is "What is the largest n for which one can ...
0
votes
2answers
72 views

Tough Turing machine multiple choice questions

I'm having a tough time deciding whether my answers for these questions are correct. Can anyone help me agree on something? They seem pretty easy, but I've found that they're actually difficult. ...
0
votes
2answers
56 views

Discrete math with SSNs

I am currently doing some discrete math and am completely stuck on two problems. They are both the same concept: An SSN is a Social Security number. How many SSNs have digits that sum to 2? How ...
1
vote
2answers
36 views

Constructing equivalent matrices with rows and columns exchanged

I am trying to construct all inequivalent $8\times 8$ matrices (or $n\times n$ if you wish) with elements 0 or 1. The operation that gives equivalent matrices is the simultaneous exchange of the i and ...
2
votes
1answer
85 views

Is the answer 6 or 7?

This is a short mathematical puzzle from mindciphers.com which says : The London racetrack needs to submit its top three horses to the Kentucky Derby next month in order to compete for a prize. ...
0
votes
1answer
42 views

Algorithm to partition a graph under constraints

What would be an algorithm to partition the vertex set of an undirected graph into 2 vertex disjoint subsets such that each vertex has at most $\left\lfloor\frac{d}{2} \right\rfloor$ no of its ...
2
votes
1answer
73 views

Graph isomorphism and existence of nontrivial automorphisms

Consider the following two algorithmic problems - one of determining whether two graphs are isomorphic and the other of determining if a graph has a nontrivial automorphism: (1) Decision problem: ...
3
votes
1answer
37 views

Finding a recursive definition and computing $B(10)$

For $n \geq 1$, let $B(n)$ be the number of ways to express $n$ as the sum of $1$s and $2$s, taking order into account. Thus $B(4) = 5$ because $4 = 1 + 1 + 1 + 1 = 1 + 1 + 2 = 1 + 2 + 1 = 2 + 1 + 1 = ...
1
vote
1answer
47 views

How can I encode this?

Let say I have 7 integers: 1, 2, 3, 4, 5, 6, 7. Among the 7 integers, I choose 3 integers. For example, my choice is (1,2,3). Note1: The order of the integers in the choice doesn't matter. This means ...
3
votes
2answers
145 views

When do repeated intervals of time overlap?

I have two time intervals A and B that occur in time at a start time and occur until an end time. These time intervals however repeat in time from their start time until another end time. So each ...
2
votes
2answers
90 views

How to efficiently encode this?

I have 5 ring oscillators whose frequencies are f1, f2, ..., f5. Each ring oscillator (RO) has 5 inverters. For each RO, I just randomly pick 3 inverters out of 5 inverters. For example, in RO1, I ...
0
votes
0answers
43 views

Speed of Algorithm

Suppose that an algorithm uses $5n^2 + 3^n$ bit operations to solve a problem of size $n$. Suppose that your machine can perform one bit operation in $10^{-9}$ seconds. How long does it take your ...
0
votes
1answer
131 views

Given an integer n, how to find (2^x) % 1000000007, where x = binary representation of n now considered base 10.

Suppose we are given n = 4. Now its binary is 100. we take x as 100 and we want to compute (2^100) % 1000000007. I know the modular exponentiation algorithm but here n <= 600000. This means the bit ...
0
votes
0answers
23 views

String satisfying the condition

Given $N$, $A_0$, $B_0$, $L_0$, $A_1$, $B_1$ and $L_1$, find a sequence S consisting only of characters '$0$' and '$1$'(a total of N characters) such that: The number of '$0$'s in any consecutive ...
0
votes
0answers
64 views

number of ways to select the sets

Suppose there are $n$ numbers, say $1,2,3,...,n$. We need to form $m$ sets (possibly empty) such that no two sets are the same and the first $v$ numbers appear in an odd number of sets while the ...
1
vote
0answers
65 views

Finding $x^{k}\mod n$ quickly- find algorithm using $x^{2l}=x^{l} \cdot x^{l}$ and $x^{2l+1}=x \cdot x^{2l}$

Finding $x^{k}\mod n$ quickly- find algorithm using $x^{2l}=x^{l} \cdot x^{l}$ and $x^{2l+1}=x \cdot x^{2l}$. Here's my simple algorithm: We first check if $k=1$ or $k=2l$ or $k=2l+1$ for some $l ...
1
vote
2answers
57 views

Polynomial Question

Find polynomials $A(x)$ and $B(x)$ such that $A(x)P(x) + B(x)Q(x) = x + 1$ for all $x$ where $P(x) = x^4 - 1$ and $Q(x) = x^3 + x^2$. I'm stumped on this question. I know that I'm supposed to apply ...
1
vote
2answers
784 views

Finding a minimal number of charging stops along the route

The question is: Your electric car needs to be charged every X kilometres. You are doing a road trip from Toronto to Vancouver and have a list of every charging station on the highway between Toronto ...
2
votes
1answer
145 views

How to find a closed form formula for the following recurrence relation?

I have to find a closed form formula for the following recurrence relation which describes Strassen's matrix multiplication algorithm - $$T(n) = 7\,T\left(n \over 2\right) + \frac{18}{16}n^2$$ with ...
2
votes
2answers
75 views

a game of coloring edges of graph

I have a clique of size 5 which is partially colored(black or white). I have to color remaining edges so that each of the triangle has either 1 or 3 black edges. How should I go about coloring the ...
2
votes
4answers
428 views

How to find a closed form solution to a recurrence of the following form?

I need to find the closed form solution to the following recurrence -: $ T(n) = 8*T(n/2) + 0.25*n^2$ with $T(1) = 1$ and $n=2^j$ and this is what I have tried so far but just can't seem to get a ...
0
votes
2answers
383 views

Is 'every exponential grows faster than every polynomial?' always true?

My algorithm textbook has a theorem that says 'For every $r > 1$ and every $d > 0$, we have $n^d = O(r^n)$.' However, it does not provide proof. Of course I know exponential grows faster ...
0
votes
1answer
41 views

Comparing algorithm running times expressed in complex form

I know how to compare running times of different algorithms. Sometimes it is obvious, sometimes it requires simplifications, and sometimes dividing and using L'Hopital's rule to see if it converges ...
0
votes
1answer
97 views

How does one prove this equation?

How does one prove the following equation , I am getting confused about this, I can't seem to find any proving technique, I tried plugging in the Stirling's formula for factorials but to no avail - ...
1
vote
1answer
270 views

What algorithm is a good to search a lotto design?

I'm interested what kind of algorithm would be suitable to find a lotto design? I saw that is has been proven that $L(39,7,4,7)=329$. This notation is explained in ...
2
votes
1answer
713 views

What is the expected number of swaps performed by Bubblesort?

The well-known Bubblesort algorithm sorts a list $a_1, a_2, . . . , a_n$ of numbers by repeatedly swapping adjacent numbers that are inverted (i.e., in the wrong relative order) until there are no ...
0
votes
2answers
482 views

Algorithm Help - Discrete Math

Could use some help here if anyone has any ideas? Develop the algorithm only Use Theorem 7.2 to develop an algorithm for the recognition of equivalence relations on a finite set.
0
votes
1answer
75 views

What are the best ways to solve discrete divide and conquer recurrences? [duplicate]

What is the best way to solve discrete divide and conquer recurrences? The "Master Theorem" is one way. What other ways are available?
1
vote
0answers
84 views

What is the best way to solve discrete divide and conquer recurrences?

Note: I have converted my announcement into a question and supplied an answer. What is the best way to solve discrete divide and conquer recurrences? The "Master Theorem" is one way. What other ...
9
votes
1answer
209 views

What's the most efficient way to put all the stones in one pile?

There are $k$ piles of $n_i$ stones, on every move you can choose two piles with sizes $a$ and $b$ and if $a \ge b$ take from the first pile $b$ stones and put to the second one, on other hand if $a ...
0
votes
0answers
89 views

Count the number of transitive functions over set of size n

What is the most efficient way to compute the number of transitive functions over a set of n variables. I cant think of anything but brute force.
0
votes
1answer
24 views

Similar statements for expressions

Is there an easy way to find out which 3 are similar from the left and right side, it will be nice with some tricks to find it out, or if you have some rules that can be followed. $$ {lg\,n +\frac12} ...
2
votes
0answers
114 views

What is Algorithmic Graph Theory? [closed]

I'm an undergraduate and I signed up for a course next semester called Algorithmic Graph Theory. The course description doesn't give any details on the contents of the class, and there's no listing of ...
2
votes
3answers
8k views

Largest prime factor of 600851475143 [duplicate]

I'm trying to use a program to find the largest prime factor of 600851475143. This is for Project Euler here: http://projecteuler.net/problem=3 I first attempted this with the code that goes through ...
1
vote
1answer
230 views

No of labeled trees with n nodes such that certain pairs of labels are not adjacent.

What is the number of trees possible with $n$ nodes where the $i$th and $(i+1)$th node are not adjacent to each other for $i \in \left[0,n-1\right)$ and $$i/2 = (i+1)/2.$$ (integer division) (nodes ...
2
votes
1answer
167 views

Computing RSA Algorithm

Modulus $N=247$; encryption exponent $r=7$ Encrypt $100$; Decrypt $120$. $Solution:$ Encryption of $100$ is $35$. Decryption exponent of is $31$. Decryption of $120$ is $42$. For a discrete math ...
0
votes
1answer
1k views

How to use Warshall's Algorithm

This question appeared on my homework and I don't have the slightest idea how to solve it! ...
3
votes
0answers
119 views

Difference between two sets of data points

I'm making a simple calibration of a z-stage, by measuring a number of points in one direction with a constant $\Delta$Z between each sample. Then I reverse the direction and measure the same number ...
1
vote
1answer
484 views

Topological Sorting in Linear Order for Hasse Diagram

I have come across an exam review question that I am stuck on. The question states: Use topological sort to compute a valid linear order of the elements for the following Hasse Diagram: This is ...
0
votes
1answer
85 views

Big-O Big theta Big omega papers

I'm studying algorithms complexities by myself (my university didn't it to me) and I'd love if someone could help me in finding good resources to learn fundamental algorithms complexities proofing. ...