Courses

The Department of Computer Science offers a variety of regular courses, as well as special topics courses and independent study courses. Courses at the 400 level are generally taken by senior undergraduates but are open to graduate students. Research seminars are intended primarily for doctoral students and master's students engaged in research. A synopsis of our current course offerings appears below. Consultants are available to help students with many courses. Course archives from past semesters are available online and in the department office.

CS 100 Introduction to Computing Tools

This course introduces the use of computer and network tools in support of individual and collaborative undergraduate studies. Topics covered in lectures and labs: structure of computing systems, electronic mail, World Wide Web, text editing, spreadsheets, symbolic mathematics, and document processing.

Credit 1 unit pass/fail

CS 101G- 102G Computer Science I-II

An introduction to algorithms, algorithmic processes and their implementation on computers. First semester: Concepts of functional programming. Computation through direct substitution. Introduction to principles of abstraction for data and procedures and the application of these principles to effectively reduce the complexity of problems. The use of levels of description and abstraction hierarchies to control the organizational complexity of software systems. Introduction to the concept of von Neumann architecture. Debugging and documentation. Implementation of several nontrivial algorithms and procedures. Second semester: Concepts of procedural programming. Use of invariants to reason about correctness of algorithms. Abstraction and Software Engineering as mean of controlling complexity. Introduction to Abstract Data Types. Introduction to Object-Oriented design and programming concepts. Concept of modularity. Debugging and documentation. Design and implementation of nontrivial algorithms and procedures. Computation in a von Neumann machine.

Corequisite: Math 131 or equivalent. Three lectures and a two-hour laboratory session each week. Credit 4 units per course.

CS 125 Introduction to Engineering Computing

Computing tools for engineers. Topics: basic computing concepts, operating environments, engineering applications of spreadsheets, equation-solving packages, introduction to programming. Emphasis on independent use of documentation. Weekly laboratory exercises give students hands-on experience using software tools to solve engineering problems.

Credit 3 units.

CS 136G Introduction to Computing

A workshop course (lectures and supervised laboratory sessions) covering the fundamental organization and operating principles of digital computers and the systematic design and development of well-structured programs. After an intensive exposure to algorithmic principles and programming techniques and practices using the C++ language, students learn about a computer's internal structure through the use of a simple Von Neumann machine simulator.

Credit 4 units.

CS 142 Computers and Society

(Same as EP142) This course is an introduction to social, legal, ethical, and economic issues related to computing. As a lecture and discussion course, a broad range of topics will be covered including the use of computers in society, risks, privacy, computer crime, growth and funding of the Internet and intellectual property laws. Students will select a topic for research throughout the semester.

Credit 2 units.

CS 143 Introduction to Java Programming

This programming language course will cover some of the object-oriented language features of Java, e.g., encapsulation, inheritance, and polymorphism. Programming assignments will be used to explore the nature of Java and the kinds of the applications for which it is useful. Although no specific knowledge is necessary, some programming experience will be required.

Credit 2 units.

CS151 Introduction to Computer Mediated Human Communication

This course is specially designed for non-CS majors from freshmen to seniors. The goals of the course are: to study how humans communicate using computer technologies such as the internet, databases, and digital TV in the future; to learn how to use computers for daily communication needs; to understand the future implications of computer technology on human communication. This course is a good introduction to more advanced computer application courses. No prerequisites. No math or computer programming is required. Weekly lab works are mandatory.

Credit 3 units

CS 201 Formal Foundations of Computer Science

Introduces elements of logic, mathematics, and philosophy that allow reasoning about computational structures and processes. Generally, the areas of discrete structures, proof techniques, and computational models are covered. Topics typically include propositional and predicate logic; sets, relations, functions, and graphs; proof by contradiction, induction, and reduction; and finite state machines and regular languages.

Corequisite: CS 101G. Credit 3 units.

CS 241 Algorithms and Data Structures

Study of fundamental algorithms and data structures. Emphasizes importance of data structure choice and implementation for obtaining the most efficient algorithm for solving a given problem. Covers asymptotic notation and techniques for solving basic recurrence relations. Attention will be given to analysis of asymptotic performance. Algorithms presented include: sorting, hashing, searching, basic graph algorithms, garbage collection, and string matching. Data structures covered: basic search trees, balanced search trees, heap data structure, B-trees, and graph representations.

Prerequisites: CS 102G, Math 142 or equivalent. Credit 3 units.

CS 260M Digital Computers I: Organizational and Logical Design

(Same as EE 260M) Digital computers and digital information-processing systems; Boolean algebra, principles and methodology of logic design; machine language programming; register transfer logic; microprocessor hardware, software, and interfacing; fundamentals of digital circuits and systems; computer organization and control; memory systems, arithmetic unit design. Occasional laboratory exercises.

Prerequisites: CS 102G or 136G, and sophomore standing. Credit 3 units.

CS 265 Introduction to Computing and Computer Applications

Basic architectural components of computers and networks and their functions; development of computer-oriented problem solving and numerical methods; program development and programming. Using the FORTRAN language and software libraries, students design and implement a variety of programs covering a broad spectrum of nontrivial computer applications. Use of high-level tools for calculus/algebraic analysis.

Corequisite: Math 217. Credit 3 units.

CS 300 The Art and Science of Computing

This course provides an introduction to the important ideas in computer science, its history and development, and the future of computing technology. It is intended for students who are interested in understanding the core concepts and the potential of computing technology, rather than developing professional expertise. Topics include data representation, algorithms, historical developments, what computers can and cannot do, the information superhighway, and the impact of computing/information technology on business and society.

