Soundbyte: Spring | Summer 2003

Scientific Computing: Still Mainstream Computer Science

Image of members of the Scientific Computing group

Picture: Left to right: Top Row: Peg Howland, Shiv Gowda, Irene Moulitsas.
Middle Row: Mahbubur Rahim Khan, Hyunsoo Kim, Kris Kampshoff, Dong Wei Cao.
Bottom Row: Cheonghee Park, Haesun Park, George Karypis, Na Li.

"Should scientific computing (or numerical analysis) be a part of computer science?" is a question often heard in computer science departments. Many, if not most, computer science departments started in the 60s and 70s as spin-offs from mathematics departments. Then the dominant topic was numerical computing, and the most common programming language was FORTRAN. Since then computer science has expanded to include many more specialties, and the field of scientific computing has itself grown to become what it is today: a field which comprises a rich variety of interrelated engineering and theoretical core disciplines, including, for example, numerical analysis, matrix computation, sparse matrix methods, and parallel numerical algorithms.

That the answer to the above question is 'yes' becomes clear only after one understands that the field of scientific computing is itself undergoing important mutations. Techniques of scientific computing are penetrating non-traditional areas, and this is changing the view of many computer scientists. As an example, methods for information retrieval may exploit vector space representation, and some of these methods require singular values and vectors of large and sparse matrices. Another example is the development of graph partitioning methods based on spectral analysis.

This interesting link between the continuous and the discrete is prevalent in many other applications. Conversely, methods in scientific computing are utilizing tools from computer science. For example, Metis, a graph-partitioning tool developed by George Karypis and Vipin Kumar, is widely used as a prerequisite step in many high-performance computing jobs where parallel approaches, i.e., approaches that harness the power of many processors toward solving a big problem, are utilized. In another example, Yousef Saad uses graph theory tools when designing solvers for sparse linear systems.

Haesun Park has recently developed a feature extraction method called LDA/GSVD. LDA/GSVD extends applicability of the widely accepted linear discriminant analysis (LDA) to high dimensional and undersampled data by using a matrix pair decomposition method called the generalized singular value decomposition (GSVD). LDA/GSVD has been successfully applied to document classification, facial recognition, and visualization. This research is closely tied to the development of knowledge-based prediction systems which are scalable to data. A system has been developed for successful prediction of protein secondary structure and solvent accessibility using the support vector machine classifiers.

George Karypis: research is primarily focused on developing tools that enable the efficient solutions of scientific applications on parallel computers. Such examples include the graph and mesh partitioning libraries, METIS and ParMETIS that can effectively decompose a variety of mesh-based parallel numerical simulations, the PSPASES library for solving symmetric positive definite systems on large numbers of processors and the MGridGen library for automatically generating a sequence of coarse grids for multigrid solvers. He has also focused on serial and parallel algorithms for mining scientific datasets and is leading a major research effort on graph mining.

Finally, Daniel Boley has developed a fast unsupervised clustering algorithm by bringing together ideas from machine learning, statistics, pattern recognition, and especially sparse linear algebra methods. The result, the method of Principal Direction Divisive Partitioning (PDDP), has been publicly available for download for five years. It is a method that has been particularly successful on text document collections, largely because it takes great advantage of the high degree of sparsity in the data. Its success depends on the use of sparse linear algebra methods similar to those used in the past in spectral graph partitioning.

A second important trend in scientific computing is its emergence as a force in a new era where multidisciplinary research has become mandatory. A generation ago one could spend a lifetime on a narrowly defined research topic and be quite prolific. As numerical methods have matured, new needs have emerged, and collaborations with experts from other areas have become the norm. In this situation the standard approach of just providing a .canned. product is limiting. Yousef Saad has had one of these collaborations. He started working with Professor Jim Chelikowsky from the Department of Chemical Engineering and Materials Science about twelve years ago. The basic research has to do with electronic structures calculations. in quantum mechanics. The goal is to study the electronic or optical properties of materials. Methods used here allow one to characterize systems of a few hundred to a thousand atoms. The simulations are among the most computationally intensive ones today. A typical simulation done in the Saad and Chelikowsky group could consume a whole week of the IBM SP computer available at the Minnesota Supercomputing Institute. The core computation is a large eigenvalue problem. A decade ago, the main goal was to just write a parallel program that could run on a parallel platform. The fact that a group from computer science was collaborating with a physics team was a huge advantage. Some of the computations done in the mid to late 90s were the first and biggest of their kind.

The field of scientific computing is currently at a turning point. As computer power increases, there is no doubt that research in more effective and more powerful new algorithms will only gain importance. Computing - as in number crunching - is basic to almost every engineering and scientific field, and the need will grow as new technologies develop and mature.

-Yousef Saad, Daniel Boley, George Karypis and Haesun Park

Software Available:

