College of Arts & Sciences

Computer Science

Chair Stan Sclaroff

Professors Bestavros, Crovella, Gacs, Homer, Kfoury, Levin, Sclaroff

Associate Professors Benson, Betke, Byers, Kollios, Matta, Reyzin, Snyder, West, Xi

Assistant Professors Appavoo, Goldberg, Terzi

Professor Emerita Friedman

The department and its curriculum reflect a broad spectrum of areas in theoretical and applied computer science. Concentrators are encouraged to balance programs by including both applied coursework—such as artificial intelligence, database systems, distributed systems, operating systems, networking, or cryptography—with coursework in theoretical computer science and core mathematics.

Students wishing to combine their interests in computer science with other disciplines may pursue the joint concentrations listed below or the collaborative degree program, BUCOP. Those wishing to cap their undergraduate studies with advanced coursework may elect the combined BA/MA program.

Department facilities include a computer laboratory with 90 work stations and a state-of-the-art teaching laboratory. Students have access to the University’s public cluster of workstations, graphics lab, high-speed campus networks, national vBNS, and Internet 2. Student residences provide Ethernet and terminal room access. The University’s pool of modems provides convenient computer access from off-campus sites.

For additional information about the department and its programs, please visit Computer Science.

Concentration in Computer Science (0701)

Students must earn a minimum grade of C in all courses taken toward a concentration in computer science. Fifteen courses are required.

The following three categories are used in the specification of concentration requirements. The assignment of a given course to one of these categories is determined by the bulletin listing in effect at the time of a student’s enrollment in the course.

CS Required Courses CAS CS 320, CAS CS 330, CAS CS 332, and CAS CS 350.

CS Background Courses are CAS CS courses designated as such in their bulletin description, and non-CS courses satisfying otherwise unsatisfied prerequisites or co-requisites of CS required courses.

CS Elective Courses are CAS CS courses numbered 400 or higher.

Of the fifteen courses required for the concentration, seven must be CS Background Courses, four must be CS Required Courses, and four must be CS Elective Courses chosen in consultation with an advisor. Note: concentration credit will not be given for CAS CS 101 or for Metropolitan College courses.

Graphical illustrations of course categories and dependencies between courses, as well as other helpful information about planning a CS program of study, are available on Computer Science.

TOP OF PAGE

Minor in Computer Science (0701)

Computers and computation play an important role in many areas of intellectual inquiry, as well as in society generally; a minor concentration in computer science can enhance the value of a wide variety of concentrations.

All minor concentrators develop their programs in consultation with an advisor.

A minor concentration in computer science requires completion, with a grade of C or higher, of six courses chosen as follows: two CS courses designated as CS background courses in their bulletin description, plus three more CS courses numbered 300 or higher, plus one more CS course (excluding CS 101) or, with prior approval by the CAS CS department, another computational course.

Joint Concentration in Mathematics and Computer Science (1721)

Please consult the Mathematics and Statistics section of this website.

BA/MA in Computer Science (0701)

This four-and-a-half-year program is designed for highly qualified students. Students must apply during their junior year and must have a cumulative grade point average of 3.5 in computer science with an overall average of 3.0.

The program requires at least 36 courses. Students must complete all BA concentration requirements and all MA requirements. For further information, please see the Graduate School of Arts & Sciences Bulletin.

BA/MA in Computer Science and Cognitive & Neural Systems (CNS)

Please consult the Cognitive and Neural Systems section of this site.

TOP OF PAGE

Computer Science Courses

Courses marked with a (†) satisfy divisional studies requirements.

†CAS CS 101 Introduction to Computers

The computer is presented as a tool that can assist in solving a broad spectrum of problems. This course provides a general introduction designed to dispel the mystery surrounding computers and introduces the fundamental ideas of programs and algorithms. (Does not count for CS major or minor concentration credit.) 4 cr, either sem. (MCS)

