Chair   (vacant)
Executive Officer   Robert P. Ingalls
Computer Science Home Page   http://www.cs.rpi.edu/

Computer science is the study of the design, analysis, communication, implementation, and application of computational processes. The core subjects of this discipline include software systems (such as operating systems and networks) and programming languages (including design and other language translation tools). They also include computer hardware systems, the design and analysis of data structures and algorithms, and the theoretical basis of computation, in particular the complexity of computation. In addition to these core subjects, various application areas are open to students, including artificial intelligence, computer graphics, databases, scientific and numeric computation, computer vision, data mining, robotics, computational learning, and user-interface design.

At Rensselaer, education in computer science prepares students for solving applied, real-world problems and for conducting research in computer science. The program provides students a solid grounding in both theory and practice. The undergraduate program also provides a rigorous background in mathematics and science.

Rensselaer’s Computer Science Department offers its own well-equipped computer laboratories for instruction and research. There are 36 Sun Ultra 10 workstations running Solaris 8 in the public labs in the Amos Eaton building (rooms 117 and 217) as well as a dedicated Enterprise 450 serving 32 thin clients (room 215). Each of our Ultra 10 workstations includes a PC subsystem, providing Windows 2000 in the public labs. In the Networking and Distributed Simulation lab, there are 41 IBM x220 servers, along with 13 Cisco routers and a Myrinet Cluster for experimenting with different network layouts. Additionally, our Cisco lab contains over 50 interconnected Cisco routers, which support a number of network technologies such as FDDI, HSSI, ISDN, and Ethernet. Numerous other specialized research computers include a Silicon Graphics Origin 2000 with 12 CPUs. Also available are two robotics labs, a distributed/parallel computing laboratory, a compter-networking lab, and a multimedia database lab. Student offices contain more than 50 other Unix workstations and PCs. Supporting all of these is a network of file servers with more than 0.75 terabytes of storage, print servers, mail servers, and Web servers. Most offices have a 100Mb dedicated connection to the gigabit Ethernet backbone.

The department offers a B.S., M.S., and Ph.D. in Computer Science.

Research Innovations and Initiatives

Scientific Computation and Numerical Analysis   Specializations include adaptive and parallel computational techniques for solving problems that arise in large-scale scientific and engineering applications. Projects include the design and implementation of computer languages and compilers for scientific parallel computations, in particular techniques and methods for compile- and run-time optimization; adaptive methods for solving partial differential equations; and the development of finite element software and of fast and stable matrix algorithms. An especially interesting project involves modeling and simulation of biological and ecological systems.

Discrete Event Simulation   This work encompasses basic simulation techniques, such as parallel simulation protocols, Time Warp performance improvements, and run-time load balance of distributed simulations. The applications include network monitoring and management, wireless networking, and biological and ecological simulations. The systems developed by faculty and publicly available include TEMPEST for spatially explicit spread of disease modeling and GALE for simulating genetic and evolutionary effects in epidemics, and GENESIS for simulating large communication networks.

Computer Vision   Computer vision and biomedical image analysis research in the Department of Computer Science covers a wide range of topics. Developing algorithms for registration and change detection, especially in the diagnosis and treatment of diseases of the human retina, is the largest current project. A related project studies the theory and application of robust estimation techniques in computer vision. A second research area focuses on the tracking of objects, both through video streams and range-image streams. Applications include surveillance, autonomous vehicle navigation, and audio-visual speech recognition. A third track involves the development of stochastic models for the interpretation of video data, for example traffic video.

Human Computer Interfaces   Research in this area is fundamental to the design of systems that mediate between computers and humans. Faculty interests include assistive technology, universal access, intelligent user interfaces, interactive computing, multimedia information visualization, and multimedia environments.

Database Systems   This research area deals with the efficient and effective methods for storing, querying, and maintaining data from possibly disparate and heterogeneous resources. Data is used in many different applications from scientific data sets, sensor data, images, video and audio to hypertext documents, and data on stock market behavior. Research focuses on methods for caching data, querying large and distributed databases, and supporting applications such as computer-aided design and manufacturing and collaborative engineering.

Theory of Computation   Projects involve the design and analysis of efficient algorithms for problems in combinatorial optimization using an experimental approach. Specific research projects include the development and evaluation of general learning and adaptive paradigms that output algorithms on specified input classes. Members of the theory group, along with participating graduate and undergraduate students, developed three large software systems for performing operations on sets and graphs, GraphPack, SetPlayer, and LINK, a comprehensive combinatorics and graph theory workbench for application and research. LINK is a collaborative effort of researchers from six universities.