Many of the software packages mentioned are freely available. Yousef Saad has made available a number of packages for sparse matrix computations over the past 12 years. Those who are familiar with iterative methods and sparse matrices know SPARSKIT, a package for performing some of the basic computations with sparse matrices. The package, the first version of which appeared in 1989, is written in FORTRAN 77, and is still widely used for its .iterative solvers. suite. A more recent package called pARMS provides parallel solvers for a message passing environment. pARMS is written in C and uses MPI for communication. Visit http://www-users.cs.umn.edu/~saad/software/home.html.

The tools developed by George Karypis described above are freely distributed via the department.s website and are used extensively in hundreds of sites world-wide and have been incorporated in many commercial applications. Information about these tools and directions for downloading can be found at http://www.cs.umn.edu/~karypis/software .

For information on getting Daniel Boley's software, see http://www-users.cs.umn.edu/~boley/Distribution/PDDP2.html.

Greetings from the Department Head

B&W image of Pen-Chung Yew High performance computing is alive and well at the University of Minnesota. Because Minnesota was the hotbed of the supercomputing industry throughout the 80s and early 90s, the faculty and students in our department have been actively involved in this strategically important industry. The research areas cover the entire spectrum of supercomputing in our department, including parallel numerical algorithms, computation intensive non-numerical applications such as data mining, middleware for grid computing, system software, and machine architectures.

With the renewal of the Army High Performance Computing Research Center last year, and the presence of the state sponsored Minnesota Supercomputing Institute within the Digital Technology Center, the University boasts two high performance computing centers that serve its high performance computing research community extremely well. In this issue of our newsletter, we highlight some of the research activities in the area of parallel numerical algorithms. It is a timely article because the federal government recently renewed its support of this strategic research area due to its significance to our basic research in sciences and technologies and the intense competition from abroad.

We have also been working closely with our industrial partners since the early 80s, currently through the Industrial Partners Program. Industrial members meet regularly during the academic year with our faculty. The members are closely involved in various activities in the department, including organizing the department open house and research forums, sponsoring student activities such as the ACM student chapter and the Graduate Student Association, recruitment, offering internships to our best undergraduate and graduate students, and providing input to our curriculum issues. Many companies are also actively involved in and are sponsoring faculty research projects.

Our industrial partners have been among our strongest supporters and allies each year advocating the importance of our program to the University and to the State of Minnesota. In this newsletter, we are very pleased to have one of our industrial partners, Bill Rohde from Unisys, present his perspective on this important partnership between industry and our department. We hope more companies will recognize the unique opportunity this partnership can bring to both our department and our partners. For more information regarding our Industrial Partners Program, please visit the web site: http://www.cs.umn.edu/external/partners.html.

We are planning to hold our 4th Biennial Department of Computer Science and Engineering Technology Forum on Friday, October 17, 2003. This is an event that brings our alumni, industrial partners, students and faculty together to exchange ideas, showcase our accomplishments, present distinguished alumni awards, and have a great time together enjoying the fall colors on campus during the University.s homecoming week. We hope you will mark your calendar and join us for this years event.

-Pen-Chung Yew

University Alliances: a Win/Win/Win Strategy

Image of members of the Scientific Computing group Everywhere in today's university environment there's talk of alliances with industry and public sector organizations. Looking simply at digital technology within the University of Minnesota, CS&E's Computer Science Associates (CSA) program comes immediately to mind. To name just a few more, one also thinks of the DTC's Affiliates program, the Carlson Information and Decision Science department's MIS Research Center and Information Industry Initiative programs, and the Department of Rhetoric's Industrial Affiliates Program (focused on web and technical communication, and related internet studies). There's clearly strong interest both inside and outside the University to create and sustain these multiple alliances. Just what is the "value proposition" for alliances like these, both from the University and the affiliating company or public sector agency perspectives?

I suspect that my company.s viewpoint on these alliances is similar to that of most other affiliate organizations. Perhaps a perspective on the Unisys philosophy and approach to university alliances can provide some insight into that broader value proposition.

For a technology-based services and products company like Unisys, close alliances with research universities have a direct and significant bearing on corporate success. Several years ago Unisys CEO Larry Weinbach personally initiated the Unisys University Alliance Program. The purpose of this program is to encourage development of deep relationships with a select number of top research universities worldwide. The University of Minnesota is one of our alliance partner schools.

These alliances are an important and highly visible part of our business. Division Presidents, Senior Vice Presidents and General Managers, and the CEO himself, serve as executives of interest responsible for guiding each relationship. Scott Vogel, Vice President and General Manager for Unisys North American Systems and Technology Sales and Services, is the Executive of Interest for the Unisys U of M Alliance. Assisting the Executive of interest is an Alliance Manager(s) (Bill Rohde and John Curtin for the U of M), and a Human Resources Partner (Michael Wiest for the U of M). For the Unisys U of M relationship we also have an extended group of employees who personally work with various University programs and student organizations. In addition, Unisys employee Tom Burk currently chairs the Minnesota High Technology Association.s U of M Committee.