Prerequisite: none. Credit 3 units.

CS 306 Processing Systems and Structures

Analysis of function and organization of major subsystems of information-processing complex. Fundamental algorithms for numerical computation, extended precision arithmetic, address translation, storage allocation, access methods, and the sequencing and control of peripheral devices. Introduction to the real-time operating systems, with emphasis on real-time signal-processing applications and resource management. Weekly laboratories, exercises, and a final laboratory project.

Prerequisites: CS 102G or 136G, and sophomore standing. Credit 3 units.

CS 313A Artificial Intelligence Laboratory

Project course in artificial intelligence. Students learn standard approaches, then alter existing code. Students integrate solutions to create an intelligent agent in a simulated world faced with classic AI problems in natural language processing, reasoning, vision, speech, organization of expert knowledge, planning, and learning.

Prerequisites: CS 102G, 201. Credit 3 units.

CS 333S Special Topics in Distributed Applications

A project-based course in which undergraduate students work alone and in small groups to develop interactive distributed applications from modular software building blocks. Several distributed application paradigms are explored.

Students use a programming environment based on a novel approach to the construction of distributed applications. Students use graphics tools to configure distributed applications and construct direct-manipulation graphical user interfaces for them. Distributed applications are constructed in a variety of domains, such as distributed interactive simulations, group collaboration, pipelined image processing, and distributed multiplayer games.

Prerequisites: CS 241 and C++ programming experience. Credit 3 units.

CS 342S Developing Object-Oriented Software with Patterns and Frameworks

Intensive focus on practical aspects of designing, implementing, and debugging object-oriented software. Topics covered include reuing design patterns and software architectures and developing, documenting, and testing representative applications using object-oriented frameworks and C++. Design and implementation based on design patterns and frameworks are central themes to enable the construction of reusable, extensible, efficient, and maintainable software.

Prerequisites: CS 101, 102, 241. Credit 3 units

CS 353T-354M Operations Analysis I-II

Introduction to the nature of operations research and some of its techniques. Topics: modeling complex systems as linear programs, the simplex method, duality, sensitivity analysis, and use of computer linear programming packages; critical path analysis, network flow, assignment problems, and dynamic programming; discounting, utility decisions under uncertainty, and inventory models; continuous and discrete simulation languages. Monte Carlo methods and queueing theory.

Prerequisite for CS 353T: CS 102G or 136G. Prerequisites for CS 354M: at least sophomore standing, CS 353T, and either SSM 326 or 325. Credit 3 units per course.

CS 362M Digital Computers: Architecture

(Same as EE 362M) Study of interaction and design philosophy of hardware and software for digital computer systems. Machine organization, data structures, I/O considerations. Comparison of microcomputer architectures.

Prerequisite: CS/EE 260M. Credit 3 units.

CS 400 Independent Work

Possible topics may be found in the Undergraduate Research Opportunities Program listing.

Prerequisite: junior standing. Credit to be arranged; no more than 3 units a semester.

CS 422S Operating Systems Organization

Exploration of operating systems as resource managers. Using UNIX as a conceptual framework, students study algorithms and data structures that support essential operating systems services. Concepts are reinforced through programming exercises and comparative studies. Topics include: process scheduling, file systems organization, memory management, virtual memory, device management, concurrent processes, and security.

Prerequisites: CS 241, 306. Credit 3 units.

CS 423S Computer Communications

An introduction to the principles and practice of communicating data. The ISO-OSI layered model is introduced and used as a framework for examining computer communication. Topics: physical aspects of reliable and efficient transmission; protocol design and analysis; assessment of network performance; datalink, routing and transport protocols. A small number of exercises supplement lectures and provide experience with computer communications programming.

Prerequisite: CS 306 or 326M. Credit 3 units.

CS 427A Special Topics in Real-Time Processing

(Same as EE 427A) Microcontrollers and digital signal processors are often utilized in applications such as communication systems, automotive control systems, biomedical instrumentation, consumer appliances, and industrial control systems. The purpose of this course is to examine a variety of issues regarding the real-time application of embedded microprocessor systems. Topics will include digital processing, the physics of sensors and transducers, signal representation, system design and software development. Classes will include lecture and laboratory sessions. Depending on student interest, exemplary applications from the following list will be studied: automotive control, biomedical instrumentation, communication systems, speech processing, data compression, and audio and acoustic processing.

Prerequisite: Senior standing or greater or by permission of instructor. Credit 3 units.

CS 431S Translation of Computer Languages

The theory of language recognition and translation is introduced in support of compiler construction for modern programming languages. Topics include syntactic and semantic analysis, symbol table management, code generation, and runtime libraries. A variety of parsing methods is covered, including Earley's algorithm, LL(k), SLR(k), and LR(k). Machine problems culminate in the course project, for which students construct a working compiler.

Prerequisites: CS 201, 241. Credit 3 units.

CS 441T Advanced Algorithms

Provides a broad coverage of fundamental algorithms. The core set of topics studied includes: median finding algorithms, dynamic programming, greedy algorithms, computational geometry, linear programming and basic duality theory, NP-completeness and reducibility, approximation algorithms, parallel computation, randomized algorithms, and an introduction to cryptography.

Prerequisite: CS 241. Credit 3 units.

CS 447T/CS 547T Algorithms for Computational Biology

