Design of Computer Programs

Programming Principles

Learn new concepts, patterns, and methods that will expand your programming abilities, helping move you from a novice to an…

Class Summary

Learn new concepts, patterns, and methods that will expand your programming abilities, helping move you from a novice to an expert programmer.

What Should I Know?

This course assumes previous programming experience, comparable to what is covered by the Udacity CS101 course.

What Will I Learn?

Move along the path towards becoming an expert programmer! In this class you will practice going from a problem description to a solution, using a series of assignments.

Syllabus

Unit 1: Winning Poker Hands

Steps of the design process; Developing for clarity and generality; Arguments for program correctness; Experimentation and simulation.; Design tradeoffs; Simplicity and Clarity. Decomposition and composability.

Unit 2: Back of the Envelope

Back of envelope calculations; When to use brute force and when to be clever; The Zebra puzzle; Generator expressions; Permutations and combinations. Cryptarithmetic; Recursive and wishful thinking.

Unit 3: Regular Expressions, other languages and interpreters

Defining the language of regular expressions; Interpreting the language; Defining the set of strings matched by a regular expression;
Other languages.

Unit 4: Dealing with complexity through search

Search: finding your way with a flashlight or boat; pouring water. Analyzing the efficiency of an algorithm; Recurrence relations; Matching data types with algorithms; Longest palindrome substring algorithm.

Unit 5: Dealing with uncertainty through probability

Probability: the game of Pig; Maximizing expected utility to optimize strategy.

Unit 6: Word Games

Managing complexity; Large sets of words; Appropriate data structures; Word games.

Unit 7: Conclusion

Final exam/project

Course Instructors

Peter Norvig is Director of Research at Google Inc. He is also a Fellow of the American Association for Artificial Intelligence and the Association for Computing Machinery. Norvig is co-author of the popular textbook Artificial Intelligence: A Modern Approach. Prior to joining Google he was the head of the Computation Sciences Division at NASA Ames Research Center.