Intro to Algorithms for Programming - Comments

[QuantumQuest]

Greg Bernhardt submitted a new PF Insights post

Intro to Algorithms for Programming

Continue reading the Original PF Insights Post.

 

[wle]

Er,

max = -30000        ! we give some arbitrary values for min, max and use the trick
min = 30000         ! of max be low and min be high

If you do this and all the inputs are more than 30000 or if they are all less than -30000 then one of the results will be wrong.

Also, maybe this was left out because it is supposed to be obvious, but I think the way any good programmer/algorithm designer/physicist/mathematician/engineer etc. would do $1 - 2 + 3 - 4 + \dotsb + 99 - 100$ is $$(1 - 2) + (3 - 4) + \dotsb + (99 - 100) = \underbrace{(-1) + (-1) + \dotsb + (-1)}_{50 \text{ terms}} = -50 \,.$$

 

[QuantumQuest]

If you do this and all the inputs are more than 30000 or if they are all less than -30000 then one of the results will be wrong.

Thanks for the comment but I cannot really see your point about giving all numbers greater than $30000$ or less than $-30000$. For each iteration there is a current maximum and minimum. How is it that one of the results will be wrong? You can give the numbers any way you wish.

Also, maybe this was left out because it is supposed to be obvious, but I think the way any good programmer/algorithm designer/physicist/mathematician/engineer etc. would do...

Yes, you can do it this way but don't forget the purpose of the tutorial. I present two methods for a beginner programmer where he / she can see how to (pseudo)code the calculation of a sum. The first is more obvious but the second way is smarter in algorithmic terms i.e. shorter and more concise, so more efficient, where the reader sees how to include the sign as an expression and use it and so eliminate the need for splitting the sum.

 

[Greg Bernhardt]

Great first Insight QQ!

 

[wle]

Thanks for the comment but I cannot really see your point about giving all numbers greater than $30000$ or less than $-30000$. For each iteration there is a current maximum and minimum. How is it that one of the results will be wrong? You can give the numbers any way you wish.

I mean in these two cases one of the outputs of the algorithm at the end (the max or the min) will be wrong. For example, suppose you apply your algorithm to find the maximum and minimum of the ten numbers 38000, 42000, 35000, 43000, 61000, 32000, 47000, 33000, 54000, 73000. These numbers are all greater than the initial value 30000 of min, so the test n < min in your loop never passes and the variable min is never updated. Your algorithm would incorrectly return a minimum of 30000 in that case.

Conversely, if the ten input numbers are all less than -30000, then the minimum will be found correctly but the maximum will be incorrectly reported as -30000.

Yes, you can do it this way but don't forget the purpose of the tutorial. I present two methods for a beginner programmer where he / she can see how to (pseudo)code the calculation of a sum. The first is more obvious but the second way is smarter in algorithmic terms i.e. shorter and more concise, so more efficient

Well it's not a big deal but my point here was: I think the reduction to computing $(-1) \times 50$ is something that a beginner could not only understand, but also quite likely notice for themselves when reading your problem statement. Then they might wonder why you don't say anything about it and proceed to solve it using loops.

 

[Mark44]

I mean in these two cases one of the outputs of the algorithm at the end (the max or the min) will be wrong. For example, suppose you apply your algorithm to find the maximum and minimum of the ten numbers 38000, 42000, 35000, 43000, 61000, 32000, 47000, 33000, 54000, 73000. These numbers are all greater than the initial value 30000 of min, so the test n < min in your loop never passes and the variable min is never updated. Your algorithm would incorrectly return a minimum of 30000 in that case.

Conversely, if the ten input numbers are all less than -30000, then the minimum will be found correctly but the maximum will be incorrectly reported as -30000.

These are good points, but a comment in the algorithm description could mention that it is assumed that all input values are between the two extreme values.

Well it's not a big deal but my point here was: I think the reduction to computing $(-1) \times 50$ is something that a beginner could not only understand, but also quite likely notice for themselves when reading your problem statement. Then they might wonder why you don't say anything about it and proceed to solve it using loops.

