Upper Division

Summary of Course Content

I. Univariate and Multivariate Distributions

• Probability mass, density, and cumulative distribution functions
• Parametric families of distributions
• Expected value, variance, conditional expectation
• Applications of the univariate and multivariate Central Limit Theorem
• Probabilistic inequalities

II. Sampling, Estimation and Modeling Building

• Random samples, sampling distributions of estimators
• Methods of Moments and Maximum Likelihood
• Statistical inference
• Introduction to multivariate statistical models: regression and classification problems, log-linear model, principal components analysis
• The problem of overfitting; model assessment

III. Application of Markov Models

• Markov chains
• Hidden Markov models
• Queuing models
• Markov Chain Monte Carlo

IV. Computer science and engineering applications (interspersed with the above topics throughout the course)

• Data mining
• Network protocols, analysis of Web traffic
• Computer security
• Software engineering
• Computer architecture, operating systems, distributed systems
• Bioinformatics

Illustrative Reading
Possible choices include:

• K.S. Trivedi, Probability and Statistics with Reliability, Queuing, and Computer Science Applications, Wiley, New York, 2001;
• M. Mitzenmacher, E. Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge, 2005;
• N. Matloff, A Course in Probabilistic and Statistical Modeling in Computer Science http://heather.cs.ucdavis.edu/~matloff/132/PLN

Potential Course Overlap
There is some topical overlap with MAT 135A and STA 131ABC, as well as with application-specific probability/statistics courses such as ECI 114, EEC 161, ECN 140 and so on. This course differs greatly in its collection of topics, its usage of computers, and especially in its computer science applications.

Summary of Course Content

I. Power tools of the trade

• Vector and matrix operation
• Building exploratory environments
• Floating point arithmetic
• Error analysis

II. Data interpolation

• The interpolating polynomial
• Piecewise linear interpolation
• Piecewise cubic Hermite interpolation
• Cubic spline

III. Zeros, roots and optimization

• Bisection
• Newton’s method
• Second method
• Inverse quadratic interpolation
• Quasi-Newton’s method

IV. Quadrature

• Basic quadrature rules
• Adaptive quadrature

V. Least squares data fitting

• Models and data curve fitting
• Norms
• The QR factorization
• Pseudoinverse

VI. Eigenvalues and singular values

• Symmetric and Hermitian matrices
• Eigenvalue and singular value decompositions
• Eigenvalue sensitivity and accuracy
• Singular sensitivity and accuracy
• Principle components

VII. Parallel computing

• Matrix-matrix product
• The Cholesky factorization 

Illustrative Reading

Moler, Numerical Computing with MATLAB, SIAM 2004 

Potential Course Overlap

Some of mathematical topics of ECS 130 overlap with MAT 128A/B/C, EAD 115/116 and ENG 180, such as interpolation and integration. However, the overlap is only very limited. Some of the ECS 130 topics are normally not treated in these courses, such as recursive and parallel matrix operations, and parallel Cholesky factorization.

ECS 130 is a one-quarter course, as opposed to the two-quarter EAD or three-quarter MAT sequences. ECS 130 is especially designed for undergraduate computer science majors who can benefit from a substantial knowledge of numerical computing, but allot only a limited time for this purpose due to many other complementary course requirements. MAT 128A/B/C, EAD 115/116 and ENG 180 cover wide areas of mathematical problems and numerical methods. In general, the focus of these courses is on the theoretical and mathematical aspects of numerical methods. 

ECS 130 will only cover fundamental parts of mathematical problems and numerical methods in scientific computation. Moreover, ECS 130 uses a matrix-vector approach with MATLAB as a problem-solving environment. Students who have taken ENG 6 will have additional background in using MATLAB language, but it is not required for ECS 130. The overlap between ECS 130 and ENG 6 is only on the introduction of MATLAB, thus the overlap is minimal. 

In ECS 130, numerical algorithms and analysis, finite precision arithmetic, graphics and matrix-vector manipulation are folded into the course in a way that gets students to appreciate the connection between continuous mathematics and numerical computing, and the subtleties of numerical computing. ECS 130 is for computer science majors to acquire scientific computation skill and tools which will be useful later on in their computational career.

Summary of Course Content

I. Introduction: Top Challenges in Bioinformatics

II. Bio-molecular Structures

• 
A. Nucleic acids
• 
B. Protein

III. Comparing Sequences and Structures

• 
A. Sequence alignment
• 
B. Structure alignment

IV. Protein Structure Databases

• A. Protein domains
• B. Protein structure classification 

V. Stability of Bio-molecules 


• A. Semi-empirical energy functions
• 
B. Statistical potentials 

VI. Structure Prediction 


• A. Protein: Comparative modeling 

• B. Protein: Ab initio prediction 

• C. RNA: secondary structure and tertiary structure predictions 

VII. Bio-molecular Simulations 

VIII. Drug Design 

IX. Databases and Web Services 



Illustrative Reading


