###### ISBN: 032163537X
earthicus · 2018-12-16 · Original thread
Thanks for stopping by! I'd like to ask a question / make a request. Unlike most of the people here, I was trained in mathematics but am just learning how to program, so I was wondering if you had any desire to expand the online algorithms material. In particular the 'generic programming' technique illustrated by Alexander Stepanov in these lectures (Four Algorithmic Journeys) [1] and book [2] caught my attention. He takes a simple number theoretic algorithm, considers what properties are required for it to work, then generalizes it and applies it in other useful and surprising cases.

For example, Stepanov starts with the problem of multiplying two integers n * m using the Ancient Egyptian Multiplication algorithm from the Rhind Papyrus (which runs in log n if i remember correctly), then observes the only property needed for the algorithm is associativity, so that it can run on any semi-group: mult(n,s) is n repetitions of the semi-group element s, using the semi-group operation. Useful and surprising applications are (1) matrix exponentiation to solve systems of linear recurrences in log n steps (no stupid Fibonacci implementation here!), and (2) encode a graph in your matrix, with elements in a tropical semi-ring, then matrix exponentiation solves shortest path. Not too bad for a 4,000 year old multiplication algorithm.

A second example is the euclidean algorithm, which he extends first to polynomials following Stevin, then to Gaussian integers, then to euclidean domains. A surprising application was to permutation algorithms managing memory.

Anyhow, I think it would be really cool if you showed these kind of applications of number-theoretic algorithms as well as the cryptography stuff. Unfortunately basically all of the modern algorithms literature seems to avoid even the tiniest hint of abstraction; it makes the subject so much harder to hold in your head! So providing a new set of examples that is more accessible than Stepanov would be doing the world a great service, i think.

Suncho · 2018-04-11 · Original thread
Yes! Alexander Stepanov is fantastic. He's the designer of the Standard Template Library (STL) for C++, which is C++'s core library of generic algorithms. It's part of the standard libary.

If you can understand how to use the STL properly, you're well on your way to becoming a profiicent C++ programmer.

His books are fantastic too.

Elements of Programming:

https://www.amazon.com/Elements-Programming-Alexander-Stepan...

and From Mathematics to Generic Programming:

https://www.amazon.com/Mathematics-Generic-Programming-Alexa...

If you prefer video lectures, his second book is based off his lecture series Four (three) Algorithmic Journeys:

It's a combination of history and math/algorithms and programming (using C++). If you're just looking for a straight intro to C++ course this isn't it. But it's a ton of fun and the generic programming/STL mindset is very powerful.

Programming Conversations is another great lecture series by Alexander Stepanov:

I would also recommend searching YouTube for videos by Sean Parent. This one in particular is very enlightening:

Sean Parent is very good at getting you in the STL mindset and showing off the expressive power of using the standard STL algorithms in your code. Except in the simplest cases, you should try to use them instead of writing your own loops.

Here are some random tips if you're coming from C or Java:

"new" is not the way to create objects in C++. new and delete should almost never be used by serious programmers in C++. Never use new and delete (or malloc and free). If you want a dynamically-allocated array, use the standard vector.

It's much easier to write C++ than it is to read it. This is because you can always write using a simple clear subset of C++ that you understand. Try to pick a style that you think as many people as possible will understand. Programming languages are for humans to read. I try to write code that I think C programmers can read.

Edit -- Another tip:

Exception safety isn't about C++'s exception-handling language feature. Exceptions still happen in C. There's just not a language feature that directly expresses them.

Writing exception-safe code is nearly impossible in C. RAII and C++'s built-in exceptions make it possible. If you're careful to always use RAII by default, you can get the basic exception safety guarantee automatically without thinking about it. And you can get the strong exception safety guarantee whenever you need it.

Good luck!

I'll give you a couple. Note that some of these are rehashes of my earlier comments.

# Elements of Programming

https://www.amazon.com/Elements-Programming-Alexander-Stepan...

This book proposes how to write C++-ish code in a mathematical way that makes all your code terse. In this talk, Sean Parent, at that time working on Adobe Photoshop, estimated that the PS codebase could be reduced from 3,000,000 LOC to 30,000 LOC (=100x!!) if they followed ideas from the book https://www.youtube.com/watch?v=4moyKUHApq4&t=39m30s

Another point of his is that the explosion of written code we are seeing isn't sustainable and that so much of this code is algorithms or data structures with overlapping functionalities. As the codebases grow, and these functionalities diverge even further, pulling the reigns in on the chaos becomes gradually impossible.

Bjarne Stroustrup (aka the C++ OG) gave this book five stars on Amazon (in what is his one and only Amazon product review lol).

This style might become dominant because it's only really possible in modern successors of C++ such as Swift or Rust, not so much in C++ itself.

https://smile.amazon.com/review/R1MG7U1LR7FK6/

# Grammar of graphics

https://www.amazon.com/Grammar-Graphics-Statistics-Computing...

This book changed my perception of creativity, aesthetics and mathematics and their relationships. Fundamentally, the book provides all the diverse tools to give you confidence that your graphics are mathematically sound and visually pleasing. After reading this, Tufte just doesn't cut it anymore. It's such a weird book because it talks about topics as disparate Bayesian rule, OOP, color theory, SQL, chaotic models of time (lolwut), style-sheet language design and a bjillion other topics but always somehow all of these are very relevant. It's like if Bret Victor was a book, a tour de force of polymathical insanity.