Worldwide Computing   Worldwide computing research involves using a wide area network as a computing and collaboration platform. Current projects include the development of an actor-oriented programming language, and an Internet-based infrastructure for mobile and distributed computing.

Generic Programming   Research in this area focuses on new ways to design and implement computational methods so that they can adapt easily to different problems, providing solutions that are as efficient as programs written especially for each problem. Research interests span many diverse issues such as behavioral concept specifications, language design, compiler optimizations, efficient memory handling, and constructing and using libraries of multipurpose, high-performance software components. Results include the C++ Standard Template Library, which is based on joint research with colleagues in industry; new generic sorting and searching algorithms; and a new memory manager for C++ programs.

High Performance Data Mining and Computational Learning Systems   This research area deals with the theoretical and applied aspects of automated information extraction (knowledge discovery) from data. For large datasets, emphasis is placed on developing efficient, scalable, and parallel algorithms for various data mining techniques, in addition to the data management itself. Examples include association rules, classification, clustering, and sequence mining. For small datasets, the emphasis is on robust computational learning systems (supervised, unsupervised, and reinforcement) and their theoretical properties. Application areas include bioinformatics, computational genomics, Web mining, geographic information systems, and computational finance.

Robotics   Research in the robotics lab focuses on developing algorithms and automatic planners for robotic manipulation and mobile robotics. Current work includes motion planning for industrial assembly and parts feeding tasks, as well as algorithms for multiple robot coordination and control.

Computational Geometry   Current research in computational geometry concentrates on algorithms for the reconstruction of smooth geometric objects from their samples. Problems of interest include characterizing the conditions on sampling density, which allow a curve to be reconstructed from its samples. The reconstruction is homeomorphic and sufficiently close to the original and the algorithms developed to achieve the reconstruction. Also involved are the dependence of such algorithms on the dimension of the embedding space, related algorithms for the reconstruction of surfaces and manifolds, and finding the most concise representation of a manifold in terms of its samples. A second research track focuses on applications of computational geometry, particularly in robotic motion planning.

Faculty

Departmental faculty listings are accurate as of the date generated for inclusion in this catalog. For the most up-to-date listing of faculty positions, including end-of- year promotions, please refer to the Faculty Roster section of this catalog, which is current as of the May 2002 Board of Trustees meeting.

Professors

Flaherty, J.E.—Ph.D. (Polytechnic Institute of Brooklyn); numerical analysis, scientific computation, parallel computation, and adaptive methods.
Glinert, E.P.—Ph.D. (University of Washington); assistive technology, universal access, human-computer interaction, multimedia information visualization.
Goldberg, M.K.—Ph.D. (Institute of Mathematics, Novosibirsk, U.S.S.R.); algorithms for combinatorial optimization experimental algorithm design and analysis, computational learning theory, graph theory.
Hardwick, M.—Ph.D. (Bristol University, U.K.); database systems for product modeling and manufacturing applications.
Luk, F.T.—Ph.D. (Stanford University); numerical linear algebra, parallel computing, image and signal processing.
Musser, D.—Ph.D. (University of Wisconsin); programming methodology, generic software libraries, formal methods of specification and verification, automated theorem proving.
Spooner, D.—Ph.D. (Pennsylvania State University); engineering database systems, object-oriented systems, database security, database browsing, and visualization.
Stewart, C.—Ph.D. (University of Wisconsin); computer vision, medical applications, robust statistics, computational geometry.
Szymanski, B.K.—Ph.D. (National Academy of Sciences, Warsaw, Poland); computer network management, modeling and simulation of computer and biological systems, distributed computing and scientific parallel computation.

Research Professor
Lawrence, C.—Ph.D. (Cornell University); bioinformatics, transcription regulation, Bayesian statistics and Markov Chain Monte Carlo algorithms.

Associate Professors
Krishnamoorthy, M.S. — Ph.D. (Indian Institute of Technology); programming environments, design and analysis of combinatorial algorithms, performance issues in the Internet, analysis of Web documents, compiler design.

