Concrete Mathematics

Ronald L. Graham, Donald Ervin Knuth, Oren Patashnik

Mentioned 24

This book, updated and improved, introduces the mathematics that supports advanced computer programming and the analysis of algorithms. The primary aim of its well-known authors is to provide a solid and relevant base of mathematical skills--the skills needed to solve complex problems, to evaluate horrendous-looking sums, to solve complex recurrence relations, and to discover subtle patterns in data. It is an indispensable text and reference, not only for computer scientists but for all technical professionals in virtually every discipline.

More on Amazon.com

Mentioned in questions and answers.

If you could go back in time and tell yourself to read a specific book at the beginning of your career as a developer, which book would it be?

I expect this list to be varied and to cover a wide range of things.

To search: Use the search box in the upper-right corner. To search the answers of the current question, use inquestion:this. For example:

inquestion:this "Code Complete"

Applying UML and Patterns by Craig Larman.

The title of the book is slightly misleading; it does deal with UML and patterns, but it covers so much more. The subtitle of the book tells you a bit more: An Introduction to Object-Oriented Analysis and Design and Iterative Development.

Masters of doom. As far as motivation and love for your profession go: it won't get any better than what's been described in this book, truthfully inspiring story!

Beginning C# 3.0: An Introduction to Object Oriented Programming

This is the book for those who want to understand the whys and hows of OOP using C# 3.0. You don't want to miss it.

alt text

Mastery: The Keys to Success and Long-Term Fulfillment, by George Leonard

It's about about what mindsets are required to reach mastery in any skill, and why. It's just awesome, and an easy read too.

Pro Spring is a superb introduction to the world of Inversion of Control and Dependency Injection. If you're not aware of these practices and their implications - the balance of topics and technical detail in Pro Spring is excellent. It builds a great case and consequent personal foundation.

Another book I'd suggest would be Robert Martin's Agile Software Development (ASD). Code smells, agile techniques, test driven dev, principles ... a well-written balance of many different programming facets.

More traditional classics would include the infamous GoF Design Patterns, Bertrand Meyer's Object Oriented Software Construction, Booch's Object Oriented Analysis and Design, Scott Meyer's "Effective C++'" series and a lesser known book I enjoyed by Gunderloy, Coder to Developer.

And while books are nice ... don't forget radio!

... let me add one more thing. If you haven't already discovered safari - take a look. It is more addictive than stack overflow :-) I've found that with my google type habits - I need the more expensive subscription so I can look at any book at any time - but I'd recommend the trial to anyone even remotely interested.

(ah yes, a little obj-C today, cocoa tomorrow, patterns? soa? what was that example in that cookbook? What did Steve say in the second edition? Should I buy this book? ... a subscription like this is great if you'd like some continuity and context to what you're googling ...)

Database System Concepts is one of the best books you can read on understanding good database design principles.

alt text

Algorithms in C++ was invaluable to me in learning Big O notation and the ins and outs of the various sort algorithms. This was published before Sedgewick decided he could make more money by dividing it into 5 different books.

C++ FAQs is an amazing book that really shows you what you should and shouldn't be doing in C++. The backward compatibility of C++ leaves a lot of landmines about and this book helps one carefully avoid them while at the same time being a good introduction into OO design and intent.

Here are two I haven't seen mentioned:
I wish I had read "Ruminations on C++" by Koenig and Moo much sooner. That was the book that made OO concepts really click for me.
And I recommend Michael Abrash's "Zen of Code Optimization" for anyone else planning on starting a programming career in the mid 90s.

Perfect Software: And Other Illusions about Testing

TITLE Cover

Perfect Software: And Other Illusions about Testing by Gerald M. Weinberg

ISBN-10: 0932633692

ISBN-13: 978-0932633699

Rapid Development by McConnell

The most influential programming book for me was Enough Rope to Shoot Yourself in the Foot by Allen Holub.

Cover of the book

O, well, how long ago it was.

I have a few good books that strongly influenced me that I've not seen on this list so far:

The Psychology of Everyday Things by Donald Norman. The general principles of design for other people. This may seem to be mostly good for UI but if you think about it, it has applications almost anywhere there is an interface that someone besides the original developer has to work with; e. g. an API and designing the interface in such a way that other developers form the correct mental model and get appropriate feedback from the API itself.

The Art of Software Testing by Glen Myers. A good, general introduction to testing software; good for programmers to read to help them think like a tester i. e. think of what may go wrong and prepare for it.

By the way, I realize the question was the "Single Most Influential Book" but the discussion seems to have changed to listing good books for developers to read so I hope I can be forgiven for listing two good books rather than just one.

alt text

C++ How to Program It is good for beginner.This is excellent book that full complete with 1500 pages.

Effective C++ and More Effective C++ by Scott Myers.

Inside the C++ object model by Stanley Lippman

I bough this when I was a complete newbie and took me from only knowing that Java existed to a reliable team member in a short time

Not a programming book, but still a very important book every programmer should read:

Orbiting the Giant Hairball by Gordon MacKenzie

The Pragmatic programmer was pretty good. However one that really made an impact when I was starting out was :

Windows 95 System Programming Secrets"

I know - it sounds and looks a bit cheesy on the outside and has probably dated a bit - but this was an awesome explanation of the internals of Win95 based on the Authors (Matt Pietrek) investigations using his own own tools - the code for which came with the book. Bear in mind this was before the whole open source thing and Microsoft was still pretty cagey about releasing documentation of internals - let alone source. There was some quote in there like "If you are working through some problem and hit some sticking point then you need to stop and really look deeply into that piece and really understand how it works". I've found this to be pretty good advice - particularly these days when you often have the source for a library and can go take a look. Its also inspired me to enjoy diving into the internals of how systems work, something that has proven invaluable over the course of my career.

