Maths Notation for Consecutive height differences. Halp!

  • (2 Pages)
  • +
  • 1
  • 2

18 Replies - 1536 Views - Last Post: 01 August 2016 - 02:41 PM

#1 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2386
  • View blog
  • Posts: 5,009
  • Joined: 11-December 07

Maths Notation for Consecutive height differences. Halp!

Posted 01 August 2016 - 12:30 PM

Please help me express this in mathematical notation.

Let's say I have a list of heights in order: (H1, H2...Hn). If I want to find the maximum height difference between two consecutive elements, how do I write that? If I want the sum of the differences, it's easy:

i=1n-1(Hi+1 - Hi)

(of course the "n-1" and "i=1") should be above and below each other.

I'm pretty sure I can't do this:

maxi=1n-1(Hi+1 - Hi)

Relatedly, how would I write the set of height differences between consecutive heights?


Reason for asking: I've been asked to retrospectively write formal specifications for code that already exists. Fun times!

Is This A Good Question/Topic? 0
  • +

Replies To: Maths Notation for Consecutive height differences. Halp!

#2 modi123_1  Icon User is online

  • Suitor #2
  • member icon



Reputation: 13566
  • View blog
  • Posts: 54,125
  • Joined: 12-June 08

Re: Maths Notation for Consecutive height differences. Halp!

Posted 01 August 2016 - 12:44 PM

When you say sum do you mean consecutive sum, or just sum of two elements?

As in items in a list are:
[0] = 5
[1] = 6
[2] = 1
[3] = 7

.. and if you wanted to find [4] it would be 7 + 1... and not 7 + 1 + 6 + 5?
Was This Post Helpful? 1
  • +
  • -

#3 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12187
  • View blog
  • Posts: 45,250
  • Joined: 27-December 08

Re: Maths Notation for Consecutive height differences. Halp!

Posted 01 August 2016 - 12:51 PM

The notation would be:

$$\max_{i \in [n-1]} H_{i+1} - H_{i}$$

Where $[k] = \{1, 2, \ldots, k\}$.

(I am assuming you can parse the LaTeX :P)
Was This Post Helpful? 2
  • +
  • -

#4 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2386
  • View blog
  • Posts: 5,009
  • Joined: 11-December 07

Re: Maths Notation for Consecutive height differences. Halp!

Posted 01 August 2016 - 01:03 PM

Oh cool. Thanks!

Assuming n = 4, does [n-1] expand to [1, 2, 3]?

Could I also write [1, n-1]?



I think I'm missing something with the where part. I don't understand how it relates to the rest of it, particularly where k comes in.

modi123_1, say I have the heights:

(10, 20, 20, 45, 47)

The differences would be:

(10, 0, 25, 2)

and the maximum difference would be

25

Tripple post:

Is this correct?

\begin{equation} \label{max height diff}
\mathit{answer} = \max_{i = 1}^{n - 1}(H_{i+1} - H_{i})
\end{equation}


I like it because it's closer to my original thoughts.

But I only like it if it is also correct.

This post has been edited by cfoley: 01 August 2016 - 01:12 PM

Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12187
  • View blog
  • Posts: 45,250
  • Joined: 27-December 08

Re: Maths Notation for Consecutive height differences. Halp!

Posted 01 August 2016 - 01:14 PM

We have [3] = \{1, 2, 3\}, which is a set. Note that [3] is not a list/tuple.

Quote

Could I also write [1, n-1]?

I would avoid introducing new notation. The bracket notation [n] = \{1, 2, ..., n\} is fairly standard. You see it in texts like Diestel's Graph Theory text and research papers. [1, n] is not standard notation.
Was This Post Helpful? 1
  • +
  • -

#6 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2386
  • View blog
  • Posts: 5,009
  • Joined: 11-December 07

Re: Maths Notation for Consecutive height differences. Halp!

Posted 01 August 2016 - 01:16 PM

How about this?

\begin{equation} \label{max height diff}
\mathit{answer} = \max_{i = 1}^{n - 1}(H_{i+1} - H_{i})
\end{equation}

Was This Post Helpful? 0
  • +
  • -

#7 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12187
  • View blog
  • Posts: 45,250
  • Joined: 27-December 08

Re: Maths Notation for Consecutive height differences. Halp!

Posted 01 August 2016 - 01:28 PM

It's not an iteration. So \max_{i=1}^{n-1} isn't formal notation. The mathematical programming formulation deals with constraints and sets. You have an objective function you want to maximize or minimize with respect to constraints. You should really write:

\max_{i \in [n-1]} H_{i+1} - H_{i}


As an afterthought- are you only interested in magnitude or sign as well? I.e., should your objective function be H_{i+1} - H_{i} or |H_{i+1} - H_{i}| ?
Was This Post Helpful? 1
  • +
  • -

#8 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2386
  • View blog
  • Posts: 5,009
  • Joined: 11-December 07