Assistant Professors
Adali, S.—Ph.D. (University of Maryland); multimedia database systems, information integration, query optimization.
Akella, S.—Ph.D. (Carnegie Mellon University); robotics, computer-aided manufacturing, geometric algorithms.
Busch, C. —Ph.D. (Brown University); distributed and parallel systems, communications networks.
Carothers, C.—Ph.D. (Georgia Institute of Technology); experimental distributed systems, simulation, wireless networks, computer architecture.
Freedman, D.—Ph.D. (Harvard University); computer vision, image processing, computational geometry, computational topology.
Huang, W.—Ph.D. (Carnegie Mellon University); robotic manipulation, mobile robotics, motion planning.
Kettnaker, V.—Ph.D. (Cornell University); computer vision, stochastic models.
Magdon-Ismail, M.—Ph.D. (California Institute of Technology); machine learning, computational finance, bioinformatics.
Schupp, S.—Ph.D. (University of Tubingen); generic and component-based programming, programming languages, symbolic computation.
Varela, C.A.—Ph.D. (University of Illinois at Urbana-Champaign); Internet computing, concurrent and distributed systems, programming languages, coordination models, mobile code, databases, the Web.
Zaki, M.—Ph.D. (University of Rochester); data mining and knowledge discovery in databases, parallel computing, bioinformatics.

Lecturer
Hollinger, D.L.—M.S. (Rensselaer Polytechnic Institute); machine learning, AI applications for the World Wide Web, genetic algorithms, Web programming.

Clinical Professor
Danchak, M.M.—Ph.D. (Rensselaer Polytechnic Institute); human-computer interaction, usability, information visualization, techniques for distance learning and human learning models.

Professor Emeritus
McNaughton, R.—Ph.D. (Harvard University); automata theory, formal languages, combinatorics of words.
Rogers, E. —Ph.D. (Carnegie Mellon University); collaborative computing, group operating systems, software engineering.

Adjunct Faculty
Ingalls, R.—Ph.D. (University of Connecticut); systems programming, network programming.
Kotfila, D. — M.Div. (Yale University) Director, Cisco Networking Academy.
Shuey, R.—Ph.D. (University of California); database systems.

Joint Appointment with Mathematical Sciences—Professors
Isaacson, D.—Ph.D. (New York University); applied mathematics, numerical analysis.
McLaughlin, H.W., II—Ph.D. (University of Maryland); analysis, differential equations, approximation theory.

Joint Appointments with Electrical, Computer, and Systems Engineering—Professors
Gerhardt, L.A.—Ph.D. (State University of New York, Buffalo); digital signal processing, communications, voice and image processing, pattern recognition, adaptive systems, computer integrated manufacturing, course development.
Wozny, M.J. —Ph.D. (University of Arizona); computer graphics, computer-aided design, digital simulation, rapid prototyping systems.

Joint Appointments with Electrical, Computer, and Systems Engineering—Associate Professors
Franklin, W.R.—Ph.D. (Harvard University); computational geometry, graphics and CAD algorithms and data structures, parallel algorithms, cartography, expert system verification and validation.
Kalyanaraman, S.—Ph.D. (Ohio State University); ATM and Internet traffic management, multimedia networking, IP telephony, performance analysis, Internet pricing.

Joint Appointment with Mechanical, Aerospace, and Nuclear Engineering—Professor
Shephard, M.—(Cornell University); scientific computation, mesh generation, adaptive and parallel finite element methods.

Joint Appointment with Mechanical, Aerospace, and Nuclear Engineering—Associate Professor
Jansen, K.E.—Ph.D. (Stanford University); large scale scientific computing with emphasis on fluid dynamics. Topics include turbulence modeling, finite element formulations, error estimation, design of software frameworks, parallel computing.

Joint Appointment with Cognitive Science—Professor
Bringsjord, S. —Ph.D. (Brown University); logic, philosophical logic, philosophy of artificial intelligence.

Undergraduate Programs

The undergraduate degree program in computer science provides an excellent background for students entering the work force directly upon graduation and for those pursuing graduate studies. Students majoring in computer science will study artificial intelligence, computer graphics, theory of computation, operating systems, robotics, data mining, databases, systems programming, parallel computing, and scientific numerical computing. The objectives of the Computer Science Department undergraduate curriculum are for students to:

• Acquaint themselves with the major applications of computing and the computing techniques pertinent to them.
• Understand models of computation and means of their implementation in both hardware and software.
• Understand methods used to predict, measure, and manage the complexity of computations.
• Appreciate the diversity of modes and techniques of specification of computations
• Integrate theoretical models with computing practice so the former’s role in assessing the effectiveness of specification, validation, and execution methods can be exploited.