†CAS CS 103 Introduction to Internet Technologies and Web Programming

Introduction to the basic architecture and protocols underlying the operation of the Internet with an emphasis on Web design, Web application programming, and algorithmic thinking. General familiarity with the Internet is assumed. 4 cr, either sem. (MCS)

†CAS CS 105 Introduction to Databases and Data Analysis

General introduction to databases. Topics include database technology and data modeling; knowledge discovery and data mining; data visualization. Applications are drawn from a variety of disciplines including medicine, psychology, and the natural sciences. (Does not count for CS concentration credit.) (Carries MCS divisional credit) Sullivan. 4 cr, either sem. (MCS)

†CAS CS 107 Computational Systems

What is computing? Where can it take place? How can we recognize computing occurring in nature? This course looks beyond traditional electronic computers to present a modern view of computation, its limitations, and its realization in varying settings. 4 cr, 2nd sem. (MCS)

†CAS CS 108 Introduction to Applications Programming

Introduction to object-oriented and procedural programming, including understanding fundamental constructs and patterns present in programming languages; using abstraction to simplify complex problems into concrete subtasks; methodical and efficient programming and debugging. Suitable for students not concentrating in Computer Science. (Cannot be taken for credit in addition to CAS CS 111.) 4 cr, either sem. (MCS)

†CAS CS 109 The Art and Science of Quantitative Reasoning

Buying music online, making phone calls, predicting the weather, or controlling disease outbreaks would be impossible without mathematics, statistics, and computer science. Focuses on methods of reasoning common to these disciplines, and how they enable the modern world.(Does not count for CS concentration credit.) Also offered as CAS MA 109. 4 cr, either sem. (MCS)

†CAS CS 111 Introduction to Computer Science I

The first course for computer science, mathematics, and physical science concentrators, and others wishing a more technical approach than CAS CS 101 through CAS CS 108. Develops basic skills in computer programming using the Java programming language. (Counts as a CS Background Course for the concentration.) 4 cr, either sem. (MCS)

†CAS CS 112 Introduction to Computer Science II

Prereq: CAS CS 111 or equivalent. Covers advanced programming techniques and data structures. Topics include recursion, algorithm analysis, linked lists, stacks, queues, trees, graphs, tables, searching, and sorting. (Counts as a CS Background Course for the concentration.) 4 cr, either sem.

CAS CS 131 Combinatoric Structures

Representation, analysis, techniques, and principles for manipulation of basic combinatoric structures used in computer science. Rigorous reasoning is emphasized. (Counts as a CS Background Course for the concentration.) Formerly CAS CS 113, therefore cannot be taken for credit in addition to CAS CS 113. 4 cr, either sem. (MCS)

CAS CS 132 Geometric Algorithms

Prereq: CAS CS 111 and CAS MA 123 recommended. Basic concepts, data structures, and algorithms for geometric objects. Examples of topics: Cartesian geometry, transformations and their representation, queries and sampling, triangulations. Emphasis on rigorous reasoning and analysis, advancing algorithmic maturity and expertise in its application. (Counts as a CS Background Course for the concentration.) Formerly CAS CS 232, therefore cannot be taken for credit in addition to CAS CS 232. 4 cr, 2nd sem.

CAS CS 210 Computer Systems

Prereq: CAS CS 111. Fundamental concepts of computer systems and systems programming. Hardware fundamentals including digital logic, memory systems, processor design, buses, I/O subsystems, data representations, computer arithmetic, and instruction-set architecture. Software concepts including assembly language programming, operating systems, assemblers, linkers, and systems programming in C. (Counts as a CS Background Course for the concentration.) 4 cr, 1st sem.

CAS CS 211 Object-Oriented Programming Paradigms

