<p>My standard answer for this is the following, copied from <a href="https://cseducators.stackexchange.com/a/4859/1293">another answer</a> I've given here.</p>
<blockquote>
<p>If you want a thorough study of how to approach and develop algorithms, get a copy of:</p>
<p><a href="https://rads.stackoverflow.com/amzn/click/com/038790641X" rel="nofollow noreferrer" rel="nofollow noreferrer">David Gries, The Science of Programming</a></p>
<p>The book will change how you think about algorithms and how they are developed. One of the key ideas is algorithm development from loop-invariants along with pre- and post-conditions. There is a science (hence the name) of modifying post-conditions in order to develop a loop and its invariant.</p>
<p>One of the magical problems in the book is a linear time sort of an arbitrary array that contains only three distinct values (Dutch National Flag). It generalizes to a linear time sort of an array containing a finite number of distinct values.</p>
</blockquote>
<p>It shows algorithm development in a way that results naturally in optimized algorithms.</p>
<p>However any non-trivial book on algorithms should discuss optimization and the various ways it is measured (space, time, average, best case, worst case, ...). Books advertised as &quot;introduction to algorithms&quot; may be a bit shallow, of course.</p>
<p>The gold standard, of course, is the multi-volume <a href="https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming" rel="nofollow noreferrer">The Art of Computer Programming</a> by Donald Knuth. The first chapter of the first book is a nearly complete treatise on the required mathematics. In this series, algorithms are presented in a specially constructed assembly like (very low level) language. The Gries book also uses a specially constructed language for presentation, but it is at about the level of Pascal  or C.</p>
<p>However, if you are interested in <em>Functional Programming</em> (Scheme) instead, you want to start with <a href="https://en.wikipedia.org/wiki/Structure_and_Interpretation_of_Computer_Programs" rel="nofollow noreferrer">The Structure and Interpretation of Computer Programs</a> by Abelson, Sussman and Sussman. While this book will teach you deep concepts of algorithms, it might not be quite in the way you expect as it doesn't focus explicitly on optimization, treating optimization as more of an organic property of algorithms.</p>
<p>In fact, none of these books start with some &quot;algorithm&quot; and say &quot;now, let's optimize it&quot;. I don't think that is a viable approach. Instead, algorithms are developed from the start to optimize on some criterion. But they are interesting partly because it is generally impossible to optimize on more than one dimension simultaneously. So most algorithms involve trade-offs of some kind. Often it is time vs space though there are other possibilities.</p>

CC BY-SA 4.0
2018-06-10T13:32:47.873Z
Actually Donald Knuth warned about worrying about optimization prematurely. When you develop an algorithm without much concern for optimization you are proving whether your requirements are valid. Once you've done that you can do tests that prove if optimization is even something you need to consider. Stick with readable code and you can make it as fast as you need to at any time. Sacrifice readable code chasing optimization and, if it turns out you need to change it, you can't, because you can't read it.
candied_orange
CC BY-SA 4.0
2018-06-10T13:49:07.513Z
@candied_orange, actually Knuth was speaking more generally of programming, not specifically what we have come to recognize as "algorithms", in what we call "The Algorithms and Data Structures" course. In fact, though, it was Tony Hoare who said "Premature optimization is the root of all evil". The idea is that most programs are sufficiently fast that you are wasting time on optimizing them initially. First run a profiler on the program to see where it is spending resources and then optimize those parts if necessary. I interpret the question here more narrowly, however.
Buffy
CC BY-SA 4.0
2018-06-10T13:55:50.027Z
On the other hand, Knuth did say "Beware of bugs in the above code; I have only proved it correct, not tried it." https://en.wikiquote.org/wiki/Donald_Knuth. Also see https://en.wikiquote.org/wiki/C._A._R._Hoare
Buffy
CC BY-SA 4.0
2018-06-10T13:58:35.737Z
Hehe, I've said [something similar](https://softwareengineering.stackexchange.com/a/315968/131624): "I write and run tests that prove it works before I suspect it works".
candied_orange
CC BY-SA 4.0
2018-06-10T14:04:04.583Z
Of course you're free to interpret the question as you like. I'm simply advocating that one of the less theoretical "algorithm optimization techniques" is to just write something simple and readable that meets the requirements first before you give in to making things all weird in the name of speed. That way as you iterate on the problem you only pick up the weirdness you really need.
candied_orange
CC BY-SA 4.0
2018-06-05T00:13:37.213Z
2018-06-05T11:09:41.977Z
2020-06-18T08:36:57.023Z
Buffy
<p>Can anyone suggest some good textbooks on optimization for MSc level? Books with more concrete applications and examples on real problems would be more appreciated.</p>

<p>I am more interested in algorithm optimization techniques rather than something more theoretical like computability theory.</p>

<p>Thanks in advance!</p>