Oh and I'd also throw in effective .net - great internals explanation of .Net from Don Box.

I recently read Dreaming in Code and found it to be an interesting read. Perhaps more so since the day I started reading it Chandler 1.0 was released. Reading about the growing pains and mistakes of a project team of talented people trying to "change the world" gives you a lot to learn from. Also Scott brings up a lot of programmer lore and wisdom in between that's just an entertaining read.

Beautiful Code had one or two things that made me think differently, particularly the chapter on top down operator precedence.

K&R

@Juan: I know Juan, I know - but there are some things that can only be learned by actually getting down to the task at hand. Speaking in abstract ideals all day simply makes you into an academic. It's in the application of the abstract that we truly grok the reason for their existence. :P

@Keith: Great mention of "The Inmates are Running the Asylum" by Alan Cooper - an eye opener for certain, any developer that has worked with me since I read that book has heard me mention the ideas it espouses. +1

I found the The Algorithm Design Manual to be a very beneficial read. I also highly recommend Programming Pearls.

This one isnt really a book for the beginning programmer, but if you're looking for SOA design books, then SOA in Practice: The Art of Distributed System Design is for you.

For me it was Design Patterns Explained it provided an 'Oh that's how it works' moment for me in regards to design patterns and has been very useful when teaching design patterns to others.

Code Craft by Pete Goodliffe is a good read!

Code Craft

The first book that made a real impact on me was Mastering Turbo Assembler by Tom Swan.

Other books that have had an impact was Just For Fun by Linus Torvalds and David Diamond and of course The Pragmatic Programmer by Andrew Hunt and David Thomas.

In addition to other people's suggestions, I'd recommend either acquiring a copy of SICP, or reading it online. It's one of the few books that I've read that I feel greatly increased my skill in designing software, particularly in creating good abstraction layers.

A book that is not directly related to programming, but is also a good read for programmers (IMO) is Concrete Mathematics. Most, if not all of the topics in it are useful for programmers to know about, and it does a better job of explaining things than any other math book I've read to date.

For me "Memory as a programming concept in C and C++" really opened my eyes to how memory management really works. If you're a C or C++ developer I consider it a must read. You will defiantly learn something or remember things you might have forgotten along the way.

http://www.amazon.com/Memory-Programming-Concept-C/dp/0521520436

Agile Software Development with Scrum by Ken Schwaber and Mike Beedle.

I used this book as the starting point to understanding Agile development.

Systemantics: How Systems Work and Especially How They Fail. Get it used cheap. But you might not get the humor until you've worked on a few failed projects.

The beauty of the book is the copyright year.

Probably the most profound takeaway "law" presented in the book:

The Fundamental Failure-Mode Theorem (F.F.T.): Complex systems usually operate in failure mode.

The idea being that there are failing parts in any given piece of software that are masked by failures in other parts or by validations in other parts. See a real-world example at the Therac-25 radiation machine, whose software flaws were masked by hardware failsafes. When the hardware failsafes were removed, the software race condition that had gone undetected all those years resulted in the machine killing 3 people.

It seems most people have already touched on the some very good books. One which really helped me out was Effective C#: 50 Ways to Improve your C#. I'd be remiss if I didn't mention The Tao of Pooh. Philosophy books can be good for the soul, and the code.

Discrete Mathematics For Computer Scientists

Discrete Mathematics For Computer Scientists by J.K. Truss.

While this doesn't teach you programming, it teaches you fundamental mathematics that every programmer should know. You may remember this stuff from university, but really, doing predicate logic will improve you programming skills, you need to learn Set Theory if you want to program using collections.

There really is a lot of interesting information in here that can get you thinking about problems in different ways. It's handy to have, just to pick up once in a while to learn something new.

I saw a review of Software Factories: Assembling Applications with Patterns, Models, Frameworks, and Tools on a blog talking also about XI-Factory, I read it and I must say this book is a must read. Altough not specifically targetted to programmers, it explains very clearly what is happening in the programming world right now with Model-Driven Architecture and so on..

Solid Code Optimizing the Software Development Life Cycle

Although the book is only 300 pages and favors Microsoft technologies it still offers some good language agnostic tidbits.

Managing Gigabytes is an instant classic for thinking about the heavy lifting of information.

My vote is "How to Think Like a Computer Scientist: Learning With Python" It's available both as a book and as a free e-book.

It really helped me to understand the basics of not just Python but programming in general. Although it uses Python to demonstrate concepts, they apply to most, if not all, programming languages. Also: IT'S FREE!

Object-Oriented Programming in Turbo C++. Not super popular, but it was the one that got me started, and was the first book that really helped me grok what an object was. Read this one waaaay back in high school. It sort of brings a tear to my eye...

My high school math teacher lent me a copy of Are Your Lights Figure Problem that I have re-read many times. It has been invaluable, as a developer, and in life generally.

I'm reading now Agile Software Development, Principles, Patterns and Practices. For those interested in XP and Object-Oriented Design, this is a classic reading.

alt text

Kernighan & Plauger's Elements of Programming Style. It illustrates the difference between gimmicky-clever and elegant-clever.

to get advanced in prolog i like these two books:

The Art of Prolog

The Craft of Prolog

really opens the mind for logic programming and recursion schemes.