The computer scientist interacts increasingly with the biologist, as computation plays an ever increasing role in how biologists view, formulate,and solve problems in molecular biology. In this course we examine algorithms relevant to studies in molecular biology. Topics include DNA sequence comparison, protein modeling, DNA fragment assembly, and construction of evolutionary trees. For each area of study, we first summarize the relevant biological background; we then study algorithms in computer science that are appropriate for application in the given area. We study both the complexity of such algorithms as well as their effectiveness in solving real problems in molecular biology. While the course will not necessarily require programming, an optional programming project will be allowed in lieu of other course work.

Prerequisites: CS 241 or equivalent. Credit: 3 units.

CS 453A Computer Graphics

Introduction to computer graphics. Input, representation, manipulation, and display of geometric information. Two-dimensional display of three-dimensional objects: perspective, hidden surface, shading, animation. Display and input devices. Issues in designing interactive graphics systems. Issues in building standard graphics packages. Students solve problems using interactive graphics with a standard graphics package and using various graphics input and output devices.

Prerequisite: CS 241. Credit 3 units.

CS 455 Programming Systems and Languages

A comparative study of programming languages: von Neumann-type, functional, and logical programming languages. Conceptual foundation, syntax, semantics (e.g., denotational, axiomatic, and operational), and implementation. Run-time structures required to support various language features such as data types, operations, flow of control constructs, exception handling, visibility rules, subprograms, concurrency, etc. Ada, LISP, and Prolog are used for illustration purposes and in assigned problems.

Prerequisites: CS 201, CS 241. Credit 3 units.

CS 456 Software Engineering Workshop

State-of-the-art, industrially-tested, object-oriented techniques are presented, illustrated on small example, and applied to realistic problems. The objective of the course is to develop an understanding of the technical and organizational complexities involved in system design and to teach key concepts and techniques used to manage these complexities. The students are required to design a complex computer-based system through team effort. The project makes use of a fictional customer problem and covers the principal system life-cycle phases: requirements generation, system design, and software design. The target system is complex involving distributed processing, user interfaces, and real-time constraints. Issues such as human factors, performance, operation costs, and maintainability are addressed and resolved in a reasonable manner. Emphasis is placed on emulating the realities of an industrial organization.

Prerequisite: CS 455. Credit 3 units.

CS 462M Digital Computers III: Computation Structures

(Same as EE 462M) Introduction to ALU design: addition, subtraction, multiplication, and division. Direct and iterative approaches for multiplication, including Wallace trees. Synchronization. Introduction to modern design methodologies. Students use a commercial CAE/CAD system for schematic capture and simulation while designing a selected computation system.

Prerequisites: CS 306, 362M. Credit 3 units.

CS 465A Numerical Methods

(Same as SSM 465A) Introduces current numerical methods: iterative methods, roots of polynomials, interpolation, numerical differentiation and integration, numerical solution of ordinary differential equations, application to numerical solution of physical and engineering problems.

Prerequisites: Math 217; CS 102G, 136G, or 265; SSM 317; and sophomore standing. Credit 3 units.

CS 467A Management Information Systems I

Introduction to the use of computing and information systems in organizations and to problems of analysis, design, implementation, and management of information systems. The role of technology and the organizational forms and processes needed to effectively apply technology in organizations is contrasted with the role of management and staff in directing and guiding information systems activities. The use of advanced systems development technologies such as application generators complements material on systems design, control, database methods, and systems organization.

Prerequisites: CS 102G, 136G, or M.B.A standing. Credit 3 units.

CS 468A Management Information Systems II

The design and implementation of computer-based information systems with emphasis on database and transaction aspects of large-scale information systems. The basics of database management, including data storage structures and large-file manipulations. Architecture of relevant database management systems. Database administration; data administration. A familiarization with COBOL is used to introduce information systems, implementation strategies, and transaction processing. Fourth-generation transaction processing systems are used to illustrate current directions in large corporate computer organizations. Data analysis; data models, database design, transaction systems design; design and implementation strategies.

Prerequisite: CS 241. Credit 3 units.

CS 493-494 Senior Project

Implementation of a substantive project on an individual basis, involving one or more major areas in computer science. Problems pursued under this framework may be predominantly analytical, involving exploration and extension of theoretical structures, or may pivot around the design/development of solutions for particular applications drawn from areas throughout the University and/or community. In either case, project serves as a focal point for crystallizing the concepts, techniques, and methodologies encountered throughout the curriculum. Students intending to take CS 493-494 must submit a project proposal for approval by the Department during the spring semester of the junior year.

Prerequisite: senior standing. Credit 3 units a semester.

CS 499 Undergraduate Honors Thesis

Working closely with a faculty member, the student investigates an original idea (algorithm, model technique, etc.), including a study of its possible implications, its potential application, and its relationship to previous related work reported in the literature. Contributions and results from this investigation are synthesized and compiled into a publication-quality research paper presenting the new idea.

Prerequisites: a strong academic record and permission of instructor. Credit 3 units.

CS 500 Independent Study

CS 501S Advanced User Interface

An introduction to various technologies for human-computer interaction through visual, haptic, and audio channels. User interface management systems for GUI (graphic user interface) and PUI (pen user interface). Object-oriented design and implementation of UI application framework. Adaptable user interfaces. An overview of event-oriented end-user programming for user definable user interfaces. First hand design experience through individualized projects.

Prerequisite: permission of instructor. Credit 3 units.

CS 505 Introduction to Computing Tools for Research