There are three primary dimensions of our Unisys University Alliance relationships: recruiting, research, and continuing education.

Recruiting: Fresh new minds driven to produce and deliver the next generation of IT products and services are as essential as air to companies for whom technology is a major factor in business success. Only with ready sources of top talent can companies in this industry thrive and grow. Deep and broad relationships with leading universities create positive relationships that help assure access to that graduating talent pool.

But business and public sector organizations also have a responsibility back to the universities in this business of developing future talent. We need to be helping guide curriculum development where appropriate, serving as classroom resources when requested, providing speakers, sponsoring student projects, partnering with student organizations, supporting universities in their diversity goals, and offering students real world work experiences through coop and internship programs. In doing so, we as alliance partners help assure that our partner universities are well positioned to attract the best and brightest students.

Research: A second key alliance dimension relates to research. Close relationships with ongoing university research projects, selected joint research efforts, equipment and other donations to help advance university research missions, and the direct involvement of industry or public sector personnel in selected research endeavors, each represent activities invaluable to both parties in the alliance. The U.s Digital Technology Center and individual University departments, such as CS&E, are particularly well positioned to leverage these joint opportunities.

Continuing Education: A third key alliance dimension relates to the university as a resource for keeping industry and public sector workforces current with today's rapidly changing skills requirements. At any one point in time, numerous Unisys employees can be found pursuing undergraduate and graduate degrees at the U of M. Others selectively enroll in individual courses, and many more take regular advantage of University-sponsored seminars or conferences. Within Unisys we have selectively arranged for U of M professors to present seminars on selected topics, sometimes using our internal corporate "Unisys Business TV" to simultaneously reach employees at other Unisys locations. In the future we anticipate even further expanding this continuing education dimension, leveraging selected areas of university expertise by arranging for professors to present custom classes or seminars as an integral part of our internal education curriculum.

In total, these three alliance dimensions combine to form what I like to call a Win/Win/Win strategy. Alliance partners are not totally altruistic in their goals, and clearly the above dimensions are a win for industry or public sector organizations participating in university alliances. Hopefully, and we in Unisys certainly believe this to be the case, universities also win in each of the above alliance dimensions. Ultimately the third winner is the student. Through university alliance relationships with industry and public sector organizations, the learning environment is hopefully enriched, real world problems and challenges are more directly brought into the classroom, research opportunities are enhanced and made more relevant, and placement opportunities for exciting careers become more readily available.

Yet perhaps there's a fourth win too, the community at large. This fourth dimension was perhaps best exemplified by the industry-government-university partnership that sparked formation of the U.s Digital Technology Center just a few years ago. Through relationships like these all partners can make a difference ... and we all, truly, win.

- Bill Rohde
Software Engineering Director and U of M Alliance Manager
Unisys Corporation

The Minnesota Intrusion Detection System (MINDS)

Graph Partitioning

The Minnesota Intrusion Detection System (MINDS) is a data mining based system for detecting network intrusions. A prototype of the MINDS system is being used by the University of Minnesota network security analysts in a live system organized as illustrated in the figure below. Input to MINDS is collected using net-flow tools that collect packet information for ten-minute windows and store the information in a flat file. Before the analyst uses MINDS to process the files in batch mode, these files are filtered to remove information that is not interesting for intrusion analysis.

Image of architecture of MINDS system
Figure 1: Architecture of MINDS system

The first step in MINDS is the construction of features that are used in the data mining analysis. Basic features available directly from net-flow data include source IP address, source port, destination IP address, destination port, protocol, flags, number of bytes, and number of packets. Derived features include time-window and connection-window based features. Time-window based features are constructed to capture connections with similar characteristics in the last T seconds, since typically Denial of Service (DoS) and scanning attacks involve hundreds of connections in short time intervals. However, some scanning attacks scan the hosts (or ports) using a much larger time interval, for example once per hour. In order to detect such slow scans we also need to keep statistics for the last N connections generated from every source. We refer to these as the connection-window based features.

After the feature construction step, the known attack detection module is used to detect network connections that correspond to attacks for which the signatures are available, and then to remove them from further analysis. Next, the data is fed into the MINDS anomaly detection module that uses an outlier detection algorithm to assign an anomaly score to each network connection. The output of the MINDS anomaly detector contains the original net-flow data along with the anomaly score and relative contribution of each of the 16 attributes used by the anomaly detection algorithm.

