# Tagged Questions

13 views

### How do you typically prove recurrence relations?

The median-of-medians algorithm gives a recurrence relation $T(n) = T(n/5)+T(7n/10)+n = O(n)$. If the subgroup was changed to a size 3 or 7, how would this effect the recurrence relation? I came to ...
21 views

I see in some notes from my instructor in Algorithm course that $\Sigma_{i=0}^{log n} (n/2^i)$ has growth bigger than $\Sigma_{i=1}^{n} (i log i)$. i couldn't understand why? any tutorial or hint?
23 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 ...
28 views

### Fast algorithm/formula for serial range of modulo of co-prime numbers [migrated]

In my project, one part of problem is there. But to simplify, here the problem is being formulated. There are two positive co-prime integers: $a$ and $b$, where $a < b$. Multiples of $a$ from 1 ...
37 views

### Question about Horners rule algorithm

I am studying Horner's rule I have a question about an algorithm I found here . I understand that the rule allows you to break down polynomials in to monomials to solve them more easily, so that for ...
29 views

### Time Complexity of one Example Code

i see an example on my note for calculating Time Complexity, but i couldn't understand. anyone could help me.
51 views

### Increasing Growth Rate Challenge [closed]

why from left to right, we have increasing in growth rate? any description for some usual equivalence formula for each of them?
52 views

### local informatics Olympiad and Algorithm

I see one of recent local informatics Olympiad question. i have a trouble to solve it. any idea? hint? or solutions? thanks to all creative man. We have two function $P_1, P_2$ and input an array $n$ ...
46 views

### Hashing With Chaining Collision

We have $1000$ elements with key=1 to 1000, and a hashing function $$h(i)=i^3 \mbox{ mod } 10$$ for an array with length $10$ (array index from $0$ to $9$) with chaining method. What is the ...
112 views

### Water Box with n Liter

I ran into a basic challenging problem. I see an high school local math Olympiad question. we have a box that keep n Liter water. each time we extract 1/k Water from box. how many times (minimum) we ...
93 views

### 2000 Olympiad in Informatics Question on Box

I have an old Olympiad question on informatics. There are 31 boxes. In each box there is one number. We know the number if and only if we open the box. We want to calculate the minimum number of ...
76 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 ...
368 views

34 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 ...
107 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 ...
58 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 ...
42 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: ...
44 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 ...
104 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 ...
63 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 ...
71 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 ...
51 views

59 views

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

Consider the following algorithm, where $n$ is a parameter. ...
39 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: ...
32 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 ...
63 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). ...
55 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 ...
44 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. ...
33 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 ...
43 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 ...
88 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 ...
35 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 ...
288 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 ...
66 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 ...
226 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 ...
39 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 ...
354 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 ...
183 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. ...
69 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 ...
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 ...