Baccalaureate Programs

All computer science students are assigned a faculty adviser to assist them with their interests and career goals throughout their academic career. As the typical 124-credit-hour B.S. curriculum leading the B.S. in computer science shown below exhibits, flexibility is a hallmark of the Rensselaer computer science program. Opportunities are available for students in many related areas, such as mathematics, electrical engineering, computer engineering, management, and psychology.

Computer Science Curriculum

* Students may skip CSCI-1100 and replace it with any other CS course.

Options

Science   Two four-credit courses in different disciplines chosen from the following: astronomy, biology, chemistry, earth and environmental science, and physics. The Pass/No Credit option cannot be used for these courses. The course ERTH-1030 cannot be used to satisfy this requirement.

Computer Science   Eleven additional credit hours of computing courses at the 4000 or 6000 level. For this purpose, courses in the series CSCI-4xxx, CSCI-6xxx, ECSE-46xx, and ECSE-47xx may be used, excluding reading and independent study courses. The Pass/No Credit option cannot be used for these courses.

Mathematics   One additional mathematics course at the 2000 level or above. The Pass/No Credit option cannot be used for this course.

Dual Major Programs 

Computer science students can obtain a dual major with any other major offered on the Rensselaer campus. In many cases students can obtain a dual major within the 124 credits of a single degree, since many courses can be counted twice. Among the popular majors often combined with computer science are philosophy, mathematics, physics, management, Electronic Media Arts, and Communication, and engineering (the latter requires additional credits hours).

Minor Programs

A computer science minor requires CSCI-1200, CSCI-2300, and three additional four-credit courses at the 2000 level or above. At least two of these must have a CSCI code and at least two must be at the 4000 or 6000 level. One course may be chosen from the ECSE-x6xx or ECSE-x7xx family.

Accelerated Programs

Students may be admitted to the graduate program in Computer Science when they are within 18 credits of completing their B.S. Students may be able to complete the B.S. and M.S. in a shorter than usual time by using advanced placement credit, taking courses during the summer, or taking extra courses during the academic year. A variety of joint degree programs can be arranged, depending on the student’s background, interests, and desired rate of progress. Any joint degree program requires that the student apply to and be accepted to the graduate program.

Special Undergraduate Opportunities

The Computer Science Department strongly encourages students to take part in the following special programs.

Cooperative Education
Numerous opportunities exist for computer science majors, and students are urged to pursue at least one co-op experience during their academic career. More detailed information on this program is available in the School of Science introduction section and the Educational Programs and Resources section of this catalog.

Undergraduate Research Program
This program allows students to participate in faculty research activities. The department urges students to take advantage of these opportunities, through which students can earn either pay or course credit. Additional benefits may include being named co-authors on journal papers or the opportunity to make presentations at professional conferences. Additional information is available in the School of Science introduction section and the Educational Programs and Resources section of this catalog.

Cisco Networking Academy
The Cisco Networking Academy provides extensive hands-on learning in networking. A lab of over 70 routers and switches simulates the backbone of the Internet and is always available for student use. The Academy prepares students for the following certifications: Cisco Certified Network Associate (CCNA), Cisco Certified Network Professional (CCNP), and Cisco Certified Internetwork Expert (CCIE).

Graduate Programs

The Department of Computer Science offers M.S. and Ph.D. degrees in computer science and in computer science with a specialization in computational science and engineering. Degrees in the former prepare students for entry into the professional world by providing a solid foundation in the basics of computer science combined with advanced study and access to modern computing facilities. The goal of the computer science with specialization in science and engineering degree is to provide students with knowledge of an engineering or scientific discipline, computer science, and numerical analysis. These programs are interdisciplinary with students conducting their research and classroom activities in collaboration with computer scientists and engineers in a chosen discipline.

Applications for the M.S. or Ph.D. in computer science should be sent to the Graduate Admissions Office to be received no later than January 15 for fall admission; October 1 for spring admission. Applicants must provide transcripts, two letters of recommendation, a statement of goals, and GRE scores. Each student’s background is expected to include courses in discrete mathematics, calculus, data structures, computer organization, and computing languages, none of which can be counted toward the graduate degree. Admission is extremely competitive, and meeting the minimum requirements does not assure admission.

Master’s Programs