Prereq: CAS CS 111; CAS CS 112 is recommended; or consent of instructor. Intensive study of object-oriented generic programming paradigms, including inheritance, templates, generic patterns, and the Standard Template Library. Students design, implement, and test large-scale C++/C# programs involving file systems, databases, and graphical interfaces using integrated development platforms. (Does not count for CS concentration credit.) 4 cr, 1st sem.

CAS CS 212 Distributed Programming Paradigms

Prereq: CAS CS 111; CAS CS 112 and 211 are recommended; or consent of instructor. Intensive study of object-oriented, distributed programming using C# in the .NET framework and the Common Language Runtime environment. Students develop networked applications involving web services and database managment systems. (Does not count for CS concentration credit.) 4 cr, 2nd sem.

CAS CS 235 Algebraic Algorithms

Coreq: CAS CS 132 recommended. Basic concepts and algorithms for manipulation of algebraic objects, such as residues, matrices, polynomials; and applications to various CS areas, such as cryptography and fault-tolerance. Emphasis on rigorous reasoning and analysis. (Counts as a CS Background Course for the concentration.) 4 cr, 2nd sem.

CAS CS 237 Probability in Computing

Prereq: CAS MA 123 or equivalent experience; CAS CS 131; CAS CS 132 or CAS CS 235 or CAS MA 294; or consent of instructor. Introduction to basic probabilistic concepts and methods used in computer science. Develops an understanding of the crucial role played by randomness in computing, both as a powerful tool and as a challenge to confront and analyze. Emphasis on rigorous reasoning, analysis, and algorithmic thinking. (Counts as a CS Background course for the concentration.) 4 cr, 1st sem.

CAS CS 320 Concepts of Programming Languages

Prereq: CAS CS 112 and CAS CS 131. Coreq: CAS CS 210. Concepts involved in the design of programming languages. Bindings, argument transmission, and control structures. Environments: compile-time, load-time, and run-time. Interpreters. 4 cr, 1st sem.

CAS CS 330 Introduction to Analysis of Algorithms

Prereq: CAS CS 112 and CAS CS 131. Coreq: CAS MA 242 or CAS CS 132; CAS MA 294 or CAS CS 235. Examines the basic principles of algorithm analysis; techniques of efficient programming; analysis of sorting and searching; graph algorithms; string-matching algorithms; matrix algorithms; integer and polynomial arithmetic; the fast Fourier transform; and NP-hard and NP-complete problems. 4 cr, 1st sem.

CAS CS 332 Elements of the Theory of Computation

Prereq: CAS CS 330. The basic concepts of the theory of computation are studied. Topics include models of computation, polynomial time, Church’s thesis; universal algorithms, undecidability and intractability; time and space complexity, nondeterminism, probabilistic computation and reductions of computational problems. 4 cr, 2nd sem.

CAS CS 350 Fundamentals of Computing Systems

Prereq: CAS CS 210; and CS 237 or MA 381, or consent of instructor. Rigorous treatment of invariant concepts, algorithms, and performance evaluation methods underlying computing systems design. Topics include modeling and analysis of concurrent processing, computational resource scheduling and consumption, and performance evaluation techniques. 4 cr, 2nd sem.

CAS CS 401, 402 Senior Independent Work

Prereq: approval of the Honors Committee. 4 cr, either sem.

CAS CS 410 Advanced Software Systems

Prereq: CAS CS 112; CAS CS 210 is recommended. Systems programming including such topics as project management, tools, I/O networking, multiprocessing, exception handling, and system services. Other topics are explored using C and Perl under the UNIX operating system. Requires a working knowledge of the C programming language and experience with UNIX as a user, or equivalent. 4 cr, 2nd sem.

CAS CS 411 Software Engineering

Prereq: CAS CS 112 or consent of instructor. Introduction to the construction of reliable software. Topics may include software tools, software testing methodologies, retrofitting, regression testing, structured design and structured programming, software characteristics and quality, complexity, entropy, deadlock, fault tolerance, formal proofs of program correctness, chief program teams, and structured walk-throughs. 4 cr, 1st sem.

