You Will Learn

This seminar is designed to help programmers, analysts, and system architects find effective solutions they can incorporate into software systems by reusing algorithms that have been successfully tested elsewhere.
Programmers spend lots of time refactoring and otherwise performing micro-optimizations on their code, but sometimes the really big win is from changing the design to use a better or more appropriate algorithm.
Code rearrangements often produce only linear improvements in performance, but algorithm improvements can lead to solutions that scale, with a manyfold performance improvement for large data sets. Often a program with a poor or inefficient algorithm will work as a prototype and in initial testing, but will fail system and load tests because the underlying algorithmic approach doesn't scale efficiently with data. This seminar will give you a toolkit of approaches you can use to deal with this problem.

Here you will find algorithmic templates to solve common problems that arise in many types of software systems.
You will learn how to evaluate tradeoffs between algorithms and how to test whether the algorithm is working correctly in your system.
The material we provide will also help you document your programs as long as you use standard algorithmic solutions.

Featured Book

This seminar is based on the new book "Algorithms in a Nutshell" by Heineman, Pollice and Selkow.

Printable Flier

This PDF flier can be printed to share with other people, post on bulletin boards, or emailed. Feel free to share it with anyone who might benefit from this seminar!

An 11x17 version of the flier is available for even more impact.

Principle: Separate the Algorithm from the Problem Being Solved

It is hard to show the implementation for an algorithm "in the general sense" without also involving details of the specific solution

In this seminar, we design each implementation to separate the generic algorithm from the secific problem. Multiple programming languages will be used. The speaker follows a strict design methodology to ensure that the code is readable and the solutions are efficient. Because of his software engineering background, it was second nature to design clear interfaces between the general algorithms and the domain specific solutions.

Coding in this way produces software that is easy to test, maintain, and expand to solve the problems at hand. Further, it helps you to more easily read and understand the description and implementation of the algorithm.

Principle: Introduce Just Enough Mathematics

Many treatments of algorithms focus on proving the correctness of the algorithm, while only explaining its details at a high level. Our goal in this seminar is to show how the algorithm is to be implemented in practice. To this end, just enough math is introduced to understand the data structures and flow control of the solutions.

We will cover the key terms and analytic techniques to differentiate algorithm behavior based on the data structures used and the desired capabilities.

Algorithms Unleashed!

A Practical Approach to Programming Algorithms

When: May 9, 2009
Where: MIT Tang Center/E51-345, Cambridge, MA
Cost:

$225 through March 17
$275 through April 17
$315 after April 18
$375 on day of conference.

This seminar is a joint production of the Greater Boston Chapter of the ACM and the Boston Chapter of the IEEE Computer Society.

Why Algorithms?

Your code works. But it has to run 10X faster. What do you do?

It is well understood that the choice of key algorithms can change the performance of an application by a factor of two, ten – even a hundred or more! Now - what does this mean to you?

Programmers often don't see the connection between a "faintly understood" algorithm they remember seeing once in an undergraduate class and a specific programming problem they are facing.

George Heineman addresses this in his book Algorithms in a Nutshell, which is the foundation of this seminar. One of the goals of the book was to present algorithms to practitioners "using their language", rather than a more traditional CS approach that involves theorems, proofs, pseudo-code and analytic functions. Towards this end the book includes six chapters with full code solutions available for free download. George notes “I was pleasantly surprised when the book was done to see that we had about 80,000 lines of commented code in Java, C, and C++ to support the book. Plus nearly 300 JUnit test cases to ensure over 90% coverage of the Java code.”

This seminar covers key topics including:

  • Sorting
  • Searching
  • Graphs
  • Path Finding in AI
  • Computational Geometry
  • Network Flow Algorithms
  • When All Else Fails

George Heineman will present 30+ algorithms, each in an appropriate context to help your understanding. For example, there is no "Best" sorting algorithm – but, if you know specific information about your data being sorted, then specific algorithms should be used because of a designed "sweet spot".

While there is a lot of material to cover, the goal is not to present all algorithms in a whirlwind. Rather the common solutions will be presented:

  • Appropriate data structure use
  • Divide and conquer
  • Dynamic programming
  • Design tradeoffs for time vs. space

Each section is motivated by a family of problems to be solved. Based on the problem, specific techniques are appropriate, and can be clearly presented. The tutorials focus on "just enough mathematics" (as the book does) to ensure that the information remains accessible.

The goal is to show how specific algorithms provide encode optimal solutions to specific problems you are likely to face. We will describe the algorithms in the language that you are using (Java/C++, etc...) rather than present the more traditional theoretic introduction. A closely related goal is to reinforce that the practitioner must devise appropriate test cases to validate the algorithms within the context where they are used.

This seminar is a joint production of the Greater Boston Chapter of the Association for Computing Machinery
and the Boston Chapter of the IEEE Computer Society.

Seminar Topics

Agenda

Welcome/Sign-in (8:00am-9:00am)

Get your badge, enjoy a continental breakfast, pick out a seat and take advantage of the opportunity to meet people facing the same challenges you are.

Introduction (9:00am-9:10pm)

 

Morning Session (9:10am-12:00 noon)

Introduction [30 mins]

  • What is an algorithm?
  • An algorithm Example: Insertion Sort
  • Description of Pattern Format
  • Mathematical notation and intuition

Sorting [50 mins]

  • Overview
  • Themes: Divide and Conquer, Space vs. Time, Arrays vs. Pointers, comparison vs. non-comparison
  • Algorithms: Quicksort, Mergesort, Heapsort, Bucket sort
  • Domains: Integers, Strings, Complex Records, Restricted Sets

Break: [10 mins]

Searching [40 mins]

  • Overview
  • Themes: Divide and Conquer, Space vs. Time, Rich Data Structures
  • Algorithms: Tree-based, Hashing-based
  • Concerns: Hash Functions, Indexing, Secondary storage

Recap: Themes in Algorithms [20 mins]

  • Data Structures [Array, Linked List, Queue, Heap, Priority Queue, Tree, Graph]
  • Divide and conquer
  • Space vs. Time tradeoff
  • Greedy algorithm
  • Dynamic Programming

Tutorial Deliverables [20 mins]

  • Overview of software supplied [Eclipse, ADK library, testing]
  • Overview of book
  • Work through simple example [Code, Figures, Examples]
  • Goal: Make sure you can run the basic code

Lunch (12:00-1:00pm)
Lunch is provided, so you can sit with your fellow attendees and discuss the morning's topics.

Afternoon Session (1:00pm-4:45pm)

Graph Problems [50 mins]

  • Overview
  • Themes: Representation (adjacency lists vs. adjacency matrix), Search strategy (breadth first vs. depth first), Space vs. Time
  • Algorithms: Shortest Path, Minimum Spanning Tree, All Pairs Shortest Path

Path Finding in AI [50 mins]

  • Overview
  • Themes: Search Trees vs. Game Trees
  • Algorithms: Minimax, AlphaBeta, BreadthFirst, DepthFirst, AStar

Break [10 mins]

Computational Geometry [50 mins]

  • Overview
  • Themes: Divide and Conquer
  • Algorithms: Line Segment Intersection
  • Concerns: Floating-point computations

Algorithms and Software Engineering [30 mins]

  • Early ideas: Program = Algorithms + Data Structures [Wirth/1975]
  • Modern ideas: How to include Algorithms in OO development process
  • Documentation
  • Unit testing
  • Stress Testing
  • Language issues (C++, Java, Perl/Python)

Summary [25 mins]

  • Comparative approach to algorithm design
  • Empirical analysis
  • When all else fails
  • Conclusion
| ©2007-2009 Greater Boston Chapter of the ACM