The human analyst investigates reported network connections with high anomaly scores through MINDSAT (MINDS AnalystTool), a PHP-based analysis engine used to search and process a database of network connections. In addition, the MINDS association pattern analysis module provides another high-level summary of network connections that are ranked highly anomalous in the anomaly detection module. These summaries allow a human analyst to examine a large number of anomalous connections quickly. Furthermore, this summarization has the advantage of providing templates from which signatures of novel attacks can be built for augmenting the database of signature-based intrusion detection systems.

The University of Minnesota network security analyst has been using MINDS to analyze the university network traffic since August 2002. During this period, MINDS has been successful in detecting many novel network attacks and emerging network behavior that could not be detected using state-of-the-art intrusion detection systems such as SNORT.

-Vipin Kumar, Aleksander Lazarevic, Jaideep Srivastava

Compter Science and Engineering 2003 Graduates

Image of 2003 Ph.D. Graduates
Ph.D. grads left to right: Byoung-Dai Lee, Michael Whalen, Sanjai Rayadurgam,
Robert Weber, Yan Huang, Mihaela Cardei, Ionut Cardei, Dan Edeen, Zhigang Gong.

Image of 2003 M.S. Graduates
M.S. grads left to right: Sandeep Karanth, Rezwan Ahmed, Rashmi Pathak, Elena Kryzhnyaya,
Tim Urness, Avinash Bathula, Parthasarathy Sundaram.

Masters 7/02 - 5/03

  • Urooj Ahmed
  • Sai Kumar Bathina
  • Avinashreddy Bathula
  • Brian Bender
  • Sai Chen
  • Tonya Custis
  • Prateep Gopalkrishnan
  • Catherine Guetzlaff
  • Sughosh Kalghatgi
  • Christine Killian
  • Sangho Kim
  • Muralidhar Koka
  • Richa Kumar
  • Raghuram Lanka
  • Jun Liang
  • Chih-Hua Lin
  • Chang Liu
  • Li Lu
  • Mu Lu
  • Sean McNee
  • Vajira Nissanka
  • Ivan Osipkov
  • Cheong Hee Park
  • Janice Pearce
  • Masakazu Seno
  • Saurabh Kumar Singhal
  • Ekta Sirohi
  • Parthasarathy Sundaram
  • Rashmi Sundareswara
  • Michael Tholkes
  • Justin Thomas
  • Tim Urness
  • Ranga Raju Vatsavai
  • Eric Wahlstrom
  • Jianlin Wang
  • Rong Wu
  • Jing Yang
  • Yu Han Yang
  • Zhihong Yao
  • Ming Yu
  • Qing Zhang
  • Xu Zhang

MCIS Graduates 7/02 - 5/03

  • Doug Erickson
  • Scot Foss
  • Greg Menzel
  • Steve Plowman

MSSE 2003 Graduates

  • Christopher Aburime, EdMentor Corporation
  • Casey Allen, UNISYS Corporation
  • Brian Basel, 3M Company
  • Venkatesh Bashyam, Best Buy Company Inc.
  • Jeremy Bauer, IBM Corporation
  • Charles Betz, Best Buy Company Inc.
  • Sthitie Bom, Seagate Technology
  • Chris Butzow, Self-employed
  • Richard Davies, Retek Inc.
  • Anupa Dhar, IPCS
  • Peggy Dora, Guidant Corporation
  • Yvon Drolet, Tek Systems Inc.
  • Chowdhury Ekram, Best Buy Company Inc.
  • Sean Goggins, Guidant Corporation
  • Luis Herrera-Calderon, Keane Inc.
  • Quang Hong, General Dynamics Information Systems Inc.
  • David Johnson, UNISYS Corporation
  • Bryan Kamrath, Medronic Inc.
  • Amar Kanade, AST Fire Protection Company
  • Pratik Khetiya, MSI Group Inc.
  • Amber Kocemba, MetLife
  • Dewi Koe, Retek Retain Solutions
  • Robert Lach, Lach and Associates
  • Ning Liu, IBM Corporation
  • Michael McMaster, XIOtech Corporation
  • Hector Meneses, Navitaire Inc.
  • Brian Muras, IBM Corporation
  • Karl Narveson, Self-employed
  • Geok Moi Ng, West Group
  • Erica Ngai, BMAC-RFC
  • Cuong Nguyen, University of Minnesota
  • James Pichler, Digital River, Inc.
  • Natasha Poppler, UNISYS Corporation
  • Chandrasekhar Pydi, Mentor Automation Technology
  • Jude Rajan, Analysts International
  • Ryan Reuss
  • Brian Rootes, Hutchinson Technology Inc.
  • Madhuri Veena, IBM Corporation
  • Rajiv Wanasinghe, Syntegra Inc.

Ph.D. graduates with Advisors and Dissertation Titles 7/02 - 5/03

