0
votes
1answer
46 views

How to deal with summation with log bounds like: $\sum \limits_{i=1}^{\lg (n)}$ [closed]

I came across this summation in my algorithms textbook. I've googled everywhere and can't seem to find anything on how to deal with these types of bounds. (Apparently it equals 2n as n approaches ...
2
votes
0answers
60 views

What is the largest value one can get in game 2048 without new tiles appear

This is a simplified version of the famous game 2048. Given a 4x4 grids with some values chosen from {0, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048}. A value of 0 indicates that the position in ...
1
vote
1answer
17 views

Finding a tight upper-bound on $T(n) = 3T(\frac{2}{3}n)$

Can the master theorem be used to prove a tight upper-bound on $T(n) = 3T(\frac{2}{3}n)$? I've drawn the tree for the recurrence and found a sequence: $n + 2n + ...
3
votes
2answers
133 views

Sums $\sum_{n=1}^{N}\sqrt{4n+1}$

I need to find sum of the first N terms of the sequence whose nth term is as follow : T(n)= $\sqrt{4*n+1}$ So the sequence is : $\sqrt{5}$,$\sqrt{9}$,$\sqrt{13}$,$\sqrt{17}$,$\sqrt{21}$...... ...
0
votes
0answers
28 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 ...
2
votes
2answers
44 views

Rewriting nested summations that sometimes sum to zero

Is there a way of re-writing the following formula in terms of just $n$: $$r = \sum_{i=1}^{n}\sum_{j=i+1}^n\sum_{k=i+j-1}^n 1 $$ From what I understand, when $i+j-1 \gt n$ the inner-most sum is ...
1
vote
2answers
28 views

How can I find The Big Oh bounds for a summation with multiple variables?

I have this as a homework problem so I won't post the same thing. I'll just post what I need to know to move forward. $$ \sum_{i=0}^n 10^i i^2 $$ I'd just like to know how to split this ...
1
vote
2answers
23 views

Add integers to a set number of lists, so that the sum of each completed list is as closely matching to the other lists as possible?

I am trying to figure out how to solve this problem in computer science. I won't go into the programming side of things, but basically what I need is this: I have a list of integers ranging from ...
0
votes
1answer
26 views

Summation of infinte series

Sir, I have three infinite summation $A =J_1 \sum_{n=2}^\infty (n-1) f(n-2) \tag 1$ , $B =\sum_{n=0}^\infty f(n) \tag 2$ and $C =J_2\sum_{n=1}^\infty f(n-1) \tag 3$, with ...
0
votes
1answer
11k views

Solution of Introduction to Algorithms 3rd edition (Cormen)

I'm studying algorithms by Cormen book. I have already find a pdf with the answers of the questions. www2.compute.dtu.dk/~phbi/files/teaching/solution.pdf But it isn't have the all solutions. I'm ...
0
votes
5answers
81 views

Refresh summation formulas

I am trying to refresh on algorithm analysis. I am looking for a refresher on summation formulas. E.g. I can derive the $$\sum_{i = 0}^{N-1}i$$ to be N(N-1)/2 but I am rusty on the and more complex ...
0
votes
0answers
16 views

Summation inside a range

I was a bit bored so I decided to create a program with a function that takes three variables: Upper, Lower, and ...
2
votes
1answer
49 views

Possible Ways to reach a Sum

Imagine that I have a N long set of numbers. I would like to know the possible ways that I could reach a specific sum using only the numbers in my set. As an example: ...
1
vote
2answers
84 views

summation of ceil and floor function

I need a closed solution or a faster algorithm for calculating $$ \sum_{k=1}^{n-1} \left\lceil \frac{n}{k}-1 \right\rceil $$ and $$ \sum_{k=1}^{n-1} \left\lfloor \frac{n}{k} \right\rfloor $$ where $ ...
0
votes
1answer
41 views

Understanding relation between Product and Summation Notation

So I am given the following: $n = \sum_{i=1}^{k}m_{i}$ I am also given $x = \sum_{i=1}^{k}log(m_{i}) = log\prod_{i=1}^{k}m_{i}$ I was only given the first part, however I believe that is a ...
0
votes
1answer
207 views

Calculating run times of programs with asymptotic notation

When calculating the run time of programs using asymptotic notation, I know how to set up the sums for things like for loops, but I'm getting stuck on summing them up. Sorry if this is a dumb ...
1
vote
2answers
33 views

Randomized Algorithm

I asked this question earlier but I wanted to change the problem. A band has tour sites A, B, and C. They get paid every time they play at each tour site, specifically: ...
5
votes
1answer
83 views

Hockey Classics at Matheletics '13

I'm trying to solve a challenge from Matheletics '13: Micheal Nobbs is organizing a training camp for identifying new talents in Indian Hockey. The camp witnessed a total of ($3K+1$) players. Each of ...
0
votes
0answers
12 views

Balanced layout

I've got a set of panels of equal width (but different height) and a container, who's width equals to $n\cdot panel_{width}$. n is number of columns in which I want to arrange the panels. I want to ...
0
votes
1answer
28 views

Need to find N value where each sum A+B is different

I need to find N value (in this case 12, but next time they could more o less) and I need that every sum of two value is a unique number. In the picture below you can see an easy matrix where there ...
0
votes
1answer
71 views

How do I go about manipulating this summation equation to solve it?

In my textbook, Introduction to Algorithms, the following is shown: And I believe I understand that. However, I have a similar equation to the one on the first line, but instead of ...
1
vote
2answers
73 views

How does my textbook solve this summation equation for the answer?

Summations have always been my weakness in mathematics, and it's showing here as I'm very confused how my textbook, Introduction to Algorithms, goes from basically the second half of the following ...
0
votes
1answer
175 views

Maximizing summation given a constraint

I am writing a software-based algorithm to calculate an optimal solution and I am completely stuck. I need to maximize the following summation with respect to x: $ \sum_{k=1}^n {a_k(1+x_k) \over ...
0
votes
1answer
234 views

showing that the summation is bounded by a constant

How can I shows that the summation of $1/k^2$ from k=1 to n is bounded above by a constant? I could bind it by the geometric series from k=0 to n and add 1 to $(1/k^2)$ to get the ratio, r, and get ...
1
vote
1answer
46 views

Sum count algorithm name

I want to find out what this algorithm is called ...
2
votes
1answer
106 views

Proof of correctness of Putzers algorithm

I have a question regarding the proof (seen below) of Putzers algorithm for matrix exponentiation. It's written by our danish lecturer at the university, so I translated the important parts into ...
9
votes
2answers
210 views

Efficient computation of $\sum_{k=1}^n \lfloor \frac{n}{k}\rfloor$

I realize there is probably not a closed form, but is there an efficient way to calculate the following expression? $$\sum_{k=1}^n \left\lfloor \frac{n}{k}\right\rfloor$$ I've noticed $$\sum_{k=1}^n ...
1
vote
0answers
23 views

simple formula to distribute inputs

I need a simple formula to do some math for my inputs to generate max number of fixed values .. Below i wrote a simple logic for the math lets say we have an object that will cost fixed numbers of 4 ...
-1
votes
1answer
100 views

Find the biggest sum from sequence of number which within a range

I need help. How do I find the greatest sum from sequence of number within a finite range, for example: Given sequence {2,5,4,3,6} and the range is 11, so how to find the number within the sequence ...
3
votes
1answer
989 views

Trouble finding closed-form solution to summation

I have this question on my assignment for a computer science course (analysis of algorithms), so any help would be appreciated, but I am not looking for the answer itself. I am trying to find the ...
0
votes
1answer
403 views

Is this formula for the number of nodes for a complete tree or a full and complete tree?

In a lecture it was said that "How many nodes are there in a complete k-ary tree with height h?" and this was the answer: $$ \sum^{h}_{i = 0}k^i $$ where h is the height and k is the max number of ...
0
votes
1answer
69 views

Why is the upper bound of this statement always incremented by 1?

Why is "for j = 1 to n" translate to this? Why is the upper bound always incremented by 1? $$\sum_{j=1}^{n+1}1 $$ Why isn't it $$\sum_{j=1}^n1 $$ "for j = 1 to n" is written in pseudo code btw ...
1
vote
1answer
305 views

Is this why this summation is equivalent to this Theta notation?

So I'm not sure if I misunderstood the lesson or not. $$T(n) =\sum_{j=2}^{n}\Theta(j) = \Theta(n^2) $$ Are these equivalent because: $$ \sum_{j=2}^{n}\Theta(j) = \frac{n(n-1)}2 - \frac{1(1 - 1)}{2} = ...
1
vote
4answers
109 views

A puzzle related to loops.

For a given input $N$, how many times does the enclosed statement executes? for $i$ in $1\ldots N$ loop $\quad$for $j$ in $1\ldots i$ loop $\quad$$\quad$for $k$ in $j\ldots i$ loop ...