algorithms – Counting primitive operations on recursive functions

I’m reading Algorithm Design and Applications, by Michael T. Goodrich and Roberto Tamassia, published by Wiley. They teach the concept of primitive operations and how to count then in a given algorithm. Everything was clear to me until the moment they showed a recursive function (a simple recursive way to calculate the maximum value of an array) and its primitive operation count.

The function (in pseudo-code) is this:

Algorithm recursiveMax(A, n):
    Input: An array A storing n ≥ 1 integers.
    Output: The maximum element in A.
    
    if n = 1 then
        return A(0)
    return max{recursiveMax(A, n − 1), A(n − 1)}

where A is an array and n its length. The author states what follows concerning how we calculate the number of primitive operations this function has:

As with this example, recursive algorithms are often quite elegant. Analyzing
the running time of a recursive algorithm takes a bit of additional work, however.
In particular, to analyze such a running time, we use a recurrence equation, which
defines mathematical statements that the running time of a recursive algorithm must
satisfy. We introduce a function T (n) that denotes the running time of the algorithm
on an input of size n, and we write equations that T (n) must satisfy. For example,
we can characterize the running time, T (n), of the recursiveMax algorithm as T(n) = 3 if n = 1 or T(n – 1) + 7 otherwise, assuming that we count each comparison, array reference, recursive call, max calculation, or return as a single primitive operation. Ideally, we would like to characterize a recurrence equation like that above in closed form, where no references to the function T appear on the righthand side. For the recursiveMax algorithm, it isn’t too hard to see that a closed form would be T (n) = 7(n − 1) + 3 = 7n − 4.

I can clearly understand that in the case of a single item array, our T(n) would be just 3 (only 3 primitive operations will occur, i.e. the comparision n = 1, the array index A(0) and the return operation), but I cannot understand why in the case where n is not 1 we have T(n-1) + 7. Why + 7? From where did we get this constant?

Also, I cannot comprehend this closed form: how did he get that T(n) = 7(n – 1) + 3?

I appreciate any help.

algorithms – Counting primitive operations on recursive functions

I’m reading Algorithm Design and Applications, by Michael T. Goodrich and Roberto Tamassia, published by Wiley. They teach the concept of primitive operations and how to count then in a given algorithm. Everything was clear to me until the moment they showed a recursive function (a simple recursive way to calculate the maximum value of an array) and its primitive operation count.

The function (in pseudo-code) is this:

Algorithm recursiveMax(A, n):
    Input: An array A storing n ≥ 1 integers.
    Output: The maximum element in A.
    
    if n = 1 then
        return A(0)
    return max{recursiveMax(A, n − 1), A(n − 1)}

where A is an array and n its length. The author states what follows concerning how we calculate the number of primitive operations this function has:

As with this example, recursive algorithms are often quite elegant. Analyzing
the running time of a recursive algorithm takes a bit of additional work, however.
In particular, to analyze such a running time, we use a recurrence equation, which
defines mathematical statements that the running time of a recursive algorithm must
satisfy. We introduce a function T (n) that denotes the running time of the algorithm
on an input of size n, and we write equations that T (n) must satisfy. For example,
we can characterize the running time, T (n), of the recursiveMax algorithm as T(n) = 3 if n = 1 or T(n – 1) + 7 otherwise, assuming that we count each comparison, array reference, recursive call, max calculation, or return as a single primitive operation. Ideally, we would like to characterize a recurrence equation like that above in closed form, where no references to the function T appear on the righthand side. For the recursiveMax algorithm, it isn’t too hard to see that a closed form would be T (n) = 7(n − 1) + 3 = 7n − 4.

I can clearly understand that in the case of a single item array, our T(n) would be just 3 (only 3 primitive operations will occur, i.e. the comparision n = 1, the array index A(0) and the return operation), but I cannot understand why in the case where n is not 1 we have T(n-1) + 7. Why + 7? From where did we get this constant?

Also, I cannot comprehend this closed form: how did he get that T(n) = 7(n – 1) + 3?

I appreciate any help.