Abdelkader Baggag
Advisor: Yousef Saad & Ahmed Sameh
"Linear System Solvers In Particulate Flows"
Jian Liu
Advisor: Eugene Shragowitz
"A Computational Framework for IP
Selection in Soc Designs"
Brian Bailey
Advisor: Joseph A. Konstan
"DEMAIS: A Behavior-Sketching Tool for
Early Multimedia Design"
Bradley Miller
Advisor: John Riedl & John V. Carlis
"Toward a Personal Recommender System"
Ionut Cardei
Advisor: Ding-Zhu Du
"Resource Management in Wireless Networks"
Robert Miller
Advisor: Anand Tripathi
"The Guardian Model for Exception
Handling in Distributed Systems"
Mihaela Cardei
Advisor: Ding-Zhu Du
"Resource Efficient Approaches in Wireless
Networking"
Doug Perrin
Advisor: Nikolaos Papanikolopoulos
"Vision-Based Tasks and Dynamic Contours"
Taisheng Chang
Advisor: David H. C. Du
"On Several Design Issues of Intelligent
High-Performance Storage Systems"
Alexei Safonov
Advisor: Joseph Konstan & John Carlis
"A Model and System for Automating User
Tasks on the World-Wide Web"
Sangyeun Cho Advisor: Pen Chung Yew & Gyungho Lee
"A High-Bandwidth Memory Pipeline for
Wide Issue Processors"
Pang Ning Tan
Advisor: Jaideep Srivastava & Vipin Kumar
"Discovery of Indirect Association and Its
Applications"
John Collins
Advisor: Maria Gini
"Solving Combinatorial Auctions With
Temporal Constraints in Economic Agents"
Wei Li Wu
Advisor: Shashi Shekhar
"Modeling Spatial Dependencies for Data
Mining"
Xiao Huang
Advisor: Ding-Zhu Du
"Routing Protocols in Ad Hoc Wireless
Networks"
Weiwen Xie
Advisor: Wei-Tek Tsai
"A Study of Developing Secure and Scalable
Business-to-Business Electronic Commerce
Systems"
Mahesh Joshi
Advisor: Vipin Kumar & R. K. Agarwal
"Learning Classifier Models for Predicting
Rare Phenomena"

CS&E Students Win Honors and Awards

National Science Foundation Fellowships

Three CS&E students received the prestigious NSF Graduate Research fellowship Awards for the coming year: graduate students Andrew Drenner and Natalie Linnell and undergraduate Kristen Stubbs. Two students received Honorable Mentions: graduate student Monica LaPoint and undergraduate Colin McMillen.

Andrew Drenner & Natalie Linnell

Image of Andrew Drenner and Natalie Linnell Andrew Drenner of Waterloo, Iowa, is a graduate of the University of Northern Iowa. His advisor is Nikolaos Papanikolopoulos. Currently Andrew is interested in issues involving multi-robot cooperation for exploration of unknown areas and maintaining sensor coverage once an area has been explored. Specifically, he is interested in constructing teams of heterogeneous robots for applications in the detection and neutralization of hazardous biological or chemical agents.

Natalie Linnell, a graduate of the CS&E Department from St. Cloud, Minnesota, works with Gopalan Nadathur in the area of programming languages. Currently she is working on modifying the unification system in Teyjus, Professor Nadathur.s implementation of Lambda Prolog. However, she wrote her grant proposal about adapting implementation techniques from Teyjus to an implementation of another declarative language, Twelf.

Monica LaPoint

Image of Monica LaPoint Monica LaPoint, a graduate of Chicago State University from Shoreview, Minnesota, has returned to graduate school after a career as a software engineer. She is currently interested in robotic vision applied to locomotion and manipulation, focusing on tracking and depth perception. Her advisor is Richard Voyles.

Kristen Stubbs and Colin McMillen

Image of Kristen Stubbs and Colin McMillenComputing Research Association Outstanding Undergraduate Finalists
Kristen Stubbs and Colin McMillen were each finalists in this competition which has separate awards for female and male students. Though they didn.t win the top award or runner-up, they were in the top six in their groups, quite an accomplishment. The work they did that qualified them to be fiinalists was with the Scout Robot project under Professor Nikolaos Papanikolopoulos.

Kristen helped to improve the software architecture used with the Scouts and to design and build the software architecture for the new, larger MegaScouts. She has also worked with Professor Papanikolopoulos on his transportation project where she worked to integrate data from multiple cameras monitoring an intersection. This work should result in better estimates of the actual positions of the cars and pedestrians in the intersection.

Colin implemented a resource scheduler that allows the Scouts. software architecture to efficiently allocate hardware and software resources. He also was primarily responsible for the installation and configuration of an embedded version of the Linux operating system that is used on the MegaScouts and for helping implement a C++ interface to many of the hardware devices present on the MegaScout. More recently he has worked with Professor Papanikolopoulos on a project which uses video cameras to track vehicles at a traffic intersection. The eventual goal of this project is to be able to warn drivers of potential collisions. Kristen, who is from Lee.s Summit, Missouri, will be enrolling in the Ph.D. program at the Robotics Institute at Carnegie Mellon University in the fall where she plans to investigate human-robot interaction utilizing principles from anthropology, psychology, and computer science.