Here's an excellent book that is not as widely applauded, but is full of deep insight: Agile Software Development: The Cooperative Game, by Alistair Cockburn.

What's so special about it? Well, clearly everyone has heard the term "Agile", and it seems most are believers these days. Whether you believe or not, though, there are some deep principles behind why the Agile movement exists. This book uncovers and articulates these principles in a precise, scientific way. Some of the principles are (btw, these are my words, not Alistair's):

  1. The hardest thing about team software development is getting everyone's brains to have the same understanding. We are building huge, elaborate, complex systems which are invisible in the tangible world. The better you are at getting more peoples' brains to share deeper understanding, the more effective your team will be at software development. This is the underlying reason that pair programming makes sense. Most people dismiss it (and I did too initially), but with this principle in mind I highly recommend that you give it another shot. You wind up with TWO people who deeply understand the subsystem you just built ... there aren't many other ways to get such a deep information transfer so quickly. It is like a Vulcan mind meld.
  2. You don't always need words to communicate deep understanding quickly. And a corollary: too many words, and you exceed the listener/reader's capacity, meaning the understanding transfer you're attempting does not happen. Consider that children learn how to speak language by being "immersed" and "absorbing". Not just language either ... he gives the example of some kids playing with trains on the floor. Along comes another kid who has never even SEEN a train before ... but by watching the other kids, he picks up the gist of the game and plays right along. This happens all the time between humans. This along with the corollary about too many words helps you see how misguided it was in the old "waterfall" days to try to write 700 page detailed requirements specifications.

There is so much more in there too. I'll shut up now, but I HIGHLY recommend this book!

alt text

The Back of the Napkin, by Dan Roam.

The Back of the Napkin

A great book about visual thinking techniques. There is also an expanded edition now. I can't speak to that version, as I do not own it; yet.

Agile Software Development by Alistair Cockburn

Do users ever touch your code? If you're not doing solely back-end work, I recommend About Face: The Essentials of User Interface Design — now in its third edition (linked). I used to think my users were stupid because they didn't "get" my interfaces. I was, of course, wrong. About Face turned me around.

"Writing Solid Code: Microsoft's Techniques for Developing Bug-Free C Programs (Microsoft Programming Series)" by Steve MacGuire.

Interesting what a large proportion the books mentioned here are C/C++ books.

While not strictly a software development book, I would highly recommend that Don't Make me Think! be considered in this list.

As so many people have listed Head First Design Patterns, which I agree is a very good book, I would like to see if so many people aware of a title called Design Patterns Explained: A New Perspective on Object-Oriented Design.

This title deals with design patterns excellently. The first half of the book is very accessible and the remaining chapters require only a firm grasp of the content already covered The reason I feel the second half of the book is less accessible is that it covers patterns that I, as a young developer admittedly lacking in experience, have not used much.

This title also introduces the concept behind design patterns, covering Christopher Alexander's initial work in architecture to the GoF first implementing documenting patterns in SmallTalk.

I think that anyone who enjoyed Head First Design Patterns but still finds the GoF very dry, should look into Design Patterns Explained as a much more readable (although not quite as comprehensive) alternative.

Even though i've never programmed a game this book helped me understand a lot of things in a fun way.

How influential a book is often depends on the reader and where they were in their career when they read the book. I have to give a shout-out to Head First Design Patterns. Great book and the very creative way it's written should be used as an example for other tech book writers. I.e. it's written in order to facilitate learning and internalizing the concepts.

Head First Design Patterns

97 Things Every Programmer Should Know

alt text

This book pools together the collective experiences of some of the world's best programmers. It is a must read.

Extreme Programming Explained: Embrace Change by Kent Beck. While I don't advocate a hardcore XP-or-the-highway take on software development, I wish I had been introduced to the principles in this book much earlier in my career. Unit testing, refactoring, simplicity, continuous integration, cost/time/quality/scope - these changed the way I looked at development. Before Agile, it was all about the debugger and fear of change requests. After Agile, those demons did not loom as large.

One of my personal favorites is Hacker's Delight, because it was as much fun to read as it was educational.

I hope the second edition will be released soon!

You.Next(): Move Your Software Development Career to the Leadership Track ~ Michael C. Finley (Author), Honza Fedák (Author) link text

I've been arounda while, so most books that I have found influential don't necessarily apply today. I do believe it is universally important to understand the platform that you are developing for (both hardware and OS). I also think it's important to learn from other peoples mistakes. So two books I would recommend are:

Computing Calamities and In Search of Stupidity: Over Twenty Years of High Tech Marketing Disasters

Working Effectively with Legacy Code is a really amazing book that goes into great detail about how to properly unit test your code and what the true benefit of it is. It really opened my eyes.

How can I calculate the time complexity of a recursive algorithm?

int pow1(int x,int n) {
    if(n==0){
        return 1;
    }
    else{
        return x * pow1(x, n-1);
    }
}

int pow2(int x,int n) {
    if(n==0){
        return 1;
    }
    else if(n&1){
        int p = pow2(x, (n-1)/2)
        return x * p * p;
    }
    else {
        int p = pow2(x, n/2)
        return p * p;
    }
}

Analyzing recursive functions (or even evaluating them) is a nontrivial task. A (in my opinion) good introduction can be found in Don Knuths Concrete Mathematics.

However, let's analyse these examples now:

We define a function that gives us the time needed by a function. Let's say that t(n) denotes the time needed by pow(x,n), i.e. a function of n.

Then we can conclude, that t(0)=c, because if we call pow(x,0), we have to check whether (n==0), and then return 1, which can be done in constant time (hence the constant c).