domain driven design – Should the Use Case be responsible for transforming its primitive parameters into typed data for the Entity to use?

I’m building a Use Case for creating blog posts, this Use Case has its own “DTO”, which is basically a parameter object with only primitive data, as follows:

Use Case’s DTO (Parameter Object):

export class CreatePostInput {
  public id: string;
  public slug: string;
  public title: string;
  public authorId: string;
  public platform: string;
  public tags: string();
  public images: string();
  public content: string;
  public createdAt: string;
}

inside my Use Case, I have to create an entity that is built with most of the data of the Use Case’s DTO, the “problem” is that most of the entity’s properties are typed with Value Object’s, for example:

Post Entity

export class Post {
    private id: PostId;
    private slug: Slug;
    private title: Title;
    private authorId: AuthorId;
    private platform: Platform;
    private tags: Tag();
    private images: Image();
    private content: string;
    private createdAt: Date;
}

Use Case:

export class CreatePost {

  public async create(CreatePostInput: CreatePostInput): Promise<CreatePostOutput> {

    if (CreatePostInput.images.length > 0) {
      // do something...
    }

    // some more logic using typed data

    const PostEntity = new Post(CreatePostInput);
    // ...
    // return CreatePostOutput
  }

}
  1. Should the Use Case be responsible for creating the entity’s Value Objects or transforming its primitive data into something else? if so, is there a problem with instantiating the Value Objects inside the Use Case?

  2. If I happen to have more entities and more Value Objects in this use case, how should i organize all this creation? builder pattern?

abstract algebra – Is the following a primitive p-th root of unity?

I guess I am sort of confused as to what constitutes a primitive p-th root of unity versus a regular p-th root of unity… for example if q is a prime then is

$$
q^{frac{p-1}{p}}
$$

a primitive p-th root of unity or just a normal pa-th root of unity? How can I test to see whether or not this root is primitive? I’m working through Dummit and Foote, so if there are any specific references you can point me towards that would be great.

design – Why does the C++ standard still allow uninitialized primitive variables?

(…) so that objects of primitive type (int, unsigned, float, double, bool, char) get default-initialized to 0? Wouldn’t this prevent an entire class of typical beginner mistakes?

I don’t think so. Usually the actual mistake is that the programmer either assumed the variable would be initialized to something useful after the declaration, or simply forgot to init it right there.

In many cases forcing zero initialization would only mask the problem. 0 is a valid value for all of the fundamental types but that doesn’t imply it’s useful and semantically valid for the use case in question. Consider:

/* Just for demonstration! This is BAD code! */

int result;  // uninitialized

// The function is supposed to initialize `result` to >=1 using an out parameter.
// But it’s buggy and doesn’t touch `result` at all.
fill_result(result);

// `result` is read here in some way.

Currently reading result at the end is undefined behaviour. Forced zero init wouldn’t improve the situation because the variable still does not contain a semantically valid value. It’s expected to hold a value greater than 0, after all. The error is just masked and likely to lead to problems later in the execution of the program. That’s very similar to undefined behaviour.

I can’t speak for the C++ committee, of course. And I cannot look into the mind of the C++ community as a whole. But I guess this is at least one important part of the reason why forced zero init isn’t considered as a change to the language – “you don’t pay for what you don’t use” being another important part.

Imo a better, although ultimately just as hopeless, idea would be to disallow uninitialized variables altogether. That would solve the problem, but would also be a backwards incompatible change to a commonly used feature. A proposal that’s guaranteed to break a vast amount of existing code is highly unlikely to make it into the standard.

What’s left is static and dynamic code analysis to detect such bugs.

Primitive elements in Hopf algebras over the integers

Let $H$ be a Hopf algebra over $mathbb Z$, and assume that $H$ is cocommutative, graded, generated in degree $1$, and connected (its degree-$0$ part is $mathbb Z$).

Are there nice, natural conditions that will enforce that $H$ is a universal enveloping algebra of a Lie algebra over $mathbb Z$?

