# Tagged Questions

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 ...
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 ...
363 views

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 ...
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 ...
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 ...
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 ...
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: ...
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 ...
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 ...
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 ...
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 ...
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 ...
49 views

52 views

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

Consider the following algorithm, where $n$ is a parameter. ...
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 ...
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: ...
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 ...
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 ...
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$ ???
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). ...
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). ...
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 ...
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. ...
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 : ...
71 views

### efficient algorithm to place people in a specific order

You are preparing a banquet where the guests are government ofﬁcials from many different countries. In order to avoid unnecessary troubles, you are asked to check the list of international conﬂicts in ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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. ...
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 ...