CAS CS 440 Introduction to Artificial Intelligence

Prereq: CAS CS 112; CAS MA 242 or CAS CS 132, or consent of instructor. Introduction to computer systems that exhibit intelligent behavior, in particular, perceptual and robotic systems. Topics include human computer interfaces, computer vision, robotics, game playing, pattern recognition, knowledge representation, planning. 4 cr, 1st sem.

CAS CS 450 Computer Architecture I

Prereq: CAS CS 210. Overview of computer architecture. Topics include representation of information, combinational and sequential circuits, design and analysis; techniques of implementing algorithms in hardware: parallelism, pipelining; Von Neumann and data flow models of computation, and hardware implementations of both models. 4 cr, 1st sem.

CAS CS 455 Computer Networks

Prereq: CAS CS 330 and CAS CS 350, or consent of instructor. Concepts underlying the design of high-performance computer networks and scalable protocols. Topics include Internet design principles and methodology, TCP/IP implementation, packet switching and routing algorithms, multicast, quality of service considerations, error detection and correction, and performance evaluation. 4 cr, 1st sem.

CAS CS 460 Introduction to Database Systems

Prereq: CAS CS 112 or equivalent. Introduction to database management systems. Examines entity-relationship, relational, and object-oriented data models; commercial query languages: SQL, relational algebra, relational calculus, and QBE; file organization, indexing and hashing, query optimization, transaction processing, concurrency control and recovery, integrity, and security. 4 cr, 2nd sem.

CAS CS 470 Performance Analysis

Prereq: CAS CS 350. Introduction to measurement, modeling, and simulation of computer systems. Applications of probability and stochastic processes to computer systems modeling; queues and queuing  networks; discrete event simulation. Applications in client/server systems and networking are emphasized. 4 cr, 1st sem.

CAS CS 480 Introduction to Computer Graphics

Prereq: CAS CS 112; CAS CS 132 or MA 242. Introduction to computer graphics algorithms, programming methods, and applications. Focus on fundamentals of two- and three-dimensional raster graphics: scan-conversion, clipping, geometric transformations, and camera modeling. Introduces concepts in computational geometry, computer-human interfaces, animation, and visual realism. 4 cr, 2nd sem.

CAS CS 491, 492 Directed Study

Prereq: consent of instructor and approval of the Directed Study Committee (CAS Room 105). Variable cr, either sem.

CAS CS 511 Object-Oriented Software Principles

Prereq: CAS CS 320 or CS 411 or consent of instructor. Specification, programming, and analysis of large-scale, reliable, and reusable Java software using object-oriented design principles. Topics may include object-oriented programming, object models, memory models, inheritance, exceptions, namespaces, data abstraction, design against failure, design patterns, reasoning about objects. 4 cr, 2nd sem.

CAS CS 520 Programming Languages

Prereq: CAS CS 320 or consent of instructor. Concepts of programming languages: data, storage, control, and definition structures; concurrent and distributed programming; functional and logic programming. 4 cr, 1st sem.

CAS CS 525 Compiler Design Theory

Prereq: CAS CS 320 or consent of instructor. Covers the basic mathematical theory underlying the design of compilers and other language processors and shows how to use that theory in practical design situations. Topics may include lexical analysis, parsing, syntax-directed translation, code optimization, and code generation. 4 cr, 2nd sem.

CAS CS 530 Analysis of Algorithms

Prereq: CAS CS 330 or consent of instructor. Studies the design and efficiency of algorithms in several areas of computer science. Topics are chosen from graph algorithms, sorting and searching, NP-complete problems, pattern matching, parallel algorithms, and dynamic programming. 4 cr, 2nd sem.

CAS CS 532 Computational Geometry

Prereq: CAS CS 330. Studies the design, analysis, and implementtion of algorithms and data structures for solving geometric problems that arise in such diverse settings as computer graphics, robotics, databases, data mining, parallel computing, statistics, and pure mathematics. 4 cr, 1st sem.