For example, if $H$ is $mathbb Z$-free, then the Milnor-Moore theorem implies $Hotimesmathbb Q=U(P)$ for $P’$ the space of primitives in $Hotimesmathbb Q$, and presumably $P’=Potimesmathbb Q$ for $P$ the $mathbb Z$-module of primitives in $H$.

I’m sure this works in a much more general setting, but I failed to locate relevant papers or books on Hopf algebras over non-fields.

Note that this question is related to the MO question
Integral Milnor-Moore theorem, though it seems orthogonal.

java – Optional int parameter ‘id’ is present but cannot be translated into a null value due to being declared as a primitive type

me encuentro con un error que no sé por donde cogerlo. Estoy realizando un api/rest de android studio (RetroFit) con SpringBoot (como servidor).
Resulta que me encuentro con este error:

 Optional int parameter 'id' is present but cannot be translated into a null value due to being declared as a primitive type. Consider declaring it as object wrapper for the corresponding primitive type.

Expongo retrofit interface:

 @PUT("editPlayer{id}")
    Call<PlayerDto> editPlayer(@Body PlayerDto player, @Path("id") int id);

Expongo llamada al servidor:

Settings.RESPONSE_CLIENT.getService()
.editPlayer(editedPlayer, 53)
.enqueue(new Callback<PlayerDto>() {
   @Override
   public void onResponse(Call<PlayerDto> call, Response<PlayerDto> response) {
      editedPlayer = response.body();
      typeError = 0;
   }

   @Override
   public void onFailure(Call<PlayerDto> call, Throwable t) {
      Log.e("Error: ", t.getMessage());
      typeError = 2;
   }
});

Expongo servidor Controller:

@PutMapping("/editPlayer{id}")
    public Player editPlayer(@RequestBody Player player, @Param("id") int id) {
        return service.editPlayer(player.getUsername(), id);
    }

Expongo servidor PlayerService:

public Player editPlayer(String username, int id) {

        repoPlayer.editUserNamePlayer(username, id);
        Optional<Player> player = repoPlayer.findById(id);

        return player.get();
    }

Expongo IPlayerRepository, aunque solo es la “Query” :

@Modifying
    @Query("UPDATE Player p SET p.username= :username WHERE p.id= :id")
    public void editUserNamePlayer(@Param("username")String username, @Param("id") Integer id);

Realizo pruebas con Insomnia y no tengo ningún problema adjunto imagen:
imagen de captura test insomnia put api/rest

Pero no tengo manera de enviar la id desde android studio, parece que se le envia “null”.
Ni ingresandolo a mano ni recogiendolo por parámetro.

Necesito ayuda, muchas gracias de antemano.

computability theory – Ordinal numbers reachable by primitive recursive ordinal functions in omega

$ def PRo {{mathcal { PR } _ omega}} $
The class of primitive recursive ordinal functions in the constant omega function (henceforth denoted by $ PRo $) are defined by Jensen and Karp (1971) as the smallest class of functions mapping finite tuples of ordinals to ordinals, which contains the constant omega function, the constant zero function, the successor function, the order testing function and all projections, and is closed under substitution and primitive recursion. More precisely, we have the following.

All the initial functions of the following forms are in $ PRo $:

  • $ Omega ( alpha ) = omega $
  • $ Z ( alpha ) = 0 $
  • $ S ( alpha ) = alpha + 1 $
  • $ C ( alpha , beta , gamma , delta ) = begin {cases} alpha & gamma < delta \ beta & gamma ge delta end {cases} $
  • $ P ^ n _ m ( alpha _ 1 , dots , alpha _ n ) = alpha _ m $, for all positive integers $ n $ and $ m $ with $ m le n $

Every function defined by means of the following rules using previously constructed functions in $ PRo $ is itself in $ PRo $:

  • $ f ( alpha _ 1 , dots , alpha _ m , beta _ 1 , dots , beta _ n ) = g big( h ( alpha _ 1 , dots , alpha _ m ) , beta _ 1 , dots , beta _ n big) $
  • $ f ( alpha _ 1 , dots , alpha _ m , beta _ 1 , dots , beta _ n ) = g big( alpha _ 1 , dots , alpha _ m , h ( alpha _ 1 , dots , alpha _ m ) , beta _ 1 , dots , beta _ n big) $
  • $ f ( alpha _ 1 , dots , alpha _ m , beta ) = g big( alpha _ 1 , dots , alpha _ m , sup _ { gamma < beta } f ( alpha _ 1 , dots , alpha _ m , gamma ) big) $