Selected review papers and technical papers and class notes will be used.



Potential Course Overlap


ECS 124 (Theory and Practice of Bioinformatics) and ECS 129 are complementary courses with minimal overlap covering bioinformatics. ECS 124 focuses on sequence analysis, while ECS 129 covers the structural challenges in bioinformatics.

Summary of Course Content

Topics to include most or all of the following:

1. Introduction (classical cryptographic goals of encryption, authentication, key distribution, as well as protocol goals like the dating problem or average-salary computation)
2. Classical ciphers (substitution ciphers)
3. Stream ciphers and LFSRs
4. Blockciphers (Feistel networks, DES, AES)
5. Symmetric encryption modes
6. Security notions for symmetric encryption (indistinguishability, semantic security, chosen-plaintext attacks, chosen-ciphertext attacks, non-malleability)
7. Reductions (for relating notions or evidencing security)
8. Message authentication codes
9. Authenticated encryption (generic composition, specialized schemes)
10. Cryptographic hash functions (SHA-1, SHA-3)
11. Number-theory background
12. Public-key encryption (RSA, Diffie-Hellman, elliptic curves)
13. Digital signatures (RSA, ElGamal, Lamport)
14. entity authentication and key-distribution protocols (Kerberos, TLS)
15. Secret sharing (Shamir’s scheme)
16. Oblivious transfer and garbled-circuit evaluation
17. Zero knowledge
18. Cryptography and public policy
19. Cryptography and intellectual property 

Illustrative Reading

• D. Stinson. Cryptography: Theory and Practice, third ed.. Chapman & Hall/CRC, 2005.
• N. Ferguson, B. Schneier, and T. Kohno. Cryptography Engineering: Design Principles and Practical Applications. Wiley, 2010. 

Potential Course Overlap

There is a small amount of overlap with course 153, Computer Security, which briefly discusses methods for shared-key and public-key encryption. ECS 127 provides a much broader and deeper description of contemporary cryptography.

Summary of Course Content

I. Initial examples of the power of bioinformatics in modern biology

• The importance of sequence and structure comparison and of database search
• The use of sequence analysis in laboratory protocols
• The use of phylogenetics in evolution and non-evolutionary areas of biology

II. Sequence analysis

• Probabilistic and biological models underlying sequence alignment
• Computational efficiency and the need for compromises in the models
• The general technique of dynamic programming
• Pairwise sequence alignment - algorithms for global, local alignment and variations
• Algorithms for multiple sequence alignment and the identification/use of motifs
• Database search, FASTA, BLAST, PSI-BLAST, scoring matrices, statistical significance and its significance
• Multiple sequence alignment
• Genome assembly and high-throughput transcriptional profiling

III. Systems Biology

• Clustering (K-means, hierarchical clustering)
• Classification (naive Bayes, Support Vector Machines)
• Machine Learning in Biology
  • Overfitting, bias-variance trade-off, curse of dimensionality
  • Validation methods
• Biological Networks
  • Introduction to networks biology
  • Functional gene networks
  • Inference of gene regulatory networks

IV. Phylogenetic algorithms

• Probabilistic and ideal-data models underlying phylogenetic algorithms
• Distance-based methods
• Character/parsimony-based methods
• Maximum-likelihood methods
• Evolutionary and non-evolutionary uses for phylogenetics
• Multiscale modeling and simulation of evolutionary systems

Illustrative Reading

• R. Durbin et al., Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids, Cambridge Press, 1998.
• A. Baxevanis and B. Ouellete, Bioinformatics: A Practical Guide to the Analysis of Genes and Proteins, Wiley-Interscience, 1998.
• M. Bishop and C. Rawlings, DNA and Protein Sequence Analysis: A Practical Approach, IRL Press, 1997.
• D. Gusfield, Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology, Cambridge Press, 1997.
• N. Jones and P. Pevzner, An Introduction to Bioinformatics Algorithms, MIT Press, 2004

Potential Course Overlap

The laboratory section of ECS 124 will overlap to some amount with Animal Genetics 212 (taught by J. Medrano) a graduate course offered every other year. The overlap in the laboratory section is only partial, as ANG 212 looks at more sequence analysis packages than in ECS 124; the lab portions of ECS 124 also look at packages for cluster enrichment, biological networks and phylogenetic analysis, which are not covered in ANG 212. They also involve computer programming in Perl or Java, while no programming is involved in ANG 212. The theoretical parts of ECS 124 (the lecture part of the course) will have no essential intersection with ANG 212, being either on different material entirely, or being a much more mathematical and algorithmic treatment of the material, i.e., fully explaining and developing the logic of the techniques, rather than focusing on learning to use these techniques in the form of packaged computer programs.