Now we consider the other case: n>0. Here we obtain t(n) = d + t(n-1). That's because we have again to check n==1, compute pow(x, n-1, hence (t(n-1)), and multiply the result by x. Checking and multiplying can be done in constant time (constant d), the recursive calculation of pow needs t(n-1).

Now we can "expand" the term t(n):

t(n) =
d + t(n-1) = 
d + (d + t(n-2)) = 
d + d + t(n-2) = 
d + d + d + t(n-3) =
... =
d + d + d + ... + t(1) =
d + d + d + ... + c

So, how long does it take until we reach t(1)? Since we start at t(n) and we subtract 1 in each step, it takes n-1 steps to reach t(n-(n-1)) = t(1). That, on the other hands, means, that we get n-1 times the constant d, and t(1) is evaluated to c.

So we obtain:

t(n) =
...
d + d + d + ... + c =
(n-1) * d + c

So we get that t(n)=(n-1) * d + c which is element of O(n).

pow2 can be done using Masters theorem. Since we can assume that time functions for algorithms are monotonically increasing. So now we have the time t(n) needed for the computation of pow2(x,n):

t(0) = c (since constant time needed for computation of pow(x,0))

for n>0 we get

        / t((n-1)/2) + d if n is odd  (d is constant cost)
t(n) = <
        \ t(n/2) + d     if n is even (d is constant cost)

The above can be "simplified" to:

t(n) = floor(t(n/2)) + d <= t(n/2) + d (since t is monotonically increasing)

So we obtain t(n) <= t(n/2) + d, which can be solved using the masters theorem to t(n) = O(log n) (see section Application to Popular Algorithms in the wikipedia link, example "Binary Search").

It takes about minute to achieve 3000 in my comp but I need to know the millionth number in the series. The definition is recursive so I cannot see any shortcuts except to calculate everything before the millionth number. How can you fast calculate millionth number in the series?

Series Def

n_{i+1} = \floor{ 3/2 * n_{i} } and n_{0}=2.

Interestingly, only one site list the series according to Google: this one.

Too slow Bash code

#!/bin/bash

function series 
{
        n=$( echo "3/2*$n" | bc -l | tr '\n' ' ' | sed -e 's@\\@@g' -e 's@ @@g' );
                                        # bc gives \ at very large numbers, sed-tr for it
        n=$( echo $n/1 | bc )           #DUMMY FLOOR func
}

n=2
nth=1

while [ true ]; #$nth -lt 500 ];
do
        series $n                        # n gets new value in the function through global value
        echo $nth $n
        nth=$( echo $nth + 1 | bc )     #n++
done

This is identified as sequence A061418 in the sequences site (AKA "The On-Line Encyclopedia of Integer Sequences"); per the relevant page,

FORMULA a(n) =A061419(n)+1 = ceiling[K*(3/2)^n] where K=1.08151366859... The constant K is 2/3*K(3) (see A083286).

and with a suitable high-precision library (GMP as already suggested, or MPIR, and maybe a wrapper on top like my baby gmpy is for Python) you can used the closed-form formula for much speedier computation of "the millionth item in the series" and the like.

It's often possible to put recursively specified recurrences into closed formulas. For an extensive beginner's introduction to the subject, Concrete Mathematics (by Graham, Knuth and Patashnik) is really hard to beat.

I've taken everything up to pre-calculus in college, but when trying to get through things like the Donald Knuth books, or even things like this link: http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree I wind up looking at math that means absolutely nothing to me. I'm not looking for magic, I don't expect to make sense of this in a week, I'm just looking for a good graduated plan of things to read / explore to get me there. Any pointers are welcome, after 20+ years as a professional programmer, I feel it would be nice to have this under my belt. Thanks in advance to everyone! :-)

You can try this: http://www.amazon.com/Concrete-Mathematics-Foundation-Computer-Science/dp/0201558025

There's a pdf version of this available online, you can easily google it out.

Many of my friends who are great programmers recommended it.

My degree is in Electrical and Computer Engineering but i'm currently employed as a Software Engineer. I took all of the algebra, geometry and calculus classes that one would expect from someone with my degree however I must admit, I think I learned just enough to pass the test but never really saw a use for it and therefore never really retained much of the material.

Now that i've matured some, I see the use for it all of the time. I KNOW that there are lots of places that math knowledge would improve my coding so i'm ready to relearn the old stuff and learn some new stuff.

What are your favorite resources out there? (Resources that can tie math into programming are even better if you have any!) Books? Websites? Blogs?

Knuth. http://www.amazon.com/Art-Computer-Programming-Volumes-Boxed/dp/0201485419

Or as I like to refer to it: The guy that made me realize I hadn't actually invented or discovered anything that hadn't been known for years.

I really like the book Mastering Technical Mathematics 3rd Edition. It's kind of a bird's-eye view of mathematics with a technical focus. It starts out with such simple concepts as addition and multiplication, but as it explains the concepts it also explains how computers do the calculations. About half-way through you'll find quadratic equations and calculus. Page 442 begins the discussion of "General Time-Space Hypervolume". I didn't see anything about matrix math in there, but for a good "everything about math in a nutshell"-type book it's great.

Math Refresher for Scientists and Engineers (by John R. Fanchi)

Just-In-Time Math for Engineers (by Archibald L. Fripp, Jon B. Fripp and Michael L. Fripp)

