1
vote
2answers
67 views

nth convolved Fibonacci numbers of order 6 modulo m

Problem: Find the coefficient of xk in (1−x−x2)-6 modulo m. Constraints: k≤264 m≤105, m can be a composite number. I have 10^5 such queries to process in 2 sec, so O(log k) for each query ...
1
vote
0answers
50 views

Solving the recursion $F(n)=K_0F(n-1)/(n-1)+K_1F(n-2)/(n-2)$

Please help me in solving the recursion $F(n)=K_0\frac{F(n-1)}{n-1}+K_1\frac{F(n-2)}{n-2}$, preferably using power series for the values of $F(n)$ in terms of $n$. Here $K_1$ and $K_2$ are ...
5
votes
3answers
363 views

Recurrence with varying coefficient

Problem 1 $$ {\rm f}\left(n\right) = \frac{1}{n}\, \left[{\rm f}\left(n - 1\right)k_{0} + {\rm f}\left(n-2\right)k_{1}\right]\tag{1} $$ ( This can also be written as ${\rm Q}\left(n\right) = ...
1
vote
1answer
32 views

Understanding an algorithm

I want to understand the above algorithm. My solution says that the algorithm should return $0$ if $n$ is a prime or 1. Otherwise it returns the smallest (positive) non-trivial divisor. Lets ...
0
votes
0answers
31 views

Inversion and permutations

Let call two arrays A and B with length n almost equal if for every i (1 <= i <= n) CA(A[i]) = CB(B[i]). CX[x] equal to number of index j (1 <=j <= n) such that X[j] < x. For two ...
0
votes
1answer
26 views

Change of variables in function $T(n)$.

I've been given this recurrence to solve: $T(n) = T(\sqrt n) + \theta(lglgn)$ And I'm told that the way to solve it is to let $m = lgn$, so that the recurrence can be rewritten as follows: $S(m) = ...
0
votes
1answer
28 views

Is $f(n) + O(f(n)) = \theta(f(n))$?

I've been asked to show whether this is always, never or sometimes true. I think I understand that in this situation, $O(f(n))$ can be treated as a macro for some function $g(n)$. So if the equation ...
0
votes
0answers
21 views

Max Function Notation [duplicate]

I've been asked whether the following is always, never or sometimes true: $f(n) + g(n) = \theta(\max(f(n), g(n)))$ I understand the definition of theta notation, but I'm not sure how to read the ...
4
votes
2answers
104 views

Count Number of Sequences

The question is: Given a sequence of positive integers A={1,2,3,...,N}. Count the number of sequences you can get after making K swaps between adjacent element on it for a given N ? My approach: My ...
2
votes
1answer
57 views

how to compute a^x %p

Hi I want to calculate $a^x mod p$ where p is prime and $x$ is large. What I know is that since $p$ is prime, it forms a cyclic group with order $p$ ie $ a^p$ $mod$ $p = a$. Thus, my problem will be ...
1
vote
1answer
34 views

Is the property reflexive, symmetric, anti-symmetric, transitive, equivalence relation, partially ordered given the relation below?

I'm working on this and I'm supposed to figure out if the following properties apply to the below relations. Properties are: ...
0
votes
1answer
39 views

if $f(n)=\Theta(n^2)$ and $g(n) = \Theta(n^2)$ then $(f+g)(n)=\Theta(n^4)$ where we define $(f+g)(n)=f(n)+g(n)$ ∀$n$.

if $f(n)=\Theta(n^2)$ and $g(n) = \Theta(n^2)$ then $(f+g)(n)=Θ(n^4)$ where we define $(f+g)(n)=f(n)+g(n)$ $∀ n$. Is the above true or false. I would say its false but honestly its a guess and i ...
0
votes
1answer
75 views

How many 10-bit strings with more 0’s than 1’s?

I have to pick the answer from: a.512 b.386 c.256 d.252 e.none of these The number of bit strings of length 10 with n 0's (or n 1's in fact): is C(10,n) , where C(a,b) = a! / [(a-b)!b!] is the ...
4
votes
2answers
60 views