The algorithm as presented is fine, IMO, since the focus is on adding the numbers, not on noticing that this particular finite sum could be added by grouping adjacent terms. A comment that for the example in question, another method could be used that would simplify things wouldn't hurt, though. In my experience of teaching college calculus for nearly 20 years, I can assure you that some beginners would not think of the simplification that you used to get the sum.

 

[QuantumQuest]

I mean in these two cases one of the outputs of the algorithm at the end (the max or the min) will be wrong. For example, suppose you apply your algorithm to find the maximum and minimum of the ten numbers 38000, 42000, 35000, 43000, 61000, 32000, 47000, 33000, 54000, 73000. These numbers are all greater than the initial value 30000 of min, so the test n < min in your loop never passes and the variable min is never updated. Your algorithm would incorrectly return a minimum of 30000 in that case.

Conversely, if the ten input numbers are all less than -30000, then the minimum will be found correctly but the maximum will be incorrectly reported as -30000.

Yes, I see what you mean but what you refer to is inside the purpose of the example - that's the way I was taught it too, many years before. If you give numbers that are all greater than $30000$ then you obviously see that $30000$ is less than them from the outset and the same holds true for the $-30000$ i.e. if you give numbers which are all less than it, then $-30000$ is bigger than them from the outset. Then the reader will see what went wrong and will have to stretch the range of numbers for $max$, $min$ as this is just for educational purposes and not a real world situation - also, we're talking about beginning programmers. In any case, I don't present the values of $max$, $min$ as "hardwired" values.

Well it's not a big deal but my point here was: I think the reduction to computing (−1)×50(−1)×50(-1) \times 50 is something that a beginner could not only understand, but also quite likely notice for themselves when reading your problem statement. Then they might wonder why you don't say anything about it and proceed to solve it using loops.

I appreciate your opinion but I don't agree.

 

[QuantumQuest]

In order to be clear about Example 2, I've added a note below the example about the values of min, max and also an alternative way.

 

[Wrichik Basu]

I had two questions:

1. In the article, the end of an "if-else" statement is written as "end_if", while the end of a loop is written as "end_for". What is the system for nested loops and nested conditional statements?
2. In any OOP based language, we have functions. You didn't write too much about functions. So, how are functions mentioned? Is it written like "start function <function_name>()" or something like that? How do I call a function in a later step of the algorithm?

 

[Arman777]

I was given to do 4 project . First we should have to write an algorithm and then we should start to write the codes. But I started with the codes and then I wrote the algorithm which it was kind of useless. My question is for programming is it really important to write an algorithm first ? Well even in the coding part I am thinking an "algorithm" to write the code but I am just not putting those into the steps. In the future years or etc is it really important or its just a tool that we may use or may not use because I don't feel like to use it.

 

[Mark44]

First we should have to write an algorithm and then we should start to write the codes. But I started with the codes and then I wrote the algorithm which it was kind of useless.

In several of your posts about a month ago, it was apparent that you started by writing code without a clear idea of what your algorithm should be. You could have floundered around a lot less if you had started with a clear idea of what the steps needed to be -- IOW, an algorithm. Several people commented that you clearly weren't starting with an algorithm.

In a programming class I had many years ago, the instructor said,

The sooner you sit down to the keyboard, the longer it will take to write your program.

My question is for programming is it really important to write an algorithm first ?

Yes, especially for any non-trivial program.

 

[Mark44]

I had two questions:

1. In the article, the end of an "if-else" statement is written as "end_if", while the end of a loop is written as "end_for". What is the system for nested loops and nested conditional statements?
2. In any OOP based language, we have functions. You didn't write too much about functions. So, how are functions mentioned? Is it written like "start function <function_name>()" or something like that? How do I call a function in a later step of the algorithm?

For #1, keep in mind that @QuantumQuest is writing about algorithms and pseudocode, and that there are no etched-in-stone guidelines or rules for this. You could do something like this, though:

for each table-row
    for each column in a given table-row
        do whatever with that entry
    end_for  // Inner loop
end_for  // Outer loop

For #2, the intent of the article was an introduction to algorithms, aimed at beginning programmers, who likely don't know much about functions just yet.