Every so often I get the impression that my knowledge of mathematics (as it pertains to the field of software development) has some gaps. I'm an educated person. I have a college degree. I've always enjoyed learning, which is why I would like to try to fill in these gaps.

My job is in the financial industry, and I feel like many of the large-scale number crunching tasks that we do could be made more efficient, possibly, if I had a better grasp on the mathematics/logic that's going into it, or concepts that could be leveraged as a shortcut.

Do you have any suggestions? Books that you've found helped with this? Video lectures?

EDIT: I should note that my degree is in Computer Science, so I am familiar with some of the areas of mathematics that are relevant. I'm just not sure how best to brush up on them or to refine what I already know :)

You should know probability and statistics. I went through this in my undergraduate physics program. Stanford offers free lectures on math and physics, I think you can access them here still (many universities are now doing this public video lectures idea). And something that one of the creators of this site just recommended.

Concrete Mathematics. This is a college textbook by Knuth that emphasizes practical problem solving in areas relevant to programmers.

I haven't taken any math classes above basic college calculus. However, in the course of my programming work, I've picked up a lot of math and comp sci from blogs and reading, and I genuinely believe I have a decent mathematical mind. I enjoy and have success doing Project Euler, for example.

I want to dive in and really start learning some cool math, particularly discrete mathematics, set theory, graph theory, number theory, combinatorics, category theory, lambda calculus, etc. My impression so far is that I'm well equipped to take these on at a conceptual level, but I'm having a really hard time with the mathematical language and symbols. I just don't "speak the language" and though I'm trying to learn it, I'm the going is extremely slow. It can take me hours to work through even one formula or terminology heavy paragraph. And yeah, I can look up terms and definitions, but it's a terribly onerous process that very much obscures the theoretical simplicity of what I'm trying to learn.

I'm really afraid I'm going to have to back up to where I left off, get a mid-level math textbook, and invest some serious time in exercises to train myself in that way of thought. This sounds amazingly boring, though, so I wondered if anyone else has any ideas or experience with this.

Sounds like you're in the same position I am. What I'm finding out about math education is that most of it is taught incorrectly. Whether a cause or result of this, I also find most math texts are written incorrectly. Exceptions are rare, but notable. For instance, anything written by Donald Knuth is a step in the right direction.

Here are a couple of articles that state the problem quite clearly:

And here's an article on a simple study technique that aims at retaining knowledge:

To this list I would now add The Haskel Road to Logic, Maths, and Programming, and Conceptual Mathematics: A First Introduction to Categories.

--- Nov 16 '09 answer for posterity--

Two books. Diestel's Graph Theory, and Knuth's Concrete Mathematics. Once you get the hang of those try CAGES.

A professor asked me to help making a specification for a college project. By the time the students should know the basics of programming.

The professor is a mathematician and has little experience in other programming languages, so it should really be in MATLAB.

I would like some projects ideas. The project should

  1. last about 1 to 2 months
    • be done individually
    • have web interface would be great
    • doesn't necessary have to go deep in maths, but some would be great
    • use a database (or store data in files)

What kind of project would make the students excited?

If you have any other tips I'll appreciate.

UPDATE: The students are sophomores and have already studied vector calculus. This project is for an one year Discrete Mathematics course.

UPDATE 2: The topics covered in the course are

  1. Formal Logic
  2. Proofs, Recursion, and Analysis of Algorithms
  3. Sets and Combinatorics
  4. Relations, Functions, and Matrices
  5. Graphs and Trees
  6. Graph Algorithms
  7. Boolean Algebra and Computer Logic
  8. Modeling Arithmetic, Computation, and Languages

And it'll be based on this book Mathematical Structures for Computer Science: A Modern Approach to Discrete Mathematics by Judith L. Gersting

General Suggestions:

There are many teaching resources at The MathWorks that may give you some ideas for course projects. Some sample links:

Specific Suggestions:

One of my grad school projects in non-linear dynamics that I found interesting dealt with Lorenz oscillators. A Lorenz oscillator is a non-linear system of three variables that can exhibit chaotic behavior. Such a system would provide an opportunity to introduce the students to numerical computation (iterative methods for simulating systems of differential equations, stability and convergence, etc.).

The most interesting thing about this project was that we were using Lorenz oscillators to encode and decode signals. This "encrypted communication" aspect was really cool, and was based on the following journal article:

Kevin M. Cuomo and Alan V. Oppenheim, Circuit Implementation of Synchronized Chaos with Applications to Communications, Physical Review Letters 71(1), 65-68 (1993)

The article addresses hardware implementations of a chaotic communication system, but the equivalent software implementation should be simple enough to derive (and much easier for the students to implement!).

Some other useful aspects of such a project:

  • The behavior of the system can be visualized in 2-D and 3-D plots, thus exposing the students to a number of graphing utilities in MATLAB (PLOT, PLOT3, COMET, COMET3, etc.).
  • Audio signals can be read from files, encrypted using the Lorenz equations, written out to a new file, and then decrypted once again. You could even have the students each encrypt a signal with their Lorenz oscillator code and give it to another student to decrypt. This would introduce them to various file operations (FREAD, FWRITE, SAVE, LOAD, etc.), and you could even introduce them to working with audio data file formats.
  • You can introduce the students to the use of the PUBLISH command in MATLAB, which allows you to format M-files and publish them to various output types (like HTML or Word documents). This will teach them techniques for making useful help documentation for their MATLAB code.

MATLAB started life as a MATrix LAB, so maybe concentrating on problems in linear algebra would be a natural fit.