Introduces the use of computer and network tools in support of individual and collaborative graduate studies. Topics covered in lectures and labs: structure of computing systems, electronic mail, World-Wide Web, text editing, spreadsheets, symbolic mathematics, statistical analysis, simulation, package libraries, scripting languages, and document processing.

Prerequsities: none. Credit 3 units. No credit toward CS graduate degree.

CS 506T Introduction to Computational Geometry

This course provides an introduction to the key concepts, problems, and methods of Computational Geometry. The fundamental geometric structures including Convex Hull, Voronoi Diagram, Delaunay Triangulation and Arrangement are covered. The elements of geometric searching are introduced through range searching and the point location problem. Geometric data structures such as Kd-Trees, segment trees, along with some of their applications are presented. Other topics may include polygon triangulation, geometric duality, shortest paths, ray tracing, and matrix searching.

Prerequisite: CS 241. Credit 3 units.

CS 507T Introduction to Formal Languages and Automata

An introduction to the mathematical theory of languages and grammars. Topics include deterministic and nondeterministic finite state machines, push-down automata, and Turing machines; regular, context-free, context-sensitive and recursive languages; closure properties of languages; the concepts of computability and undecidability.

Prerequisite: CS 201. Credit 3 units.

CS 510A Artificial Intelligence Concepts

An introduction to the field of artificial intelligence and the basic computational tools utilized. Fundamental issues and concepts along with historical and current trends in the field. Skills in programming languages and methodologies (e.g., logic, lisp, and prolog) that support work in artificial intelligence are developed. Topical surveys of knowledge engineering, cognitive science, and other advanced topics in artificial intelligence complete the course.

Prerequisites: Experience with high level programming language, mathematical maturity, and permission of instructor. Undergraduate credit toward general distribution, but not toward CS requirements. No credit toward CS graduate degree. Credit 3 units.

CS 511A -512A Artificial Intelligence I, II

A study of what is required to produce intelligent, human-like behavior in a computer system. Topics include search algorithms, logical reasoning, knowledge representation, strategy selection and the use of heuristic knowledge. These basic methods are used to accomplish fundamental tasks performed intelligently by humans such as problem solving, game playing, natural language understanding, vision, planning, and learning. A variety of programming languages and paradigms are discussed and illustrated. Examples include rule-based programming, functional programming, logic programming, and object-oriented programming.

Prerequisite: CS 510A or CS 455. CS 511A is prerequisite for 512A. Credit 3 units.

CS 513A Applied Knowledge Engineering

Application of artificial intelligence techniques in a significant prototype system. Techniques of knowledge acquisition, knowledge codification, and the general function of tools and shells in enhancing the work of knowledge engineering are discussed. Practical issues of knowledge representation and of building expert systems using various commercially available and other tools and shells are addressed. System prototyping methodologies and delivery vehicles are also presented. This course requires a major student project for completion.

Prerequisites: CS 511A. Credit 3 units.

CS 514 Fundamentals of Computer Science

This course, intended for new graduate students without a computer science background, covers the core components seen in a computer science undergraduate curriculum on which our graduate level courses rely. Topics include fundamental algorithms, data structures, proof techniques, computational models, machine organization, and software design and implementation. No credit toward CS graduate degree.

Prerequisite: graduate standing. Some programming experience and mathematical sophistication highly desirable. Credit 3 units.

CS 515A Natural Language Processing

Study of techniques for computer processing of natural language. Emphasis will be placed on syntactic processing, semantic interpretation, and the study of discourse structure. Linguistic models and formalisms relevant to this task will be discussed. Additional topics will be selected from mechanical translation, natural language queries to a database, response generation, question-answering systems, story understanding, representation, and connectionist natural language processing. Students are expected to prepare and present research papers chosen from the literature.

Prerequisite: CS 511A. Credit 3 units.

CS 516A Multiagent Systems

Multiagent systems research, a subfield of artificial intelligence, studies the interactions of computational agents. These agents can represent real world parties, and they can have different preference structures. A key research goal is to design open distributed systems in a principled way that leads to globally desirable outcomes even though every participating agent only considers its own good and may act insincerely. The course covers relevant results in AI, game theory, market mechanisms, voting, auctions, coalition formation, and contracting. Effects of different computational limitations of the agents are discussed. Software tools for multiagent systems are presented. The course is targeted to graduate students and senior-level undergraduates. Non-AI students are also highly welcome. Application examples are presented in networks, operating systems, manufacturing, and logistics. Evaluation is based on presentations, written and programming assignments, and a final project of each student's choice.

CS 517T Mathematics of Algorithm Analysis

Mathematical tools and techniques used in analyzing algorithms and data structures. Topics covered include general combinatorics, generating functions, recurrence relations, rook polynomials, and convergence of sequences. Concepts developed include Catalan Numbers, Bernoulli Numbers, and Stirling Numbers of the First and Second kind. The course will emphasize the development of these tools and their application to the analysis of algorithms and data structures.

Prerequisite: Math 233 or equivalent. Credit 3 units.

CS 520A Intelligent Real-Time Systems

In many computer systems, it is not feasible (computationally) or desirable (economically) to compute the "optimal" answer. This course examines a variety of techniques that allow small quantities of computational commodities - such as time, memory, or information - to be traded for gains in the value of computed results. It covers both theory and applications in such areas as combinatorial optimization, multiagent systems, automated diagnosis and treatment, and information gathering. Topics include: models for representing computational limitations and tradeoffs, decision theory and rational choice, the value of information, the deliberative vs. reactive debate, principles of meta-reasoning, real-time search, memory-bounded search, utility-directed search, deliberation scheduling (control of reasoning), soft real-time, anytime algorithms, design-to-time algorithms, dynamic planning and execution, reinforcement learning, and evaluation of resource-bounded reasoning techniques.

