Why You Can’t Have a Real Software Engineering Discipline

As we all know the fields of computer science and software engineering are in their infancies.  Many a blog post has been written lamenting the fact that software engineering is not a real engineering discipline, and while I have not written that exact post, I have written about the subject and have deconstructed what others have said about it.  A number of these points do apply to why software projects routinely fail, yet another topic that has received considerable attention.  Now admittedly all engineering disciplines regardless of their maturity and formalization have project failures and creating a real software engineering discipline will not eliminate this problem but one would hope that it would abate it.

I find it odd that at a time when so many people are involved in IT there seems to be little discernible progress in creating a real software engineering disciple.  There are probably millions of people working on creating software.  Also there are many researchers trying to solve this problem from many different angles.  Practitioners have been attempting to solve it with ideas like Agile and Software Craftsmanship, etc.  Additionally there is a long list of failures surrounding the formalization software engineering.  

My biggest complaint is the fact that there really are no good formal standards in general software engineering principles and methodologies lack a formal foundation and even the more vague principles can be easily thwarted and misused, and often, as I have previously complained, it often ends up being based on pure opinion which is usually won through positional authority, perseverance or by those who are just more politically savvy.

The intent of this post is not to attempt to solve or even offer solutions to the problem of creating a real software engineering discipline but to look at what I think are some barriers to creating this discipline and in some of these cases offer thoughts on overcoming those barriers.

Low Entry Requirements

If we are to think software engineering as an engineering discipline, I challenge you to find another engineering discipline that routinely has practitioners with no formal training in the field.  I very much doubt that someone who did not hold a degree in engineering and who built a shed in his back yard is now working as a structural engineer on a construction project, the mere idea seems ludicrous.  Yet I have worked with non technical degree holders who became software developers, one who started by building web pages and now calls himself an "Internet Application Architect", and is probably one of the biggest cargo cult coders I’ve ever had the misfortune to work with.  This egalitarian aspect isn’t all bad as it does let good people into the field as well.   Another non technical degree holder I once worked with became an accomplished developer and went on to get an advanced degree in CS and is now a CS professor.   Although it’s probably the case that for every good non technical degree holder who joins the field it is likely that dozens of mediocre and bad practitioners will also join.   It seems that in other engineering disciplines there are much more stringent educational requirements to ensure proper training.   To be clear here I am not equating having a degree with being competent because I have met many incompetent people with degrees, but still you need something.   I confess I am at a loss for a solution for this one.

The Lack of Differentiation between Science and Engineering

Chemistry is a scientific discipline, chemical engineering is an engineering discipline, and you can make this comparison between other engineering disciplines and the sciences that they employ e.g. electrical, mechanical, and structural map to various areas of physics.  Engineering and scientific disciplines are different types of disciplines often taught in separate schools.  Although each engineering discipline has some scientific overlap and it would probably be possible to move from the appropriate scientific field to the corresponding engineering field in general you probably would not do so without returning to school.   In recent years software engineering curricula have been added to the rosters of many colleges and while this is potentially a step forward, discounting for the moment that software engineering is still not really real engineering, a software engineering degree and a computer science degree in many cases gets you the same job!   

So in other fields there would be a differentiation between a degree that would put you on a track to do scientific research and one that would put you on a track to do engineering work.  As I understand it, if you are fresh out of school with a BS in CS that qualifies you to be a tester at Microsoft¹, developers hired right out of school need at least a Masters degree in CS.   This is an extreme case of how this really breaks down in our industry.  In most cases engineering practitioners are the software engineering, MIS, CS or even non technical degrees and the few scientific careers generally go to the advanced degree holders.  I admit this probably fairly normal a BS in chemistry or biology is also more likely to get you a job in IT than a job as a research scientist.  Still compared to more mature engineering fields there seems to be a lack of real differentiation between the degrees that yield a career as a software engineer versus one as a computer scientist.

Bad Management

The entry requirements for managers in software make the low entry requirements for software engineering practitioners look downright rigorous.  I have previously criticized the fact that many organizations find the cheapest people, especially for software management and give them an obligatory certification.  Now I know that engineering management regardless how formal or established the engineering discipline is an area that has problems and failures, but again I very much doubt that you would find a twenty something business or liberal arts major with a freshly minted PMP suffix managing construction or civil works projects.   Yet in my experience this is pretty normal in IT especially in the government sector.  Of course bad software management is executed by older managers as well.

A post by Larry White titled "Engineering Management Is Dying" delves into some these issues.  It is definitely the case that methodologies like Agile have changed how software projects work and the traditional corporate management approach to software really doesn’t work.  One point he makes is that it is not uncommon to see a two hundred person project at Google headed by an engineer.  To me this implies that someone is in some way managing that project.  I think all of this is indicative of the need for software engineering mangers to also be practitioners in engineering or at least very well versed in how software development works.  The situation he talks about at Google is not the case everywhere, in that case the company is its own client, but there are many cases where software is being built for clients and this does create a need for management that deals with the client, perhaps this should be a role that is separated from management and called a client liaison, which is what often happens.  Also I am not sure how things work at Google but I have also seen internal development in organizations where the IT department provides services to an internal client, I have also seen this go horribly awry with contentious unproductive relationships between departments.  In short I feel that just as we need a real software engineering discipline we also need a real incarnation of software engineering management.

The Disconnect between Academia and Industry

Most practitioners do not keep up with, or read academic research, actually many practitioners don’t read at all, but that’s another issue, and most academicians don’t work in the field so they lack the hands on knowledge.  Unfortunately this rift can take on a somewhat disdainful tone as is the case in my exploration of one practitioner’s attempt to define "Real Engineering".   Fortunately some people, I’d like to count myself among them, take a more constructive approach to building bridges across this rift.  Daniel Lemire has an interesting critique the quality of software produced in academia. 

I think the solution here is for both sides to become more engaged in problems faced on each side. I am optimistic about this one as I feel that these walls are breaking down as the field is growing up and many of the emerging technologies are forcing developers to be more cognizant of and engaged in research topics.  I also have encountered much more research that has ties to the practical concerns of day to day software development, some I have mentioned with more to come.

The Lack of an Effective CS Math Curriculum 

If you read my blog you know it to be a mix of math and software practices. I would describe myself as a software practitioner and a math enthusiast.  My math journey has taken me on some interesting math excursions into areas of math that seem to get little or no mention in CS curricula and I feel that this is a major problem in really applying math to the field of software engineering.  Another problem is in the way that it is taught, my experience was that it was not only taught badly but in a way that made it seem irrelevant to many of the programming courses.  Specifically I would shift the CS math curriculum to include less differential and integral calculus and include more logic, combinatorics, abstract algebra, graph theory, order theory, category theory and probably some topology among others.

Over the last few years I have been progressively learning more math which has been in part motivated by necessity for understanding research papers.  This approach has changed the way I see things, I now see the patterns of math in software. They are there and I believe that they can be exploited to create a real software engineering discipline.