Discrete math problems using matricies include:

  1. Spanning trees and shortest paths
  2. The marriage problem (bipartite graphs)
  3. Matching algorithms
  4. Maximal flow in a network
  5. The transportation problem

See Gil Strang's "Intro to Applied Math" or Knuth's "Concrete Math" for ideas.

Math skills are becoming more and more essential, and I wonder where is a good place to brush up on some basics before moving on to some more CompSci specific stuff?

A site with lots of video's as well as practice exercises would be a double win but I can't seem to find one.

I suggest books with good tutorials throughout if you're unable to partake in a maths course. For computer science-related maths Don Knuth's Concrete Mathematics is meant to be very good.

Obviously nothing can replace a good teacher, but good tutorials can come pretty damn close. You really get to learn the subject in the tutorials I think.

Where can I find e-books on Data Structures and Algorithms? I am currently reading "Computer Algorithms: Introduction to design and Analysis" by Sara Baase and Allen Van Gelder. I would like to have additional information to supplement what's in this book. Also some references on worst-case analysis would be great.

Introduction to Algorithms

The Art of Computer Programming - by Donald Knuth (hard read, but well worth it, not recommended for a first algorithms book)

Concrete Mathemetics - By Donald Knuth (understanding the math behind algorithms)

I don't know if e-book versions are available for these, but if they are...these books will definitely give you the theory behind worst-case, and asymptotic analysis of algorithms.

Possible Duplicate:
Plain English explanation of Big O

I can't find any sufficient help for learn or understand about O-notation, and how learn about time or space complexity. So please suggest me , where can I start this. Its really need to me, for now these time.So please give me solution quick. Thanks a lot in advance.

Algorithms

Introduction to Algorithms

Also http://en.wikipedia.org/wiki/Big_O_notation

Also, there are some great lectures out there on youtube and itunesU

"Concrete Mathematics: A Foundation for Computer Science (2nd Edition)" would be another book recommendation I'd toss out there. Big O isn't that difficult but it can take a while to get the hang of what it is trying to convey.

I have a number of slots and pegs arranged in a straight line. The pegs can be moved and need to be moved to a slot each. A slot can be left empty only if all pegs are taken. When a peg is moved, it is not allowed to go past another peg. In other words the order of the pegs must be maintained. Preferably, the total distance moved by all pegs should be kept at a minimum. As far as possible, a peg should be placed in the nearest available slot.

All I want to know is: What field of mathematics deals with such a problem? What are the names of any well known algorithms which deal with similar problems? I am looking for Google fodder. Some keywords.

+--oooo-+--+---+---o--+------+--+-ooo+o-+-------o--+-----o-o-+-o

+ - Slots
o - Pegs


EDIT: I think that this visualization makes more sense. They are two separate tracks that need to line up.

Slots: +-------+--+---+------+------+--+----+--+----------+---------+--
Pegs:  ---oooo------------o--------------ooo-o---------o--------o-o---o

EDIT: Just want to make it clear that the number of slots can be greater than, less than or equal to the number of pegs.