Colin, who is from New Hope, Minnesota, will be entering the Computer Science Ph.D. program at Carnegie Mellon University. He is interested in working with artificial intelligence, especially as applied to multiagent and multirobot systems.

Matt Rasmussen

Image of Matt RasmussenMatthew Rasmussen Wins Goldwater Scholarship
For the second year in a row, a CS&E undergraduate has won the prestigious Goldwater Scholarship. Congress established the Barry M. Goldwater Scholarship and Excellence in Education Program in 1986 to honor Senator Barry M. Goldwater and to provide a continuing source of highly qualified scientists, mathematicians, and engineers by awarding scholarships to college students who intend to pursue careers in these fields.

Matt, who is from Eden Prairie, Minnesota, participated in the Army High Performance Computing Research Center Summer Institute last summer. He has also worked with Professor George Karypis developing a GUI for his clustering toolkit library. See www.cs.umn.edu/~cluto. Matt's GUI is called gCLUTO (Graphical Clustering Toolkit). Matt plans to attend graduate school in bioinformatics after completing his undergraduate degree at the University.

-Bobbie Othmer

CS&E News Briefs

Team Competes in World Finals

The World Finals of the ACM Collegiate Programming Contest was held in Beverly Hills, March 25. The CS&E team of James Esser, Jonathan Moon, and Elliot Olds (coached by Carl Sturtivant) was among 68 teams competing. They tied for 30th place with 12 other teams, all who solved 4 problems correctly during the 5-hour contest. The top three teams were from Warsaw University, Moscow State University, and St. Petersburg Institute of Fine Mechanics and Optics. Of the 26 North American teams, CalTech was the highest at 13th place.

Faculty Serve as Workshop Chairs

Anand Tripathi was the Program Chair for the Workshop on Mobile Distributed Computing, held on May 19, 2003, in conjunction with the International Conference on Distributed Computing Systems. For more details see: http://www.cse.msu.edu/icdcs/

Vipin Kumar served as the Honorary Chair for The International Conference on Computational Science and its Applications, held in Montreal, Quebec, Canada, May 18 - May 21, 2003.

Faculty Serve on Various Boards

Vipin Kumar was appointed to serve on the editorial boards of the following publications: IEEE Computational Intelligence Bulletin and the Annual Review of Intelligent Informatics.

Vipin Kumar has been invited to serve as the Chair of the Board of Visitors for the biennial program review of the Mathematics and Computer Science Division of the Army Research Office (ARO) this year. The board prepares an appraisal of the overall ARO Mathematics and Computer Science research program for the Director of the Army Research Office. The board's report is used in assisting the ARO director Chang in improving the Army's basic research program.

Sturtivant Voted Best CS&E Instructor

For the third year in a row, Carl Sturtivant was selected by I.T. students as the best instructor of the CS&E department.

Recent Grants Awarded to CS&E Faculty

"Estimation within the CLARAty Architecture," JPL/NASA, 4/1/03-3/31/05, $120,000, Stergios Roumeliotis.

"Automatic Evaluation and Assignment of Business Opportunities," IBM, 5/14/03-5/13/05, $50,000, Jaideep Srivastava.

"A Compiler Framework for Supporting Speculative Execution," Intel, 6/1/03-5/31/04, $79,999, Pen-Chung Yew.

"Combat Zones that See," Honeywell International/DARPA, 9/1/03-8/31/06, $500,612, Nikolaos Papanikolopoulos.

"ALGORITHMS: Parallel Large-Scale Sparse Linear System Solvers: New Methods and Paradigms," NSF, 6/1/03-5/31/06, $350,494, Yousef Saad.

"Community Services: Parallel Scientific Computation Made Easy," USDOE, 5/1/03-4/30/06, $250,993, Jon Weissman.

"Real-Time Collision Warning and Avoidance at Intersections," MNDOT, 3/12/03-12/31/04, $195,000, Ravi Janardan.

"Vision Based and Inertial State Estimate for Autonomous Aerial and Ground Vehicles," JPL/NASA, 2/24/03-9/28/03, $10,340, Stergios Roumeliotis.

"NGS: A Framework for Dynamic Service Adaptation in the Grid," NSF, 2/1/03-1/31/06, $240,000, Jon Weissman.

"CAREER: High Quality and Efficient Rendering of Discrete Primitives for Interactive Visualization," NSF, 2/1/03-1/31/08, $541,882, Baoquan Chen.

Tolaas Receives Award