In an OOP language, you also have objects, which have their own data and their own functions. All procedural languages have functions, at least by some name, so this isn't limited to OOP languages. If you wanted to write an algorithm that used functions, you could say "call Fun1()", and then have a separate part of the algorithm that described what Fun1() was supposed to do, including parameters passed to it, and any value it returned. I suspect that was well beyond the scope of what QuantumQuest was trying to do.

 

[QuantumQuest]

In the article, the end of an "if-else" statement is written as "end_if", while the end of a loop is written as "end_for". What is the system for nested loops and nested conditional statements?

The purpose of using end_if, end_while, end_for. is to denote where the end of a conditional or repetition structure is, while in real Pascal, when there are more than one statements we use "BEGIN" and "END" to denote the beginning and the end of the series of statements. The only exception is the "REPEAT...UNTIL" repetition structure where we don't use "BEGIN", "END". Now, if you have nested conditional or repetition structures in pseudocode, you use the same "end_if", "end_while", "end_for" for the end of each such construct and you align them appropriately in order to show explicitly where each "end_..." refers to.

In any OOP based language, we have functions. You didn't write too much about functions. So, how are functions mentioned? Is it written like "start function <function_name>()" or something like that? How do I call a function in a later step of the algorithm?

In an OOP language we prefer to call it methods because they refer to specific objects and we say x object has a, b, c, d... methods in general, in contrast to functions of an e.g. procedural type language, where functions are constructs which take arguments in a more agnostic i.e. abstract way. In any case, I didn't write about more advanced constructs like procedures and functions - I mention these because I've presented Pascal - like pseudocode, for the two reasons I give in the article

I have omitted more advanced constructs – like procedures and functions for example, for two reasons. First, Pascal is almost not used anymore – I mean the old Turbo Pascal but of course there are modern descendants like Object Pascal, for anything other than educational purposes – and even this, is very limited now. So, anyone wanting to get into the programming realm will likely pick some other language at some point but all the above will still be useful. Second, all this stuff is formally taught along with a real programming language, so it is advisable that a reader that does not have such a requirement in his / her formal courses and / or wants to learn programming on his / her own should follow some tutorial or go through some textbook or other relevant resource, in order to learn the programming basics.

but if you want to write pseudocode for e.g. a procedure you can do it like this

PROCEDURE <procedure_name> (<parameters_list>)

<declarations>

BEGIN

<statements to be executed>

END_PROCEDURE

and for calling it

CALL <procedure_name> (<real_parameters_list>)

The representation of a function in pseudocode is done in a similar way - taking into account the differences between procedures and functions in Pascal.

Now, a note for the above: As I also write in the article, there is no absolute standardization for pseudocode worldwide, as this is not a real programming language. I wrote it the way I was taught it many years before but again the basic ideas are still the same in any type / style of Pascal-like pseudocode.

EDIT: Also a note about <real_parameters_list> above. Here, with "real", I mean the specific arguments used for calling the procedure.

 

[QuantumQuest]

I was given to do 4 project . First we should have to write an algorithm and then we should start to write the codes. But I started with the codes and then I wrote the algorithm which it was kind of useless. My question is for programming is it really important to write an algorithm first ? Well even in the coding part I am thinking an "algorithm" to write the code but I am just not putting those into the steps. In the future years or etc is it really important or its just a tool that we may use or may not use because I don't feel like to use it.

I'll totally agree to what @Mark44 said in post #11. The reason that I began this series of insights for programming from algorithms is that they are an extremely important thing for anyone that wants to be a programmer or at the very least to learn the fundamentals about programming. Pseudocode is a very useful and helpful - for me indispensable, tool to this end. Every beginning programmer is tempted to sit at the keyboard and write the program directly, without thinking about the algorithms - and a little later about the basic data structures needed, first. Well, for simple small programs, there is really not much to think. But when the things are starting to get tougher, if you try to write directly your program then you'll have to think about the most efficient strategy you can follow, about mathematical methods you need to utilize, about the syntax of the language you use, all at the same time. Now, beyond syntax errors that the compiler will complain about, inevitably, various logical errors will escape your attention and all these just because you won't have a design of the program in place. Conversely, if you start writing your program by designing first, what is the optimal strategy to follow i.e. pick the algorithm(s) you need, how you can do the various computations you'll have to do in the most efficient way and finally writing some pseudocode tailored to the specific programming language you'll use, you'll have almost entirely solved the problem for which you want to write code and you'll just have (maybe) to do some minor corrections and implement it in some programming language. The difference between the two above ways of writing your code is not so evident till the time that you'll have to deal with some complicated problem. I highly recommend to take a look at the recommended resource I've put in the article.

 