M.S. in Computer Science
In addition to meeting the degree requirements of the Office of Graduate Education, a candidate must plan a degree program and complete the plan of study form in consultation with a faculty adviser. A degree program must include at least 30 credits, at least 18 of which must be at the 6000 level. It must include two required courses, CSCI-6050 (can be replaced by CSCI-6480) and CSCI-4210 (can be replaced by CSCI-6140). It must also include at least one additional course in each of four areas: software systems, hardware systems, theory of computation, and computer applications. Finally, it must include a master’s thesis and regular attendance at department colloquia.

M.S. in Computer Science Specializing in Computational Science and Engineering
Applicants apply to this program in the usual manner. However, student backgrounds are expected to include courses in calculus, elementary linear algebra, elementary differential equations, discrete mathematics, data structures, and numerical computing. Courses in computer organization and computing languages are recommended. Students lacking some of this material may be admitted but will be expected to acquire this knowledge during their studies. This may require taking courses beyond the normal degree requirements.

Students must complete a plan of study that includes 30 credits at the 4000 and 6000 levels with 1) at least six credits in numerical analysis and/or scientific computation; 2)at least eight credits in an area of natural science or engineering; 3) at least one course in each of software and hardware systems; and 4) a significant (3–4 credit) software project. At least 18 credits must be at the 6000 level and students should attend the computer science colloquium and the scientific computation seminars.

Students interested in further study within this area should refer to the Ph.D. in Computer Science Specializing in Computational Science and Engineering below.

Doctoral Programs

Ph.D. in Computer Science
Students must demonstrate skill using computational tools and high achievement in scholarship and independent research. During the first year, the student focuses on obtaining a breadth of knowledge in computer science. At the end of the first year, the student must pass a written doctoral qualifying examination. This examination covers the material of five courses: CSCI-6050, CSCI-4020, CSCI-6140, CSCI-4250, and CSCI-4430.

After passing this examination, the student’s primary focus is research in computer science. After identifying a research topic, the student must pass an oral candidacy examination. This examination evaluates the student’s knowledge in the chosen research area and determines that the student’s proposed research topic is suitable. After completing the research, the student writes a thesis and presents it at an oral defense.

In addition to the above requirements, the student must earn a total of 90 credits beyond the bachelor’s level. Between 45 and 60 credits must be course credits. The remaining credits are for dissertation research. All students must have courses in three of the following four areas on their undergraduate or graduate transcript: database systems, artificial intelligence, numerical computing, and computer graphics/user interfaces. In addition, all doctoral students must have had at least three courses in mathematics at the junior/senior level, and they must demonstrate programming ability on a substantial programming project. The area requirements, the mathematics requirement, and the programming requirement can be satisfied by course work completed prior to entering the Ph.D. program. Finally, all doctoral students are expected to have presented at least two public lectures on their research prior to their defense.

Ph.D. in Computer Science Specializing in Computational Science and Engineering
Students must complete 90 credits of course work and research beyond the B.S. degree, with at least 45 credits in formal course work. They must take 1) at least 12 credits in an area of natural science or engineering; 2) at least nine credits in numerical analysis and/or scientific computation; and 3) at least one course in software systems, hardware systems, and visualization. They must further demonstrate mathematical sophistication by having taken at least eight credits of 4000- or 6000-level mathematics courses (exclusive of numerical analysis) and programming ability by having done a substantial software project.

After one year of study, students must pass a written qualifying examination in 1) numerical computing (material equivalent to CSCI-4800), 2) software and hardware systems (material equivalent to CSCI-4020, CSCI-4250, and CSCI-4430), and 3) a scientific or engineering field of specialization.

Upon passing this examination, students begin dissertation research with a chosen adviser. After their third year of graduate study, students are expected to pass an oral candidacy examination that focuses on their research. Subsequent to passing this examination, students must present two public lectures on their research and write and defend a dissertation.

Doctoral course requirements are inclusive of those for the M.S. degree. As with the M.S. degree, applicants apply in the usual manner, but should have backgrounds including courses in calculus, elementary linear algebra, elementary differential equations, discrete mathematics, datastructures, and numerical computing. Courses in computer organization and computing languages are recommended. The mathematical and programming proficiency requirements can be satisfied by work done outside of the Ph.D. degree program.

Course Descriptions

Courses directly related to all Computer Science curricula are described in the Course Description section of this catalog under the department code CSCI.