2
$\begingroup$

So, for one of my university courses, I have to analyse an algorithm on one of my assignments and identify a loop invariant that would allow for a formal proof of algorithmic correctness.

I believe that I identified it in the form of a sum of all of the elements of an array A that have positive values, ranging from 0 to i (where i is the number of time the algorithm has iterated).

I know how to annotate most of that - you write a capital sigma with “k=0” as a subscript and i as a superscript, followed by A[k] but I’m not sure how to specify that I’m only summing the positive elements, so the kth element of A is only added to the sun if it has a positive value.

The lecturer has assured me that that’s not a problem since I can just explain my answer in words, but I still sort of want to know how to do it properly.

$\endgroup$
3
  • $\begingroup$ CHeck out "Concrete Mathematics: A Foundation for Computer Science" by R. Graham, D. Knuth. The authors introduce a notation at the beginning of the book which addresses your question and which is IMHO quite elegant and flexible. $\endgroup$ Commented Apr 2, 2019 at 10:50
  • $\begingroup$ Is that the same Knuth that “Knuth’s up-arrow notation” is named after? $\endgroup$ Commented Apr 2, 2019 at 11:43
  • 1
    $\begingroup$ @nick012000 yes :) $\endgroup$ Commented Apr 2, 2019 at 15:40

4 Answers 4

Reset to default
3
$\begingroup$

Mathematically an array is typically treated as a vector, and is indexed to indicate where in the array/vector you are. You've written $A[k]$ in your question, but I would suggest that, at least for this part of your analysis, you use a subscript instead and let your vector be $A = (A_1, A_2 \ldots ,A_n)$. Each iteration of the vector can then be written as $A^{(k)}$ and any individual element of the $k^{th}$ iterate can be written as $A^{(k)}_j$.

So, with this notation set up, the positive elements of the array are those where $A_j > 0$.

EDIT: from the comments, it's now clear that you want to add the $k^{th}$ element of the array to the overall sum only after $k$ iterations, and if it's positive.

$$\sum_{j=0}^i \max \{0,A^{(j)}_j\}$$ or, if you want to avoid using additional functions (such as $\max$):

$$\sum_{\stackrel{j=0}{A^{(j)}_j >0}} A^{(j)}_j$$

i.e. the sum of those elements of the array $A$ summed if the $k^{th}$ element is positive after $k$ iterations. (If I might offer some additional advice use $T$ for final time rather than $i$).

$\endgroup$
4
  • $\begingroup$ Thank you for answering, but I’m not sure if this answer correctly answers the question? I’m not looking to perform a summation with each iteration of the loop, which is what I think your summation is saying, I’m looking for a statement that is true at both the beginning and ending of each iteration of the loop - and since the loop is performing a summation, the most useful such value would be a statement of the summation being performed. $\endgroup$ Commented Apr 2, 2019 at 20:33
  • $\begingroup$ Ok, drop the first summation sign and the $(k)$ superscript on A to get $\sum_{A_j>0} A_j$. I found your second paragraph hard to follow: did you mean that after iteration $k$ you have $0<A_j\leq k$ then? $\endgroup$ Commented Apr 2, 2019 at 20:47
  • $\begingroup$ After iteration i, it’s summed the first i elements of the array; then on the next iteration, it goes to the next value of the array, then adds it to the summation total if it’s positive. The value of the summation at i could potentially be any valid positive number because the values of the array could be any valid integers. $\endgroup$ Commented Apr 2, 2019 at 21:05
  • $\begingroup$ @nick012000 I've updated the answer based on your comments. Don't forget, if one of the other answers is clearer to you, you should accept that one :) $\endgroup$ Commented Apr 3, 2019 at 5:37
1
$\begingroup$

There are many, many different ways of notating such an expression, none of them particularly "standard". Mathematical notation is not as agreed-upon as it seems from most undergrad and earlier experience. More algorithmic things are even less agreed-upon. There is no "proper" way short of defining your notation.

