Number of machine instructions generated by code

[justinanthonyhamilton]

Hello, everyone. I recently took a class on Data Structures in C++
(using D.S. Malik's C++ Programming: Program Design Including Data
Structures), and while I learned a good about specific data
structures, I felt that the class was a little too rushed and sparse
for my liking. I passed the class with flying colors, but I think it
would be hard for anyone not to do so. I decided to pick up Robert
Sedgewick's Algorithms in C++ 3rd edition to get a better
understanding of the structures and their algorithms

So I am reading through the introduction and I find a few of the
exercises a little annoying. They either seem extremely vague in what
they are expecting, or else they reference a term not decribed in the
previous text is. I know what an "edge" on a tree is because of my
data structures course, but for a book stating that it is "not just
for programmers and computer-science students" I think it would ease
into the subject matter a little better.

Then I run into something that stumps me - there are a few exercises
asking the minimum and/or maximum number of machine instructions
produced by example programs. Maybe I have completely misunderstood
the language, but I thought that C++ produces a different number of
machine instructions based on the computer platform it is on due to
the fact that it is a high level language. Am I completely mistaken?
Is this something I should know?

 

[Stuart Redmann]

Hello, everyone. I recently took a class on Data Structures in C++
(using D.S. Malik's C++ Programming: Program Design Including Data
Structures), and while I learned a good about specific data
structures, I felt that the class was a little too rushed and sparse
for my liking. I passed the class with flying colors, but I think it
would be hard for anyone not to do so. I decided to pick up Robert
Sedgewick's Algorithms in C++ 3rd edition to get a better
understanding of the structures and their algorithms

So I am reading through the introduction and I find a few of the
exercises a little annoying. They either seem extremely vague in what
they are expecting, or else they reference a term not decribed in the
previous text is. I know what an "edge" on a tree is because of my
data structures course, but for a book stating that it is "not just
for programmers and computer-science students" I think it would ease
into the subject matter a little better.

Just out of curiosity: Does Sedgewick define what he understands under a tree?
If he stated that he sees trees as directed graphs with special properties, I
wouldn't take offense at the word 'edge'.

Then I run into something that stumps me - there are a few exercises
asking the minimum and/or maximum number of machine instructions
produced by example programs. Maybe I have completely misunderstood
the language, but I thought that C++ produces a different number of
machine instructions based on the computer platform it is on due to
the fact that it is a high level language. Am I completely mistaken?
Is this something I should know?

I believe that there actually is some kind of misunderstanding there. Sedgewick
is almost surely not talking about C++ but his own pidgin programming language.
In this language were are only interested in the number of atomic operations
(whichever Sedgewick consideres atomic) that are needed to fulfill a certain
task. If you count how many copy operations, comparison operations and branching
operations are needed, you'll almost surely be on the safe side (some of these
operations may be optimized away by a real compiler, but this is not relevant in
theoretical computer science). Anyway, I believe that you only should determine
the asymptotic run-time behaviour.

Regards,
Stuart

 

[Jerry Coffin]

(e-mail address removed)>,
(e-mail address removed) says...

Hello, everyone. I recently took a class on Data Structures in C++
(using D.S. Malik's C++ Programming: Program Design Including Data
Structures), and while I learned a good about specific data
structures, I felt that the class was a little too rushed and sparse
for my liking. I passed the class with flying colors, but I think it
would be hard for anyone not to do so. I decided to pick up Robert
Sedgewick's Algorithms in C++ 3rd edition to get a better
understanding of the structures and their algorithms

Big mistake!

So I am reading through the introduction and I find a few of the
exercises a little annoying. They either seem extremely vague in what
they are expecting, or else they reference a term not decribed in the
previous text is. I know what an "edge" on a tree is because of my
data structures course, but for a book stating that it is "not just
for programmers and computer-science students" I think it would ease
into the subject matter a little better.

IMO, nearly every other book in earth is written better than this one.

Then I run into something that stumps me - there are a few exercises
asking the minimum and/or maximum number of machine instructions
produced by example programs. Maybe I have completely misunderstood
the language, but I thought that C++ produces a different number of
machine instructions based on the computer platform it is on due to
the fact that it is a high level language. Am I completely mistaken?
Is this something I should know?

You're right and it's wrong -- it's asking for something that's
indeterminate, and you should only rarely care about anyway. From a
viewpoint of writing C++ you should generally have at least a vague idea
of the relative speed of basic operations on different types of
operands, and then look at how many operations are needed to carry out a
particular algorithm. Trying to express this as a number of instructions
executed, however, is generally an exercise in pointless frustration.
Your chances of figuring the number of instructions correctly is
minimal, and even if you did it wouldn't mean anything. A modern
processor can typically execute instructions in parallel if they don't
have data dependencies, so the number of instructions is only loosely
related to speed anyway.