There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult. — C.A.R. Hoare
Algorithms This page contains all my lecture notes for the algorithms classes required for all computer science undergraduate and graduate students at the University of Illinois, Urbana-Champaign. I have taught incarnations of this course eight times: Spring 1999, Fall 2000, Spring 2001, Fall 2002, Spring 2004, Fall 2005, Fall 2006, Spring 2007, Fall 2008, Spring 2009, Spring 2010, and Fall 2010. These notes are numbered roughly in the order I use them in my undergraduate class.
100 Vim Commands Every Programmer Should Know Since the 70′s, Vi is one of the programmer’s best friend. Nevermind you’re new to Vi or not, here’s a big list of 100 useful commands, organized by topic, which will make your coder life better.
Out of the Tar Pit Complexity is the single major difficulty in the successful development of large-scale software systems. Following Brooks we distinguish accidental from essential difficulty, but disagree with his premise that most complexity remaining in contemporary systems is essential. We identify common causes of complexity and discuss general approaches which can be taken to eliminate them where they are accidental in nature. To make things more concrete we then give an outline for a potential complexity-minimizing approach based on functional programming and Codd’s relational model of data.
Practicing Ruby Practicing Ruby articles are jam-packed with meaningful code samples and clear explanations that help you level up your programming skills. Since 2010, our carefully designed content has helped countless Ruby programmers get better at their craft in a fun and efficient way.
Nobody should call themselves a professional if they only knew one language.
Type Theory and Functional Programming Constructive Type theory has been a topic of research interest to computer scientists, mathematicians, logicians and philosophers for a number of years. For computer scientists it provides a framework which brings together logic and programming languages in a most elegant and fertile way: program development and verification can proceed within a single system. Viewed in a different way, type theory is a functional programming language with some novel features, such as the totality of all its functions, its expressive type system allowing functions whose result type depends upon the value of its input, and sophisticated modules and abstract types whose interfaces can contain logical assertions as well as signature information. A third point of view emphasizes that programs (or functions) can be extracted from proofs in the logic.
Principles of Docking: An Overview of Search Algorithms and a Guide to Scoring Functions The docking field has come of age. The time is ripe to present the principles of docking, reviewing the current state of the field. Two reasons are largely responsible for the maturity of the computational docking area. First, the early optimism that the very presence of the “correct” native conformation within the list of predicted docked conformations signals a near solution to the docking problem, has been replaced by the stark realization of the extreme difficulty of the next scoring/ranking step. Second, in the last couple of years more realistic approaches to handling molecular flexibility in docking schemes have emerged.
Humble Little Ruby Book Ruby is an open-source, multi-paradigm, interpreted programming language (a bit of a mouthful I know! I’m going to explain it, I promise!). Ruby was created by Yukihiro “Matz” Matsumoto, a very fine Japanese gentleman who currently resides in Shimane Prefecture, Japan; Matz’s work on the language was started on February 24, 1993 (commonly considered the birthday of the language; I hear that over in Japan they roll out a two-story cake and sing) and released to the public in 1995. Ruby is often hailed as one the most expressive and concise languages available to developers today. In that spirit of expressiveness, let’s look at exactly what it all means. Let us now eviscerate these verbal furbelows with conviction!
The Absolute Minimum Every Software Developer Absolutely, Positively Must Know About Unicode and Character Sets (No Excuses!) Ever wonder about that mysterious Content-Type tag? You know, the one you’re supposed to put in HTML and you never quite know what it should be? Did you ever get an email from your friends in Bulgaria with the subject line “???? ?????? ??? ????”? I’ve been dismayed to discover just how many software developers aren’t really completely up to speed on the mysterious world of character sets, encodings, Unicode, all that stuff.
Fundamental Concepts in Programming Languages This paper forms the substance of a course of lectures given at the International Summer School in Computer Programming at Copenhagen in August, 1967. The lectures were originally given from notes and the paper was written after the course was finished. In spite of this, and only partly because of the shortage of time, the paper still retains many of the shortcomings of a lecture course. The chief of these are an uncertainty of aim—it is never quite clear what sort of audience there will be for such lectures—and an associated switching from formal to informal modes of presentation which may well be less acceptable in print than it is natural in the lecture room. For these (and other) faults, I apologise to the reader.
CSS3 Cheat Sheet In this post we present a printable CSS 3 Cheat Sheet (PDF), a complete listing of all the properties, selectors types and allowed values in the current CSS 3 specification from the W3C. Each property is provided in a section that attempts to match it with the section (module) that it is most actively associated within the W3C specification. Next to each property is a listing of the expected values that that property takes (normal text shows named values it accepts and italics shows value types it will accept).
Dynamo: amazon’s highly available key-value store Reliability at massive scale is one of the biggest challenges we face at Amazon.com, one of the largest e-commerce operations in the world; even the slightest outage has significant financial consequences and impacts customer trust. The Amazon.com platform, which provides services for many web sites worldwide, is implemented on top of an infrastructure of tens of thousands of servers and network components located in many datacenters around the world. At this scale, small and large components fail continuously and the way persistent state is managed in the face of these failures drives the reliability and scalability of the software systems. This paper presents the design and implementation of Dynamo, a highly available key-value storage system that some of Amazon’s core services use to provide an “always-on ” experience. To achieve this level of availability, Dynamo sacrifices consistency under certain failure scenarios. It makes extensive use of object versioning and application-assisted conflict resolution in a manner that provides a novel interface for developers to use.
Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I A programming system called LISP (for LISt Processor) has been developed for the IBM 704 computer by the Artificial Intelligence group at M.I.T. The system was designed to facilitate experiments with a proposed system called the Advice Taker, whereby a machine could be instructed to handle declarative as well as imperative sentences and could exhibit “common sense” in carrying out its instructions. The original proposal  for the Advice Taker was made in November 1958. The main requirement was a programming system for manipulating expressions representing formalized declarative and imperative sentences so that the Advice Taker system could make deductions.
Java is “heavyweight, verbose, and everyone loves to hate it,” but Wall still thinks you should know it.
Great Hackers by Paul Graham Productivity varies in any field, but there are few in which it varies so much. The variation between programmers is so great that it becomes a difference in kind. I don’t think this is something intrinsic to programming, though. In every field, technology magnifies differences in productivity. I think what’s happening in programming is just that we have a lot of technological leverage. But in every field the lever is getting longer, so the variation we see is something that more and more fields will see as time goes on. And the success of companies, and countries, will depend increasingly on how they deal with it.
An Axiomatic Basis for Computer Programming Computer Programming = Exact Science; What is Programming; Programming: The writing of a computer program; Program: A set of coded instructions that enables a machine, especially a computer, to perform a desired sequence of operations; What is Science; Science: The observation, identification, description, experimental investigation, and theoretical explanation of phenomena.
Why Functional Programming Matters As software becomes more and more complex, it is more and more important to structure it well. Well-structured software is easy to write, easy to debug, and provides a collection of modules that can be re-used to reduce future programming costs. Conventional languages place conceptual limits on the way problems can be modularised. Functional languages push those limits back. In this paper we show that two features of functional languages in particular, higher-order functions and lazy evaluation, can contribute greatly to modularity. As examples, we manipulate lists and trees, program several numerical algorithms, and implement the alpha-beta heuristic (an algorithm from Artificial Intelligence used in game-playing programs). Since modularity is the key to successful programming, functional languages are vitally important to the real world.
Regular Expressions Quick Start This quick start will quickly get you up to speed with regular expressions. Obviously, this brief introduction cannot explain everything there is to know about regular expressions. For detailed information, consult the regular expression tutorial. Each topic in the quick start corresponds with a topic in the tutorial, so you can easily go back and forth between the two.
How to Be a Programmer: A Short, Comprehensive, and Personal Summary To be a good programmer is difficult and noble. The hardest part of making real a collective vision of a software project is dealing with one’s coworkers and customers. Writing computer programs is important and takes great intelligence and skill. But it is really child’s play compared to everything else that a good programmer must do to make a software system that succeeds for both the customer and myriad colleagues for whom she is partially responsible. In this essay I attempt to summarize as concisely as possible those things that I wish someone had explained to me when I was twenty-one.
Six Super Helpful Typography Cheat Sheets Some may argue that typography is the single most important aspect of web design, but yet it’s often one of the most neglected and overlooked. There’s a lot involved in typography, and becoming a master can be difficult. A lot of it requires much experience, practice, and knowing the rules and do’s and dont’s. Nevertheless, there’s a lot to remember. So to provide a little typography aid, we’ve rounded up Six Super Helpful Typography Cheat Sheets.
jQuery Fundamentals jQuery Fundamentals is designed to get you comfortable working through common problems you’ll be called upon to solve using jQuery. To get the most out of this site, you’ll want to read the content and try the various interactive examples. Each chapter will cover a concept and give you a chance to try example code related to the concept.
The Bastards Book of Ruby The Bastards Book of Ruby is an introduction to programming and its practical uses for journalists, researchers, scientists, analysts, and anyone else whose job is to seek out, make sense from, and show the hard-to-find data. This does not require being “good at computers”, having a background in programming, or the desire (yet) to be a full-fledged hacker/developer. It just takes an eagerness to be challenged.
Clever Algorithms: Statistical Machine Learning Recipes This is a handbook of recipes for computational problem solving techniques from the field of Statistical Machine Learning. Clever Algorithms are interesting, practical, and fun to learn about and implement. Research scientists may be interested in browsing algorithm in search of an interesting system to investigate. Developers and software engineers may compare various problem solving algorithms and technique-specific guidelines. Practitioners, students, and interested amateurs may implement state-of-the-art algorithms to address business or scientific needs, or simply play with the fascinating systems they represent.
Grand Challenges for Computing Research From these examples, particularly the human genome project, we can infer the characteristic properties that distinguish a grand challenge project in science and engineering from the many other more normal kinds of challenges that face researchers every day. First, a grand challenge can be a major scientific and engineering project that is undertaken by large international efforts spread over 10 or 15 years. Grand challenges are correspondingy rare…
A pervasive elitism hovers in the background of collaborative software development: everyone secretly wants to be seen as a genius. In this talk, we discuss how to avoid this trap and gracefully exchange personal ego for personal growth and super-charged collaboration. We’ll also examine how software tools affect social behaviors, and how to successfully manage the growth of new ideas.
HTML5 Cheat Sheet XHTML 2 is dead, long live HTML 5! According to W3C News Archive, XHTML 2 working group is expected to stop work end of 2009 and W3C is planning to increase resources on HTML 5 instead. And even although HTML 5 won’t be completely supported until 2022, it doesn’t mean that it won’t be widely adopted within the foreseeable future. So in the spirit of the upcoming change we decided to release a handy printable HTML 5 Cheat Sheet that lists all currently supported tags, their descriptions, their attributes and their support in HTML 4.
Being A Better Programmer I always had this fantasy that game programmers were the cream of the crop. Anyone can write a word processor or a Visual Basic application, and anyone can hack a save file, but game programmers have to push the limits of the machine! They have to get every aspect of an environment on the screen and somehow not have a frame rate hit. I always thought game programmers were the cream of the crop, until I actually joined the industry. The harsh reality hit me almost instantly and I began to think -even say aloud, I’m amazed our game even runs.
Programming Paradigms (Stanford) Programming Paradigms (CS107) introduces several programming languages, including C, Assembly, C++, Concurrent Programming, Scheme, and Python. The class aims to teach students how to write code for each of these individual languages and to understand the programming paradigms behind these languages.
The Verifying Compiler: A Grand Challenge for Computing Research I propose a set of criteria which distinguish a grand challenge in science or engineering from the many other kinds of short-term or long-term research problems that engage the interest of scientists and engineers. As an example drawn from Computer Science, I revive an old challenge: the construction and application of a verifying compiler that guarantees correctness of a program before running it.
Time, Clocks, and the Ordering of Events in a Distributed System The concept of one event happening before another in a distributed system is examined, and is shown to define a partial ordering of the events. A distributed algorithm is given for synchronizing a system of logical clocks which can be used to totally order the events. The use of the total ordering is illustrated with a method for solving synchronization problems. The algorithm is then specialized for synchronizing physical clocks, and a bound is derived on how far out of synchrony the clocks can become.