Prerequisite: Basic knowledge of AI and probability theory, or permission of the instructor. Credit 3 units.

CS 521M Computer Systems Organization

(Same as EE 560) An exploration of the central issues in computer architecture: instruction set design, addressing and register set design, control unit design, microprogramming, memory hierarchies (cache and main memories, mass storage, virtual memory), pipelining, bus organization, RISC (Reduced Instruction Set Computers), and CISC (Complex Instruction Set Computers).

Prerequisites: CS 306, 260M. Credit 3 units.

CS 523S Operating Systems

Review of the standard operating system concepts: process and storage management, file systems, and input/output. Overview of distributed operating system. Interprocess communication models: message passing, remote procedure call, and shared memory. Process management and synchronization. Naming. Distributed and networked file system. Deadlock detection and avoidance. Case studies of distributed operating systems, such as MACH, Amoeba, Locus, and others.

Prerequisite: CS 422S. Credit 3 units.

CS 524S Advanced Topics in Networking

The course begins with a systematic study of techniques for improving network performance. The prevalence of video and audio will require the network to provide delay bounds and traffic isolation. We will study current approaches to fair queuing and traffic reservation. We will study current proposals for changing routing protocols to be scalable while supporting multicasting and mobility. We will also study current proposals for scalable reliable multicast and fault-tolerance techniques. If time permits, we will study security and accounting techniques that become important as the Internet becomes used for and funded by commercial applications.

Prerequisite: CS 423S or CS 533S. Credit 3 units.

CS 528A Introduction to Robotics

The programming and control of robot manipulators and robot manufacturing systems. Introduction to system organizations, kinematic models, mathematics of world models. Sensors and sensor interactions. Programming techniques, with examples from current robot system languages. Model based and task oriented specification of programs. Laboratory work with real and simulated robot systems.

Prerequisites: CS 306 and CS 455, or permission of instructor. Credit 3 units.

CS 529 Readings in Computer Science

This is a reading course designed to expose students to computer science literature and prepare them for graduate research in the Department. The course is organized around a set of reading lists dealing with research topics of current interest to the computer science faculty; these include parallel algorithms, software engineering image processing, computer-aided instruction, logic simulation, program verification, analysis of algorithms, database normalization, distributed computing, compiler design, VLSI circuit complexity. Several lists are selected during each semester that the course is taught. Each student is responsible for all the papers on one of the lists and presents lectures on selected papers. Students must also write short critical reviews of papers on their reading lists and write a term paper, which may be either a survey or a research proposal.

Prerequisite: graduate standing. Credit 3 units.

CS 530A Information Systems and Database Design

A study of many different data models and database management systems that support these data models. The design theory for databases is developed and various tools are utilized to apply the theory to case studies. General query languages are studied and techniques for query optimization are investigated. Integrity and security requirements are studied in the context of concurrent operations on a database, where the database may be distributed over one or more locations. The unique requirements for engineering design databases, image databases, and long transaction systems are analyzed.

Prerequisite: CS 455. Credit 3 units.

CS 531S The Theory of Compiling and Language Translation

Algorithms and intermediate representations for automatic program analysis are examined, with an emphasis on practical methods and efficient engineering of program optimization and transformations. The course includes a thorough treatment of monotone data flow frameworks: a mathematical model in which most optimization problems can be specified and solved. The course primarily covers optimizations that are applicable to any target architecture; however, optimizations specific to parallel, distributed, and storage-hierarchical systems are also discussed.

Prerequisite: CS 431S or 455. Credit 3 units.

CS 533S Design and Analysis of Protocols

The course is concerned with the design, specification, performance analysis, and implementation of protocols used in existing and emerging computer networks. Local and wide area network access protocols, such as Carrier Sense Multiple Access/Collision Detect (CSMA/CD), token access, X.25, and Q.93B. Internetworking with Internet Protocol (IP). Frame-relay and Switched Multimegabit Data Service (SMDS) as proposed internetworking solutions. Transport protocols such as User Datagram Protocol (UDP), Transmission Control Protocol (TCP), and TP4. Proposed high speed transport protocols such as eXpress Transport Protocol (XTP), Netblt, and Versatile Message Transport Protocol (VMTP). Host-network interfacing. Hardware and software protocol implementation models.

Prerequisites: CS/EE 260M. Credit 3 units.

CS 540T Formal Concepts in Computer Science

An introduction to the mathematical, logical, and linguistic concepts that underlie the formal aspects of computer science. An overview of naive set theory, propositional calculus and graph theory. Comparison of different formalizations of algorithms.

Prerequisite: permission of instructor. Credit 3 units.

CS 541T Network Algorithms and Programs

This course is concerned with the design and analysis of efficient algorithms, focusing principally on algorithms for combinatorial optimization problems. A key element in the course is the role of data structures in algorithm design and the use of amortized complexity analysis to determine how data structures affect performance. The course is organized around a set of core problems and algorithms, including the classical network optimization algorithms, as well as newer and more efficient algorithms. This core is supplemented by algorithms selected from the recent technical literature.

Prerequisite: CS 241. Credit 3 units.

