Algorithms Unleashed! A Practical Approach to Programming Algorithms

You may need: Adobe Flash Player.

Parts 1 and 2: Sorting and Searching

When: 
Saturday, May 9, 2009 - 9:00am
Room: 
E51-345
Lecturer(s): 
George T. Heineman
George T. Heineman
Algorithms in a Nutshell

This seminar is designed for software practitioners, programmers, and designers. To meet your objectives, you need access to quality resources that explain real solutions using real algorithms to solve real problems.

It is best suited to moderately experienced programmers, typically with 2-10 years of software development experience.

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
  • 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.

Seminar in Detail: 

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)

  • Announcements for the day

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

George T. Heineman is an Associate Professor of Computer Science at WPI. His research interests are in Software Engineering.

He co-edited the 2001 book "Component-Based Software Engineering: Putting the Pieces Together". He was the Program Chair for the 2005 International Symposium on Component-Based Software Engineering. He is a co-author of the new (October 2008) book "Algorithms in a Nutshell".

Peter Mager
Additional audio recordings: 

You may need: Adobe Flash Player.

Part 3: Graph and Path Finding

You may need: Adobe Flash Player.

Part 4: Computational Geometry

Your rating: None Average: 5 (2 votes)