For the math learning problem I do have some ideas many of which are expressed in my blog.  Some of my posts like refactoring if statements with Demorgan’s Laws or the String Monoid, the Object Graph, etc. are about making these mathematical ideas more relevant and accessible to programmers. Other posts like my series on naming and my post on generic programming and entropy and complexity are about my own ideas and ideas in the research literature that I feel may help to create a real software engineering discipline.  These are my attempts at solutions to these problems, so expect more of both of these and more thoughts on the CS math curriculum.

The Software Architect Debacle

This is one that really bothers me.  I feel the software architect role in general has a very negative effect on creating quality software and it dissuades the industry from developing a real engineering discipline.  The Software Architect role tends to be broadly defined, you have enterprise architects, software architects, etc., some architects tend to be involved with hardware and networking, some work on configuration management, some do software design, some do all of these things and more.  I feel this is a problem as each of these is a separate engineering area with different types of problems. By not breaking these down it often leads to a lack of focus on specific problems, also I have seen cases where the architect focuses on their preference and ignores other issues.  The architect role is often divorced from the code.  I have met many architects that were responsible for software but had never even looked at the code.  To me this is a huge failing that architects that are responsible for building software often lack the interest, time, or even aptitude to know the quality or underlying of structure of the software that they are delivering.

To really do justice to these ideas I might need a separate post, my solution would be to break down the architect role into specific engineering roles, which could include:

• Software Process Engineering - this would be involved with software team and resources planning, some aspects of configuration management such as defining policies, requirements analysis and general project management aspects of software construction including the definition and refinement of the SDLC.  This role is tightly coupled with software engineering management.
• Software Structural Engineering - this would include requirements comprehension, code infrastructure planning, prototyping work, hands on code structural work including custom frameworks and reusable components, third party library products, and general code quality including reviews and static analysis.
• Software Quality Engineering - This would include the QA roles, software testing and testing tools, requirements validation and refinement, usability and reliability and general software quality issues.
• Software Infrastructure Engineering - This would include hardware, networking, database, app server and general service infrastructure, non functional requirements fulfillment and possibly the implementation of configuration management, continuous integration, etc.

This is a rough "sketch" of these possible roles and each of these areas has some overlap implying that all of the people in these roles would work closely together, also some combination of, or all of these roles might be performed by a single individual depending on the organization’s size and structure.  What this approach does is clearly defines roles and responsibilities as opposed to some nebulous software architect role.

The Continuous Turnover of the Work Force

A young CEO once commented that he thinks young programmers are superior.  In general companies prefer younger workers as they often don’t have family commitments so they can work more hours and you can pay them lower salaries, DC area government contractors rely on this to keep their profit margins up.

As an older developer I often find this frustrating.  I confess that I have not moved up the ladder and still mostly work as a developer or what might be called a hands on architect, yes I know but that’s the current term, actually my preferred title would be: Software Structural Engineer.  Working as a contractor I have on several occasions found myself on projects that were dominated by younger developers and unfortunately on more than one occasion I watched as teams would make many mistakes due to a lack of experience, in some cases I was able to help in others I was ignored by the younger developers.  This is not to say that I do not still make mistakes, I’ve just been around long enough to have made a lot of them already.

If you buy into the software craftsmanship thing, I admit to being skeptical of this idea, you might be inclined to draw a parallel to craftsman of the past when older established masters took on apprentices and passed on their wisdom to the next generation.  Given the access to information these days such process is somewhat antiquated and perhaps impractical.  Nevertheless I feel, and the industry supports me here, that older developers who keep their skills up to date have value.  I know several younger developers who have sought me out to learn from me so I think I can safely say I still have some value.

Many older developers have let their skills get rusty and have not kept up on current technologies I have seen this many times.  Also many companies seem to lack the vision to allow for real hands on technical career growth.  I can’t help but feel that this inclination to recycle developers in each new generation is hurting or at least slowing our ability to develop a real software engineering discipline, this potential loss of continuity seems like it leads to some lost wisdom.

The Social Networking Drain and Hollywoodification of Silicon Valley

As I write this Hollywood gears up to deliver a reality TV show that takes place in silicon valley and Mark Zuckerberg now gets the paparazzi treatment.  Another article that I previously mentioned was about how CS enrollment was up because the movie The Social Network had enticed many aspiring Zuckerberg wannabes.  At present there does seem to be a gold rush mentality and it is noticeable and even discussed on sites like Hacker News. 

As someone who has never worked in the valley I am very much an outsider and may not have a good perspective on these things, but it seems that there are a lot of startup companies focusing on crap. Now I get it.  We live in a shallow consumer society with a rapacious appetite for crap. But are not these supposed to be some of the smartest people and I am not the only one to wonder why so many smart people who should have better taste and higher standards are settling for working on serving up ads and other vapid crap instead of doing more meaningful work like working on real problems that would advance human society or even just work on advancing software engineering. 

¹I believe this was the case in the late 90’s and may have changed, this information was conveyed to me by a former Microsoft employee.

What is Generic Programming?

Over the course of my career I have strived to write reusable code, always looking for more general patterns and trying to refactor code to more flexible more generic versions sometimes with mixed success.  Lately it has become something of an obsession of mine in that I both try to employ it and have been endeavoring to learn more about it, what it really is, and how to do it right, as I have previously pondered I believe there is a complexity cost with increased reuse.  Over the last few years, which I have been programming in Java, generics has become a central tool in achieving reuse.  So such a concept comes to mind but it is just one idea in a larger framework of ideas on generic programming.

There is a fair amount of research and discussion of the ideas pertaining to generic programming, the title of this post is taken directly from a paper on the topic, which perhaps not so coincidently was presented at the same OOPSLA (2005) as the paper on Software Reuse and Entropy that I previously discussed.  It just seems like every idea I explore is super-interrelated to everything else and this post will be no exception, I can conceptually connect these two papers using a Kevin Bacon like approach using just two other research papers, ideas I have for other posts.  I will try to keep this one as focused as possible.  Also the referenced paper is, like the Software Framework paper, very math heavy but different math, Category Theory,Order Theory, Universal Algebra, etc. This post will focus on more high level concepts and not the details of math that I wish I could claim that I fully understand.

So back to our question, what is generic programming?   For me it is about reuse, and while the information entropy approach to understanding reuse was about reuse from perspective of measure and the reuse (measurable) variation on different domains, I feel that the generic programming concept is about the structure of reuse and how it is implemented in various programming paradigms but the concept itself transcends language specific interpretations and implementations.

As you can tell I am not sure how to exactly answer this question so I will defer to the experts.

"What is generic programming?" in part outlines the paradigmatic distinctions between mainstream OO languages (Java Generics, C++ with STL) and Functional languages (Haskel, Scheme):

As for most programming paradigms, there are several definitions of generic programming in use. In the simplest view generic programming is equated to a set of language mechanisms for implementing type-safe polymorphic containers, such as List<T> in Java. The notion of generic programming that motivated the design of the Standard Template Library (STL) advocates a broader definition: a programming paradigm for designing and developing reusable and efficient collections of algorithms. The functional programming community uses the term as a synonym for polytypic and type-indexed programming, which involves designing functions that operate on data-types having certain algebraic structures.