Image of Georganne Tolaas Georganne Tolaas has won the Outstanding DGS Assistant Award, a University-wide award given to recognize and reward the University's top DGS Assistants for their contributions in keeping graduate programs running smoothly, and for their direct support of students in the programs.


Mark your calendar for Friday, October 17, 2003 for the 4th Biennial Computer Science and Engineer Technology Forum.

Faculty Books

Image of "Mastering Data Modeling: A User-Driven Approach" book cover Mastering Data Modeling: A User-Driven Approach by John Carlis, Joseph Maguire
(Addison-Wesley, 2001, ISBN 0-201-70045-X)
This book provides a complete guide to successful data modeling. It features a requirements-driven approach with explanations of key concepts, a user-oriented data modeling notation, and a step-by-step process for collecting, modeling, and documenting the data the users need. This process is illustrated with two annotated examples of conversations with users.

Image of "Problem Solving in Automata, Languages, and Complexity" book cover Problem Solving in Automata, Languages, and Complexity by Ding-Zhu Du, Ker-I Ko
(Wiley-Interscience, 2002, ISBN 0-47-122464-2)
This text is designed for an undergraduate or graduate level course in computability theory that emphasizes problem solving. It usually explains proof ideas and techniques in a constructive way, rather than the usual inductive method. Because the emphasis is on problem solving, only the most common topics in the theory of computation are included: finite-state automata, context-free grammars, Turing machines, recursive and recursively enumerable languages, complexity classes, and NP-completeness.

Image of "Word of Mouse: The Marketing Power of Collaborative Filtering" book cover Word of Mouse: The Marketing Power of Collaborative Filtering by John Riedl, Joseph Konstan, Eric Vrooman
(Warner Books, 2002, ISBN 0-44-653003-4)
Professors John Riedl and Joseph Konstan have spent more than a decade conducting research into "Collaborative Filtering," the technology behind online recommender systems. Systems such as their MovieLens web site (movielens.cs.umn.edu) make personal recommendations based on a visitor's ratings and the opinions of others in the community. In this book, the authors describe Collaborative Filtering and then review three dozen case studies of how companies do, can, and should use recommender systems to provide better customer service and improve sales.

Image of "History of Computing: Software Issues" book cover History of Computing: Software Issues edited by Ulf Hashagen, Reinhard Keil-Slawik, and Arthur Norberg
(Springer, 2002, ISBN 3-540-42664-7)
This volume is based on the international conference "Mapping the History of Computing: Software Issues", held in April 2000 at the Heinz Nixdorf Museums Forum in Paderborn, Germany. The book reviews the present understanding of the history of software and establishes a research agenda for further work to develop a better understanding of this history. The articles in this collection offer a fresh view with new categories and interrrelated themes, comparing software with artifacts in other disciplines in order to determine in what ways software is similar to and different from other technologies.

Image of "Introduction to Parallel Computing: Design and Analysis of Algorithms" book cover Introduction to Parallel Computing: Design and Analysis of Algorithms, 2e by Ananth Grama, Anshul Gupta, George Karypis, Vipin Kumar
(Addison-Wesley, 2003, ISBN 0-201-64865-2)
This book provides an in-depth look at various techniques for the design and analysis of parallel algorithms and for implementing them on commercially available parallel platforms. It includes extensive coverage of MPI, POSIX threads, and Open MP. Topics include sorting, graph algorithms, discrete optimization techniques, data mining algorithms, and algorithms in numerical and scientific computing.

Data Mining for Scientific and Engineering Applications edited by Robert L. Grossman, Chandrika Kamath, Phillip Kegelmeyer, Vipin Kumar, Raju R. Namburu
(Kluwer Academic Publishers, 2001, ISBN 1402001142)

Image of "Data Mining for Scientific and Engineering Applications" book cover Spatial Databases: A Tour by Shashi Shekhar, Sanjay Chawla
(Prentice Hall, 2003, ISBN 0-13-017480-7)
Shekhar and Chawla present the fundamentals and trends in geographical information processing, a topic of great importance for applications such as location based services, public health and safety, climate prediction, and precision agriculture. The core of the book is a sequence of concepts and methods, progressively explaining models, languages and algorithms . The concepts are illustrated with numerous examples. The authors emphasize the many nontrivial issues in integrating spatial data into traditional databases, ranging from deep ontological questions about the modeling of space to important issues about file management. Each chapter is supplemented with many thought-provoking exercises that aid readers in better understanding of the concepts and algorithms presented. The book ends with an exposition of spatial data mining and future trends in spatial databases. This book is being used as a text for advanced courses on GIS and spatial databases, and practioners are finding it to be a handy reference. Prentice Hall has selected this book for translation into Chinese.

Many Thanks...

We would like to express our thanks to the following alumni and friends. Your support is invaluable in helping the department. We look forward to continuing this partnership in the future. Thank you for your support!