Re: Maths Notation for Consecutive height differences. Halp!

Posted 01 August 2016 - 01:38 PM

Thanks for the explanation. I'm much happier with that now.

The input is constrained to be sorted so the result will alway be positive. The ABS notation isn't necessary but I'll have a think about weather it adds clarity.

However, that leads to another question. How should I go about describing this "list" of heights. It's not a set as there might be duplicates, and as I described, the ordering is important.
Was This Post Helpful? 0
  • +
  • -

#9 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12187
  • View blog
  • Posts: 45,250
  • Joined: 27-December 08

Re: Maths Notation for Consecutive height differences. Halp!

Posted 01 August 2016 - 01:40 PM

It's a tuple. You can supply the tuple upfront. Note that a tuple is an element from the Cartesian product of sets. So if we look at (x, y) in the Cartesian plane, (x, y) \in \mathbb{R}^{2}.

I'll also comment that the mathematical programming formulation is useful to know. In operations research, it is common to cope with hard problems by using a linear programming relaxation. That is, we construct an Integer-Linear Programming formulation (note that ILP is NP-Hard) and relax the integer variables to be real-variables. There are algorithmic techniques like branch-and-bound or cutting planes for polytopes to obtain integer solutions (which may not be optimal).
Was This Post Helpful? 1
  • +
  • -

#10 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2386
  • View blog
  • Posts: 5,009
  • Joined: 11-December 07

Re: Maths Notation for Consecutive height differences. Halp!

Posted 01 August 2016 - 01:56 PM

All right, so if I want to describe the tuple of height differences, could I write something like this?

\left\{ {(H_{i+1}-H_{i}) \mid i \in [i-1]} \right\}


Mathematical notation has been one of my weaker areas for a while. I can generally read it OK but writing it isn't somehting I have practised.
Was This Post Helpful? 0
  • +
  • -

#11 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12187
  • View blog
  • Posts: 45,250
  • Joined: 27-December 08

Re: Maths Notation for Consecutive height differences. Halp!

Posted 01 August 2016 - 01:57 PM

I would just stick with the tuple of heights, rather than their differences. It's easier to work with it, and you don't get bogged down in notation. :)

\max_{i \in [n-1]} H_{i+1} - H_{i} s.t.
H = (H_{1}, ..., H_{n})

Where you replace H_{1}, H_{2}, ..., H_{n} with your fixed values.
Was This Post Helpful? 1
  • +
  • -

#12 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2386
  • View blog
  • Posts: 5,009
  • Joined: 11-December 07

Re: Maths Notation for Consecutive height differences. Halp!

Posted 01 August 2016 - 02:04 PM

That's not really an option for me. :(/>

The thing I posted above would look a bit like this:

{(Hi+1 - Hi) | i ∈ [n-1]}

This post has been edited by cfoley: 01 August 2016 - 02:05 PM

Was This Post Helpful? 0
  • +
  • -

#13 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12187
  • View blog
  • Posts: 45,250
  • Joined: 27-December 08

Re: Maths Notation for Consecutive height differences. Halp!

Posted 01 August 2016 - 02:22 PM

So this: {(H_{i+1} - H_{i}) | i ∈ [n-1]} is a set of ordered pairs.

Quote

That's not really an option for me. :(

Can you clarify this? I was under the impression that:

Quote

Let's say I have a list of heights in order: (H1, H2...Hn). If I want to find the maximum height difference between two consecutive elements, how do I write that?



So we have:

INSTANCE: A sequence H of non-negative integers ordered in non-decreasing order.

OUTPUT: The maximum difference of consecutive terms.


So if we let n := |H|, then the mathematical program would be:

\max_{i \in [n-1]} H_{i+1} - H_{i}


Does this sound correct? If not, what details am I missing? :)
Was This Post Helpful? 1
  • +
  • -

#14 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2386
  • View blog
  • Posts: 5,009
  • Joined: 11-December 07

Re: Maths Notation for Consecutive height differences. Halp!

Posted 01 August 2016 - 02:30 PM

Sorry for the confusion. You have understood (and answered) my original question perfectly. Thanks!

I'm now asking a new question where I want to describe a tuple containing the differences.

Quote

So this: {(H_{i+1} - H_{i}) | i ∈ [n-1]} is a set of ordered pairs.


I don't understand how I have accidentally turned it into pairs. Does this bit (H_{i+1} - H_{i}) not find the difference between the elements in the pairs?

Is it straightforward to make it describe a tuple rather than a set?
Was This Post Helpful? 0
  • +
  • -

#15 macosxnerd101  Icon User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12187
  • View blog
  • Posts: 45,250
  • Joined: 27-December 08

Re: Maths Notation for Consecutive height differences. Halp!

Posted 01 August 2016 - 02:31 PM

I would just say: Let D be a tuple of length n-1, where D_{i} = H_{i+1} - H_{i}.

Sometimes English helps. :)
Was This Post Helpful? 1
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2