A good analogy to explain the partial intersection is that ANG 212 is a course on “flying an airplane” while ECS 124 will be on the “physics of flight” with exercises in flying to make the ideas concrete. ECS 124 intersects with ECS 221 (taught by I. Tagkopoulos), a graduate seminar course which focuses on Machine Learning methods in Systems and Synthetic Biology. The overlap is mainly on the areas of clustering, classifications and network analysis. ECS 221 assumes advanced computer science knowledge and treats these topics with more mathematical rigor than ECS 124, which includes lectures related to fundamental computer science methods (e.g. suffix trees, dynamic programming, etc.). In contrast to ECS 124, ECS 221 focuses on the presentation of research papers in the field, while it does not requires any laboratories/homeworks.

ECS 124 intersects EVE 298 (taught by M. Sanderson and S. Nadler) in the subarea of phylogenetics. However, the emphasis of the two courses in that overlapping subarea is again different. EVE 298 is oriented towards teaching biology graduate students to use computerized phylogenetic tools effectively in their biological (phylogenetic) research, while ECS 124 will have a more algorithmic and mathematical orientation.

ECS 124 intersects GGG 298D (taught by C. Warden and M. Syvanen) in the subarea of sequence analysis. Again the emphasis is quite different. GGG 298D is oriented towards teaching biology graduate students to use computerized sequence analysis tools effectively in their (biological sequence analysis) research, while ECS 124 will have a more algorithmic and mathematical orientation. There are no undergraduate courses on campus that have any substantial intersection with ECS 124.

Final Exam

Yes Final Exam

Justification for No Final Exam

final exam

Summary of Course Content

1. NP-completeness theory and implications for algorithm design.
2. Examples of polynomial time reductions.
3. Graph algorithms: network flow, min-cost flow, applications of network flow.
4. Approximation algorithms.
5. Randomized algorithms.
6. Dynamic programming and practical speedups.
7. Branch and bound methods for hard problems
8. Computational studies of chosen algorithms and implementations. Emphasis on time versus space versus programming simplicity. What methods really work in practice versus theory. Use of timing and profiling tools.

Illustrative Reading

• Jon Bentley, Programming Pearls, Addison-Wesley, second edition, 1999.
• J. Kleinberg and É. Tardos, Algorithm Design, Addison-Wesley, 2005.

Potential Course Overlap

This course does not duplicate any existing course.

Summary of Course Content

1. Complexity of algorithms, bounds on complexity, analysis methods.
2. Searching, sorting, pattern matching, graph algorithms.
3. Algorithm design techniques: divide-conquer, greedy, dynamic programming.
4. Approximation methods. NP-complete problems. 

Illustrative Reading

T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Introduction to Algorithms, 3rd edition. The MIT Press, 2009.

Potential Course Overlap

There is no significant overlap with other courses.

Summary of Course Content

I. Automata Theory and Formal Languages

• Regular languages. Finite automata and the class of languages they define. Closure properties of regular languages. Multiple-characterization of regular languages (DFAs, NFA, regular expressions). The pumping lemma for regular languages.
• Context-free languages. Grammars and pushdown automata. Normal forms. The pumping lemma for CFLs.

II. Computability Theory

• The Turing-machine model, RAM model, and other equivalent models of effective computability. The Church-Turing thesis.
• Decidable and undecidable problems. Recursively-enumerable sets. The halting problem and other examples of undecidable problems.
• Reducibility. Examples of many-one reductions.

III. Complexity Theory

• Time complexity. P and NP. Polynomial-time reducibility. NP-Completeness. The Cook-Levin Theorem. Example reductions among NP-hard sets.
• Any of the following topics, as time permits:
  • Parallel models of computation
  • The role of randomness in computation
  • Interactive proofs

Illustrative Reading
M. Sipser, Introduction to the Theory of Computation, 3rd ed. Course Technology, 2012 

Potential Course Overlap
none

Summary of Course Content

1. Introduction: security, assurance
2. World Wide Web: browsers, computer viruses and worms, firewalls, networks
3. Privacy: data protection, sanitization, encryption, secure email
4. Society and Computer Security: e-voting, social networking, e-commerce, home computing, mobile computing (phones, smart devices)
5. Doctors, Lawyers, and Regulations: electronic medical records, forensics, government regulations such as HIPAA and Sarbanes-Oxley
6. How Do You Know It Works: analyzing systems, vulnerabilities, defenses, secure coding
7. Cybercrime, cyberwarfare, and cyber-terrorism
8. Miscellaneous: virtual computing, cloud computing

Illustrative Reading

A selection of handouts and books will be used and are to be updated regularly. Examples include:

• Michael G. Solomon and Mike Chapple, "Information Security Illuminated," Jones and Bartlett Publishers, Sudbury, MA (2005); ISBN 0-7637-2677-X
• John Viega, "The Myths of Security: What the Computer Security Industry Doesn't Want You to Know," O'Reilly Media, Inc., Sebastopol, CA (2009); ISBN 978-0-596-52302-2

Potential Course Overlap

The content of this course overlaps some of the content of course 153, but is intended for non-majors. This course is less theoretical than course 153. The coverage of this course is broader, and goes into less technical depth, than course 153.