22
$\begingroup$

I am looking for a concise introductory text on algorithms with a high ratio $$\frac{\mbox{theory covered}}{\mbox{total number of pages}}.$$ It should begin at the beginning but then progress quickly without spending too much time on real world examples, elementary proof techniques, etc. As a research mathematician I have a solid background in mathematics which I happily employ to understand formalisms and condensed proofs, for example.

Do there exist such texts? Any recommendations?

$\endgroup$
24
$\begingroup$

I like this textbook very much:

Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani: Algorithms
Published by McGraw-Hill 2007.

I don't calculate your suggested ratio but I think you will also like it :)

$\endgroup$
  • 7
    $\begingroup$ Available here: cs.berkeley.edu/~vazirani/algorithms.html $\endgroup$ – usul Sep 16 '13 at 15:07
  • 4
    $\begingroup$ This looks like a nice book I will certainly try out. Thanks for the suggestion. $\endgroup$ – Gregor Sep 17 '13 at 6:42
  • $\begingroup$ @user13136 would you mind telling me what is the required mathematical background to understand this book? $\endgroup$ – user30467 Dec 23 '14 at 11:48
17
$\begingroup$

Jeff Erickson will not say this himself, but his online lecture notes are among the best out there to cover the basics of algorithm design at a level that doesn't patronize the reader. I use them in my grad algorithms class, and for a research mathematician, these notes convey the right kind (and level) of intuition, allowing you to fill in the details yourself easily.

$\endgroup$
  • 5
    $\begingroup$ These are Great notes. $\endgroup$ – T.... Sep 17 '13 at 13:09
8
$\begingroup$

Knuth's "The Art of Computer Programming" would probably be the book with the highest ratio.

If you want a more textbook style book then Cormen, Leiserson, Rivest, and Stein's "Introduction to Algorithms" would be my suggestion to a mathematician.

There are also many lecture notes and a few Wikibooks on algorithms.

$\endgroup$
  • 8
    $\begingroup$ Not so sure about CLRS as an introduction for a researcher. I definitely know many CS researchers who do not like to use it to look up things. TAoCP is an interesting quandry for me. I agree that it maxes the ratio, but there is a lot of attention to programmatic detail that a mathematician might find distracting. $\endgroup$ – Vijay D Sep 16 '13 at 16:30
  • $\begingroup$ @Vijay, yes, I know that CLRS is not everyone's favorite. Still I feel other textbooks are generally made "more readable" for undergrad students by lots of explanations which are not really needed for a mathematically mature person, this one is mathematically solid and relatively concise. I think it is a good book for people with good mathematical background. $\endgroup$ – Kaveh Sep 16 '13 at 16:34
  • $\begingroup$ [cont.] Your point about TAoCP is also correct but not surprising in my opinion considering that it is written by Knuth. Based on my own experience it should be easy to skip the parts about MIX and MMIX when one doesn't care about them. $\endgroup$ – Kaveh Sep 16 '13 at 16:38
  • $\begingroup$ Knuth is actually a book I knew before but had forgotten about entirely -- so thanks for the reminder. CLRS seems to be nice book but maybe a bit too wordy for my taste. Then on the other hand, I only had quick two hour look at it. $\endgroup$ – Gregor Sep 17 '13 at 6:45
  • 1
    $\begingroup$ Contrary to Vijay, I think that CLRS is the right way to learn algorithms. It explains everything really nicely, and is worth another look. $\endgroup$ – Huck Bennett Sep 18 '13 at 21:25
6
$\begingroup$

Algorithm Design by Kleinberg Tardos This book helps develop a concrete understanding of how to design good algorithms and talk of their correctness and efficiency. (I studied this in my first year at college, very much readable)

For an online copy/lecture notes/reference, (as suggested by Suresh Venkat) go with Jeff Erikson's lecture notes. They are really awesome!

$\endgroup$
5
$\begingroup$

I'd go for Combinatorial Optimization: Theory and Algorithms - Korte & Vygen. It will go you a good overview of algorithms with a constant focus on optimization. This book is intended for those with a heavy math inclination IMHO.

This would go well with Algorithms: Dasgupta & Papdimitrou, I believe.

$\endgroup$
  • $\begingroup$ This book seems to come closest to what I had in mind in terms of the above ratio. I will look at it more seriously soon and maybe use it together with Dagupta et al. indeed. So thanks for the suggestion. $\endgroup$ – Gregor Sep 17 '13 at 6:51
4
$\begingroup$

I wrote a disposition for the algorithms course I attended. It's purpose was exactly that; to be a concise version of the most important topics covered in our text box (which was CLRS). I'm reluctant to publish it on Scribd.com or anywhere else until I have examined the document thoroughly and being satisfied with its contents, but a working copy can be obtained at https://github.com/CasperBHansen/DIKU_AD_2013/. In order to read it you will need to know how to build the pdf document from the LaTeX source, which is what the repository is for. The document itself is just 65 pages long.