Combinatorics. Combinatorial algorithms. Concrete mathematics. (Also the title of an excellent and relevant book by Donald Knuth.

I'm stuck on this cryptography problem using multiplication of a whole number and a fraction mod 10.

Here is the equation:

7 * (4/11) mod 10 =?

I know I am supposed to convert this to an integer since the mod operator does not work with fractions, but I cannot figure this one out. Obviously,

7 * (4/11) = 28/11,

but I cannot get the mod 10 of a fraction. The instructor wants the exact answer, not a decimal. Any help would be greatly appreciated!

Have a look here: "Is it possible to do modulo of a fraction" on math.stackexchange.com.

One natural way to define the modular function is

a (mod b) = a − b ⌊a / b⌋

where ⌊⋅⌋ denotes the floor function. This is the approach used in the influential book Concrete Mathematics by Graham, Knuth, Patashnik.

This will give you 1/2(mod3)=1/2.

To work through your problem, you have a = 7 * (4/11) = 28/11, and b = 10.

a / b = (28/11)/10 = 0.25454545...

⌊a/b⌋ = 0

b ⌊a/b⌋ = 0 * 0 = 0

a - b ⌊a/b⌋ = 28/11 - 0 = 28/11

This means your answer is 28/11.

Wolfram Alpha agrees with me and gives 28/11 as the exact result. Google also agrees, but gives it as a decimal, 2.54545454.....

A fraction is an exact answer and not a decimal.

I've been trying to read and understand the contents of this book: http://www.amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/0262033844

But I'm finding the contents to be challenging purely because I don't understand the mathematical or pseudo code notation. Are there any resources or books I should read / study in order to help me understand the content? I think I'm looking for the missing mathematical link in my life. I need something to bridge the gap between school and college level.

Thanks Chris

Be sure to read the first sections and the appendix at the end of the book, which has some mathematical background explained.

A good, not easy, but suitable for high school student, introduction to mathematics used in computer science is Concrete Mathematics, by Knuth, Graham & Patashnik.

There are many methods for representing structure of a program (like UML class diagrams etc.). I am interested if there is a convention which describes programs in a strict, mathematical way. I am especially interested in the use of mathematical notation for this purpose.

An example: Classes are represented as sets (fields, properties) and functions (operating on the elements of sets). A parent class' fields are a subset of child class'. Functions are described in pseudocode which has to look like this and that...

I've been given the following problem about loop invariants:

Consider

x=4; for(i=5;i<k;i++) { a=a+x+i; x=x*2; }

Define the appropiate loop invariant that utilizes a closed formula for a and x.

Now, How do you know you have the right loop invariant here? I mean you can set the loop invariant to be: "At j'th iteration 'x' is less than 'a'" which will be correct but will not use any closed formulas right?

How can a statement (the loop invariant) can be used to determine the value of "a" when the loop is over? All the examples I've seen just state the loop invariant and its not being used as a closed formula.

Any ideas?

Thanks for all of your help.

Start with the closed formulas: clearly for x(j) [for j from 0 to k-5], x at entry to the j-th leg of the loop, x(j+1) = x(j) * 2, so, x(j) is 4 * 2**j (using ** for "raise to power") since x(0) is 4; and a(j+1) = a(j) + x(j) + j + 5 -- we're not told what a(0) is, but we can factor it out and write a(j) as a(0) + something. Can you figure out what that something is, given the above closed-formula resoution for x(j)? I'm reluctant to do your homework from you -- have you yet started studying Concrete Mathematics or whatever your textbook IS...?

Once you're written down the closed-form formula for a(j), to go with the trivial one I supplied for x(j), can you see how they combine to make a loop invariant...?

I have a quite big development experience and I wonder is it possible to start learning math from scratch. I forgot almost everything I know, even school program. Please give me some guidance on this. Where to start what to do. Are there any math books for developers. May be with exercises to write code or experiment, etc...

Any help is appreciated.

Yes, there are math books for developers:

It's hard to say if either one would be a good starting point without knowing what level you're at.

I would like to know in which order I should learn different areas of maths so I can have a robust overview of all the theory in case I need something for a computer programming problem.

So I've created this mind map

enter image description here

I do not intend to know all those small details about how to do a certain thing (e.g. "gauss-jordan reduction"), I would rather look over an example, but then do it with math software like sage-maths or mathematica.

I would like to know, for instance, how to get to a taylor series, given the analytical function (I know it already, I am merely illustrating the kind of knowledge depth I expect).

So all I all, I want to be able to read academic articles about maths which have applicability in computer science / programming, and actually understand something from those articles, so I can use that knowledge in solving actual programming problems.

The open question is:

  1. (a) In what order do you suggest to learn about these areas, on what areas should I insiste more?

    (b) Do you see any missing areas in the mind map?

There is a good book, that I think would help you to get more out of computer science research papers and dissertations. It's called "Concrete Mathematics: A foundation for Computer Science", and it's available on Amazon:

http://www.amazon.com/Concrete-Mathematics-Foundation-Computer-Science/dp/0201558025/ref=sr_1_1?s=books&ie=UTF8&qid=1341081763&sr=1-1&keywords=math+computer+science

I think this would help because it will all be relevant, and its consolidated which will help expedite the learning process.

Even if you don't have any money, just Google it and take a look at the index to get an idea of what areas you might want to learn.

And here's one more interesting book.

I have been writing PHP, Ruby, ColdFusion, and javascript (not a language, I know), for several years.

But I am really wanting to get more into the world of Computer Science and writing in lower-level languages.

What are some good resources for starting out? It seems like every book I have gotten has been extremely elementary, and that isn't at all helpful. I need something that skips the basics.

For computer science, I would recommend starting with discrete mathematics. A good book is the Rosen book, which my university uses. From there, you can move on to Concrete Mathematics, Introduction to Algorithms, and Introduction to the Theory of Computation. I can't speak much about Introduction to Algorithms - it's still on my wish list. But the other two are very good. That should cover the basics of computer science.

From there, you can go down any route. Some major fields in computer science are theoretical computer science (logic, automata theory), computational theory (computability theory and complexity theory), algorithms and data structures, computer architectures (parallel processing), operating systems, computer networks, graphics, vision, databases, AI...You would have to decide what interests you the most and investigate that particular topic area in more depth.

In my Data Structures Class, we're looking at recurrence relations like T(n) and big O problems O(n). I'd appreciate any resources for learning these, my textbook doesn't cover T(n), and the professor skips over lots of steps.

I haven't seen a good, step-by-step method for solving these things. I realize that every problem is unique, but there has to be some sort of framework for doing these.

Thanks.

Check Concrete Mathematics - A Foundation for Computer Science, it's a brilliant book with lots of examples and exercises.

Another great book is Introduction to Algorithms. It has a pretty thorough section on solving recurrence relations.

You are right, there is a generalized method for solving simple recurrence relations called the Master Theorem. (The explanation in Introduction to Algorithms is much better than the Wikipedia page.) It doesn't work for every case, but it solves a lot of common ones.

I want to cover the equivalent of a typical CS undergrad course in material, so I'm making a list of books to cover the typical topics. I've split the list into topics that, from the research I did, I think are compulsory and optional. I would like some help to confirm if the topics are split correctly, and if the books are of the correct level. Also, please let me know if I left out any important topics, or if any are beyond undergrad level.

Thank you for your time!

Edit regarding the on hold status: I do not believe this question is off-topic as I am not asking for a recommendation for books - I am asking if the topics I have listed are indicative of a typical CS course, and if any important topics are missing. The books links are only there in case the books I have chosen are not correct for the topic, and can be removed if necessary.


COMPULSORY

Operating Systems: Operating System Concepts

Networks: Computer Networking: A Top-Down Approach

Discrete Mathematics: Concrete Mathematics

Data Structures and Algorithms: Introduction to Algorithms

Computer Architecture: Computer Systems: A Programmer's Perspective

Automata Theory: Introduction to the Theory of Computation

Compilers: Engineering a Compiler was recommended to me over the dragon book.

Database Theory: An Introduction to Database Systems

Programming Language Concepts and Design: Programming Language Pragmatics

OPTIONAL

Cryptography: Cryptography Engineering: Design Principles and Practical Applications

Functional Programming: Learn You a Haskell for Great Good!

Artificial Intelligence: Artificial Intelligence: A Modern Approach

Computer Graphics: Real-Time Rendering

Your list is very good on the subjects directly related to computer science. However, it is light on math. In my own B.Sc. in Computer Science I also had a ton of calculus, linear algebra, algebra (groups, rings, etc), statistics, analytic geometry and numerical analysis. Some applications of computer science rely heavily on those:

  • Machine learning depends on lots of linear algebra, calculus, and statistics;
  • Computer graphics depends a lot on analytic geometry and linear algebra;
  • Scientific computation relies on calculus and numerical analysis.

I never used much of the ton of Algebra I had, but I hear it is important for cryptography. :-)

