CODEWITHSUNDEEP
algorithm
Pat
Pat

Reputation: 43

Dynamic Programming Algorithm Notation

From Chapter 6 of Algorithms, S. Dasgupta, C. Papadimitriou, U. Vazirani, 2006.

I am trying to understand some of the psuedocode with the algorithms at the beginning of this chapter. The first one is the topological sort linearization I understand the dist and min routines. But I do not understand notation min *subscript* (u, v)∈Edges {dist(u) + l(u, v)}. Does anyone know how to describe each piece of that particular notation. Is this cycling through ever node u connected to v by a directed edge?

My second question is the notation in the Longest Increasing Subsequence algorithm. How do you interpret the max{L(i):(i, j)∈Edges}. What does the colon mean in this statement? And in the text I see L(.) and what does that mean?

Upvotes: 0

Views: 162

Answers (1)

Nico Schertler
Nico Schertler

Reputation: 32627

Both minimum and maximum need a domain to operate on. I.e. from a specific set, those operators return the maximum or minimum element.

Both notations are variants to define this domain. The first one basically says: "Considering all pairs (u, v) in the Edges set, find the minimum value of dist(u) + l(u, v).

The second variant defines the set of values: {L(i) : (i, j) ∈ Edges} is the set of all values L(i) that can be formed from the pairs (i, j) in the Edges set. Then, the maximum operator finds the maximum value from this set.

So the differences are marginal. The first one specifies a domain and an expression that maps every element of the domain to a value. The second one directly specifies the set to pick the maximum element from.

Actually, both variants can be used interchangeably. It is probably just some inconsistency between the authors that the book used both.

Upvotes: 0

Related Questions