David Wagner

181 Tumblebrook Drive
South Windsor, CT 06074
USA

+82-10-4901-1442
dwagndwagn at gmail.com
http://www.cs.dartmouth.edu/~dwagn

Education

Ph.D., Dartmouth College - Concentration in Computer Science, February 2006
Co-Advisors: Robert Scot Drysdale, Clifford Stein (Columbia University)
Additional Thesis Committee: Amit Chakrabarti, Joseph S. B. Mitchell (State University of New York at Stony Brook)
Ph.D. Dissertation: Path Planning Algorithms under the Link-Distance Metric
M.S., State University of New York at Stony Brook - Concentration in Computer Science, May 1995
Advisor: Steven Skiena
Master's Project: LINK: A Software System for Discrete Mathematics
B.A., Colgate University - Double concentration in Computer Science and Mathematics, May 1993
Advisors: Phil Mulry (Computer Science), Tom Tucker (Mathematics)

Research Interests

Computational Geometry, Approximation Algorithms, Graph Algorithms, Data Structures, Link-Distance Problems

Scholarships and Awards

NSF Summer Institute in Korea, Summer 2002
NSF Summer Institute in Japan, Summer 2000
Five Year Dartmouth Fellowship, 1998-2003

Research Experience

Teaching and Research Assistant, Dartmouth College, September 1998 - February 2006
Assisted professors with various teaching duties. Implemented and maintained class web pages. Delivered occasional lectures. Investigated Euclidean problems under the Minimum Bends metric.
Research Intern, Korea Advanced Institute for Science and Technology, Summer 2002
Researched Minimum Bends Path Problem in Three Dimensions. Delivered Research presentations at various universities in Korea and Japan.
Research Intern, IBM Tokyo Research Laboratory, Summer 2000
Developed new algorithms for the optimization of an assembly line at a steel factory. Taught a class in the C++ programming language.
Research Assistant, State University of New York at Stony Brook, January 1994 - May 1995
Implemented classes for an experimental algorithms package in C++.
Tutor/Research Assistant, Colgate University, January 1990 - May 1993
Assisted Students with class projects. Researched parallel algorithms for optimal timing conditions.

Publications and Presentations

Journal Publications

An O(n^5/2log n) Algorithm for the Rectilinear Minimum Link-distance Problem in Three Dimensions; Robert Scot Drysdale, Clifford Stein, David Wagner; Computational Geometry: Theory and Applications; To Appear (Accepted April 2008)

Refereed Conferences

An O(n^5/2log n) Algorithm for the Rectilinear Minimum Link-distance Problem in Three Dimensions; Robert Scot Drysdale, Clifford Stein, David Wagner; The Seventeenth Canadian Conference on Computational Geometry (CCCG 2005) ; Windsor, Canada; August 2005; (Submitted by invitation to Computational Geometry: Theory and Applications)
Approximation Algorithms for the Minimum Bends Traveling Salesman Problem; Clifford Stein, David Wagner; The Eighth International Integer Programming and Combinatorial Optimization Conference (IPCO 2001); Utrecht, The Netherlands; Springer-Verlag; June 2001

Refereed Workshop Presentation

The Rectilinear Minimum Bends Path Problem in Three Dimensions; David P. Wagner, Robert Scot Drysdale, and Clifford Stein; DIMACS Workshop on Computational Geometry; Piscataway, NJ; November 2002

Unrefereed Reports

Boolean Operations with Two Dimensional Segment Trees; Robert Scot Drysdale, David Wagner; 2005 (appears in Ph.D. thesis)
An NP-Completeness result for the Minimum Bends Traveling Salesman Problem; Clifford Stein, David Wagner; 2002 (appears in Ph.D. thesis)

In Progress

Dynamically maintaining Upper and Lower Envelopes with MinMax Queries using Segment Trees; Robert Scot Drysdale, David Wagner
A Graph Theoretic Approximation Algorithm for the Three Dimensional Minimum Link Path Problem in O(n²log n) time; Robert Scot Drysdale, David Wagner

Work Experience

Software Design Engineer Microsoft Corporation, July 2006 - September 2007
Performed various programming duties in Microsoft Access database program. These included fixing potential security problems, assisting with migration from 32-bit to 64-bit platform, simplifying internationalization of user interface, and designing interaction with web services. Designed heat chart algorithm in Microsoft Excel spreadsheet program.
Engineering Intern, Google, February 2006 - May 2006
Designed, implemented, tested, and deployed Spam Prevention Program in Google online calendar program.
Technical Support Engineer, Prolifics/JYACC, July 1996 - August 1998
Assisted customers having problems using database front end. Designed and implemented email support system in Unix. Trained employees in use of VMS operating system.
Programmer, Wanderlust Interactive, November 1995 - May 1996
Performed various programming duties in the design of a children's computer game. Created "Walking Manager", using Shortest Path algorithm, to guide main character across the screen.
Chief Programmer, R. T. Griffin Inc., October 1994 - November 1995
Designed and implemented software which controls a shortwave radio.
Summer Engineer, Asea Brown Boveri, Summer 1990 and Summer 1991
Performed code conversion of Fortran code from MS-DOS to Unix. Programmed TPU Editor to emulate popular company editor.

Teaching Experience

Faculty Experience