For a programmer developing more regular applications your list is very good, but for those interested in these more specialized areas (which are still pretty important), these subjects are vital.

How can an open-form of recurrence be converted into its equivalent closedform. Furthermore, what are some commonly used closed-forms that are usually used efficiently.

I think you are talking about recursive functions and math.

e.g. consider the following sum recursive function

sum(0) = 0
sum(i) = sum(i-1) + i

this form is not closed. A closed form is sum(n) = (n+1)*n/2, where you only use basic operations like +-*/, power, and sometimes factorial.

For your question, how to convert a open-form formula into a closed form. The answer is there is no general rule to transform all open-form into closed form because some of the open forms don't have equivalent closed forms.

You may refer to Concrete Mathematics for a serious treatment of this subject. The book's primary goal is to convert a large family of recursive function/open forms into their closed forms.

Okay, so far, I have been taking computer science courses in my high school and doing some of my own research on the web, and I have found I really like the subject. However, the computer science courses, having given me a small amount of experience in a few languages (C++, java, and python), leave me wondering where to go for development on my own.

I would like to create desktop applications, or even web applications if I could wrap my head around it. What language would you think would best facilitate this?

As a side-note, what are some good books or online documents that explain general computer science topics? I have found some good ones, but they haven't given me the depth I really want.What are some good ones?

Since you're still in high school, I would tell you that time is on your side. You have plenty of time to develop as a computer scientist. Therefore, take the long view for your development. So it's much better for you to understand the abstractions that underly software technology.

In my humble opinion, C++ and Java will always be around and you have plenty of time to develop your skills in that arena. However, a higher level language like Scheme or Python will pay plenty of dividends. You might find this recommendation highly enlightening.

In addition, every application will deal with a database as its system of record. Understanding SQL and data modeling is a win-win.

Also, understanding formal logic and/or discrete mathematics is indispensable for computer science. Computer languages are nothing but formal languages for executing procedures: i.e. mathematical induction is used to define their syntax and semantics.

Hey everyone, could anyone help me out with doing the Dollars in this function. It does the change just fine but it does all of the amount back in change and i want to big bills ($1,$5,$10, & $20)'s in dollars and the change in Q/D/N/P's.

Dim Quarters As Integer
Dim Dimes As Integer
Dim Nickels As Integer
Dim Pennies As Integer

Sub GetChange(ByVal Amount As Currency, ByRef Quarters As Integer, ByRef Dimes As Integer, ByRef Nickels As Integer, ByRef Pennies As Integer)
Dim Cents As Integer

   Cents = Amount * 100
   Quarters = Cents \ 25
   Cents = Cents Mod 25
   Dimes = Cents \ 10
   Cents = Cents Mod 10
   Nickels = Cents \ 5
   Pennies = Cents Mod 5

End Sub

Call GetChange(5.56, Quarters, Dimes, Nickels, Pennies)

Any help would be awesome! :o)

Update, solved

Private Sub theUSChange(Amount)
    Dim USCurrency(9) As Currency
    Dim USCurrencyNames(9) As Currency
    Dim Amount As Currency
    Dim Result As Currency
    Dim I As Integer

    USCurrencyNames(0) = " Pennies: "
    USCurrency(0) = 0.01
    USCurrencyNames(1) = "   Dimes: "
    USCurrency(1) = 0.05
    USCurrencyNames(2) = " Nickles: "
    USCurrency(2) = 0.1
    USCurrencyNames(3) = "Quarters: "
    USCurrency(3) = 0.25

    USCurrencyNames(4) = "      $1: "
    USCurrency(4) = 1
    USCurrencyNames(5) = "      $5: "
    USCurrency(5) = 5
    USCurrencyNames(6) = "     $10: "
    USCurrency(6) = 10
    USCurrencyNames(7) = "     $20: "
    USCurrency(7) = 20
    USCurrencyNames(8) = "     $50: "
    USCurrency(8) = 50
    USCurrencyNames(9) = "    $100: "
    USCurrency(9) = 100

    For I = UBound(USCurrency) To LBound(USCurrency) Step -1
        Do While Amount >= USCurrency(I)
            Amount = Amount - USCurrency(I)
            Result = Result + 1
        Loop
        Debug.Print(USCurrencyNames(I) & Result)
        Result = 0
    Next
End Sub

call theUSChange(5.77)

OUTPUT:
    $100: 0
     $50: 0
     $20: 0
     $10: 0
      $5: 1
      $1: 0
Quarters: 3
 Nickles: 0
   Dimes: 0
 Pennies: 2

David

This problem is worked out as an example in Concrete Mathematics using generating functions.