Graduate

Summary of Course Content
I. Exact matching using the Z and the Boyer-Moore algorithms

II. Suffix trees and linear time algorithms for computing them

III. Applications of suffix trees in pattern matching and computational biology

IV. Inexact matching, edit distance and alignment

V. Accelerations for inexact matching

VI. Additional alignment models for biological applications of inexact matching. Gap questions.

VII. Hybrid dynamic programming -- integrating suffix trees with inexact matching

VIII. Database searching

IX. Applications of string algorithms in DNA sequencing problems

X. String algorithms in phylogenetic reconstruction

Project:

The project involves some computer implementation of an important algorithm or the theoretical development of some new method.

Illustrative Reading
D. Gusfield, Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Cambridge Press, 1997

Potential Course Overlap
There is no significant overlap with any other course.

Summary of Course Content
I. Overview
Types of parallel systems, and motivations for parallel systems. Discussion of general
techniques for designing parallel algorithms.

II. Classes of Parallel Algorithms
The class NC, P completeness and processor time trade-offs.

III. Parallel Algorithms for Comparison Problems
Algorithms for maximum finding, selection, merging and sorting.

IV. Parallel Graph Algorithms
Parallel algorithms for minimum spanning tree, connectivity, tree functions, ear decomposition,
and matching will be discussed.

V. Lower Bounds on Parallel Computations
Lower bounds for parallel algorithms for first maximum independent set and for Boolean or
Relationship to other problems.

Project/Design Statement:
The class has a substantial project involving in-depth study of a parallel system and application.

Illustrative Reading
Selected papers from recent journals and conferences, and class notes.

Potential Course Overlap
This course does not have a significant overlap with any other course. ECS 201C also covers models of parallel systems, but the focus there is on the architecture and systems aspect, while this course looks at the algorithmic implications (and thus has a very different focus).

Summary of Course Content
I. Models of Computational Complexity
A. RAM
B. Turing machine
C. Bit and arithmetic complexity

II. Problem Classification
A. P and NP
B. Proving problems NP-complete
C. P-space and exp.-time completeness

III. Matching
A. Algorithms for bipartite graphs
B. Discussion of non-bipartite matching

IV. Network Flows
A. Study of advanced flow algorithms
B. Minimum cost flows
C. Extensions to the model
D. Application of flow

V. Matrix Multiplication
A. Fast algorithms by Strassen and others
B. Order of matrix multiplication

VI. Approximation Algorithms
A. General Techniques
B. Applications to Knapsack
C. Bin-packing
D. Scheduling
E. Limits of approximation

VII. Advanced Topics (selection from)
A. Probabilistic algorithms
B. Parallel algorithms
C. Encryption techniques
D. Scheduling theory

Project/Design Statement:
The course requires an in depth project involving the design, implementation, and experimental evaluation of an advanced algorithm.

Illustrative Reading
T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, 2nd edition, McGraw Hill, 2001

Potential Course Overlap
This course does not have a significant overlap with any other course. It covers some of the same general topics as ECS 222A but does so at a more advanced and formal level. Topic II (P and NP) is also covered in ECS 220 but the focus is quite different in the two classes (ECS 220 takes a much more formal approach, while ECS 222B stresses the algorithmic implications).

Summary of Course Content
I. Overview of Algorithm Design and Analysis
A. Design techniques
B. Classes of algorithms
C. Analysis techniques

II. Dynamic Programming

III. Probabalistic Analysis and Randomized Algorithms

IV. Advanced Graph Algorithms
A. All pairs Shortest paths
B. Connectivity
C. Network flow

V. Advanced Data structures and Amortized Analysis

VI. String Matching and Suffix Trees

VII. Lower bounds

VIII. The Classes P and NP
A. NP-hard and NP-complete problems
B. Use of reductions
C. Dealing with NP-complete problems

IX. Approximation algorithms

X. Selected Advanced Topics
A. Number theoretic algorithms
B. Computational geometry
C. Parallel algorithms

Illustrative Reading
T. Cormen, C. Leiserson, R. Rivest, An Introduction to Algorithms, McGraw Hill, 2001
(second edition)

Potential Course Overlap
This course does not have a significant overlap with any other course. It covers some of
the same general topics as ECS 122A and B (the undergraduate algorithms courses) but
does so at a more advanced and formal level. Topic VIII (P and NP) is also covered in
ECS 220 but the focus is quite different in the two classes (ECS 220 takes a much more
formal approach, while ECS 222A stresses the algorithmic implications).