CC BY-SA 4.0
2018-06-04T22:43:16.300Z
I've downvoted because of the lack of context. Optimization is a fairly broad topic, so any qualifiers you could add or any indications of textbooks you've looked at would be super hepful.
thesecretmaster
CC BY-SA 4.0
2018-06-04T23:55:46.017Z
@Buffy Thanks for the reply! I am more interested in algorithm optimization techniques.
velut luna
CC BY-SA 4.0
2018-06-05T04:05:28.933Z
@velutluna Add that information into the question, and hopefully a bunch more information into the question as well, and you will find that your downvotes disappear :) The question is topical, it just needs more information. Also, welcome to [cseducators.se]!
Ben I.
CC BY-SA 4.0
2018-06-05T17:06:20.873Z
Is this a self-learning question, or are you trying to find something to use with your students?
Ben I.
CC BY-SA 4.0
2018-06-06T00:40:29.307Z
I am a student. It is for self-learning.
velut luna
CC BY-SA 4.0
2018-07-03T10:55:44.153Z
See references in Wikipedia article on [Analysis of algorithms](https://en.wikipedia.org/wiki/Analysis_of_algorithms#References). ["Introduction to Algorithms"](https://en.wikipedia.org/wiki/Introduction_to_Algorithms) is the standard in most college level programming courses. [Big O](https://en.wikipedia.org/wiki/Big_O_notation) is the keyword you want to use when searching.
Guy Coder
<resource-request><self-learning><textbook>
Textbook on Optimization
# Textbook on Optimization

(Asked by: username_0 on 2018-06-04)

Can anyone suggest some good textbooks on optimization for MSc level? Books with more concrete applications and examples on real problems would be more appreciated.

I am more interested in algorithm optimization techniques rather than something more theoretical like computability theory.

Thanks in advance!

**Tags:** resource-request, self-learning, textbook

> **Comments:**
> **username_1**: I've downvoted because of the lack of context. Optimization is a fairly broad topic, so any qualifiers you could add or any indications of textbooks you've looked at would be super hepful.  
> **username_0**: @username_4 Thanks for the reply! I am more interested in algorithm optimization techniques.  
> **username_2**: @velutluna Add that information into the question, and hopefully a bunch more information into the question as well, and you will find that your downvotes disappear :) The question is topical, it just needs more information. Also, welcome to [cseducators.se]!  
> **username_2**: Is this a self-learning question, or are you trying to find something to use with your students?  
> **username_0**: I am a student. It is for self-learning.  
> **username_3**: See references in Wikipedia article on [Analysis of algorithms](https://en.wikipedia.org/wiki/Analysis_of_algorithms#References). ["Introduction to Algorithms"](https://en.wikipedia.org/wiki/Introduction_to_Algorithms) is the standard in most college level programming courses. [Big O](https://en.wikipedia.org/wiki/Big_O_notation) is the keyword you want to use when searching.  

---

## 1 answers

### Answer by username_4 on 2018-06-05. Score: 3

My standard answer for this is the following, copied from [another answer](https://cseducators.stackexchange.com/a/4859/1293) I've given here.

> If you want a thorough study of how to approach and develop algorithms, get a copy of:
>
> [David Gries, The Science of Programming](https://rads.stackoverflow.com/amzn/click/com/038790641X)
>
> The book will change how you think about algorithms and how they are developed. One of the key ideas is algorithm development from loop-invariants along with pre- and post-conditions. There is a science (hence the name) of modifying post-conditions in order to develop a loop and its invariant.
>
> One of the magical problems in the book is a linear time sort of an arbitrary array that contains only three distinct values (Dutch National Flag). It generalizes to a linear time sort of an array containing a finite number of distinct values.

It shows algorithm development in a way that results naturally in optimized algorithms.

However any non-trivial book on algorithms should discuss optimization and the various ways it is measured (space, time, average, best case, worst case, ...). Books advertised as "introduction to algorithms" may be a bit shallow, of course.

The gold standard, of course, is the multi-volume [The Art of Computer Programming](https://en.wikipedia.org/wiki/The_Art_of_Computer_Programming) by Donald Knuth. The first chapter of the first book is a nearly complete treatise on the required mathematics. In this series, algorithms are presented in a specially constructed assembly like (very low level) language. The Gries book also uses a specially constructed language for presentation, but it is at about the level of Pascal or C.

However, if you are interested in *Functional Programming* (Scheme) instead, you want to start with [The Structure and Interpretation of Computer Programs](https://en.wikipedia.org/wiki/Structure_and_Interpretation_of_Computer_Programs) by Abelson, Sussman and Sussman. While this book will teach you deep concepts of algorithms, it might not be quite in the way you expect as it doesn't focus explicitly on optimization, treating optimization as more of an organic property of algorithms.

In fact, none of these books start with some "algorithm" and say "now, let's optimize it". I don't think that is a viable approach. Instead, algorithms are developed from the start to optimize on some criterion. But they are interesting partly because it is generally impossible to optimize on more than one dimension simultaneously. So most algorithms involve trade-offs of some kind. Often it is time vs space though there are other possibilities.

> **Comments:**
> **username_5**: Actually Donald Knuth warned about worrying about optimization prematurely. When you develop an algorithm without much concern for optimization you are proving whether your requirements are valid. Once you've done that you can do tests that prove if optimization is even something you need to consider. Stick with readable code and you can make it as fast as you need to at any time. Sacrifice readable code chasing optimization and, if it turns out you need to change it, you can't, because you can't read it.  
> **username_4**: @username_5, actually Knuth was speaking more generally of programming, not specifically what we have come to recognize as "algorithms", in what we call "The Algorithms and Data Structures" course. In fact, though, it was Tony Hoare who said "Premature optimization is the root of all evil". The idea is that most programs are sufficiently fast that you are wasting time on optimizing them initially. First run a profiler on the program to see where it is spending resources and then optimize those parts if necessary. I interpret the question here more narrowly, however.  
> **username_4**: On the other hand, Knuth did say "Beware of bugs in the above code; I have only proved it correct, not tried it." https://en.wikiquote.org/wiki/Donald_Knuth. Also see https://en.wikiquote.org/wiki/C._A._R._Hoare  
> **username_5**: Hehe, I've said [something similar](https://softwareengineering.stackexchange.com/a/315968/131624): "I write and run tests that prove it works before I suspect it works".  
> **username_5**: Of course you're free to interpret the question as you like. I'm simply advocating that one of the less theoretical "algorithm optimization techniques" is to just write something simple and readable that meets the requirements first before you give in to making things all weird in the name of speed. That way as you iterate on the problem you only pick up the weirdness you really need.  

---