CS 542T Analysis of Algorithms and Computational Complexity

Introduction to computational complexity, emphasizing the theory of NP-completeness, Cook's theorem, polynomial time reducibility, approximation algorithms, PSPACE and the polynomial time hierarchy.

Prerequisite: CS 541T. Credit 3 units.

CS 545S Modular Programming

Modular programming and object-oriented programming in C++, Modula-2, Smalltalk and Ada: Packages, modules, tasking, exception handling, messages, classes, inheritance, and generic objects.

Prerequisites: CS455 and CS 456. Credit 3 units.

CS 549A Neural Networks I: Foundations

Introduction to neural computation. Fundamental concepts behind various models of neural networks. Back-Propagation, Hopfield Nets, and Boltzmann machines models will be covered in detail. We will study neural networks as intelligent digital systems with fine-grained parallelism. Potentials and limitations of neural networks will be reviewed.

Prerequisites: mathematical maturity; CS 510A or permission of instructor. Credit 3 units.

CS 550A Neural Networks II: Applications

A continuation of the foundations course, this course examines current neural network research in several areas, for example, memory, pattern recognition, reading, speech, and language. Selected current papers are reviewed and tools for conducting neural network experiments are presented and discussed. Issues of parallel versus sequential processing, symbolic versus subsymbolic systems, and distributed versus local representation are highlighted and discussed.

Prerequisites: CS 549A, CS 510A or permission of instructor. Credit 3 units.

CS 552A Advanced Computer Graphics

A survey of the current state of the art in computer graphics. The emphasis will be on techniques used in the generation and display of raster images. The fundamentals of raster graphics will be discussed, including algorithms for scan-line generation, hidden line and surface removal, shading and texturing, and antialiasing. Advanced topics include: image synthesis (the generation of graphical images with a realistic appearance), real-time image generation, the development of new architectures and implementations for graphics engines, and the use of human factors analysis in designing graphical interfaces.

Prerequisites: CS 201, 453A, 455. Credit 3 units.

CS 554A Digital Image Processing

An introduction to the use of computers in the processing of digital images. Topics to be discussed include: acquisition of digital images, hardware and software for the display of digital images, the role of visual psychophysics in image processing, transform analysis and filtering, image restoration and reconstruction, and pattern recognition. Frequent laboratory exercises will be used to implement processing algorithms and build intuition in evaluating image quality.

Prerequisites: CS 241 and SSM 317. Credit 3 units.

CS 555T Programming Language Theory

A formal treatment of programming languages-mathematical models and practical implications. Formal definition of programming languages: axiomatic, operational and denotational semantic models. Models of concurrency and communication. Logical verification of sequential and parallel programs. Proving properties of recursive programs: fixpoint theory. Program schemata.

Prerequisite: CS 455 Credit 3 units.

CS 556M Principles of Digital System Interconnections

(Same as EE 556) Characterization of computer links and networks used for inter- and intra-digital system communication. Development of functional, logical, and electrical parameters useful in both application and design tasks. Generation of link models. Example systems D including the PDP-11 Unibus, SUE bus, CAMAC Highway, Macro-modules, Synchronous Data Link Control, IEEE Standard Bus, and the ARPA net D will be employed for purposes of parameter extraction, system comparison, and performance evaluation.

Prerequisites: CS 136G or CS 102, CS 260M and an elementary knowledge of pulse excitation transmission line theory. Credit 3 units.

CS 557M Computer Systems Analysis

(Same as EE 557A) Introduction to the basic tools of computer and communications systems analysis and evaluation. Deterministic and stochastic modeling concepts are presented. Queueing theory and discrete event simulation methods are studied with application to a variety of examples drawn from the computer and communications performance evaluation literature. Topics of current interest such as computer input/output models, mass memory, bus models, and communications network models are discussed. A modeling project is typically required.

Prerequisites: CS 102G or CS136G, and 260M or their respective equivalents. Credit 3 units.

CS 561T Graphs and Networks

Graphs, properties of graphs, and algorithms for extracting information about graphs are studied. Graphs studied include: simple graphs, directed and undirected graphs, tree, planar graphs, bipartite graphs, Euler and Hamiltonian graphs; networks and flow. Algorithms studied include: shortest path, minimal spanning trees, min cut/max flow, and depth first and breath first search. Concepts studied include: connectivity, edge and vertex colorings, chromatic number, dual graphs, isomorphisms, cut edges and vertices, and the use of graphs for solving problems.

Prerequisite: CS 201. Credit 3 units.

CS 563T Concurrent Algorithms: Shared Data

Concurrency presents programmers with unprecedented complexity further exacerbated by our limited ability to reason about concurrent computations. Yet, concurrent algorithms are central to the development of software executing on modern multiprocessors or across computer networks. This course reviews several important classes of concurrent algorithms and presents a formal method for specifying, reasoning about, verifying, deriving, and visualizing concurrent algorithms. The selected algorithms are judged to have made significant contributions to our understanding of concurrency. Rigorous treatment of the design and programming process is emphasized. A new feature of the course is the use of visualization tools to explore and present concurrent programs. Students entering this course must be familiar with predicate calculus and sequential algorithms. Upon completion of this course students will be able to reason completely formally about small concurrent programs and to apply systematically and correctly their formal skills to larger problems.

Prerequisite: CS 455. Credit 3 units.

CS 564T Concurrent Algorithms: Message Passing