Summary of Course Content
The course aims to introduce graduate students to various computational and experimental challenges in systems and synthetic biology. It will (a) help biologists to perform data analysis and create customized programs, and (b) help computer scientists identify important biological challenges to which computational thinking can be applied. The course will focus on state-of-the-art computational methods for the analysis and construction of biological networks, the simulation of biological systems, and the automated design of biological constructs. Students will have to read and present technical papers, and complete two sets of homework and a final project. Guest speakers from Life Sciences will deliver some of the lectures. 1. Introduction to Systems and Synthetic biology (week 1): a. Systems Biology: A network perspective b. Synthetic Biology: How (not) to engineer biological systems 2. Methods in computational biology (week 2 – 4): a. Dynamic programming b. Clustering (K-means, Hierarchical, Bi-clustering, Expectation Maximization) c. Classification (Naïve Bayes, Neural Nets, Support Vector Machines) d. Markov processes e. Hidden Markov Models 3. Biological networks (week 5 – 6): a. Probabilistic reconstruction b. Network analysis and statistics c. Motif finding d. Graphical Models 4. Biological modeling and simulation (week 7 – 8): a. Fundamental regulatory models b. Monte Carlo Method c. Markov Chain Monte Carlo sampling d. Numerical integration: Ordinary and Stochastic Differential Equations 5. Engineering biological systems (week 9 – 10): a. Part standardization and characterization b. Flux Balance Analysis c. Computer Aided Design and Implementation d. Testing and verification e. Ethics

Illustrative Reading
Textbook: None Technical papers and class notes will be used. Optional additional reading from: - C. Bishop, “Pattern Recognition and Machine Learning”, Springer, 2007 - Edda Klipp, Wolfram Liebermeister, Christoph Wierling, Axel Kowald, Hans Lehrach, Ralf Herwig, “Systems Biology: A Textbook”, Wiley, 2009 - Uri Alon, “An introduction to Systems Biology”, Chapman & Hall/CRC, 2007

Potential Course Overlap
none

Summary of Course Content
I. Turing machines and Turing-equivalent models of computation. Turing-undecidable problems from a variety of domains. II. First order logic, completeness, second-order logic, undecidability and incompleteness, the recursion theorem. III. Complexity classes, the time and space hierarchy, Savitch's theorem, reductions, completeness. The polynomial time hierarchy. Decision vs. search. NL = coNL. IV. The Cook-Levin theorem. NP-Complete problems. PSPACE completeness. Practice with reductions. V. Randomized computations, BPP, problems for which randomness provably helps. Interactive proofs. IP=PSPACE. PCP (Probabilistically Checkable Proofs). VI. Approximation algorithms. Non-approximability results.

Illustrative Reading
C. Papadimitriou, Computational Complexity, Addison Wesley, 1994

Potential Course Overlap
This course does not have a significant overlap with any other course. NP-completeness is discussed, at a lower and more pragmatic level, in ECS 120.

Summary of Course Content:
The faculty member in charge will present the main topics. There will also be presentations by other faculty members describing the types of research in their area and panel presentations by senior graduate students discussing their research experience.

1. What makes a good research area and topic
2. Major research topics in computer science (this is the majority of the class)
   1. Theory: cryptography, computational geometry, computational biology, optimization, scientific computing
   2. Systems: security, software development, distributed systems, high performance
   3. Networking: optical, wireless, sensor, protocols
   4. Architecture
   5. Graphics and Visualization
   6. Information Systems
   7. Artificial Intelligence
3. Choosing a research topic
4. Picking an advisor
5. Ethical issues in class work and research

Illustrative Reading:
Selected articles and Web sites

Potential Course Overlap:
Slight overlap with 293B in the introductory part of the course. The focus on computer science research makes this course substantially different from orientation classes in other fields.

Summary of Course Content
The faculty member in charge will present the main topics. There will also be presentations by other faculty members describing the types of research in their area and panel presentations by senior graduate students discussing their research experience.

1. What makes a good research area and advanced topics
2. II. How to do research
   1. How to find and manage information (prior work)
   2. How to read a research paper
   3. How to write a research paper
3. Writing a CS conference paper (selling your ideas)
4. Giving a good CS technical talk
5. How to write a research/fellowship proposal

Illustrative Reading
Selected articles and Web sites

Potential Course Overlap
Slight overlap with 293A in the introductory part of the course. The focus on computer science research makes this course substantially different from orientation classes in other fields.