In "Generic Programming" written in 1988 by David A. Musser and Alexander A. Stepanov use Ada and Scheme and describe generic programming as:

By generic programming, the definition of algorithms and data structures at an abstract or generic level, thereby accomplishing many related programming tasks simultaneously.  The central notion is that of generic algorithms, which are parameterized procedural schemata that are completely independent of the underlying data representation and are derived from concrete efficient algorithms.

...

A discipline that consists of the gradual lifting of concrete algorithms abstracting over details, while retaining the algorithm semantics and efficiency.

That last sentence has a very Agile/Refactoring feel to it.

Ralf Hinze in "Generic Programs and Proofs" describes it as: 

A generic program is one that the programmer writes once, but which works over many different data types.

...

Broadly speaking, generic programming aims at relieving the programmer from repeatedly writing functions of similar functionality for different user-defined data types. A generic function such as a pretty printer or a parser is written once and for all times; its specialization to different instances of data types happens without further effort from the user. This way generic programming greatly simplifies the construction and maintenance of software systems as it automatically adapts functions to changes in the representation of data.

...

So, at first sight, generic programming appears to add an extra level of complication and abstraction to programming. However, I claim that generic programming is in many cases actually simpler than conventional programming.  The fundamental reason is that genericity gives you "a lot of things for free" ...

This last statement resonates with me as it parallels my thoughts on the desirability of using software frameworks and I feel that I continuously have this conversation (argument) with junior level programmers and also senior level cargo cult coders who don’t get it.

Design Patterns are a common generic concept in mainstream programming.  It turns out that a number of design patterns can be described in the framework laid out by these papers and a number of papers do exactly that including "Design Patterns as Higher-Order Datatype-Generic Programs " part of extensive research on the topic by Jeremy Gibbons:

Design patterns, as the subtitle of the seminal book has it, are ‘elements of reusable object-oriented software’. However, within the confines of existing mainstream programming languages, these supposedly reusable elements can only be expressed extra-linguistically: as prose, pictures, and prototypes. We believe that this is not inherent in the patterns themselves, but  evidence of a lack of expressivity in the languages of today. We expect that, in the languages of the future, the code parts of design patterns will be expressible as directly-reusable library components. The benefits will be considerable: patterns may then be reasoned about, typechecked, applied and reused, just as any other abstractions can. Indeed, we claim that the languages of tomorrow will suffice; the future is not far away. All that is needed, in addition to what is provided by essentially every programming language, are higher-order (parametrization by code) and datatype-generic (parametrization by type constructor) features. Higher-order constructs have been available for decades in functional programming languages such as ML and Haskell. Datatype genericity can be simulated in existing programming languages [2], but we already have significant experience with robust prototypes of languages that support it natively [2]. We argue our case by capturing as higher-order datatypegeneric programs a small subset ORIGAMI of the Gang of Four (GOF) patterns. (For the sake of rhetorical style, we equate ‘GOF patterns’ with ‘design patterns’.) These programs are parametrized along three dimensions: by the shape of the computation, which is determined by the shape of the underlying data, and represented by a type constructor (an operation on types); by the element type (a type); and by the body of the computation, which is a higher-order argument (a value, typically a function).  Although our presentation is in a functional programming style, we do not intend to argue that functional programming is the paradigm of the future (whatever we might feel personally!).  Rather, we believe that functional programming languages are a suitable test-bed for experimental language features - as evidenced by parametric polymorphism and list comprehensions, for example, which are both now finding their way into mainstream programming languages such as Java and C#.  We expect that the evolution of programming languages will continue to follow the same trend: experimental language features will be developed and explored in small, nimble laboratory languages, and the successful experiments will eventually make their way into the outside world. Specifically, we expect that the mainstream languages of tomorrow will be broadly similar to the languages of today — strongly and statically typed, object-oriented, with an underlying imperative mindset — but incorporating additional features from the functional world — specifically, higher-order operators and datatype genericity

Lately I have been making more of an effort to learn Scala. Bruno Oliveira and Jeremy Gibbons make the case in "Scala for Generic Programmers" that it might be one of or even the best language for expressing Generic Programming concepts in part due to its hybridization of object oriented and functional paradigms. Here is the abstract in its entirety:

Datatype-generic programming involves parametrization by the shape of data, in the form of type constructors such as ‘list of’.  Most approaches to datatype-generic programming are developed in the lazy functional programming language Haskell. We argue that the functional object-oriented language Scala is in many ways a better setting. Not only does Scala provide equivalents of all the necessary functional programming features (such parametric polymorphism, higher-order functions, higher-kinded type operations, and type- and constructor-classes), but it also provides the most useful features of object-oriented languages (such as subtyping, overriding, traditional single inheritance, and multiple inheritance in the form of traits). We show how this combination of features benefits datatype-generic programming, using three different approaches as illustrations.

So far for me Scala has been a joy.  Its features and flexibility are beautifully elegant of course I am tainted coming from the clumsy, clinking, clanking, clattering caliginous world of Java, BTW Java we need to talk, it’s not you, it’s me. I’ve met someone else.

Jeremy Gibbons Makes the following point in "Datatype-Generic Programming":

Generic programming is about making programming languages more flexible without compromising safety. Both sides of this equation are important, and becoming more so as we seek to do more and more with computer systems, while becoming ever more dependent on their reliability.

This idea is similar to ideas that Gerald Sussman explores in his talk at Strangeloop 2011 "We Really Don’t Know How To Compute".  However, his general and perhaps philosophical approach to the idea of generic programming is very different from the previous ideas:    

[8:40]We spend all of our time modifying existing code, the problem is our code is not adequately evolvable it is not adequately modifiable to fit the future in fact what we want is to make systems that have the property that they are good for things that the designer didn’t even think of or intend.  ... That’s the real problem. ...  The problem is that when we build systems whatever they are we program ourselves into holes. ...  It means that we make decisions early in some process that spread all over our system the consequences of those decisions such that the things that we want to change later are very difficult to change because we have to change a very large amount of stuff.  ... I want to figure ways that we can organize systems so that the consequence of the decisions we make are not expensive to change, we can’t avoid making decisions but we can try to figure out ways to minimize the cost of changing decisions we have made.

...

[11:40]Dynamically extensible generic operations  ...  I want to dynamically extend things while my program is running  ... I want a program to compute up what it is going to do.

He shows an example[19:00] which is "the definition of the method of computing Lagrange Equations from a Lagrangian given a configuration space path". This is apparently easy stuff, to him at least.  Fortunately you don’t really need to understand the details of this math to understand his points here:

[20:45]This is a little tiny feeling of what is it needed to make things more flexible consider the value here, the value is that I am dynamically allowed to change the meaning of all my operators to add new things that they can do. Dynamically. Not at compile time, at runtime.

...