Let’s say an ordinal number $ alpha $ is $ PRo $-reachable whenever there is a unary function $ f $ in $ PRo $ such that $ f ( 0 ) = alpha $.

My question is how to characterize the $ PRo $-reachable ordinal numbers. What is the supremum of the $ PRo $-reachable ordinals? What is the least ordinal not $ PRo $-reachable? Do they coincide (i.e. is the class of $ PRo $-reachable ordinals downward closed)?

I have only the simple observation that each $ PRo $-reachable ordinal must be countable, and as there are only countably many functions in $ PRo $, not all countable ordinals are $ PRo $-reachable. I also suspect that there is a connection with $ omega _ 1 ^ { text { CK } } $, as $ PRo $ is recursively defined, but this feeling is a loose one.


Jensen, Ronald B.; Karp, Carol, Primitive recursive set functions, Axiomatic Set Theory, Proc. Sympos. Pure Math. 13, Part I, 143-176 (1971). ZBL0221.02027.

computability – How can primitive recursion be a special case of minimization?

Your suspicion is correct. Without primitive recursion we get a very small class of functions, namely maps of the form $f(vec{x}) = x_i + m$, possibly with some undefined values.

Let $mathcal{F}_k$ be the least class of partial maps $f : mathbb{N}^k to mathbb{N}$ closed under $0$, successor, projections, composition and minimization.

Theorem: For every $f in mathcal{F}_k$ there exist $i$ and $m$ such that, for all $vec{x} = (x_1, ldots, x_k) in mathbb{N}^k$, either $f(vec{x})$ is undefined or $f(vec{x}) = x_i + m$.

Proof. We proceed by induction on the structure of $f$. It is obvious that $0$, successor, projections, and compositions preserve the stated property. Now consider $f in mathcal{F}_k$ which is defined by minimization of $g in mathcal{F}_{k+1}$, so that
$$f(vec{y}) = min {x in mathbb{N} mid g(x, vec{y}) = 0}.$$
By induction hypothesis there are two possibilities:

  1. There exists $m$ such that $g(x, vec{y}) = x + m$ whenever $g(x, vec{y})$ is defined. In this case:

    • If $m = 0$ then $f(vec{y}) = 0$
    • If $m > 0$ then $f$ is everywhere undefined
  2. There exists $m$ and $i$ such that $g(x, vec{y}) = y_i + m$ whenever $g(x, vec{y})$ is defined. In this case:

    • if $m = 0$ then $$f(vec{y}) = begin{cases}0 & text{if $y_i = 0$ and $g(0, vec{y})$ is defined}\ text{undefined} & text{otherwise} end{cases}$$
    • if $m > 0$ then $f(vec{y})$ is everywhere undefined.

In all cases minimization preserves the stated property. $Box$

Let us also try to speculate how the falacy “primitive recursion is a special case of minimization” arises. Suppose $f : mathbb{N} to mathbb{N}$ is defined by primitive recursion by
begin{align*}
f(0) &= k\
f(n+1) &= h(n, f(n)),
end{align*}

where $h : mathbb{N}^2 to mathbb{N}$ is primitive recursive. Then there is a primitive recursive function $g : mathbb{N} times mathbb{N} to mathbb{N}$ such that
$$
g(x, y) = begin{cases}
0 & text{if $f(x) = y$},\
1 & text{otherwise.}
end{cases}
$$

The map $g$ involves a good deal of arithmetic, encoding of lists as numbers, etc. Cruicially, $g$ may be more complicated than $f$ and $h$.

Therefore, we could define $f$ by minimization as
$$f(x) = min {y mid g(x,y) = 0}.$$
However, we need the entire primitive recursion machinery to get the suitable $g$, so we cannot infer from this that primitive recursion can be dispensed with in the presence of minimization.