CAS CS 535 Complexity Theory

Prereq: CAS CS 332, or consent of instructor. Covers topics of current interest in the theory of computation chosen from computational models, games and hierarchies of problems, abstract complexity theory, informational complexity theory, time-space trade-offs, probabilistic computation, and recent work on particular combinatorial problems. 4 cr, 1st sem.

CAS CS 537 Probability in Computing

Prereq: CAS CS 330 or CS 530 or consent of instructor. CAS CS 535 is recommended. Survey of probabilistic ideas of the theory of computation. Topics may include: Monte Carlo and Las Vegas probabilistic computations; average case complexity and analysis; random and pseudorandom strings; games and cryptographic protocol; information; inductive inference; reliability; others. (Offered alternate years.) 4 cr, 2nd sem.

CAS CS 538 Fundamentals of Cryptography

Prereq: CAS CS 131 and CS 237 or consent of instructor. Basic algorithms to guarantee confidentiality and authenticity of data. Definitions and proofs of security for practical constructions. Topics include perfectly secure encryption, pseudorandom generators, RSA and Elgamal encryption, Diffie-Hellman key agreement, RSA signatures, secret sharing, block and stream ciphers. 4 cr, 1st sem.

CAS CS 539 Methods of Scientific Computing

Prereq: CAS MA 225 or MA 230 and MA 226 or MA 231 and MA 242 or MA 442 and CS 330 or consent of instructor. Meets with CAS MA 539. An introductory survey of topics including computational linear algebra, solutions of linear equations, numerical integration and solution of differential equations, finite element methods, and methods of stochastic simulation (i.e., Monte Carlo methods). 4 cr, 2nd sem.

CAS CS 542 Machine Learning

Prereq: CAS CS 112 or equivalent programming experience, and familiarity with linear algebra, probability, and statistics. Introduction to modern machine learning concepts, techniques, and algorithms. Topics include regression, kernels, support vector machines, feature selection, boosting, clustering, hidden Markov models, and Bayesian networks. Programming assignments emphasize taking theory into practice, through applications on real-world data sets. 4 cr, 2nd sem.

CAS CS 548 Advanced Cryptography

Prereq: CAS CS 538 or consent of instructor. Continuation of CAS CS 538. Advanced techniques to preserve confidentiality and authenticity against active attacks, zero-knowledge proofs; Fiat-Shamir signature schemes; non-malleable public-key encryption; authenticated symmetric encryption; secure multiparty protocols for tasks ranging from Byzantine agreement to mental poker to threshold cryptography. 4 cr, 2nd sem.

CAS CS 549 Pattern Matching and Detection with Applications is Biological Sequence Analysis

Prereq: CAS CS 330 and senior standing, or consent of instructor. Examines algorithmic techniques for pattern matching and detection with applications geared to biological sequence analysis. Readings from original journal articles and textbooks. Algorithm correctness, time and space complexity, and sensitivity/specificity trade-offs are discussed. 4 cr, 1st sem.

CAS CS 550 Computer Architecture II

Prereq: CAS CS 350. Overview of concepts underlying the design of high-performance computer architectures, with emphasis on quantitative evaluation and effect on compiler and operating system design. Topics include: pipeline, superscalar, vector, and parallel processors; hard-wired scheduling and branch prediction; cache and virtual memory-hierarchy design; shared-memory and message-passing scalable multiprocessors. Case studies including RISC/CISC and SIMD/MIMD architectures. 4 cr, 2nd sem.

CAS CS 552 Introduction to Operating Systems

Prereq: CAS CS 210 and CS 350, or consent of instructor. Examines process synchronization; I/O techniques, buffering, file systems; processor scheduling; memory management; virtual memory; job scheduling, resource allocation; system modeling; and performance measurement and evaluation. 4 cr, 1st sem.

