How do you optimally encode a text file?
How do you find shortest paths in a map? How do you design a communication
network? How do you route data in a network? What are the limits of efficient
computation? This course gives a comprehensive introduction to design and analysis
of algorithms, and answers along the way to these and many other interesting
computational questions. You will learn about problem-solving; advanced data
structures such as universal hashing and red-black trees; advanced design
and analysis techniques such as dynamic programming and amortized analysis;
graph algorithms such as minimum spanning trees and network flows;
NP-completeness theory; and approximation algorithms.
Data Structures and Algorithms
This is a course about Algorithms and Data Structures using the Java programming language.
We introduce the basic concepts about complexity of an algorithm and methods on how to compute the running time of algorithms.
Then, we describe data structures like stacks, queues, maps, trees, and graphs, and we construct efficient algorithms based on these representations.
The course builds upon existing implementations of basic data structures in Java and extends them for the structures like trees, studying the performance of
operations on such structures, and the efficiency when used in real-world applications. A large project introducing students to the challenges of software
engineering concludes the course.
Programming Languages and Techniques
CIS 120 is a fast-paced introduction to the fundamental concepts of programming and software design. It introduces students to computer science by emphasizing the design aspects of programming. Topics include:
- Data types and data representation
- Abstraction, interfaces, and modularity
- Test-driven development
- Programming patterns (recursion, iteration, events, call-backs, collections, map-reduce, GUIs, …)
- Functional programming
- How and when to use mutable state
- Object-oriented programming
CIS 120 teaches programming concepts in two different languages: OCaml and Java, spending approximately equal time on how to design programs in each language.
Computer Operating Systems
This course surveys methods and algorithms used in modern operating systems. Concurrent distributed operation is emphasized. The main topics covered are as follows: process synchronization; interprocess communication; concurrent/distributed programming languages; resource allocation and deadlock; virtual memory; protection and security; distributed operation; distributed data; performance evalaution.
Scalable & Cloud Computing
What is the "cloud"? How do we build software systems and components that scale to millions of users and petabytes of data, and are "always available"? In the modern Internet, virtually all large Web services run atop multiple geographically distributed data centers: Google, Yahoo, Facebook, iTunes, Amazon, EBAY, Bing, etc. Services must scale across thousands of machines, tolerate failures, and support thousands of concurrent requests. Increasingly, the major providers (including Amazon, Google, Microsoft, HP, and IBM) are looking at "hosting" third-party applications in their data centers - forming so-called "cloud computing" services.
Databases & Information Systems
This course provides an introduction to the broad field of database and information systems, covering a variety of topics relating to structured data, ranging from data modeling to logical foundations and popular languages, to system implementations. We will study the theory of relational and XML data design; the basics of query languages; efficient storage of data, execution of queries and query optimization; transactions and updates; web-database development; and "big data" and NoSQL systems. The course assumes mathematical and programming experience equivalent to CIS160 and CIS121.
Compilers & Interpreters
You know how to program, but do you know how to implement a programming language? In CIS341 you'll learn how to build a compiler. Topics covered include: lexical analysis, grammars and parsing, intermediate representations, syntax-directed translation, code generation, type checking, simple dataflow and control-flow analyses, and optimizations. Along the way, we study objects and inheritance, first-class functions (closures), data representation and runtime-support issues such as garbage collection. This is a challenging, implementation-oriented course in which students build a full compiler from a simple, typed object-oriented language to fully operational x86 assembly. The course projects are implemented using OCaml, but no knowledge of OCaml is assumed. Prerequisite: Two semesters of progrmming courses, e.g., CIS 120, 121, 240.
Big Data Analytics
In the new era of big data, we are increasingly faced with the challenges of processing vast volumes of data. Given the limits of individual machines (compute power, memory, bandwidth), increasingly the solution is to process the data in parallel on many machines. This course focuses on the fundamentals of scaling computation to handle common data analytics tasks. You will learn about basic tasks in collecting, wrangling, and structuring data; programming models for performing certain kinds of computation in a scalable way across many compute nodes; common approaches to converting algorithms to such programming models; standard toolkits for data analysis consisting of a wide variety of primitives; and popular distributed frameworks for analytics tasks such as filtering, graph analysis, clustering, and classification.
This course investigates algorithms to implement resource-limited knowledge-based agents which sense and act in the world. Topics include, search, machine learning, probabilistic reasoning, natural language processing, knowledge representation and logic. After a brief introduction to the language, programming assignments will be in Python.
DevOps is the breaking down of the wall between Developers and Operations to allow more frequent and reliable feature deployments. Through a variety of automation-focused techniques, DevOps has the power to radically improve and streamline processes that in the past were manual and susceptible to human error.
In this course we will take a practical, hands-on look at DevOps and dive into some of the main tools of DevOps: automated testing, containerization, reproducibility, continuous integration, and continuous deployment. Throughout the semester we build toward an end-to-end pipeline that takes a webserver, packages it, and then deploys it to the cloud in a reliable and quickly-reproducible manner utilizing industry-leading technologies like Kubernetes and Docker. Evaluation is based on homework assignments and a final group project.
Solving Hard Problems in Practice
What does Sudoku have in common with debugging, scheduling exams, and routing shipments? All of these problems are provably hard -- no one has a fast algorithm to solve them. But in reality, people are quickly solving these problems on a huge scale with clever systems and heuristics! In this course, we'll explore how researchers and organizations like Microsoft, Google, and NASA are solving these hard problems, and we'll get to use some of the tools they've built!
Python is an elegant, concise, and powerful language that is useful for tasks large and small. Python has quickly become a popular language for getting things done efficiently in many in all domains: scripting, systems programming, research tools, and web development. This course will provide an introduction to this modern high-level language using hands-on experience through programming assignments and a collaborative final application development project.
Algorithmic Game Theory
How should an auction for scarce goods be structured if the sellers wish to maximize their revenue? How badly will traffic be snarled if drivers each selfishly try to minimize their commute time, compared to if a benevolent dictator directed traffic? How can couples be paired so that no two couples wish to swap partners in hindsight? How can you be as successful as the best horse-racing expert at betting on horse races, without knowing anything about horse racing? In this course, we will take an algorithmic perspective on problems in game theory, to solve problems such as the ones listed above. Game theory has applications in a wide variety of settings in which multiple participants with different incentives are placed in the same environment, must interact, and each "player"'s actions affect the others.
Computer Organization and Design
This is the second computer organization course
and focuses on computer hardware design. Topics covered are:
(1) basic digital system design including finite state machines,
(2) instruction set design and simple RISC assembly programming,
(3) quantitative evaluation of computer performance,
(4) circuits for integer and floating-point arithmetic,
(5) datapath and control,
(8) storage hierarchy and virtual memory,
(10) different forms of parallelism including instruction level parallelism, data-level parallelism using both vectors and message-passing multi-processors, and thread-level parallelism using shared memory multiprocessors. Basic cache coherence and synchronization.
Introduction to Computer Architecture
The goal of this course is to teach you how a computer really works. We begin by discussing transistors, the basic switching elements that constitute modern computers. We then describe how these transistors can be aggregated into more complex units like gates and ALUs and ultimately datapaths that perform computation. Once we have described how we can build a computer we will move on to talking about assembly language and how the computer is programmed at the lowest level. We will spend the second half of the course talking about the C programming language and how the features of this language are mapped onto the lower level assembly constructs.
Automata, Computability, and Complexity
This course explores questions fundamental to computer science such as which problems cannot be solved by computers, can we formalize computing as a mathematical concept without relying upon the specifics of programming languages and computing platforms, and which problems can be solved efficiently. The topics include finite automata and regular languages, context-free grammars and pushdown automata, Turing machines and undecidability, tractability and NP-completeness. The course emphasizes rigorous mathematical reasoning as well as connections to practical computing problems such as text processing, parsing, XML query languages, and program verification.
Mathematical Foundations of CS
What are the basic mathematical concepts and techniques needed in computer science? This course provides an introduction to proof principles and logics, functions and relations, induction principles, combinatorics and graph theory, as well as a rigorous grounding in writing and reading mathematical proofs.
AP Computer Science A
AP Computer Science emphasizes object-oriented programming methodology with an emphasis on problem solving and algorithm development. It also includes the study of data structures and abstraction. Topics include: Primitive Types; Using Objects; Boolean Expressions and if Statements; Iteration; Writing Classes; Array; ArrayList; 2D Array; Inheritance; Recursion.