Distributed algorithms are the protocols by which computers in a distributed system cooperate towards the solution of a problem. Such algorithms must cope with unpredictable communication delays and failures of network components. The first half of the course will cover the theory of message passing distributed algorithms. We will cover proof techniques, key concepts, useful building blocks, and impossibility results. The second half of the course will use this conceptual foundation to understand and design algorithms for real systems. Examples from real systems will be used as case studies. Upon completion of this course, students will have a deeper insight into both distributed algorithms and distributed systems; they should be able to translate this insight into designing real world solutions to problems in distributed computing.

Prerequisite: CS 455. Credit 3 units.

CS 565A Parallel Numerical Methods

A review of numerical methods on parallel computers. Synchronous parallel algorithms for the solution of linear algebraic equations, eigenvalue problems, and linear least-squares problems. Asynchronous iterative methods for the solution of nonlinear equations. Some applications of parallel computation in signal processing and other areas of engineering.

Prerequisites: CS 465A or permission of instructor. Credit 3 units.

CS 566M Systems Simulation: Continuous and Discrete Systems

(Same as EE 566) Computer Modeling and simulation of continuous and discrete event systems. Topics include the architecture of sequential and parallel simulators, Monte Carlo methods and solving queueing and discrete event systems, analysis of simulation output, and numerical integration techniques for solving differential equations.

Prerequisites: SSM 326; FORTRAN, C, or equivalent. Credit 3 units.

CS 567T Queueing Systems and Discrete Stochastic Processes

(Same as EE 536 and SSM 576) This course corresponds to a comprehensive, self-contained introduction to discrete stochastic processes. A brief coverage is first given on Markov chain, Markov process, and Poisson process. Various single-server queueing systems are investigated with their waiting time, occupancy, and other performance characteristics fully investigated. Multi-server queueing systems in the form of networks are addressed and their behaviors in product forms and in non product forms are studied. Some approximation and equivalence techniques are introduced such as Norton Theorem, reversibility, and truncation method. Applications to communication, manufacturing and computer systems are shown. Depending on the instructor, students in this class may be required to do a project.

Prerequisites: SSM 326. Credit 3 units.

CS 576S Distributed System Design: Models and Languages

The goal of the course is to familiarize students with basic concepts, associated models, and current trends in distributed computing. The design of concurrent and distributed systems is an area that is still in its formative stage. A multitude of models, languages, and methodologies have been put forth by both researchers and practitioners but no dominant approach has emerged so far. The course starts with a review of a broad range of models of concurrent computation and communication including: shared variables, data flow, object-oriented systems, indeterminate applicative systems, models using synchronous message exchanges, and shared dataspace. The objective of the survey is to identify fundamental issues and alternate treatments of these issues both from the theoretical and practical perspective. The second part of the course focuses on specialized areas of growing import to the field. They include well-established ones such as real-time processing and security as well as newly emerging concerns such as mobile computing and multimedia.

Prerequisite: CS 455. Credit 3 units.

CS 577M - 578M Design and Analysis of Switching Systems I, II

(Same as EE 577-578M) Switching systems are central components in large communication systems. This course is concerned with the design of practical switching systems and analysis of their performance and complexity. CS 577M focuses on Asynchronous Transfer Mode (ATM) switching systems, surveying a variety of architectural alternatives and comparing them on the basis of performance and complexity. It also covers engineering considerations in classical space division and time division switching systems. CS 578M concentrates on analytical methods for switching systems for both point-to-point and multipoint switching analysis of blocking and queueing in switching systems and congestion control issues in ATM networks.

Prerequisites: CS 241 and 260M. CS 577M is prerequisite for CS 578M. Credit 3 units.

CS 579M Parallel Architectures and Algorithms

(Same as EE 579) A number of contemporary parallel computer architectures are reviewed and compared. The problems of process synchronization and load balancing in parallel systems are studied. Several selected applications problems are investigated and parallel algorithms for their solution are considered. These will include solution of sets of algebraic and ordinary differential equations, selected types of partial differential equations, problems in linear algebra, Monte Carlo problems and problems in discrete event simulation. Some parallel algorithms will be implemented using a real parallel programming environment.

Prerequisite: graduate standing. Credit 3 units.

CS 580S Special Topics in Tools for Parallel Programming

This course focuses on research issues in tool development and will emphasize the role of visualization in the development and use of these tools. Topics will include overviews of message passing and shared variable programming paradigms, commercial and research tools and issues in the development of tools for design and specification, performance evaluation, debugging, and program understanding.

Prequisite: CS 579M. Credit 3 units.

CS 582T Computational Learning Theory

Building machines that learn from experience is an important research goal of artificial intelligence. The area of computational learning theory strives to define formal mathematical models of machine learning that enable rigorous analysis of the performance and efficiency of learning algorithms. In this course we study the most prominent learning models used in computational learning theory with a focus on the PAC model. Within these models we will study the commonly used algorithm design and analysis techniques. The primary goal of the field is to determine what is efficiently learnable. For some problems we present learning algorithms that are efficient in their use of both time and data. Contrasting these positive results, for some problems we present hardness results indicating that no efficient learning algorithm exists. We also explore how the difficulty of the learning task changes as the learner is provided with the ability to perform experimentation. We also look at the situation in which the data are noisy.

Prerequisites: CS 241, and familiarity with NP-completeness reductions. Credit 3 units.

CS 585S Software Project Management