CAS CS 553 Operating Systems II

Prereq: CAS CS 552. Advanced course focusing on technical papers and case studies of modern operating systems. Rigorous study of OS structure, design, and implementation for real-world systems. Abstractions, mechanisms, and policies for future system design, including address-space protection, scheduling, synchronization, and fast interprocess communication. 4 cr, 2nd sem.

CAS CS 556 Advanced Computer Networks

Prereq: CAS CS 455 or consent of instructor. Strengthens understanding of networking issues and solutions. Relates fundamental concepts, requirements, and design tradeoffs to scheduling, congestion control, routing, traffic management, wireless access and mobility, and applications. Considers how networking may evolve to provide ubiquitous support for quality-of-service in heterogeneous environments. 4 cr, 2nd sem.

CAS CS 558 Computer Networks Security

Prereq: CAS CS 235 or consent of instructor; recommended corequisite: CAS CS 455. Theory and practice of computer network security. Cryptographic tools: shared and public key cryptography, encryption, key exchange, and signature. Applying these tools in protocols and systems: confidentiality, authentication, data integrity (Kerberos; SSL/TLS, ISPEC; VPNs; certificates, PK). Firewalls, intrusions, viruses. 4 cr, 1st sem.

CAS CS 559 Algorithmic Aspects of Computer Networks

Prereq: CAS CS 330 and CAS CS 455 or consent of instructor. Studies the role of algorithms in large-scale networked applications such as Internet content delivery, peer-to-peer file sharing, and network monitoring. Topics include randomized summarization, information coding, and distributed hash tables. 4 cr, 2nd sem.

CAS CS 562 Advanced Database Applications

Prereq: CAS CS 460, or consent of instructor. Research issues in the design and implementation of modern database systems. Spatial, temporal, and spatiotemporal index structures. Indexing methods for image and multimedia databases and data warehouses. New data analysis techniques for large databases, clustering and rule discovery for very large datasets. 4 cr, 1st sem.

CAS CS 565 Data Mining

Prereq: CAS CS 112 or equivalent programming experience, and familiarity with linear algebra, probability, and statistics. Introduction to data mining concepts and techniques. Topics include association and correlation discovery, classification and clustering of large datasets, outlier detection. Emphasis on the algorithmic aspects as well as the application of mining in real-world problems. 4 cr, 1st sem.

CAS CS 580 Advanced Computer Graphics

Prereq: CAS CS 480 or equivalent, or consent of instructor. Survey of advanced modeling, rendering, and animation algorithms. Emphasis on implementation and underlying theory for simulating various phenomena. Topics include: photorealistic image synthesis, modeling natural objects and phenomena, character animation, virtual reality, and advanced computer-human interface techniques. (Offered alternate years.) 4 cr, 2nd sem.

CAS CS 585 Image and Video Computing

Prereq: CAS CS 132 or CAS MA 242 and CAS CS 112 or equivalent programming experience and familiarity with calculus. Introduction to images and video as multimedia data types and algorithms for image and video understanding based on color, shading, stereo, and motion. Topics include face recognition, human-computer interfaces, animal and vehicle tracking, and medical image analysis. 4 cr, 2nd sem.

CAS CS 591 Topics in Computer Science

Various issues in computer science. 4 cr, either sem.

Related Courses  In special cases, a student, with consent of the instructor, may petition the Undergraduate Director to count courses other than those listed here toward concentration credit. Attention is called to the following, with descriptions listed in the Graduate School of Arts & Sciences Bulletin: CS courses numbered 600 and above; the 500-level courses in mathematics; the 500-level courses in cognitive and neural systems; the Joint Mathematics and Computer Science Program; and the computer engineering courses offered by the College of Engineering.

TOP OF PAGE

Published by Trustees of Boston University
One Silber Way
Boston, MA 02215

16 October 2009
Boston University
Questions
Credits