[21:15]It gives me tremendous flexibility. Flexibility because the program I wrote to run on  a bunch of numbers with only a little bit of tweaking suddenly runs on matrices so long as I didn’t make mistake of commuting something wrong. ... So this makes proving the theorems very hard In fact maybe impossible the cost and the benefits are very extreme. I can pay  correctness or proofs of correctness or belief in correctness, I can pay that for tremendous flexibility. ... Is correctness the essential thing I want, I am not opposed to proofs, I love proofs I am an old mathematician. The problem is that putting us into the situation that Mr. Dijkstra got us into ... where you are supposed to prove everything to be right before you write the program getting into that situation puts us in a world where we have to make the specifications for the parts as tight as possible because it’s hard to prove general things, except occasionally it’s easier but it’s usually harder to prove a general theorem about something so you make a very specialized thing that works for a particular case you build this very big tower of stuff and boy is that brittle change the problem a little and it all falls over.

His ideas tend towards adaptable and self modifying code at one point he talks about self modifying code in both assembly language and the use of eval in Lisp.  He also touches on a number of parallels in the biological world including genetics and the adaptability of the human immune system to fight off mutating parasites.  Interestingly some of his ideas seem similar to work done by Stephanie Forrest on using evolutionary/genetic algorithms for program repair which she speaks about at the keynote of SPLASH 2010, formerly known as OOPSLA.  The genetic repair approach at the conceptual level is striving for the same results as what Gerald Sussman describes.  Also did you notice that the Levenshtein Distance between "generic programming" and "genetic programming" is (one substitution), pretty weird!

Seriously though, the objectives of all of these approaches are the same: building better more flexible software that handles more situations. These ideas are reflected in how Glenn Vanderburg describes software engineering:

Software engineering is the science and art of designing and making, with economy and elegance, systems so that they can readily adapt to situations which they may be subjected.

I feel this Software Engineering insight reinforces my opinion that we will eventually see a real math backed discipline of software engineering and I think that the research work discussed  here both supports my conjecture on this point and most likely lays part of that foundation.  I also think some of these ideas reflect ideas I discussed in "The Software Reuse Complexity Curve" which implies that programmers will need to become more aware and more adept at more advanced theoretically based concepts like for example GADT’s (Generalized algebraic datatypes), etc. and of course math in general such as Abstract Algebra.

Clearly the idea of Generic programming has some very specific ideas and some very general objectives. There seem to be two approaches here which might described Predictive vs. Adaptive, much like the idea of Separation of Design and Construction described by Martin Fowler.  The Gibbons et al more calculational approach is predictive whereas the Sussman/Forrest ideas describe an adaptive approach. I suspect that this will just be another dimension of program design that will have to be considered and assessed as a tradeoff in its application, which Sussman also mentions.

Eleven Equations True Computer Science Geeks Should (at Least Pretend to) Know

This idea is a complete rip off an article that appeared in Wired a little while ago and it got me thinking what would my list for Computer Science look like?  Plus I thought it might be a fun post and unlike the Wired list this one goes to eleven.  So here they are in no particular order:

Binomial Coefficient

The Binomial Coefficient equation generates Pascal’s Triangle and gives you the coefficients for the Binomial Theorem these ideas are often attributed to Pascal but in fact they have been known in part for over a millennia.

As I mentioned that this list is no particular order and I don’t wish to play favorites but if there is one equation here that you should really consider learning and committing to memory this is it. It is central to Combinitorics which has connections to many areas of math, I guess I should qualify that if you are serious about computer science and math related programming topics then you should be able to recite and apply it from memory, even when you are drunk, sleep deprived or being held at gun point. Ok that might be a bit much but you get the idea.  If you are programmer and you haven’t learned it, or need a refresher, I have a post that relates it to the Java Collections API.

Demorgan’s Laws

Logical form:

Set Form:

Ok so that’s like four "equations" for DeMorgan’s Laws, one can’t help but to struck by the similarity between the two sets and this is not a coincidence these two sets of formulas are essentially the same thing, they are special cases of complemented distributive lattices^†  which means technically it’s really just two formulas:

In this case the ∨ symbol means lattice join operation and the ∧ symbol is the lattice meet operation and the dash with the right downward mark means lattice complementation, I used this to differentiate from the tilde for Boolean complementation.  Also these two formulas are categorical duals of each other, which means that if one were smart and had a good grasp of Category Theory we could probably be really OCD about it and get it down to one formula.

Understanding Set Theory and Boolean Algebra are very important basic concepts in our profession and the Boolean version can make you better programmer, as you can use it to refactor logical if statements. 

Eigenvector and Eigenvalue

This equation and these concepts are not only central to Linear Algebra but these Linear Algebraic ideas and others are both used and extend into many other areas of math including Linear Transformations and Graphs in terms of matrices like the Adjacency Matrix and much more.

Linear Algebra is becoming increasingly central to the types of things we are doing in our profession, it is used heavily in Statistics and Machine Learning not to mention the Page Rank Algorithm is based in part on this equation.

Pumping Lemma for Regular Languages

No Comp Sci list would be complete with at least one formula from either Formal Language Theory or Automata Theory.  The problem is that these two are pretty different from other areas of math in terms of "Equations" I tried to think of some basic Ideas and The Pumping Lemma came to mind, and I found the above formula concisely expressed on Wikipedia.  This version of the Pumping Lemma is a more limited version of Another Theory which is used to check whether a Language is Regular. Also this is maybe not the best choice as it is pretty dense, if you want a better explanation I recommend this.

While this "equation" is pretty specialized, it is actually a special case of the more general Iteration Theorem, the real point here is really about more general domain knowledge.  It is central to what you do every day you are programming such as compilers and regular expressions not to mention the almost ubiquitous Kleene Star.

Information Entropy

I confess after all my machinations to try to reduce Demorgan’s Laws down to less equations I am totally cheating here by pulling a twofer in including two formulas, both Shannon’s Information Theory:

And the formula for Chaitin’s Constant, which is associated with Algorithmic Information Theory and Kolmogorov Complexity:

Interestingly this area has a parallel in the physical word, in terms of Thermodynamic Entropy, which also parallels the Boltzman Equation mentioned in the Wired Article.  Seth Loyd draws some interesting connections between computation and the physical world including Entropy and Boltzman’s Equation.

In programming and computer science information is our business and these ideas are central to many things that we deal with especially the storage, transmission, computational transformation (like compression), and computation of information.  We’ve already seen the possible relationship between both of these theories and Reusability and Software Frameworks.

Bayes' Theorem

Of all of equations on the list, Bayes' Theorem may stand out on its own merits as being one of the most recognizable and it might even qualify as a poster child for the statistical revolution sweeping our industry.  It rose from obscurity to being used for spam detection and with such applications as classifiers, Machine Learning, Data Mining and more.

Mathematically it is part of a rift in statistics and probability and I confess I may not yet call myself "an initiate of the bayesian conspiracy" but it hard to deny its utility plus there seems to be a more axiomatic basis that relates to Boolean Logic Set Theory, which makes it all the more alluring.

Fermat’s Little Theorem

These two equations of Fermat’s Little Theorem are really the same equation written in two different forms, where (a ⊥ p) means coprime and (p ∈ P) means prime.