Corporations

  • Honeywell Int'l Fdn. Inc.
  • Microsoft Corporation
  • Proc. Assessment Consulting/Training
  • Sprint United Management Co.

Individuals

  • John B. Ahlquist, Jr.
  • Keumog L. Ahn
  • Edward F. Ambrose
  • Kevin C. Andersen
  • Rolland B. Arndt
  • Thomas K. Austin
  • Tien T. Bach
  • Jeanne M. Blaskowski
  • Erik W. Brom
  • Charles A. Buckner
  • John W. Bull
  • Yigang Chen
  • Martin L. Davis
  • Jason M. Drake
  • Nathan W. Fisher
  • Grant B. Edwards
  • Daniel L. Ellingson
  • Richard S. Farrell
  • Julie A. Federico
  • Gregory A. Ford
  • David A. Foster
  • Jesse Freese
  • Matthew J. Galligan
  • David P. Gendron
  • Daniel M. Golliet
  • Philip L. Graetz
  • James G. Grindeland
  • Jonathan R. Gross
  • Richard J. Grutkoski
  • Scott J. Gute
  • Gregory W. Hanka
  • Patricia E. Hansen
  • Richard J. Hedger
  • Russell C. Heinselman
  • George F. Heyne
  • J. Andrew Holey & Gary S. Whitford
  • Joseph J. Holiday
  • Aaron Horne
  • Robert H. Hu
  • Joseph V. Jaeb
  • Mark G. Jahnz
  • Erik A. Jezierski
  • William C. Johnson
  • Theresa Marie Jurisch
  • Mike W. Kersch
  • Marlys A. Kohnke
  • Michael J. Kottke
  • Matthew E. Kramer
  • David P. LaMotte
  • Matthew D. Landgren
  • Colleen M. Lanhart
  • Greg Larson
  • Donald G. & Constance J. Lee
  • Mark R. & Christine Litchy
  • Tok Hui Mackenthun
  • Linda A. Mazzuco
  • Blaine W. McKeever
  • David A. Meyer
  • F. Brendan Murphy
  • Barbara L. Ndosi
  • Mong-Hang T. Nguyen
  • Anna Nookala
  • David R. Odalen
  • Pat J. O.Toole
  • Paul N. Pazandak
  • Michael W. Pease
  • David Rios
  • Richard J. Roiger
  • Frederick W. Roos
  • Christopher W. Root
  • Tom E. Rosenthal
  • Bruce D. Rovner
  • Barbara A. Ruf
  • Allen J. Sames
  • Matt Sandnas
  • David R. Schaal
  • David L. Schmidt
  • Charles M. Sheaffer
  • Marc G. Smith
  • Stephen M. Sohn
  • Daryl L. Spartz
  • Charles D. Steigerwald
  • Jeffrey M. Steil
  • Douglas E. Stewart
  • John P. Strait
  • Steve M. Stupca
  • Susan M. Swenson
  • Geoffrey W. Trenholme
  • Jainag Vallabhaneni
  • Steve E. Van Allen
  • Laura J. Walch
  • Douglas J. Weber
  • Patrick G. Wegerson
  • Kenneth A. Williams
  • Patrick D. Wirz
  • Roy E. Wood
  • Jianzhong Xu
  • Xin Xu
  • Ben L. Yip
  • Garrick H. Yoong
  • Shaoping Zhou
  • Shelly R. Zien

Fall 2003 Colloquia

9/22/03**
Elaine Weyuker, Bell Labs, "Building Dependable Software Through Prediction," 11:15 a.m.-12:15 p.m., EE/CS 3-125

10/06/03*
Ramesh Jain, Georgia Tech, "Experiential Computing: From Information to Insights," 11:15 a.m.-12:15 p.m., EE/CS 3-180

10/13/03*
John Canny, UC-Berkeley, "A Design Science for Computing Applications," 11:15 a.m.-12:15 p.m., EE/CS 3-180

10/20/03**
Wen-mei Hwu, UIUC, "Ultra-Efficient Computer Architectures: How do we get there?" 11:15 a.m.-12:15 p.m., EE/CS 3-125

10/27/03*
Robert E. Kraut, Carnegie Mellon U, "Managing Human Attention," 11:15 a.m.-12:15 p.m., EE/CS 3-180

11/10/03**
Pankaj Agarwal, Duke University, "Geometric Clustering Problems: An Overview," 11:15 a.m. - 12:15 p.m., EE/CS 3-180

11/24/03**
Maria Klawe, Princeton U, "Myths, Opinions and Facts About Females and Computing," 11:15 a.m.-12:15 p.m., EE/CS 3-125

*Denotes speaker for Cray Lecture Series **Denotes speaker for Unisys Lecture Series

Please visit http://www.cs.umn.edu/colloquia/fall_03.html for additional information regarding department colloquia.