- #1
- 926
- 483
Greg Bernhardt submitted a new PF Insights post
Intro to Algorithms for Programming
Continue reading the Original PF Insights Post.
Intro to Algorithms for Programming
Continue reading the Original PF Insights Post.
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...
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.
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
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.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.
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.wle said: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.
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.
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.
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.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.
The sooner you sit down to the keyboard, the longer it will take to write your program.
Yes, especially for any non-trivial program.My question is for programming is it really important to write an algorithm first ?
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:I had two questions:
- 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?
- 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 each table-row
for each column in a given table-row
do whatever with that entry
end_for // Inner loop
end_for // Outer loop
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?
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?
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.
PROCEDURE <procedure_name> (<parameters_list>)
<declarations>
BEGIN
<statements to be executed>
END_PROCEDURE
CALL <procedure_name> (<real_parameters_list>)
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 dont feel like to use it.
I see your point and yes, thats 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.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.
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.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 dont feel like to use it.
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
I dont 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 lets say in numerical analysis or in some physics problems.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.
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:...
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.
waiting for the second part :-)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
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.. . . 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.