What is the value of the following? $3^{302} \mod 5.$

I have to choose from a. 0 b. 1 c. 2 d. 3 e. 4 I think its e. 4 because $$3^{302} = 3^{300} \cdot 3^2 = 3^{4\cdot 75} \cdot 3^2 = (3^4)^{75} \cdot 3^2.$$ Applying Fermat's Little Theorem to ...
1
vote
0answers
21 views

Ideal shrinking of discrete randomness source

I have a discrete randomness source that emits random integer numbers in range [0..N) with uniform distribution. I need to reduce this distribution, limiting it to ...
0
votes
1answer
69 views

Properties of the relation R on the set of all real functions

So... I'm working on this and I'm supposed to figure out if each of these properties are pertinent. Can someone please help me? Thank you! Properties: Reflexive Symmetric Anti-Symmetric Transitive ...
1
vote
2answers
49 views

Time complexity (in Θ-notation) in terms of n?

Can someone please help me with this problem? Any help would be much appreciated? Thanks in advance!! ...
2
votes
1answer
52 views

What is the time complexity (in Θ-notation) in terms of n?

Consider the following algorithm, where $n$ is a parameter. ...
1
vote
0answers
37 views

How to find the lengths of the shortest paths in a directed graph in $O(m)$ steps?

Let $G = (V,A)$ be a directed graph for which it is true that if $(v_i , v_j) \in A$, it is implied that $i < j$. Question: How does one construct an $\mathcal{O}(m)$ algorithm to find the ...
2
votes
3answers
61 views

Why in formulas a return value of a function sometimes shown as an argument?

Sorry for a perhaps newbie question, I had a hard time in the school. Well, the title says the problem, let's look at example, which I stole from the coursera video-lectures about an algorithms: ...
0
votes
1answer
31 views

Smoothing Spline Example

I am learning the smoothing spline method. I saw that smoothing spline is a penalty term to reduce overfitting in linear regression. Given dataset {$(x_1,y_1),(x_2,y_2)..(x_n,y_n)$}So the formular ...
1
vote
1answer
56 views

Dijkstra's Algorithm- Two equal weights, one leads to a shorter path. What to do?

I am confused about this situation that happened to me as I was trying to solve a shortest path problem using Dijkstra's Algorithm. '$s$' is the starting point and '$t$' is finish. When I reach to ...
1
vote
2answers
25 views

Finding the number of solutions satisfying an equation?

Given one condition $x_1+x_2+x_3=n$ where n is known number. Given a set of data X={$a_1,a_2....a_n$}. Can you help me find all possible cases satisfying the above condition $x_1+x_2+x_3=n$ ???
1
vote
1answer
43 views

Proving breath first traversal on graphs [duplicate]

I am trying to proof the following algorithm to see if a there exists a path from u to v in a graph G = (V,E). ...
0
votes
1answer
54 views

Proofing a Reachable Node Algorithm for Graphs

I am trying to proof the following algorithm to see if a there exists a path from u to v in a graph G = (V,E). ...
2
votes
0answers
39 views

Prove that (x+1)! is not O(x!)

Discrete math question which is as follows: Prove that (x+1)! is not O(x!) using only the definition of Big-Oh notation. (Hint!: log(a * b) = (log a + log b)) I used a proof by contradiction saying ...
0
votes
1answer
41 views

Understanding Recursive algorithm using FIB

I am studying for an exam, and I came across this question, I think I got the answer correct, just need some validation. ...
0
votes
1answer
32 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
1answer
71 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
42 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
86 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
32 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
2answers
266 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
55 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
194 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
35 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
327 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
172 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
68 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
44 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
98 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
44 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
85 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
39 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
60 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
173 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
106 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
45 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
156 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
24 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 ...