Class:Software Design, (Graduate Class) Korea University, Spring 2009
Approximate Class Size:9
Average Student Evaluation:(in progress)
Duties - Responsible for writing syllabus, selecting textbook, assigning and grading homework problems, designing and grading projects, and delivering all lectures.
Class:Object-Oriented Programming, (Undergraduate Class) Korea University, Spring 2009
Approximate Class Size:45
Average Student Evaluation:(in progress)
Duties - Responsible for writing syllabus, selecting textbook, assigning and grading homework problems, designing and grading projects, and delivering all lectures.
Class:C Programming, (Undergraduate Class) Korea University, Spring 2009
Approximate Class Size:100
Average Student Evaluation:(in progress)
Duties - Responsible for jointly following syllabus with another professor and delivering all lectures.
Class:Advanced Compilers, (Graduate Class) Korea University, Autumn 2008
Approximate Class Size:7
Duties - Responsible for writing syllabus, selecting textbook, assigning and grading homework problems, designing and grading projects, and delivering all lectures.
Class:C Programming, (Undergraduate Class) Korea University, Autumn 2008
Approximate Class Size:120
Duties - Responsible for jointly following syllabus with another professor and delivering all lectures.
Class:Software Design, (Graduate Class) Korea University, Spring 2008
Approximate Class Size:35
Average Student Evaluation:4.32/5.0, 4.45/5.0 (in 2 categories)
Duties - Responsible for writing syllabus, selecting textbook, assigning and grading homework problems, designing and grading projects, and delivering all lectures.
Class:C Programming, (Undergraduate Class) Korea University, Spring 2008
Approximate Class Size:20
Average Student Evaluation:3.85/5.0, 3.81/5.0, 3.86/5.0 (in 3 categories)
Duties - Responsible for jointly following syllabus with another professor and delivering all lectures.

Instructor Experience

Class:Group Theory and Linear Algebra in Computer Graphics, Dartmouth College High School Math Program, Summer 2003
Approximate Class Size:5
Duties - Collaboratively designed syllabus in a one week course for gifted high school students; Designed and delivered mathematical lectures; Designed, wrote, and implemented an in-class project on Platonic and Archimedean solids, culminating with in-class presentations; Designed, wrote, and implemented a computer lab on matrices of transformation with associated homework questions.
Class:Number Theory and RSA Cryptography, Dartmouth College High School Math Program, Summer 2003
Approximate Class Size:20
Duties - Collaboratively designed syllabus in a one week course for gifted high school students; Designed and delivered historical and mathematical lectures; Designed, wrote, and implemented a computer lab with the objective of sending RSA encrypted messages.

Teaching Assistant Experience

Class:Algorithms, Spring 2004, Fall 2003, Fall 1998
Professor:Prasad Jayanti, Robert Scot Drysdale, Javed Aslam
Approximate Class Size:15, 15, 50
Duties - Grading, Lecturing, Tutoring, Office Hours
Class:Information Theory, Spring 2003
Professor:Javed Aslam
Approximate Class Size:20
Duties - Grading
Class:Advanced Algorithms, Fall 2002
Professor:Robert Scot Drysdale
Approximate Class Size:20
Duties - Grading
Class:Operating Systems, Fall 2001
Professor:Sean Smith
Approximate Class Size:30
Duties - Grading, Lecturing, Lab Hours, Writing Exam Questions, Testing Class Project
Class:Concepts in Computing, Summer 2001, Winter 2000, Summer 1999
Professor:Tom O'Connell, Javed Aslam, Javed Aslam
Approximate Class Size:80, 160, 100
Duties - Grading, Lecturing, Tutoring, Lab Hours
Class:Advanced Operating Systems, Winter 2001
Professor:Sean Smith
Approximate Class Size:15
Duties - Grading, Lecturing, Lab Hours
Class:Electronic Commerce, Spring 1999
Professor:Filia Makedon
Approximate Class Size:20
Duties - Grading, Maintaining Class Web Page
Class:Current Trends and Ethical Issues in Computer Science, Winter 1999
Professor:David Kotz
Approximate Class Size:25
Duties - Designing, Writing, Presenting and Grading Class Project

Leadership Experience

Instructor, Microsoft Dance Club, 2006-2007
Co-Founder/Instructor, Dartmouth Argentine Tango Society, 2005
Chief Organizer, Dartmouth Japan Society Taiko Drum Festival, Winter 2005
Founder/Coach/Captain, Dartmouth Graduate Student Intramural Hockey Team, 2003-2005

Department Service

Referee, Journal articles and conference papers, including those appearing in The Computer Journal, Journal of Algorithms, Foundations of Computer Science, and Symposium on Dicrete Algorithms.
Chief Organizer, Dartmouth Computer Science Department Algorithms Seminar, Winter 2000
Coach/Captain, Dartmouth Computer Science Department Intramural Hockey Team, 1999-2002

Computer Skills

Fluent in C, C++, HTML, Javascript, Pascal, BASIC
Familiar with Java, Objective C, LISP, 68000 Assembler, Python
Proficient in use of MS Windows XP, Unix, Mac OS 9, Mac OS X, VMS, MS-DOS, NeXTStep, and their scripting languages

Foreign Languages

Proficient in Spanish (6 years study)
Semi-proficient in Japanese (3 years study)
Familiar with Mandarin Chinese and Korean (3 months study each)

Research References

Robert Scot Drysdale
6211 Sudikoff Laboratory
Dartmouth College
Hanover, NH 03755-3510, USA
scot@cs.dartmouth.edu
(603) 646-2101

Clifford Stein
Department of IEOR
Columbia University
500 W. 120 St., MC 4704
New York, NY 10027, USA
cliff@ieor.columbia.edu
(212) 854-5238

Joseph S. B. Mitchell
Department of Applied Mathematics and Statistics
Math Tower, Room 1-109
State University of New York at Stony Brook
Stony Brook, NY 11794-3600, USA
jsbm@ams.stonybrook.edu
(631) 632-8366

Teaching Reference

Lee Stemkoski
Department of Mathematics and Computer Science
111 Alumnae Hall
Adelphi University
Garden City, NY 11514, USA
stemkoski@adelphi.edu
(516) 877-4495