[Arman777]

I'll totally agree to what @Mark44 said in post #11. The reason that I began this series of insights for programming from algorithms is that they are an extremely important thing for anyone that wants to be a programmer or at the very least to learn the fundamentals about programming. Pseudocode is a very useful and helpful - for me indispensable, tool to this end. Every beginning programmer is tempted to sit at the keyboard and write the program directly, without thinking about the algorithms - and a little later about the basic data structures needed, first. Well, for simple small programs, there is really not much to think. But when the things are starting to get tougher, if you try to write directly your program then you'll have to think about the most efficient strategy you can follow, about mathematical methods you need to utilize, about the syntax of the language you use, all at the same time. Now, beyond syntax errors that the compiler will complain about, inevitably, various logical errors will escape your attention and all these just because you won't have a design of the program in place. Conversely, if you start writing your program by designing first, what is the optimal strategy to follow i.e. pick the algorithm(s) you need, how you can do the various computations you'll have to do in the most efficient way and finally writing some pseudocode tailored to the specific programming language you'll use, you'll have almost entirely solved the problem for which you want to write code and you'll just have (maybe) to do some minor corrections and implement it in some programming language. The difference between the two above ways of writing your code is not so evident till the time that you'll have to deal with some complicated problem. I highly recommend to take a look at the recommended resource I've put in the article.

I see your point and yes, that's exactly me..I enrolled the course I am not sure I can finish it but I ll try my best to do so.I also need to improve my coding skills but I guess I should open another thread for that.

 

[.Scott]

In the future years or etc is it really important or its just a tool that we may use or may not use because I don't feel like to use it.

It depends on what you are going to be doing in future years. If it's going to be basically the same algorithms over and over again, then you're all set.
But if you never write a program that's bigger than what you can hold in your head in one moment, you are not programming at the professional level - or anything close. Things like pseudo-code and flowcharts are the tip of the iceberg. For large systems, you will be dealing with pages of requirements and systems with several components - and a team of developers. The entire project needs to be done very systematically. Perhaps the most important documents will be interface documents - where you describe what the rules are when one system component uses or communicates with another.

When you do flow charts or pseudo code "in the real world", it is generally for one of these reasons:
1) You are writing a design document and you need to explain what the system needs to do. Normally, design documentation does not include the depth that is reached in the coding process - but in some cases it does.
2) You are writing the code for the first time - and you need to work out precisely what needs to happen in a particular module. In this case, you may be drawing things out on a white board or that famous "back of a paper napkin".
3) You are documenting code you have just written. In this case, the pseudo-code will address the issues that need to be communicated - not necessarily every detail.
4) You are changing code or hunting down a bug. Once again, this is "back of the napkin" type stuff. You are writing things out because you want to condense what is in the code to the essential elements of the task at hand.
5) You are "programming" a person. That is, you are providing operator instructions.

 

[.Scott]

As far as that min/max algorithm is concerned: This is a special case where there are exactly 10 values and they are being processed as they are being received serially. But to handle the min/max more fluently:

Data //max, min, i, n:INT//         ! here we do variable definition and declaration
i←1                                 ! initialize counter for repetitions
while i≤10 do                       ! while…do repetition for ten numbers
  read n
  if i=1 then
    min = n
    max = n
  else
    if n>max then                   ! if…then conditional structures for comparing numbers
      max←n
    end_if
    if n<min then
      min←n
    end_if
  end_if
  i←i + 1                           ! increase counter by 1 to proceed to the next iteration
end_while
write max,min                       ! display max and min number

 

[Arman777]

It depends on what you are going to be doing in future years. If it's going to be basically the same algorithms over and over again, then you're all set.

