CS and Related Undergraduate Courses Revised August 2016The courses listed below are relevant for computer science majors as required courses or constrained electives. See the Undergraduate Catalog for information about additional SCS courses including available electives.COMPUTER SCIENCE 15-050 Study Abroad Fall and Spring Students who are interested in studying abroad should first contact the Office of International Education. More information on Study Abroad is available on OIE's Study Abroad page and at the CS Undergraduate Office. 15-075 Computer Science Co-Op Fall and Spring This course is meant for CS undergraduate students with a full-time internship that encompasses a summer and a contiguous semester, either Spring-Summer or Summer-Fall who wish to have this recorded on their academic transcript. Units posted for this course do not count toward any requirement for the CS undergraduate degree including free elective units. This course is not available to international students; consult with the Office for International Education for more information. 15-090 Computer Science Practicum Summer: 3 units This course is for Computer Science students who wish to have an internship experience as part of their curriculum. Students are required to write a one-page summary statement prior to registration that explains how their internship connects with their CS curriculum, specifically on how it uses material they have learned as well as prepares them for future courses. Near the end of the internship, students will be required to submit a reflection paper that describes the work they did in more detail, including lessons learned about the work experience and how they utilized their CS education to work effectively. International students should consult with the Office of International Education for appropriate paperwork and additional requirements before registration. Units earned count toward the total required units necessary for degree completion; students should speak with an academic advisor for details. This course may be taken at most 3 times for a total of 9 units maximum. Students normally register for this course for use during the summer semester. 15-112 Fundamentals of Programming and Computer Science Fall and Spring: 12 units A technical introduction to the fundamentals of programming with an emphasis on producing clear, robust, and reasonably efficient code using top-down design, informal analysis, and effective testing and debugging. Starting from first principles, we will cover a large subset of the Python programming language, including its standard libraries and programming paradigms. We will also target numerous deployment scenarios, including standalone programs, shell scripts, and web-based applications. This course assumes no prior programming experience. Even so, it is a fast-paced and rigorous preparation for 15-122. Students seeking a more gentle introduction to computer science should consider first taking 15-110. NOTE: students must achieve a C or better in order to use this course to satisfy the pre-requisite for any subsequent Computer Science course. 15-122 Principles of Imperative Computation Fall and Spring: 10 units For students with a basic understanding of programming (variables, expressions, loops, arrays, functions). Teaches imperative programming and methods for ensuring the correctness of programs. Students will learn the process and concepts needed to go from high-level descriptions of algorithms to correct imperative implementations, with specific application to basic data structures and algorithms. Much of the course will be conducted in a subset of C amenable to verification, with a transition to full C near the end. This course prepares students for 15-213 and 15-210. NOTE: students must achieve a C or better in order to use this course to satisfy the prerequisite for any subsequent Computer Science course. Prerequisite: 15-112. Corequisite: 21-127 or 15-151. 15-128 Freshman Immigration Course (Pittsburgh) Fall: 1 unit The Freshman Immigration Course is taken by first-semester Computer Science majors on the Pittsburgh campus. The course is designed to acquaint incoming majors with computer science at CMU. Talks range from historical perspectives in the field to descriptions of the cutting edge research being conducted in the School of Computer Science. Enrollment is limited to SCS Freshmen in Pittsburgh ONLY. 15-129 Freshman Immigration Course II (Doha, Qatar) Fall: 3 units This course is ONLY offered at Carnegie Mellon in Qatar. Students and instructors will solve different problems each week by searching the Web and other likely places for answers. The problems will be submitted by other faculty who will grade the quality of the answers. Students will learn strategies and techniques for finding information on the Web more efficiently; learn when to start with a search engine, a subject-oriented directory, or other tools; explore and practice using advanced search syntax for major search engines; experience specialized search engines for images, sound, multimedia, newsgroups, and discussion lists as well as subject-specific search engines; discover valuable resources to help keep you up-to-date in this fast-changing environment. 15-131 Great Practical Ideas in Computer Science (Pittsburgh) Fall: 2 units THIS COURSE IS OPEN TO CS FRESHMAN IN PITTSBURGH ONLY. Throughout your education as a Computer Scientist at Carnegie Mellon, you will take courses on programming, theoretical ideas, logic, systems, etc. As you progress, you will be expected to pick up the so-called "tools of the trade." This course is intended to help you learn what you need to know in a friendly, low-stress, high-support way. We will discuss UNIX, LaTeX, debugging and many other essential tools. Laptop required. (Laptops will be available for those without their own laptops.) 15-150 Principles of Functional Programming Fall and Spring: 10 units An introduction to programming based on a "functional" model of computation. The functional model is a natural generalization of algebra in which programs are formulas that describe the output of a computation in terms of its inputs---that is, as a function. But instead of being confined to real- or complex-valued functions, the functional model extends the algebraic view to a very rich class of data types, including not only aggregates built up from other types, but also functions themselves as values. This course is an introduction to programming that is focused on the central concepts of function and type. One major theme is the interplay between inductive types, which are built up incrementally; recursive functions, which compute over inductive types by decomposition; and proof by structural induction, which is used to prove the correctness and time complexity of a recursive function. Another major theme is the role of types in structuring large programs into separate modules, and the integration of imperative programming through the introduction of data types whose values may be altered during computation. NOTE: students must achieve a C or better in order to use this course to satisfy the pre-requisite for any subsequent Computer Science course. Prerequisites: (21-127 or 15-151) and (15-112). 15-151 Mathematical Foundations of Computer Science Fall: 10 units This course is offered to incoming Computer Science freshmen and focuses on the fundamental concepts in Mathematics that are of particular interest to Computer Science such as logic, sets,induction, functions, and combinatorics. These topics are used as a context in which students learn to formalize arguments using the methods of mathematical proof. This course uses experimentation and collaboration as ways to gain better understanding of the material. Open to CS freshmen only (Fall 2012 and Fall 2013). NOTE: students must achieve a C or better in order to use this course to satisfy the pre-requisite for any subsequent Computer Science course. 15-210 Parallel and Sequential Data Structures and Algorithms Fall and Spring: 12 units Teaches students about how to design, analyze, and program algorithms and data structures. The course emphasizes parallel algorithms and analysis, and how sequential algorithms can be considered a special case. The course goes into more theoretical content on algorithm analysis than 15-122 and 15-150 while still including a significant programming component and covering a variety of practical applications such as problems in data analysis, graphics, text processing, and the computational sciences. NOTE: students must achieve a C or better in order to use this course to satisfy the pre-requisite for any subsequent Computer Science course. Prerequisite: 15-122 and 15-150. 15-213 Introduction to Computer Systems Fall and Spring: 12 units This course provides a programmer's view of how computer systems execute programs, store information, and communicate. It enables students to become more effective programmers, especially in dealing with issues of performance, portability and robustness. It also serves as a foundation for courses on compilers, networks, operating systems, and computer architecture, where a deeper understanding of systems-level issues is required. Topics covered include: machine-level code and its generation by optimizing compilers, performance evaluation and optimization, computer arithmetic, memory organization and management, networking technology and protocols, and supporting concurrent computation. NOTE: students must achieve a C or better in order to use this course to satisfy the pre-requisite for any subsequent Computer Science course. Prerequisite: 15-122. 15-214 Principles of Software Construction: Objects, Design, and Concurrency Fall and Spring: 12 units Software engineers today are less likely to design data structures and algorithms from scratch and more likely to build systems from library and framework components. In this course, students engage with concepts related to the construction of software systems at scale, building on their understanding of the basic building blocks of data structures, algorithms, program structures, and computer structures. The course covers technical topics in four areas: (1) concepts of design for complex systems, (2) object oriented programming, (3) static and dynamic analysis for programs, and (4) concurrent and distributed software. Student assignments involve engagement with complex software such as distributed massively multi-player game systems and frameworks for graphical user interaction. Prerequisites: (15-121 or 15-122) and (21-127 or 15-151). 15-221 Technical Communications for Computer Scientists (Doha, Qatar) Spring: 9 units The course is designed for sophomore computer science majors to improve their abilities in practical, professional communications (both written and oral). It aims to help students compose clear, concise technical writings and oral presentations for multi-level audiences. Assignments include technical definitions, descriptions, instructions, process explanations, abstracts, memos, and research reports. Assignments may incorporate recent computer science research at Carnegie Mellon, projects in related technical courses, and professional case studies. Sophomores will likely find the course more useful if they have either had an internship or faculty-supervised research, including SURG projects prior to enrollment. Prerequisite: 76-101. 15-251 Great Theoretical Ideas in Computer Science Fall and Spring: 12 units This course is about how to use theoretical ideas to formulate and solve problems in computer science. It integrates mathematical material with general problem solving techniques and computer science applications. Examples are drawn from algorithms, complexity theory, game theory, probability theory, graph theory, automata theory, algebra, cryptography, and combinatorics. Assignments involve both mathematical proofs and programming. NOTE: students must achieve a C or better in order to use this course to satisfy the pre-requisite for any subsequent Computer Science course. Prerequisites: (15-112) and (21-127 or 15-151). 15-300 Research and Innovation in Computer Science Fall: 9 units This Fall course is the first part of a two-course sequence that is designed to help prepare students to invent the future state-of-the-art in the field of computer science. Course topics will include the following: an overview of important things to know about how research and innovation works in the field of computer science; a survey of the current cutting- edge of computer science research, both here at Carnegie Mellon and elsewhere; critical thinking skills when reading research publications that disagree with each other; strategies for coping with open-ended problems; and technical communication skills for computer scientists. Students will also match up with a faculty mentor for a potential Technology Innovation Project (to be performed in the Spring), put together a detailed plan of attack for that project, and start to get up to speed (including background reading, etc.). This course can be used to satisfy the Technical Communications requirement for the CS major. Prerequisites: 15-210. 15-213. 15-251 and 76-101. 15-312 Foundations of Programming Languages Spring: 12 units This course discusses in depth many of the concepts underlying the design, definition, implementation, and use of modern programming languages. Formal approaches to defining the syntax and semantics are used to describe the fundamental concepts underlying programming languages. A variety of programming paradigms are covered such as imperative, functional, logic, and concurrent programming. In addition to the formal studies, experience with programming in the languages is used to illustrate how different design goals can lead to radically different languages and models of computation. Prerequisites: 15-210 and 15-251. 15-313 Foundations of Software Engineering Fall: 12 units Students gain exposure to the fundamentals of modern software engineering. This includes both core CS technical knowledge and the means by which this knowledge can be applied in the practical engineering of complex software. Topics related to software artifacts include design models, patterns, coding, static and dynamic analysis, testing and inspection, measurement, and software architecture and frameworks. Topics related to software process include modeling, requirements engineering, process models and evaluation, team development, and supply chain issues including outsourcing and open source. This course has a strong technical focus, and will include both written and programming assignments. Students will get experience with modern software engineering tools. Prerequisite: 15-214. 15-317 Constructive Logic Fall: 9 units This multidisciplinary junior-level course is designed to provide a thorough introduction to modern constructive logic, its roots in philosophy, its numerous applications in computer science, and its mathematical properties. Some of the topics to be covered are intuitionistic logic, inductive definitions, functional programming, type theory, realizability, connections between classical and constructive logic, decidable classes. Prerequisite: 15-150. 15-322 Introduction to Computer Music Fall: 9 units Computers are used to synthesize sound, process signals, and compose music. Personal computers have replaced studios full of sound recording and processing equipment, completing a revolution that began with recording and electronics. In this course, students will learn the fundamentals of digital audio, basic sound synthesis algorithms, and techniques for digital audio effects and processing. Students will apply their knowledge in programming assignments using a very high-level programming language for sound synthesis and composition. In a final project, students will demonstrate their mastery of tools and techniques through music composition or by the implementation of a significant sound-processing technique. Prerequisite: 15-112. 15-323 Computer Music Systems and Information Processing Spring: 9 units This course presents concepts and techniques for representing and manipulating discrete music information, both in real time and off line. Representations of music as explicitly timed event sequences will be introduced, and students will learn how to build efficient run-time systems for event scheduling, tempo control, and interactive processing. The MIDI protocol is used to capture real-time performance information and to generate sound. The course will also cover non-real-time processing of music data, including Markov models, style recognition, computer accompaniment, query-by-humming, and algorithmic composition. This course is independent of, and complementary to 15-322, Introduction to Computer Music, which focuses on sound synthesis and signal processing. Prerequisite: 15-122. 15-354 Computational Discrete Mathematics Fall: 12 units This course is about the computational aspects of some of the standard concepts of discrete mathematics (relations, functions, logic, graphs, algebra, automata), with emphasis on efficient algorithms. We begin with a brief introduction to computability and computational complexity. Other topics include: iteration, orbits and fixed points, order and equivalence relations, propositional logic and satisfiability testing, finite fields and shift register sequences, finite state machines, and cellular automata. Computational support for some of the material is available in the form of a Mathematica package. Prerequisite: 15-251 or 21-228. 15-355 Modern Computer Algebra Spring: 9 units The goal of this course is to investigate the relationship between algebra and computation. The course is designed to expose students to algorithms used for symbolic computation, as well as to the concepts from modern algebra which are applied to the development of these algorithms. This course provides a hands-on introduction to many of the most important ideas used in symbolic mathematical computation, which involves solving system of polynomial equations (via Groebner bases), analytic integration, and solving linear difference equations. Throughout the course the computer algebra system Mathematica will be used for computation. Prerequisite: 15-251. 15-359 Probability and Computing Once every three semesters: 12 units Probability theory has become indispensable in computer science. In areas such as artificial intelligence and computer science theory, probabilistic methods and ideas based on randomization are central. In other areas such as networks and systems, probability is becoming an increasingly useful framework for handling uncertainty and modeling the patterns of data that occur in complex systems. This course gives an introduction to probability as it is used in computer science theory and practice, drawing on applications and current research developments as motivation and context. Topics include combinatorial probability and random graphs, heavy tail distributions, concentration inequalities, various randomized algorithms, sampling random variables and computer simulation, and Markov chains and their many applications, from Web search engines to models of network protocols. The course will assume familiarity with 3-D calculus and linear algebra. Prerequisite: 15-251 and 21-241 and 21-259. 15-381 Artificial Intelligence: Representation and Problem Solving Fall: 9 units This course is about the theory and practice of Artificial Intelligence. We will study modern techniques for computers to represent task-relevant information and make intelligent (i.e. satisficing or optimal) decisions towards the achievement of goals. The search and problem solving methods are applicable throughout a large range of industrial, civil, medical, financial, robotic, and information systems. We will investigate questions about AI systems such as: how to represent knowledge, how to effectively generate appropriate sequences of actions and how to search among alternatives to find optimal or near-optimal solutions. We will also explore how to deal with uncertainty in the world, how to learn from experience, and how to learn decision rules from data. We expect that by the end of the course students will have a thorough understanding of the algorithmic foundations of AI, how probability and AI are closely interrelated, and how automated agents learn. We also expect students to acquire a strong appreciation of the big-picture aspects of developing fully autonomous intelligent agents. Other lectures will introduce additional aspects of AI, including natural language processing, web-based search engines, industrial applications, autonomous robotics, and economic/game-theoretic decision making. Prerequisite: 15-122. 15-400 Research Practicum in Computer Science Spring: 12 units This Spring course is the second part of a two-course sequence that is designed to help prepare students to invent the future state-of-the-art in the field of computer science. Building directly upon 15-300 (the prerequisite for this course), students will conduct a semester-long independent research project, under the guidance of both the course staff and a faculty project mentor. The course does not meet for lecture or recitations. Instead, the students will spend their time working on their research projects, and will also meet with course staff on a bi-weekly basis to discuss their progress. Students will prepare a written report and a poster presentation at the end of the semester to describe what they have accomplished. Prerequisite: 15-300. 15-410 Operating System Design and Implementation Fall and Spring: 12 units Operating System Design and Implementation is a rigorous hands-on introduction to the principles and practice of operating systems. The core experience is writing a small Unix-inspired OS kernel, in C with some x86 assembly language, which runs on a PC hardware simulator (and on actual PC hardware if you wish). Work is done in two-person teams, and "team programming" skills (source control, modularity, documentation) are emphasized. The size and scope of the programming assignments typically result in students significantly developing their design, implementation, and debugging abilities. Core concepts include the process model, virtual memory, threads, synchronization, and deadlock; the course also surveys higher-level OS topics including file systems, interprocess communication, networking, and security. Students, especially graduate students, who have not satisfied the prerequisite at Carnegie Mellon are strongly cautioned - to enter the class you must be able to write a storage allocator in C, use a debugger, understand 2's-complement arithmetic, and translate between C and x86 assembly language. The instructor may require you to complete a skills assessment exercise before the first week of the semester in order to remain registered in the class. Auditing: this course is usually full, and we generally receive many more requests to audit than we can accept. If you wish to audit, please have your advisor contact us before the semester begins to discuss your educational goals. Prerequisite: 15-213. 15-411 Compiler Design Fall: 12 units This course covers the design and implementation of compiler and run-time systems for high-level languages, and examines the interaction between language design, compiler design, and run-time organization. Topics covered include syntactic and lexical analysis, handling of user-defined types and type-checking, context analysis, code generation and optimization, and memory management and run-time organization. Prerequisite: 15-213. 15-414 Bug Catching: Automated Program Verification and Testing Fall: 9 units Many CS and ECE students will be developing software and hardware that must be ultra reliable at some point in their careers. Logical errors in such designs can be costly, even life threatening. There have already been a number of well publicized errors like the Intel Pentium floating point error and the Arian 5 crash. In this course we will study tools for finding and preventing logical errors. Three types of tools will be studied: automated theorem proving, state exploration techniques like model checking and tools based on static program analysis. Although students will learn the theoretical basis for such tools, the emphasis will be on actually using them on real examples. Prerequisite: 15-122 and 15-251. 15-415 Database Applications Fall: 12 units This course covers the fundamental topics for Database Management Systems: Database System Architectural Principles (ACID properties; data abstraction; external, conceptual, and internal schemata; data independence; data definition and data manipulation languages), Data models (entity-relationship and relational data models; data structures, integrity constraints, and operations for each data model; relational query languages: SQL, algebra, calculus), Theory of database design (functional dependencies; normal forms; dependency preservation; information loss), Query Optimization (equivalence of expressions, algebraic manipulation; optimization of selections and joins), Storage Strategies (indices, B-trees, hashing), Query Processing (execution of sort, join, and aggregation operators), and Transaction Processing (recovery and concurrency control). Prerequisite: 15-210 or 15-213. 15-418 Parallel Computer Architecture and Programming Fall and Spring: 12 units The fundamental principles and engineering tradeoffs involved in designing modern parallel computers, as well as the programming techniques to effectively utilize these machines. Topics include naming shared data, synchronizing threads, and the latency and bandwidth associated with communication. Case studies on shared-memory, message-passing, data-parallel and dataflow machines will be used to illustrate these techniques and tradeoffs. Programming assignments will be performed on one or more commercial multiprocessors, and there will be a significant course project. Prerequisite: 15-213. 15-424 Foundations of Cyber-Physical Systems Spring: 12 units Cyber-physical systems (CPSs) combine cyber effects (computation and/or communication) with physical effects (motion or other physical processes). Designing algorithms to control CPSs, such as those in cars, aircraft and robots, is challenging due to their tight coupling with physical behavior. At the same time, it is vital that these algorithms be correct, since we rely on CPSs for safety-critical tasks like keeping aircraft from colliding. Students in this course will understand the core principles behind CPSs, develop models and controls, identify safety specifications and critical properties of CPSs, understand abstraction and system architectures, learn how to design by invariant, reason rigorously about CPS models, verify CPS models of appropriate scale, understand the semantics of a CPS model and develop an intuition for operational effects. Students will write hybrid programs (HPs), which capture relevant dynamical aspects of CPSs in a simple programming language with a simple semantics, allowing the programmer to refer to real-valued variables representing real quantities and specify their dynamics as part of the HP. Prerequisites: (15-122) and (21-122) and (15-251 or 21-241 or 18-202) 15-440 Distributed Systems Fall and Spring: 12 units The goals of this course are twofold: First, for students to gain an understanding of the principles and techniques behind the design of distributed systems, such as locking, concurrency, scheduling, and communication across the network. Second, for students to gain practical experience designing, implementing, and debugging real distributed systems. The major themes this course will teach include scarcity, scheduling, concurrency and concurrent programming, naming, abstraction and modularity, imperfect communication and other types of failure, protection from accidental and malicious harm, optimism, and the use of instrumentation and monitoring and debugging tools in problem solving. As the creation and management of software systems is a fundamental goal of any undergraduate systems course, students will design, implement, and debug large programming projects. As a consequence, competency in both the C and Java programming languages is required. Prerequisite: 15-213. 15-441 Computer Networks Fall: 12 units The emphasis in this course will be on the basic performance and engineering trade-offs in the design and implementation of computer networks. To make the issues more concrete, the class includes several multi-week projects requiring significant design and implementation. The goal is for students to learn not only what computer networks are and how they work today, but also why they are designed the way they are and how they are likely to evolve in the future. We will draw examples primarily from the Internet. Topics to be covered include: network architecture, routing, congestion/flow/error control, naming and addressing, peer-to-peer and the web, internetworking, and network security. Prerequisite: 15-213. 15-451 Algorithm Design and Analysis Fall and Spring: 12 units In this coruse, we study specific algorithms for a variety of problems, as well as general design and analysis techniques. Specific topics include searching, sorting, algorithms for graph problems, efficient data structures, lower bounds and NP-completeness. A variety of other topics may be covered at the discretion of the instructor. These include parallel algorithms, randomized algorithms, geometric algorithms, low level techniques for efficient programming, cryptography, and cryptographic protocols. Prerequisites: 15-210 and 15-251 and 21-241. 15-453 Formal Languages, Automata and Complexity Spring: 9 units An introduction to the fundamental ideas and models underlying computing: finite automata, regular sets, pushdown automata, context-free grammars, Turing machines, undecidability, and complexity theory. Prerequisite: 15-251 or 21-228. 15-455 Undergraduate Complexity Theory Fall: 9 units Complexity theory is the study of how much of a resource (such as time, space, parallelism, or randomness) is required to perform some of the computations that interest us the most. In a standard algorithms course, one concentrates on giving resource efficient methods to solve interesting problems. In this course, we concentrate on techniques that prove or suggest that there are no efficient methods to solve many important problems. We will develop the theory of various complexity classes, such as P, NP, co-NP, PH, #P, PSPACE, NC, AC, L, NL, UP, RP, BPP, IP, and PCP. We will study techniques to classify problems according to our available taxonomy. By developing a subtle pattern of reductions between classes we will suggest an (as yet unproven!) picture of how by using limited amounts of various resources, we limit our computational power. Prerequisite: 15-251. 15-456 Computational Geometry Spring (every other year): 9 units How do you sort points in space? What does it even mean? This course takes the ideas of a traditional algorithms course, sorting, searching, selecting, graphs, and optimization, and extends them to problems on geometric inputs. We will cover many classical geometric constructions and novel algorithmic methods. Some of the topics to be covered are convex hulls, Delaunay triangulations, graph drawing, point location, geometric medians, polytopes, configuration spaces, linear programming, and others. This course is a natural extension to 15-451, for those who want to learn about algorithmic problems in higher dimensions. Prerequisite: 15-451. 15-462 Computer Graphics Fall and Spring: 12 units This course provides a comprehensive introduction to computer graphics modeling, animation, and rendering. Topics covered include basic image processing, geometric transformations, geometric modeling of curves and surfaces, animation, 3-D viewing, visibility algorithms, shading, and ray tracing. Prerequisite: (21-259 and 15-213 and 21-240) or (21-259 and 15-213 and 21-241) or (18-202 and 18-213) 15-591 Independent Study in Computer Science Fall and Spring: 3-12 units Specially selected projects and readings in computer science under supervision of a faculty member in SCS. Application required. Poster presentation is generally required to present completed work. More information is available on the Undergraduate Research page. 15-599 Undergraduate Thesis Research Fall and Spring: 36 units total over 2 semesters (18 + 18) Formal research leading to an original result in computer science under the supervision of an SCS faculty member. Requires a written thesis and final presentation at the Meeting of the Minds campus symposium. Thesis prospectus is required and must be approved before student can start research. More information is available on the Undergraduate Research page.COMPUTATIONAL BIOLOGY 02-510 Computational Genomics Spring: 12 units Dramatic advances in experimental technology and computational analysis are fundamentally transforming the basic nature and goal of biological research. The emergence of new frontiers in biology, such as evolutionary genomics and systems biology is demanding new methodologies that can confront quantitative issues of substantial computational and mathematical sophistication. In this course we will discuss classical approaches and latest methodological advances in the context of the following biological problems: 1) Computational genomics, focusing on gene finding, motifs detection and sequence evolution.2) Analysis of high throughput biological data, such as gene expression data, focusing on issues ranging from data acquisition to pattern recognition and classification. 3) Molecular and regulatory evolution, focusing on phylogene tic inference and regulatory network evolution, and 4) Systems biology, concerning how to combine sequence, expression and other biological data sources to infer the structure and function of different systems in the cell. From the computational side this course focuses on modern machine learning methodologies for computational problems in molecular biology and genetics, including probabilistic modeling, inference and learning algorithms, pattern recognition, data integration, time series analysis, active learning, etc.HUMAN COMPUTER INTERACTION 05-391 Designing Human Centered Software Spring: 12 units Why are things so hard to use these days? Why doesn�t this thing I just bought work? Why is this web site so hard to use? These are frustrations that we have all faced from systems not designed with people in mind. The question this course will focus on is: how can we design human-centered systems that people find useful and usable? This course is an introduction to designing, prototyping, and evaluating user interfaces. If you take only one course in Human-Computer Interaction, this is the course for you. This class is open to all undergrads and grad students, with either technical or non-technical backgrounds. We will cover theory as well as practical application of ideas from Human-Computer Interaction. Course work includes lectures, class discussion, homework, class presentations, and group project.MACHINE LEARNING 10-401 Introduction to Machine Learning Fall and Spring: 12 units Machine learning is subfield of computer science with the goal of exploring, studying, and developing learning systems, methods, and algorithms that can improve their performance with learning from data. This course is designed to give undergraduate students a one-semester-long introduction to the main principles, algorithms, and applications of machine learning. Topics. The topics of this course will be in part parallel with those covered in the graduate machine learning courses (10-715, 10-701, 10-601), but with a greater emphasis on applications and case studies in machine learning. After completing the course, students will be able to: *select and apply an appropriate supervised learning algorithm for classification problems (e.g., naive Bayes, perceptron, support vector machine, logistic regression). *select and apply an appropriate supervised learning algorithm for regression problems (e.g., linear regression, ridge regression). *recognize different types of unsupervised learning problems, and select and apply appropriate algorithms (e.g., clustering, linear and nonlinear dimensionality reduction). *work with probabilities (Bayes rule, conditioning, expectations, independence), linear algebra (vector and matrix operations, eigenvectors, SVD), and calculus (gradients, Jacobians) to derive machine learning methods such as linear regression, naive Bayes, and principal components analysis. *understand machine learning principles such as model selection, overfitting, and underfitting, and techniques such as cross-validation and regularization. *implement machine learning algorithms such as logistic regression via stochastic gradient descent, linear regression (using a linear algebra toolbox), perceptron, or k-means clustering. *run appropriate supervised and unsupervised learning algorithms on real and synthetic data sets and interpret the results. Prerequisites: 15-122 and (15-151 or 21-127). Corequisite: 15-359 or 36-217 or 36-225 or 21-325.LANGUAGE TECNOLOGIES 11-411 Natural Language Processing Fall and Spring: 12 units This course will introduce students to the highly interdisciplinary area of Artificial Intelligence known alternately as Natural Language Processing (NLP) and Computational Linguistics. The course aims to cover the techniques used today in software that does useful things with text in human languages like English and Chinese. Applications of NLP include automatic translation between languages, extraction and summarization of information in documents, question answering and dialog systems, and conversational agents. This course will focus on core representations and algorithms, with some time spent on real-world applications. Because modern NLP relies so heavily on Machine Learning, we'll cover the basics of discrete classification and probabilistic modeling as we go. Good computational linguists also know about Linguistics, so topics in linguistics (phonology, morphology, and syntax) will be covered when fitting. From a software engineering perspective, there will be an emphasis on rapid prototyping, a useful skill in many other areas of Computer Science. In particular, we will introduce some high-level languages (e.g., regular expressions and Dyna) and some scripting languages (e.g., Python and Perl) that can greatly simplify prototype implementation. Prerequisite: 15-122.ROBOTICS 16-384 Robot Kinematics and Dynamics Fall: 12 units Foundations and principles of robotic kinematics. Topics include transformations, forward kinematics, inverse kinematics, differential kinematics (Jacobians), manipulability, and basic equations of motion. Course also include programming on robot arms. Prerequisite: 15-122 or 16-311 or 18-202 or 21-241 or 24-311. 16-385 Computer Vision Spring: 9 units Basic concepts in machine vision, including sensing and perception, 2D image analysis, pattern classification, physics-based vision, stereo and motion, and object recognition. Prerequisites: (15-122 and 21-241 and 21-259) or (15-122 and 18-202).MATHEMATICS 21-120 Differential and Integral Calculus Fall and Spring: 10 units Functions, limits, derivatives, logarithmic, exponential, and trigonometric functions, inverse functions; L'Hospital's Rule, curve sketching, Mean Value Theorem, related rates, linear and quadratic approximations, maximum-minimum problems, inverse functions, definite and indefinite integrals, and hyperbolic functions; applications of integration, integration by substitution and by parts. 21-122 Integration and Approximation Fall and Spring: 10 units Integration by trigonometric substitution and partial fractions; arclength; improper integrals; Simpson's and Trapezoidal Rules for numerical integration; separable differential equations, Newton's method, Euler's method, Taylor's Theorem including a discussion of the remainder, sequences, series, power series. Parametric curves, polar coordinates, vectors, dot product. Prerequisite: 21-120. 21-127 Concepts of Mathematics Fall and Spring: 10 units This course introduces the basic concepts, ideas and tools involved in doing mathematics. As such, its main focus is on presenting informal logic, and the methods of mathematical proof. These subjects are closely related to the application of mathematics in many areas, particularly computer science. Topics discussed include a basic introduction to elementary number theory, induction, the algebra of sets, relations, equivalence relations, congruences, partitions, and functions, including injections, surjections, and bijections. 21-241 Matrices and Linear Transformations Fall and Spring: 10 units A first course in linear algebra intended for scientists, engineers, mathematicians and computer scientists. Students will be required to write some straightforward proofs. Topics to be covered: complex numbers, real and complex vectors and matrices, rowspace and columnspace of a matrix, rank and nullity, solving linear systems by row reduction of a matrix, inverse matrices and determinants, change of basis, linear transformations, inner product of vectors, orthonormal bases and the Gram-Schmidt process, eigenvectors and eigenvalues, diagonalization of a matrix, symmetric and orthogonal matrices. 21-127 is strongly recommended. 21-242 Matrix Theory Fall and Spring: 10 units An honors version of 21-241 (Matrix Algebra and Linear Transformations) for students of greater aptitude and motivation. More emphasis will be placed on writing proofs. Topics to be covered: complex numbers, real and complex vectors and matrices, rowspace and columnspace of a matrix, rank and nullity, solving linear systems by row reduction of a matrix, inverse matrices and determinants, change of basis, linear transformations, inner product of vectors, orthonormal bases and the Gram-Schmidt process, eigenvectors and eigenvalues, diagonalization of a matrix, symmetric and orthogonal matrices, hermitian and unitary matrices, quadratic forms. 21-341 Linear Algebra Fall and Spring: 9 units A mathematically rigorous treatment of Linear Algebra over an arbitrary field. Topics studied will include abstract vector spaces, linear transformations, determinants, eigenvalues, eigenvectors, inner products, invariant subspaces, canonical forms, the spectral theorem and the singular value decomposition. 21-373 recommended. Prerequisite: 21-241 or 21-242. 21-259 Calculus in Three Dimensions Fall and Spring: 9 units Vectors, lines, planes, quadratic surfaces, polar, cylindrical and spherical coordinates, partial derivatives, directional derivatives, gradient, divergence, curl, chain rule, maximum-minimum problems, multiple integrals, parametric surfaces and curves, line integrals, surface integrals, Green-Gauss theorems. Prerequisite: 21-122. 21-300 Basic Logic Fall: 9 units Propositional and predicate logic: Syntax, proof theory and semantics up to completeness theorem, Lowenheim Skolem theorems, and applications of the compactness theorem. Prerequisite: 15-251 or 21-228 or 21-373. 21-301 Combinatorics Fall and Spring: 9 units A major part of the course concentrates on algebraic methods, which are relevant in the study of error correcting codes, and other areas. Topics covered in depth include permutations and combinations, generating functions, recurrence relations, the principle of inclusion and exclusion, and the Fibonacci sequence and the harmonic series. Additional topics may include existence proofs, partitions, finite calculus, generating combinatorial objects, Polya theory, codes, probabilistic methods. Prerequisites: 21-122 and (15-251 or 21-228). 21-325 Probability Fall: 9 units This course focuses on the understanding of basic concepts in probability theory and illustrates how these concepts can be applied to develop and analyze a variety of models arising in computational biology, finance, engineering and computer science. The firm grounding in the fundamentals is aimed at providing students the flexibility to build and analyze models from diverse applications as well as preparing the interested student for advanced work in these areas. The course will cover core concepts such as probability spaces, random variables, random vectors, multivariate densities, distributions, expectations, sampling and simulation; independence, conditioning, conditional distributions and expectations; limit theorems such as the strong law of large numbers and the central limit theorem; as well as additional topics such as large deviations, random walks and Markov chains, as time permits. Prerequisites: 21-259 or 21-268 or 21-269. 21-484 Graph Theory Spring: 9 units Graph theory uses basic concepts to approach a diversity of problems and nontrivial applications in operations research, computer science and other disciplines. It is one of the very few mathematical areas where one is always close to interesting unsolved problems. Topics include graphs and subgraphs, trees, connectivity, Euler tours and Hamilton cycles, matchings, graph colorings, planar graphs and Euler's Formula, directed graphs, network flows, counting arguments, and graph algorithms. Prerequisites: (15-251 or 21-228) and (21-241 or 21-242).STATISTICS 36-217 Probability Theory and Random Processes Fall and Spring: 9 units This course provides an introduction to probability theory. It is designed for students in electrical and computer engineering. Topics include elementary probability theory, conditional probability and independence, random variables, distribution functions, joint and conditional distributions, limit theorems, and an introduction to random processes. Some elementary ideas in spectral analysis and information theory will be given. A grade of C or better is required in order to use this course as a pre-requisite for 36-226 and 36-410. Not open to students who have received credit for 36-225, or 36-625. Prerequisite: 21-112 or 21-122 or 21-123 or 21-256 or 21-259. 36-225 Introduction to Probability Theory Fall: 9 units This course is the first half of a year long course which provides an introduction to probability and mathematical statistics for students in economics, mathematics and statistics. The use of probability theory is illustrated with examples drawn from engineering, the sciences, and management. Topics include elementary probability theory, conditional probability and independence, random variables, distribution functions, joint and conditional distributions, law of large numbers, and the central limit theorem. A grade of C or better is required in order to advance to 36-226 and 36-410. Not open to students who have received credit for 36-217 or 36-625.PHILOSOPHY 80-310 Formal Logic Fall: 9 units Among the most significant developments in modern logic is the formal analysis of the notions of provability and logical consequence for the logic of relations and quantification, known as first-order logic. These notions are related by the soundness and completeness theorems: a logical formula is provable if and only if it is true under every interpretation. This course provides a formal specification of the syntax and semantics of first-order logic and then proves the soundness and completeness theorems. Other topics may include: basic model theory, intuitionistic, modal, and higher-order logics. Prerequisite: 15-251 or 80-210 or 80-211 or 80-212. 80-311 Undecidability and Incompleteness Spring: 9 units This course focuses on two central problems of mathematical logic: the undecidability of predicate logic (established by Church and Turing) and the incompleteness of formal theories (discovered by Gödel for theories that contain a modicum of set or number theory). The mathematical solutions of these problems involve a rigorous concept of computability or calculability that turned out to be fundamental for computer science, but also cognitive science. We first discuss predicate logic and systematic ways of constructing proofs; that is followed by the formal development of elementary set theory. The concept of Turing machine computation is introduced and shown to be equivalent to the concept of recursive function. That provides the mathematical, methodologically adequate tools for establishing the results mentioned above. The mathematical and computational notions and results are among the most significant contributions of logic, not just to the solution of internal logical questions and to the foundations of computer science, but also to (the beginnings of) a deeper understanding of the human mind and mental processes. In addition to the mathematical developments, we will discuss historical and philosophical aspects of the subject. Prerequisite: 15-251 or 21-300 or 80-210 or 80-211 or 80-310.
