1
$\begingroup$

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!

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – thesecretmaster ♦
    Jun 4, 2018 at 22:43
  • 1
    $\begingroup$ @Buffy Thanks for the reply! I am more interested in algorithm optimization techniques. $\endgroup$
    – velut luna
    Jun 4, 2018 at 23:55
  • 2
    $\begingroup$ @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 Computer Science Educators! $\endgroup$
    – Ben I. ♦
    Jun 5, 2018 at 4:05
  • $\begingroup$ Is this a self-learning question, or are you trying to find something to use with your students? $\endgroup$
    – Ben I. ♦
    Jun 5, 2018 at 17:06
  • $\begingroup$ I am a student. It is for self-learning. $\endgroup$
    – velut luna
    Jun 6, 2018 at 0:40

1 Answer 1

Reset to default
3
$\begingroup$

My standard answer for this is the following, copied from another answer 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

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 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 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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – candied_orange
    Jun 10, 2018 at 13:32
  • $\begingroup$ @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. $\endgroup$
    – Buffy
    Jun 10, 2018 at 13:49
  • $\begingroup$ On the other hand, Knuth did say "Beware of bugs in the above code; I have only proved it correct, not tried it." en.wikiquote.org/wiki/Donald_Knuth. Also see en.wikiquote.org/wiki/C._A._R._Hoare $\endgroup$
    – Buffy
    Jun 10, 2018 at 13:55
  • $\begingroup$ Hehe, I've said something similar: "I write and run tests that prove it works before I suspect it works". $\endgroup$
    – candied_orange
    Jun 10, 2018 at 13:58
  • $\begingroup$ 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. $\endgroup$
    – candied_orange
    Jun 10, 2018 at 14:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.