I don't know what I ll do in future years. I am a physics student so coding is kind of a language that we should know. But I want to learn more about it so I can be better. Other then the school homeworks I manage to solve 30 project euler questions. But as I said I know just the basics of the coding, it would be better to go deeper not deep as computer scientist or a great programmer but learning the basics of the coding or at least mastering most of the stuff...Like let's say in numerical analysis or in some physics problems.

 

[QuantumQuest]

As far as that min/max algorithm is concerned: This is a special case where there are exactly 10 values and they are being processed as they are being received serially. But to handle the min/max more fluently:...

Yes, that's the addition I did to the insight as an alternative more efficient way presenting only the interesting part and leaving the rest to be filled in by the reader by comparing with the initial algorithm of Example 2. However, for a beginning programmer it is useful to see both algorithms.

 

[scottdave]

So I learned flowcharts, way back when I first took a programming course (Pascal, actually in college). I taught myself BASIC on an Apple II+ from a book, and with some friends. I think maybe that book also used flowcharts to show how the programs worked.

I've heard of pseudocode, but not actually used it. It looks like a good tool to use when developing the algorithm to be programmed.

 

[anorlunda]

Good Insight Article. Congratulations.

Everything I know about this subject came from The Art of Computer Programming: Sorting and Searching. Volume 3 even though it's scope was limited to sort&search, his whole approach to algorithms was IMO the canonical example of the art. I read and re-read it so many times that I could cite page numbers from memory like Bible students cite passages. It would be nice to see it included in your bibliography.

Knuth used pseudocode extensively, and many times I wrote code in different programming languages based on his pseudocode. I think that is the superior way to document any algorithm.

 

[QuantumQuest]

Good Insight Article. Congratulations.

Everything I know about this subject came from The Art of Computer Programming: Sorting and Searching. Volume 3 even though it's scope was limited to sort&search, his whole approach to algorithms was IMO the canonical example of the art. I read and re-read it so many times that I could cite page numbers from memory like Bible students cite passages. It would be nice to see it included in your bibliography.

Knuth used pseudocode extensively, and many times I wrote code in different programming languages based on his pseudocode. I think that is the superior way to document any algorithm.

Thank you very much. For me, as for most people involved with CS and programming, Donald E. Knuth is more than a giant in the fields of Mathematics and Computer Science and I really admire his great contributions in these fields. I have the complete series of the books The Art of Computer Programming and they're really classic. I can't really find another way to describe their great value and their beauty. In this first part of my insights, I have put Concrete Mathematics: A Foundation for Computer Science in the Recommended Bibliography (co-authored by Donald Knuth) in order to point out the great importance of the relevant CS math for the beginner programmer. In the second part of this insights series, where I'll try to give some important things about data structures and some more advanced things about algorithms, I'll definitely include The Art of Computer Programming in the bibliography. In my opinion, Knuth's books are best for a mid-level programmer and beyond but in any case, the great influence of his work and books is present both in explicit and implicit ways in other books, such as the ones I've included in the bibliography in this first part.

 

[Wrichik Basu]

In the second part of this insights series, where I'll try to give some important things about data structures and some more advanced things about algorithms

waiting for the second part :-)

 

[QuantumQuest]

I'll also give my opinion about considering "go to" statements harmful in the third part of this insights series which will be about programming.

 

[scottdave]

. . . I have put Concrete Mathematics: A Foundation for Computer Science in the Recommended Bibliography (co-authored by Donald Knuth) in order to point out the great importance of the relevant CS math for the beginner programmer.

After reading this article, I decided to buy Concrete Mathematics: A Foundation for Computer Science. I found a used one on Amazon for less than $40 (in great condition BTW). It arrived Friday, but I just started reading it. It's pretty impressive, so far. I think it'll be a good resource to hang onto.

 

[scottdave]

Con
I started readingrthe book: Concrete Mathematics A Foundation for Computer Science. The book has various quotes (many from students) in the margin. I like this algorithm for self study on page 173. https://drive.google.com/open?id=0BxUZlTyD-AbqVTFITXdocExtdXZ1NnRjZzJKbGhpS0V6bWJz

How many Homework forum posters decide on a value for N of 1 or less?