An introduction to the issues and basic methods used in managing software development projects. The course will include factors affecting software projects, life-cycle models, project scheduling, size and staffing, progress tracking, software metrics, managing people, and crisis management. The course will include lectures, hands-on training in selected project managment tools, and case studies. In addition, each student will plan and manage a simulated software project. The course is designed to familiarize software engineers and computer scientists to the issues and problems involved in managing software projects.

Prerequisite: CS 456 or permission of instructor. Credit 3 units.

CS 592A Digital Representation of Signals

(Same as EE 592) This course addresses the representation of real-world analog signals in digital forms, describes network interfaces for the digital transmission of such signals, and is intended to give students a broad introduction to the subject followed by practical illustration of the basic concepts. Analog signals of differing characteristics, such as the electrocardiogram, voice, audio, images, and video are considered, and appropriate digitizing and coding techniques for network transmission are described. Both lossless and lossy coding for data compression are covered as is the reconstruction of analog signals that approximate the original signal. Existing standards for data compression and transmission will be studied, with emphasis on the basic concepts leading to such standards.

Prerequisite: graduate standing. Credit 3 units.

CS 593A Signalling and Control in Communication Networks

(Same as EE 593) The operation of modern communications networks is highly dependent on sophisticated control mechanisms that direct the flow of information through the network and oversee the allocation of resources to meet the communication demands of end users. This course covers the structure and operation of modern signaling systems and addresses the major design trade-offs that center on the competing demands of performance and service flexibility. Specific topics covered include protocols and algorithms for connection establishment and transformation, routing algorithms, overload and failure recovery and networking dimensioning. Case studies provide concrete examples and reveal the key design issues.

Prerequisites: graduate standing and permission of instructor. Credit 3 units.

CS 595 Networking and Communications Design Project I

This course is for students who are enrolled in the networking and communications masters program. Students in this program are expected to complete an individual or small group (up to three students) design project under the supervision of a faculty sponsor. Students undertaking a project are required to first prepare a short project proposal (3-5 pages) and give a short presentation (30 minutes) to which all students and faculty in the networking and communications program are invited. In the design phase of the project, students carry out a detailed design, identify key implementation decisions and develop a plan for proceeding through the implementation phase, including identification of major steps and assignment of responsibilities to team members. The design phase ends in a design report and a presentation on the design and implementation plan. In the final phase of the project, students implement their design, demonstrate the resulting system, evaluate it, document their results in a final report (20-30 pages) and give a final presentation. Students should plan to complete the first phase at least five months before their intended graduate date and the second phase at least two months before their intended graduation. Students can register for CS/EE 596 only after completing the first phase and having a faculty sponsor agree to supervise their project.

Prerequiste: permission of the program director. Credit 3 units.

CS 596 Networking and Communications Design Project II

This course is for students who have completed the first phase of a design project in CS 595 and have a faculty sponsor who has agreed to supervise their project. In the final phase of the project, students implement their design, demonstrate the resulting system, evaluate it, document their results in a final report (20-30 pages) and give a final presentation. Students should plan to complete this phase at least two months before their intended graduation.

Prerequisites: CS 595 and permission of the program director. Credit 3 units

CS 598 Master's Project

Students electing the project option for their master's degree perform their project work under this course.

Prerequisite: permission of adviser. Credit to be arranged.

CS 599 Master's Thesis Research

Prerequisite: permission of adviser. Credit to be arranged.

CS 600 Independent Study

CS 670 Research Seminar on Algorithms and Computational Complexity

This seminar is intended for students interested in research in analysis of algorithms and computational complexity. Of particular interest are the design and analysis of efficient algorithms to effectively solve NP-complete problems. Examples of such problems are the matrix bandwidth minimization problem, the graph coloring problem, the shortest common matching string problem, and the Steiner tree problem.

CS 672 Research Seminar on Visual Programming

This seminar investigates the possibilities and limitations of visual icon-driven programming languages. Specific topics are (1) formal specification of two-dimensional languages, their grammar, parsing algorithms, and semantics, (2) visual representation of programming concepts such as recursion, concurrency, iteration, abstract data types, and exceptions, (3) declarative programming in visual programming languages, i.e., visualization of functional programming (Picture LISP) and logic programming (Picture Prolog).

CS 673 Research Seminar on Distributed System Design

The theme of this seminar is the ability to factor into the modelling analysis and verification of distributed systems, the impact of the operating system and hardware organization on the distributed application software. The focus is on the formal treatment of methodological issues relating to distributed systems design.

CS 674 Research Seminar on Artificial Intelligence

This seminar is intended for students interested in conducting research in the field of artificial intelligence. Each semester is devoted to an in-depth study of one topic, primarily by detailed reading of current research papers.

CS 678 Research Seminar on Programming Languages

In this seminar we will examine the design, use, and support of the Java programming language, both as a vehicle for delivering applications over networks and as a stand-alone programming language. While covering the basic aspects of the Java programming language, and including labs that exercise such knowledge, the class will emphasize Java in the evolution of object-oriented languages. Support issues such as separate compilation, bytecode verification, and run-time support of objects will be discussed.

CS 679 Research Seminar on Multimedia Networking

(formerly CS 675 High Speed Communications)

In this research seminar we study some of the techniques that are used in the performance evaluation of telecommunication networks. The objectives of this research seminar are achieved through selective readings from the literature of stochastic processes and broadband telecommunication networks. The participants learn fundamental concepts from the theory of Markov processes, Markov chains, renewal theory and Markov renewal theory. The above topics and related knowledge are utilized in the study of basic papers from the literature of broadband networks.