At any rate, probably the most "usual" approach would be to define a separate function by cases using a notation like $f(x)=\begin{cases}x,& x>0\\ 0,& x\leq 0\end{cases}$. Then your expression would be $\sum_{k=0}^i f(A[k])$. (Actually, Eevee Trainer's suggestion of defining the sequence $a_k$ is even more likely.) This is not particularly pleasant as we need to define a separate function, and it doesn't really "filter out" from the sum, it just makes the undesired entries $0$. There are some notations to do something like this inline, but they aren't particularly widespread and wouldn't be understood without explanation. One example is $\sum_{k=0}^i (A[k]>0\to A[k];0)$.

A more direct rendition would be to use a notation like $\sum_{k=0,A[k]>0}^i A[k]$ or many variations on this. I'd be more inclined to write this more like $\sum_{k\in[i], A[k]>0}A[k]$ or $\sum\{A[k]\mid k\in [i] \land A[k]>0\}$. Variations on notation like this are reasonably widespread, but there isn't a "standard" way. Most mathematicians would be able to figure out what was intended.

For your particular problem, we can do something a bit hacky to get what you want with notation that is covered in high school. Namely, $\sum_{k=0}^i (|A[k]|+A[k])/2$. Closely related would be $\sum_{k=0}^i \max(0,A[k])$. These are not general solutions for filtering by arbitrary predicates, of course. That said, it can often be valuable to be able to express functions this way, but in most cases it would just be obfuscatory.

In a more computer science context, there is also tons of notation inspired by various programming languages.

$\endgroup$
0
$\begingroup$

I can't think of an elegant way to do this. You could define a set $S$ by the following:

$$S = \{ \text{all} \; k \; \text{such that} \; A[k] > 0 \}$$

Then your desired sum would have the form

$$\sum_{k \in S} A[i]$$

though this isn't much more elegant than really just explaining it in words.

Another way that comes to mind is sort of inspired by the Kronecker delta (in a very tangential way, it was merely what made me think of this approach, even if the two are fairly different in a literal sense).

Let's say your array has $n$ elements, $A[1],A[2],...,A[n]$. Define a sequence of corresponding values $a_1,...,a_n$ by the following:

$$a_k = \left\{\begin{matrix} A[k] & A[k]>0\\ 0 & A[k] \le 0 \end{matrix}\right.$$

where $k=1,2,...,n.$ Then your sum is simply

$$\sum_{k=0}^n a_k$$

in that case.

Personally I'm with your lecturer in the sense that, unless you're doing some sort of further manipulation with these sums, it's better to just say it words. Seems like defining it symbolically, while possible, doesn't really achieve anything meaningfully different, in the sense that the information communicated is the same.

Matter of opinion though, I suppose.

$\endgroup$
0
$\begingroup$

For your next question, please consider using LaTeX notation for the Math part. Just write stuff between two dollar signs! Weird symbols are written with "\". Quick cheat-sheet here: http://web.ift.uib.no/Teori/KURS/WRK/TeX/symALL.html

If I got you correctly, you want to sum all elements on a vector $(x_0, ...x_n)$ removing the negative ones. Well, let $f:\mathbb{R} \rightarrow \mathbb{R}$ where $f(x)=x$ if $x>0$ and $f(x)=0$ otherwise. Now you can write your sum as:

$\sum_{k=0}^{n} x_{k}f(x_k)$

$\endgroup$
2
  • $\begingroup$ @postmortes Thank you! I was not aware of the existence of the "\rightarrow weird symbol" $\endgroup$ Commented Apr 2, 2019 at 7:29
  • 1
    $\begingroup$ You can just use \to ($\to$) instead of \rightarrow, but for variations you'll need things like \Rightarrow ($\Rightarrow$). StackExchange uses MathJax, so the relevant reference is this one. $\endgroup$ Commented Apr 2, 2019 at 7:39

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.