The book is in full color and it has some of the nicest looking and most instructive graphics I've ever seen even for things that I understand, such as Central Limit Theorem. It makes sense the the best graphics would be in the book written by the guy who wrote a book on how to do visualizations mathematically. The book is also interesting if you are doing any sort of UI interfaces, because UI interfaces are definitely just a subset of graphical visualizations.

# Scala for Machine Learning

https://www.amazon.com/Scala-Machine-Learning-Patrick-Nicola...

This book almost never gets mentioned but it's a superb intro to machine learning if you dig types, scalable back-ends or JVM.

It’s the only ML book that I’ve seen that contains the word monad so if you sometimes get a hankering for some monading (esp. in the context of ML pipelines), look no further.

Discusses setup of actual large scale ML pipelines using modern concurrency primitives such as actors using the Akka framework.

# Hands-On Machine Learning with Scikit-Learn and TensorFlow: Concepts, Tools, and Techniques for Building Intelligent Systems

https://www.amazon.com/Hands-Machine-Learning-Scikit-Learn-T...

Not released yet but I've been reading the drafts and it's a nice intro to machine learning using modern ML frameworks, TensorFlow and Scikit-Learn.

# Basic Category Theory for Computer Scientists

https://www.amazon.com/gp/product/0262660717/ref=as_li_ss_tl...

Not done with the book but despite it's age, hands down best intro to category theory if you care about it only for CS purposes as it tries to show how to apply the concepts. Very concise (~70 pages).

# Markov Logic: An Interface Layer for Artificial Intelligence

https://www.amazon.com/Markov-Logic-Interface-Artificial-Int...

Have you ever wondered what's the relationship between machine learning and logic? If so look no further.

# Machine Learning: A Probabilistic Perspective (Adaptive Computation and Machine Learning series)

https://www.amazon.com/gp/product/0262018020/ref=as_li_ss_tl...

Exhaustive overview of the entire field of machine learning. It's engaging and full of graphics.

# Deep Learning

https://www.amazon.com/gp/product/0262035618/ref=as_li_ss_tl...

http://www.deeplearningbook.org/

You probably have heard about this whole "deep learning" meme. This book is a pretty self-contained intro into the state of the art of deep learning.

# Designing for Scalability with Erlang/OTP: Implement Robust, Fault-Tolerant Systems

https://www.amazon.com/Designing-Scalability-Erlang-OTP-Faul...

Even though this is an Erlang book (I don't really know Erlang), 1/3 of the book is devoted to designing scalable and robust distributed systems in a general setting which I found the book worth it on it's own.

# Practical Foundations for Programming Languages

https://www.amazon.com/gp/product/1107150302/ref=as_li_ss_tl...

Not much to say, probably THE book on programming language theory.

# A First Course in Network Theory

https://www.amazon.com/First-Course-Network-Theory/dp/019872...

Up until recently I didn't know the difference between graphs and networks. But look at me now, I still don't but at least I have a book on it.

I've been recently trying to make my way though Elements of Programming (https://www.amazon.com/Elements-Programming-Alexander-Stepan...) by Alexander Stepanov and Paul McJones and it makes me say abstract algebra. It's the first and only rigorous foundation of software engineering that I've seen. It basically maps abstract algebra to this somewhat simple subset of C++, introduces new algebraic objects (such as memory) and then shows this really nice correspondence between the the C++-- and the abstract algebra.

If you are not familiar with the author, Alexander Stepanov is the guy who basically figured out generic programming, was instrumental in the design of C++ templates and the C++ STL. C++ gets a lot of flak but templates are very powerful (if you disregard the complexity). I think that they are actually one of the main reasons why C++ is still relevant. Also I'm starting to think that generic programming might actually be the most powerful paradigm out there (this is just a hunch). This book doesn't take the middle road, only the low level (C++) and extreme high level (abstract algebra) and totally cuts out the middle part (aka boiler plate).

Funnily enough, this C++-like language actually translates very nicely to the modern C++ successors like Swift and Rust (or it seems, I'm in the progress of exploring this).

Has anyone here tried to explore the contents of this book in either Swift or Rust?

But remember that this is not an easy book, I've met very smart people who told me they read only a part of this and are still wrapping their heads around that.

I'm finally taking a stab at Elements of Programming (https://www.amazon.com/Elements-Programming-Alexander-Stepan...). I think that this might actually be one of the most important books to read as a software developer. The book puts C++ and abstract algebra into a blender and creates this abstract algebra for software development which has some really deep insights. The author is Alexander Stephanov (the father of generic programming).

This is double true if you are using one of the newer languages that aim to kill C++ like Swift or Rust as some of the concepts apply really nicely.

Bjarne Stroustrup (the guy who made C++) wrote a comment about it on Amazon (https://www.amazon.com/review/R1MG7U1LR7FK6/ref=cm_cr_dp_cmt...) and gave it five stars.

limist · 2010-09-07 · Original thread
@jhck, drothlis: Thank you very much to both of you, those suggestions are exactly what was asked for. I'd upvote you more if I could. :)

Both the Gries book and Stepanov's book have really impressive reviews on Amazon, am looking forward to diving into them.

http://www.amazon.com/Science-Programming-Monographs-Compute...

http://www.amazon.com/Elements-Programming-Alexander-Stepano...

Get dozens of book recommendations delivered straight to your inbox every Thursday.