This is a beautiful little theorem in Number Theory which can be generalized and written even more succinctly using Eulers Totient Function which is represented by φ (n):

These ideas are crucial for understanding encryption algorithms like RSA and there’s this cool result.

Natural Join

Natural Join, like all of the Relational Algebra Join Operations is a composition of the more basic, operations: Selection (σ), Projection (π), Cartesian Product (×), Set Difference (-) and Union (∪).  Natural Join is the Cartesian Product of two tables selecting matching rows and eliminating duplicate columns.  (In the formula above the projection (π) is the set (A) of attributes with duplicates removed and then selects (σ) the set (C) of common attributes which match in both sets and are equal in both sets.)

The Relational Algebra is in my opinion a bit of an odd beast when it comes to algebraic structures, but if you use SQL you are already using an implementation of it.  As data persistence becomes more heterogeneous I think understanding these concepts, will become more important.  Additionally Relational Algebra also has strong ties to Abstract Algebra[ and Category Theory[.

The Fixed-Point (Y) Combinator

Just as we need a "equation" from Formal Language Theory or Automata Theory we really should have one that is related to Lambda Calculus, in this case this equation is in the untyped lambda calculus.  Even though the Fixed-point Combinator stands up on its own, it is fairly well known, well at least in name due to the use of it by Paul Graham for his incubator (Y-Combinator).

The Fixed-Point Combinator allows one to implement anonymous recursion which is a powerful programming technique.  It also ties into some deeper theoretical aspects of computer science and logic such as Combinatory Logic.

O(n)

Many CS majors may cringe at this, and another possible reaction is that’s not much of an equation.  There’s actually quite a bit to this for example did you know there are some substantial and quite beautiful equations associated with this seemingly simple formula.  They are:

Also the following is a definition of (lim sup) Limit Superior:

Where inf is infimum and sup is supremum two concepts that seem to show up quite a bit especially when you are concerned with bounds like with Lattices and they also seem to show up in relation to Topology.

And we all know why we should care about his one: Algorithms, Algorithms, Algorithms.

Euler’s Identity

Euler’s Identity is also listed in Wired’s article and I have to agree that it is one the most beautiful and intriguing formulas in math.

Now this isn’t really as relevant to CS as the other formulas but if you a true computer geek you are hopefully some kind of math geek, and this is such a great formula, not to mention that it appears in The Simpsons' Homer³. It’s actually a specific case (where θ = π) of Euler’s Formula:

These formulas will give one a better understanding complex numbers which are needed in other areas of advanced math also these formulas relate to Fourier Analysis which does have applications in Computer Science.

I am curious to see how well this list holds up, how will I feel about it in a year?  Also in writing this I realized that I still have quite a bit more to learn about at least half of this list, if not all of it, which made it hard to write as it was quite a little (unfinished) research project. I have already written individual articles on several of these equations and have at least two in the works for Linear Algebra, at least two on the Relational Algebra and one planned for Pascal’s Triangle, and those are just the ideas I’ve already had, who knows what the future holds.  I hope you enjoyed it as much as I did writing it.

^† The Set version may not apply to all cases in set theory, this assumes Union and Intersection over the Power Set of a Set Universe, this would be closed under these operations and would include complements of all elements.  The Set Universe is the upper bound and the empty set is the lower bound.

O(log(n))

I find O(log(n)) to be a very interesting algorithm complexity, it’s also highly desirable and if you achieve it you are probably doing well, or you are just using a couple of common time tested algorithms and data structures such as Binary Search or [Self] Balanced Binary Trees like Red Black or AVL trees. The order of Big O Complexities is:

O(1)	constant
O(log log n)	Double Logarithmic
O(log n)	Logarithmic
O(nm)  0 < m < 1	fractional power
O(n)	Linear
O(n log n) = O(log n!)	Loglinear
O(n2)	Quadratic
O(n3)	Cubic
O(nm)  m > 1	(general) polynomial (m is a fixed, non-negative integer; e.g. n4, n5)
O(mn)	exponential (m >= 2; ; e.g. 2n, 3n)
O(n!)	Factorial

When I was growing up and hand held calculators were quickly evolving much like smart phones are now, although perhaps not as rapidly, my father would bring these calculators home and I would play with them, this was my first exposure to logarithms when I got to high school I learned more about them including some of the identities.  Actually I find the Logarithmic Identities to be quite interesting and have found them important in understanding logarithms which are useful in understanding other areas of science and math.  I even used to use log base 10 to calculate the number of digits of numbers for print formatting way back before we had better ways to do number formatting^†, ⌈log₁₀(n)⌉, of any base 10 number is its number of digits, where ⌈x⌉ is the ceiling function.   Also many common measurements like the Richter Scale, pH and Decibel among other things are logarithmic scale.  Also we have previously encountered logs in relation to information entropy.  Some useful logarithmic identities are:

1. y = log_b(x) if and only if x = b ^y
2. log_b(1) = 0
3. log_b(b) = 1
4. -log_b(x) = log_b(1/x)
5. log_b(x*y) = log_b(x) + log_b(y)
6. log_b(x/y) = log_b(x) - log_b(y)
7. log_b(xⁿ) = n log_b(x)
8. log_b(x) = log_b(c) * log_c(x)
9. log_b(x) = log_c(x) / log_c(b)

The first one demonstrates the relation between the functions of logarithm and exponentiation, as you can see the value y, which is log base b of the value x, is the exponent to raise b to get the value x, so a logarithm is just a way to get the exponent. Log base 10 of 100 is 2, log₁₀(100) = 2, since 10 to second power is 100, 10² = 100.  Log base b of y, x = log_b(y) is inverse function of raising b to the y power, x=b^y, so:

b ^log_b(x) = x

Another interesting observation that one can draw from the logarithmic identities is the answer to the question:  What is the difference between O(log₂(x))  and O(log₁₀(x))? It’s a little trick question that I like. The answer is they are the same.  Using the second to last identity (#8):

O(log₂(x))  =  O(log₂(10) * log₁₀(x))

Since log₂(10) is a constant:

O(log₂(x))  =  O(log₁₀(x))

Pretty cool!

This would also work with the second to last identity (#9) as well and remember that Big O notation is about [asymptotic] growth, so equals in the case of Big O notation is not the same as equals e.g. log₂(x) ≠ log₁₀(x). Also for small quantities like the examples in this article, the base does make a difference.

Simlarily exponetiation has its identities as well:

1. b⁰ = 1
2. b¹ = b
3. b^-n = 1/bⁿ
4. b^mbⁿ = b^m+n
5. b^m/bⁿ = b^m-n
6. (b^m)ⁿ = b^mn
7. (b/b)ⁿ = bⁿ/bⁿ
8. (b/a)^-n = (a/b)ⁿ

The binary tree structure (a rooted acyclic graph) visually illustrates O(log(n)) and the inverse function relationship between logarithms and exponentiation.  The diagram above shows a complete^‡ and therefore balanced binary tree structure.  As you can see the number of items in each row grows exponentially as powers of two, shown in red, also the total number of elements in the tree as each row is added grows in the same exponential fashion, denoted in square braces.  So in a balanced tree you will fill all of the n rows up to the 2ⁿ – 1 item, and when that number is exceeded (greater than or equal to 2ⁿ) a new (n + 1) row will be added.   Now the growth is not necessarily exponential, you can add items at any rate, but the structure in which items are stored are broken down along “exponential row boundaries”.   So to search 2⁴ – 1 (15) items for the number 7 value we would traverse 8-4-6-7, shown in green, which is 4 nodes, this is the maximum searches for this tree, a search can also be 1,2, or 3 depending on the depth of the item.  Since 4 the exact exponent of the total size of the graph, which is [2⁴-1], and therefore the log: [log₂(2⁴-1) = 3.9…], almost 4, our max traversal, O(log(2ⁿ-1)) = O(log(2ⁿ)).  Since we know that these two functions are inverses this illustrates O(log(n)) in visual terms.

The Binary Search algorithm has similar log base 2 characteristics, if you remember the algorithm it takes list which has to be ordered, and it repeatedly halves the length of the remaining items and checks the element at each new position, if it is equal you are done, if it is not then depending on whether the search value is greater or less than the midpoint value you then half the bottom or top of the list respectively and repeat the process. This is better illustrated by the following Java code:

public static int binarySearch(int value, int[] array) {

int min = 0;

int max = array.length - 1;

while (min <= max) {

int mid = min + (max - min) / 2;

if (value < array[mid])

max = mid - 1;

else if (value > array[mid])

min = mid + 1;

else

return mid;

}

return -1;

}

The following recursive code example is both more elegant and gives a more intuitive feel for the Divide and Conquer nature of the algorithm. Also it is this Divide and Conquer behavior that breaks the list apart logarithmically.

public static int binarySearch(int value, int[] array) {

returnbinarySearch(value, array, 0, array.length – 1);

}

 

public static intbinarySearch(int value, int[] array, int min, int max) {

if (max < min)

return -1;

int mid = min + (max - min) / 2;

if (array[mid] > value)

return binarySearch(value, array, min, mid - 1);

else if (key > array[mid])

return binarySearch(value, array, mid + 1, max);

return mid;

}

Let's view a search visually:

In our search for the value 7 in our 16 item list we first go to 8, which is too large, then to 4 which is too small and then to 6, and then 7, at each point in our search the size of what remains to be searched is half of the size of the previous search space.

In our visual example needed to search 4 positions (8, 4, 6, 7) and log₂(16) = 4 which is O(log(n)).

An interesting side note is that many binary search algorithms are broken due to possible overflow problems with integers, as pointed out in a blog post by Joshua Bloch, I account for the issue, you can read more about it here.

^† Due to computing a logarithm, this may not be optimally efficient.

^‡ Complete in this context means that all positions up to and including 2ⁿ-1 positions are filled, i.e. have a node. Also it should be noted that Self Balancing algorithms may not yield such a well balanced tree and it might have more rows for 15 items, but it is still O(log(n)).

The Object Graph

In the ORM world, e.g. Hibernate, the term Object Graph is used quite a bit and it is a powerful notion, however, I suspect that Object Graph often gets used without much thought to some of the underlying concepts.  Generally the term refers to an Object, usually a Domain Object which often contains other Domain Objects and/or Collections of other Domain Objects via composition.  With an ORM like Hibernate very complex Object Graphs can be read, altered and persisted with very little work, it is a effective concept that can make building applications both easy and elegant especially if you have the proficiency and forethought to design your mappings properly.

In order to talk more intelligently about some of the underlying concepts regarding the Object Graph it is helpful to get a few fundamentals of Graph Theory out of the way, if you know them feel free to skip ahead.  Actually this is a good opportunity to put them in a context that may be more intuitive for many developers.  Graph Theory is an abstraction, a framework if you will, built on top of Set Theory, however, we don’t need to get bogged down in a Set based definition here, I do encourage you to pursue this on your own as it is extremely seminal and becoming increasingly essential.  We just need to get four fairly simple graph concepts out of the way which can be explained easily and visually, they are: The difference between a simple graph and a multi graph, the difference between a cyclic graph and an acyclic graph, the definition of a directed graph, and the definition of a tree.   Let’s start with the graphs:

As you can see from the above diagram we have several different types of graphs, now it should be noted that these attributes can overlap, the Undirected Graph contains cycles, so it is cyclic as does the Directed Graph, the Multi-Graph¹, by definition contains cycles so it is cyclic this one is also undirected.  The Acyclic Graph is undirected. So these attributes can combine, except for an acyclic multi-graph which by definition can’t exist, I think.

In order to limit complexity for our discussion we are going to limit our object graph to the case of a directed acyclic graph, which is also known as a DAG.  More specifically we will be considering a specific case of this known as a directed rooted tree, where edges have a direction away from the root. The following example shows a "rooted" DAG aka a tree:

As you can see the above tree is also a domain object graph it is also it is a directed graph where the direction indicates containment via composition, which can be thought of as a "has-a" relation.  Now in some cases using ORM’s like hibernate one might include a mapping from Address back to Person so the ORM knows how to manage the relation and this is a cycle but it is an artifact created by the ORM since all accesses to this object graph by the application are from the root (Person node).  Now that is not to say that there might not be other structural reasons for such a cycle, perhaps an application needs to hold a list of addresses, but needs to get some of the Person attributes, then in this use case the Address node becomes the "relative" root from which the application access occurs so the object graph would then have two roots and need a cycle to maintain that duality.

So in many cases in regards to the ORM entity model the object graph can be thought of as a tree, a rooted directed acyclic graph (DAG).  There is one important divergence from traditional graph theory which is the presence of collections in graphs, these form a special node that can have combinatorial enumerative properties, in the case of the various types of collections also it can have certain mapping properties in the case of a Map object. An example of a modified person object that might hold a collection of addresses is:

There are a number of ways to expand on these ideas further but I think I will leave those for future posts. 

 

¹ This is the graph that Euler came up with for famous the Seven Bridges of Königsberg problem. The bridges are shown in the top image.

Free Math Resources You Can Use

In my opinion, this actually may be the best time in human history to learn math, or just about anything for that matter. If you are of sufficient means to have access to the internet, which unfortunately not all people are, you have access to an unprecedented amount of information. The problem is the overwhelming amount of information that is out there and how to find it. So I wanted to share some of my tricks to finding good math information, which I call "Math Mining", of course these can be used for any academic information, so maybe "Academic Mining" may be more apropos.

One of the reasons that the present time is a good time to learn math is due to the diversity of sources for information, Wikipedia is one of those sources, Wiki Surfing, as has been previously discussed, but that is just the tip of the math iceberg and the really cool thing is that there are many resources that can give you entirely new and fresh perspectives on things that may sometimes seem dull and obfuscated by more traditional approaches found in books, not that there aren't a lot of great books too. It really is an exciting time.

Many professors have their publications, notes and course resources freely available on the internet and some of these include full books in pdf or ps or html format. In fact that leads me to my little google trick, let's assume you want to find some information about a math subject, we'll use Linear Algebra as an example. Then if you use the Google search:

"Linear Algebra" inurl:pdf

You will get a lot of hits that are academic pages, these will be a mix of publications and course related material. Once you find a document, you can use that url to find more information. For example let's say that our above search leads us to the following (fictitious) url:

www.math.umars.edu/~hjfarnsworth/math420/fall2010/chapter10.pdf

After you click the link and get your reward, you should realize that this is a potential gateway to much more information. Now admittedly this might be seen as a moral gray area, because sometimes I get the feeling that some of these resources are not as openly exposed as they could be so it may be that the instructors do not want to openly share their work and they are practicing security through obscurity, but in my opinion if directory browsing is enabled and/or your documents are indexed by Google, then they're fair game, so if you are someone who this applies to, I suggest that you either share it openly it or lock it down. I encourage anyone who is sharing their work to do it freely and openly regardless of whether people are taking your classes. After all it's for the greater good. "The greater good." And if you openly share it then people like me can read it, learn it, know it and talk about how awesome you and your work are. It's a win-win.

Hack the Site

Hack #1 Url Suffix Removal

By removing "chapter10.pdf" yielding www.math.umars.edu/~hjfarnsworth/math420/fall2010/ will expose more resources if this directory has browsing enabled or if it has a default page. You can progressively remove directories to find one that is useful, and actually sometimes it is worth it to jump directly to www.math.umars.edu/~hjfarnsworth/ which will often be a professor home page which can yield links to publications, course pages with documents, and other potentially interesting information.

Hack #2 File Name Enumeration

So you looked at chapter10.pdf and it's awesome but Hack #1 did not yield it or the related chapters. Due to the naming convention try: www.math.umars.edu/~hjfarnsworth/math420/fall2010/chapter09.pdf or www.math.umars.edu/~hjfarnsworth/math420/fall2010/chapter9.pdf, often this approach will yield other related documents.

Hack #3 Invoke the Power of Google

Let's say the hack #1 didn't work and the resultant url had a random characteristic like:

www.math.umars.edu/~hjfarnsworth/math420/fall2010/larnd42-chap10.pdf

The following Google search will ferret out those pesky hard to find pdf's:

site:www.math.umars.edu/~hjfarnsworth/ inurl:pdf

Also you can use .ps and .ps.gz in place of .pdf for file type searches. If you feel that this is crossing some kind of moral line then don't do it, but I like to say all is fair in Love and Math.

I would like to give another example of this technique, I recently came across "Mapreduce & Hadoop Algorithms in Academic Papers (4th update - May 2011)" which linked to "Max-cover algorithm in map-reduce" which caught my interest, and of course the ACM is charging for it, but no worries, there is usually no need to pay them, actually I recommend boycotting them. I employed the above tricks but they didn't work, simply Googling one of the authors did (always pick the most unique name(s)):

"Flavio Chierichetti"

Pulled up his web site which had a free copy of the paper, now all I have to do is find the time to read it. Also the above techniques yielded the paper's "cliff notes".

Of course you can just look up someone by name, for example, you can find some of Donald Knuth's publications here.

In regards to academic publications there are two excellent repositories with a wealth of information these are Citeseer out of Penn State, this site can be a little flaky in terms of availability, at least that's been my experience in the past and the other is arXiv run by Cornell University. These mostly contain research oriented work but you can often find relevant information even for neophytes, actually a lot of advanced papers and books for that matter start out with introductory sections that can be worth looking at.

Encyclopedic and other Miscellaneous Resources

Wikipedia, obviously, as previously mentioned. Also the oft controversial Stephen Wolfram provides an excellent resource called Wolfram Mathworld.

Project Euler is a site dedicated to collaboratively solving math oriented problems programmatically more about it can be found here.

Math on the Web by category here provides some interesting links, I believe this is run by the American Mathematical Society but I am not sure.

The National Institute of Standards and Technology site: NIST Digital Library of Mathematical Functions.

Also there is Mathoverflow which is a Stackoverflow type of question and answer community devoted to Math.

Blogs

There are a number of blogs that blog about both math and programming related math. Actually if your primary interest is machine learning, I recommend Bradford Cross's Measuring Measures blog, it is hard to find things on his site and it was recently restyled with a magenta/maroon background which I now find a little bit harder to read. The relevant links here are: Learning About Network Theory, Learning About Statistical Learning, and Learning About Machine Learning, 2nd ed. Additionally Ravi Mohan did a follow-up: Learning about Machine Learning.

Good Math Bad Math by Mark Chu-Carroll has lots of good articles about math including some for beginners in various areas. Catonmat by Peteris Krumins has some nice entries with notes about the online MIT courses that he has worked through which currently covers Algorithms and Linear Algebra also mentioned above. The Unapologetic Mathematician has a lot of nice articles, this is a bit more advanced though. Math-Blog has a lot of articles as well. They tend to focus on more traditional areas of math. Math blog's abound and there are too many to mention, here's a few:

• The n-Category Café
• Michi's blog
• A Neighborhood of Infinity
• XOR's Hammer
• Gödel's Lost Letter and P=NP
• Terrance Tao's Blog
• Arsmathematica
• Steven Strogatz
• Devlin's Angle by Keith Devlin
• The programming/CS Theoretical Lambda The Ultimate

Lastly I will mention a blog by Jeff Moser, actually he only has a few math related posts, but his Computing your Skill on Probability and Statistics is a beautiful work of art well worth looking at.

Online Courses

The well known Khan Academy offers a number of courses including several math courses.

MIT Open Courseware has many online courses most notably for CS majors Introduction to Algorithms by the venerable Charles Leiserson and Erik Demaine videos here and Linear Algebra by Gilbert Strang.

On Stanford Engineering Everywhere the following might be of interest:

Artificial Intelligence | Machine Learning

Artificial Intelligence | Natural Language Processing

Linear Systems and Optimization | The Fourier Transform and its Applications

The Mechanical Universe is primarily dedicated to physics, but several math topics such as Calculus and Vectors are covered explicitly. It's also a nice series of lectures on the topic in spite of being a little dated in productions values.

Other Online Videos

Two math documentaries are covered here are Fermat’s Enigma: The Epic Quest to Solve the World’s Greatest Mathematical Problem and the overly dramatic but still interesting Dangerous Knowledge.

The story of Maths by Marcus du Sautoy.

Keith Devlin talks about Pascal and Fermat's coorespondance while working out probability in this intersting talk: Authors@Google: Keith Devlin.

Bob Franzosa - Introduction to Topology.

The Catsters videos on youtube cover various Category Theory related topics.

N J Wildberger's Algebraic Topology

Dan Spielman has a video discussing Expander Graphs.

Introduction to Game Theory by Benjamin Polak at Yale.

The site videolectures has many lectures in Computer Science and Math including:

• Basics of probability and statistics by Mikaela Keller.
• Probability, Information Theory and Bayesian Inference by Joaquin Quiñonero Candela.
• Introduction To Bayesian Inference by Christopher Bishop
• Information Theory by David MacKay
• Gaussian Process Basics by David MacKay,
• Statistical Learning Theory by John Shawe-Taylor
• Bayesian Learning by Zoubin Ghahramani.

If you find these videos too slow this might interest you.

Math Software

There are many math related software packages and libraries three of which are covered in more detail here.

Math library Sage written in Python

GNU Octave

The R project for Statistical Computing

Scilab

Maxima, a Computer Algebra System

Various Books and Academic Stuff

Here are a bunch of interesting courses and books that I have encountered during my searching which you might find interesting as well. These are presented in no particular order:

Algorithims

Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani.

Jeff Erickson has some Algorithms Course Materials

Steven Skiena author of the The Algorithm Design Manual offers some pretty comprehensive course notes for his cse541 LOGIC for COMPUTER SCIENCE not to mention the opportunity to learn how to bet on Jai-alai in the Cayman Islands.

Gregory Chaitin's Algorithmic Information Theory.

Computer Science

Foundations of Computer Science by Jeffrey Ullman and Al Aho.

The Haskell Road to Logic, Math and Programming by Kees Doets and Jan van Eijck

Discrete Math

Discrete Mathematics with Algorithms by M. O. Albertson and J. P. Hutchinson.

Analysis

Analysis WebNotes is a self-contained course in Mathematical Analysis for undergraduates or beginning graduate students.

Introduction to Analysis Lecture Notes by Vitali Liskevich.

Applied Analysis by John Hunter and Bruno Nachtergaele.

REAL ANALYSIS by Gabriel Nagy.

Probability Theory

Introduction to Probability Theory by Ali Ghodsi.

Introduction to Probability by Charles M. Grinstead.

The first three chapters of Probability Theory: The Logic of Science by E. T. Jaynes. Can be found here.

Think Stats: Probability and Statistics for Programmers by Allen B. Downey.

LECTURE NOTES MEASURE THEORY and PROBABILITY by Rodrigo Bañuelos.

Principles of Uncertainty by by Chapman and Hall.

Information Theory, Inference, and Learning Algorithms by David MacKay.

Machine Learning/Date Mining

Machine Learning Module ML(M) by M. A .Girolami.

Alexander J. Smola's and and S.V.N. Vishwanathan's draft of Introduction to Machine Learning.

The Elements of Statistical Learning: Data Mining, Inference, and Prediction (Second Edition) by Trevor Hastie, Robert Tibshirani and Jerome Friedman.

Introduction to Information Retrieval by Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze.

Mining of Massive Datasets by Jeffrey Ullman.

Fourier Theory

Lecture Notes for EE 261 The Fourier Transform and its Applications pdf By Brad Osgood.

Abstract Algebra

Abstract Algebra by Thomas W. Judson.

James Milne has a number of sets of extensive notes on Algebraic topics like goup theory here.

ABSTRACT ALGEBRA: A STUDY GUIDE FOR BEGINNERS by John A. Beachy.

Elements of Abstract and Linear Algebra Edwin H. Connell.

Abstract Algebra by Elbert A. Walker.

A series of chapters on groups by Christopher Cooper.

Linear Algebra

Linear Algebra by Robert A. Beezer.

A course on Linear Algebra with book chapters.

Really cool interactive tutorial on Singular Value Decomposition by Todd Will.

Model Theory

Fundamentals of Model Theory pdf by William Weiss and Cherie D'Mello.

Set Theory

A book on Set Theory pdf by William Weiss.

Graph Theory

Reinhard Diestel makes his excellent and comprehensive book Graph Theory available, pdf here.

Logic

You can find Introduction to Mathematical Logic by J. Adler, J. Schmid, Model Theory, Universal Algebra and Order by J. Adler, J. Schmid, M. Sprenger and other goodies here.

Introduction to Logic by Michal Walicki.

Logic for Computer Science: Foundations of Automatic Theorem Proving by Jean Gallier.

The Novel Research Institute has a number of free academic books including: Logic and Metalogic:Logic, Metalogic, Fuzzy and Quantum Logics and Algebraic Topology, Category Theory and Higher Dimensional Algebra-Results and Applications to Quantum Physics

Category Theory

Some course notes on Category Theory by Tom Leinster.

Basic Category Theory pdf by Jaap van Oosten.

Abstract and Concrete Categories The Joy of Cats by Jiri Adámek, Horst Herrlich, George E. Strecker.

A gentle introduction to category theory --- the calculational approach pdf by Maarten M. Fokkinga.

Steve Easterbrook's An introduction to Category Theory for Software Engineers.

Algebraic Topology/Topos Theory

Eugenia Cheng of Catsters fame has a course in Algebraic Topology with some substantial notes.

The above links of Eugenia Cheng refer to Algebraic Topology by Allen Hatcher.

An informal introduction to topos theory pdf by Tom Leinster.

Topology

A free, protected, password available by request, e-book on topology: Topology without Tears by Sidney A. Morris.

Chapters for a topology course by Anatole Katok can be found here.

Computational Topology

Jeff Erickson has some nice notes on Computational Topology, pdf's can be found on the schedule page.

Afra Zomorodian has some nice resources on Computational Topology including a nice introductory paper.

Spectral Graph Theory

Fan Chung Graham has a lot interesting stuff, some pretty advanced, relating to graph theory including social graph theory and spectral graph theory.

Dan Spielman has some course notes on Spectral Graph Theory.

Expander Graphs

Avi Wigderson's Expander Graphs and their Applications.

Fractal Geometry

The Algorithmic Beauty of Plants pdf by Przemyslaw Prusinkiewicz and Aristid Lindenmayer is available on the Algorithmic Botany site.

Game Theory

Thomas S. Ferguson's course at UCLA on Game Theory also Game Theory for Statisticians.

A course in game theory by Martin J. Osborne and Ariel Rubinstein, requires registration.

Algebraic/Enumerative Combinatorics

MIT Open Courseware in Algebraic Combinatorics

An uncompleted book and notes on Enumerative Combinatorics by the Late Kenneth P. Bogart also here.

Lionel Levine's notes on Algebraic Combinatorics

Richard P. Stanley new edition of Enumerative Combinatorics Volume one.

A Course in Universal Algebra by Stanley N. Burris and H.P. Sankappanavar

Misc

Pat Hanrahan's CS448B: Visualization.

Sean Luke's "Essentials of Metaheuristics".

It's all a click away

The links in this entry, especially the academic links are susceptible to link rot, people move from institution to institution or leave academia for jobs in the private sector. I will endeavor to revisit this entry and try to keep these up to date and perhaps even add to them, however, if you encounter this page and have any interest in any or all of these resources I recommend downloading them now so that you have them.

Using the resources of this blog you should be able to get your hands on a huge amount of free resources on a wide range of topics. This can be helpful if you are on a budget or just want to try before you buy an expensive book on a topic. I hope you avail yourself of some of these, there's lots of great stuff and if you know of some that I do not please add them in the comments.