An older copy can be downloaded directly from my website at http://casperbhansen.dk/files/ad-disposition.pdf — this obviously contains more typos/mistakes, which have since been corrected.

It does contain several typos because it was written over just a few days whilst undergoing another exam and obviously preparing for the algorithms exam by practicing proofs, and I have yet to patch the typos and errors up as I have been very busy ever since. But I'm sure anyone who reads it would recognise the mistakes easily, as they are usually in contradiction with accompanying text or formulae, so it is easily figured out whenever a typo occurs.

I hope it can help you get started.

$\endgroup$
0
$\begingroup$

here are two other refs that may be helpful.

  • Algorithms by Sedgewick you said "introductory"; this book is sometimes used in undergraduate CS classes, although it could be used in some graduate classes. Sedgewick has other very technical refs on TCS and some of this mathematical style is reflected in Algorithms and its a generally succinct style. the coverage is very central to (T)CS (but not so much in advanced areas). also wrt "influences" note he did his Phd thesis under Knuth.

  • Computers and intractability, a guide to the theory of NP completeness an older but still very relevant ref. it focuses on NP completeness of course but in many ways "thats where a lot of the action is". the scope is broad and will probably be appealing to mathematicians in that it is focused on many mathematical objects eg graphs etc, and note theres a section on number theory. as wikipedia states

The book is now outdated in some respects as it does not cover more recent development such as the PCP theorem. It is nevertheless still in print and is regarded as a classic: in a 2006 study, the CiteSeer search engine listed the book as the most cited reference in computer science literature.[3]

$\endgroup$
0
$\begingroup$

I will post an answer which gave a high level view on the chapters I read. Handbook of Theoretical Computer Science: Algorithms and complexity, Volume 1 edited by Jan Leeuwen. It has big name contibutions like H.W. Lenstra, Valiant etc. This is not a text per se. However, reading this after some preliminary understanding gives more insight and goes into topics of interest within TCS. It is also mathematical with each chapter providing an introduction into a topic before diving into the topic. Note that the topics have moved on ever since the book came out in $1990$.

$\endgroup$
-5
$\begingroup$

try Concise encyclopedia of computer science, Wiley. unfortunately a complete/thorough table of contents for this ref does not seem to be available on the web [a somewhat unusual omission nowadays, maybe Wiley could correct this on request] but the complete index appears to be browsable on amazon. it has coverage that is much broader than TCS such as hardware concepts etc, but it appears to cover significant parts of TCS eg:

  • Information and Data
  • Software
  • Mathematics of Computing
  • Theory of Computation
  • Methodologies
  • Applications

it is a 902pp abridged version of the complete encyclopedia, Encyclopedia of Computer Science, 4th Edition, 2064pp

$\endgroup$
  • 17
    $\begingroup$ Have you opened this book? Looking at samples from the "complete encyclopedia" like media.wiley.com/assets/152/09/mathematics.pdf it looks like a horrible suggestion. It's the exact opposite of a survey of algorithms written for mathematicians. $\endgroup$ – Sasho Nikolov Sep 16 '13 at 19:49
  • $\begingroup$ dont really follow all the strong opposition or the issue with the cited entry. the questioner did not specifically insist that the ref would contain lots of mathematics in the descriptions; while ok angle think crowd is projecting that & a concise encyclopedia would appear to fulfill the basic request & even be advantageous. other option just ran across, somewhat similar see also encyclopedia of algorithms, springer. "No comparable reference work on algorithms is currently available." $\endgroup$ – vzn Sep 28 '13 at 14:45
  • $\begingroup$ are you kidding? he wants a lot of theory covered per page, and asks for a book that's not afraid to present succinct proofs with plenty of formalism. you suggest a chatty general audience book, that's 900 pages and covers little theory. $\endgroup$ – Sasho Nikolov Sep 28 '13 at 18:42
  • 2
    $\begingroup$ BTW most of what you write here, including this answer and the above comment, is ungrammatical and illogical to the point of being barely comprehensible. $\endgroup$ – Sasho Nikolov Sep 28 '13 at 18:43
  • $\begingroup$ he said he understands formalism/proofs but did not state the ref should have it. the encyclopedia refs are obviously/naturally relevant/apropos. maybe not perfect, but not worthless or to be trashed either. "good enough" for some purposes. as for your constant/so far endless/consistently unconstructive haranging/griping/personal vendetta over constructive/good faith answers, have no answer to that $\endgroup$ – vzn Sep 29 '13 at 1:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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