Foundations Course Group Status Report

1. Summary

The courses in this group, while related to each other, also differ in important respects from each other. CSE 541 provides basic coverage of essential numerical techniques. Math 366 and Math 566 acquaint students with fundamental skills related to discrete mathematics, skills that are necessary to explore essential topics in theoretical computer science.  All undergraduates are required to take all three of these courses.

CSE 625 and CSE 725 offer a two course sequence in automata theory and computational complexity. In CSE 625 students encounter finite state machines, pushdown automata and formal languages. These topics are continued in CSE 725 where students gain an appreciation for the theoretical genesis of computer science. Topics include Turing machines and an introduction to complexity theory including the classes P, NP and NP-comple CSE 625 is a required course for undergraduate majors; 725 is a required course for CSE graduate students, and an elective for undergraduates.

CSE 680, CSE 723 and CSE 780 comprise the algorithms subgroup. In CSE 680 students are introduced to formal algorithmic analysis and asymptotic notation. Algorithmic design is also covered. CSE 780 further examines algorithmic topics with emphasis on advanced design methods such as dynamic programming. CSE 723 is a new course on cryptographic algorithms and protocols. CSE 680 is a required course for undergraduate majors; 780 a required course for CSE graduate students, and an elective for undergraduates; CSE 723 is an elective for both undergraduates and graduate students.

Taken together, the courses above provide our students with a broad and detailed overview of the foundations of computer science. Students who master this material are well prepared for further study and are also likely to gain a deeper understanding of the content of other, less theoretical, courses.

2. Detailed Analysis

2.1 Summary of the Courses

2.1.1 Descriptions

Math 566: Discrete Mathematical Structures II   is a continuation of topics from Math 366. These include counting and combinatorics, recurrence relations, an introduction to algorithmic efficiency and graphs. Math 566 is now required of all undergraduate majors in the CSE Department. Current textbook: Discrete Mathematics with Applications, 3rd Edition, Susanna S. Epp.

CSE 541: Elementary Numerical Methods  is a survey of basic numerical methods.  CSE 541 is required of all undergraduate majors in computer science. The course covers number systems and errors of finite representation, solution of a single non-linear equation, interpolation, numerical integration, and solutions of linear systems.  In the final weeks, either interval arithmetic or least squares curve fitting are covered. Some sections of the course use MatLab. Typical textbook: Numerical Mathematics and Computing, Cheney and Kincaid.

CSE 625: Introduction to Automata and Formal Languages is a standard undergraduate course in automata theory and formal languages and is required of all undergraduate majors in the CSE Department.  The course covers regular expressions, regular languages, regular and context-free grammars, finite and pushdown automata and the pumping lemma.  Turing machines are sometimes introduced in the final weeks of the course. Typical textbook: Introduction to Languages and the Theory of Computation, John Martin.

CSE 680: Introduction to Analysis of Algorithms & Data Structures is required of all undergraduate computer science majors. It is a standard undergraduate algorithms course with emphasis on run-time analysis, asymptotic notation, recursive algorithms, sorting algorithms and graph algorithms. There is also some coverage of algorithmic design techniques including divide-and-conquer and greedy. Typical textbook: Introduction to Algorithms, Cormen, Leiserson, Rivest & Stein.

CSE 725: Computability and Unsolvability is a graduate course in decidability and NP-completeness.  It is required of all CSE graduate students but some CSE and CIS undergraduate students also take the class.  The course covers Turing machines, Church's thesis, recursive and recursively enumerable languages, self replicating programs, polynomial time and NP-completeness.  Typical textbook: Introduction to the Theory of Computation, Michael Sipser.

CSE 780: Analysis of Algorithms is a graduate course in algorithms.  It is required of all CSE graduate students and is open to undergraduates.  The course covers divide and conquer algorithms, greedy algorithms, dynamic programming, and advanced graph algorithms. Typical textbook: Introduction to Algorithms, Cormen, Leiserson, Rivest & Stein. 

2.2.2 Relation of the courses to the rest of the CSE program

CSE 321 includes formal program specification which requires that students be able to understand, write and reason with formal logic and notation. Students in CSE 625 must be familiar with proofs and proof techniques, including proof by induction. Students in CSE 630 must be familiar with logic and proofs for knowledge representation. In CSE 670, students use logic to form database queries. Boolean logic is essential to the circuit design covered in CSE 675. To understand algorithm design and analysis, students in CSE 680 need to be familiar with proofs and proof techniques and with basic counting arguments. In CSE 755 students learn formal specification methods requiring familiarity with formal logic.

Math 566: Discrete Mathematical Structures II:  Prerequisites: Math 366
Prerequisite for: CSE 680. In CSE 680 students are asked to analyze and write recursive algorithms and to understand a variety of graph algorithms. Both topics are covered in Math 566. 

CSE 541: Elementary Numerical Methods: Prerequisites: CSE 221 (majors) or CSE 230 (non-majors) or CSE 502 (non-majors), Math 153 (third quarter calculus).
Prerequisite for: CSE 621, 640, 642 and 682.
CSE 621, Introduction to High Performance Computing, makes direct use of many topics from CSE 541. CSE 640 and CSE 642 (though neither has been offered recently) are continuations of CSE 541. CSE 682 is a course in computer animation. Numerical methods are crucial in graphics.

CSE 625: Introduction to Automata and Formal Languages: Prerequisites: CSE 321 and Math 366.
Prerequisite for: CSE 655, 725 and 756.
In CSE 655 (Programming Languages) and CSE 756 (Compiler Design) students must have familiarity with grammars and finite state machines. As a continuation of 625, CSE 725 relies heavily on much of the material in that course.

CSE 680: Introduction to Algorithms and Data Structures: Prerequisites: CSE 560 or CSE 668 or ECE 668, Stat 427 and Math 566.
Prerequisite for: CSE 756 and 780.
In CSE 756 students study parsing, an understanding of which will benefit from an understanding of efficiency. CSE 780 is a continuation of topics studied in CSE 680.

CSE 725: Computability and Unsolvability: Prerequisites: CSE 625.
CSE 725 is a continuation of the material covered in 625.

CSE 780: Analysis of Algorithms: Prerequisites: CSE 680.
Prerequisite for: CSE 725.
Students in CSE 725 benefit from an understanding of algorithmic efficiency and the simple complexity classes (for example, P) covered in 780.

2.2 Evaluation of courses

CSE 541 learning outcomes

1. Master using IEEE single precision floating point arithmetic standard.
2. Master single variable root finding.
3. Master numerical differentiation.
4. Master numerical integration.
5. Master Gaussian elimination with scaled partial pivoting.
6. Be familiar with loss of significant digits in numerical calculations.
7. Be familiar with polynomial interpolation.
8. Be exposed to bounding errors in differentiation, integration and interpolation.
9. Be exposed to iterative solutions of linear systems.
10. Be exposed to least squares fitting.
11. Be exposed to Monte Carlo simulation.

Root finding methods (outcome 2) are discussed at length. Students typically applying the methods to specific functions and are exposed to theoretical analysis of these methods. Numerical integration and differentiation methods (outcomes 3, 4, 10) are discussed at some length although the depth of discussion varies. Most students should be able to apply these methods and to understand some theory underlying the error analysis.

Gaussian elimination (outcome 5) is usually discussed in considerable detail. Most students are able to apply Gaussian elimination with pivoting and solve problems using Gaussian elimination.

Most 541 offerings include a significant programming/implementation component.

Changes from the previous report

 CSE 625 learning outcomes

1. Master using regular expressions, and finite state machines.
2. Master using push-down automata.
3. Master using regular and context-free grammars.
4. Be familiar with the properties of regular and context-free languages.
5. Be familiar with the pumping lemma for regular languages and its use to show that certain languages are not regular.
6. Be familiar with using Turing machines as a general computational model.

Toward the end of the quarter Turing machines, Church’s thesis is discussed (outcome 5). The students learn to construct simple Turing machines and are exposed to the concept of a universal Turing machine.

Changes from the previous report

The previous report contained "Be exposed to decision problems, including the halting problem" as an outcome.  There is often not enough time to cover the halting problem in CSE 625 and so we deleted it as an outcome.  The halting problem is discussed extensively in CSE 725. 

 CSE 680 learning outcomes

1. Master analyzing running time of for and while loops.
2. Master analyzing running time of simple iterative algorithms.
3. Master analyzing running time of simple recursive algorithms.
4. Master solving simple recurrence relations.
5. Master using asymptotic notation.
6. Be familiar with designing divide-and-conquer algorithms.
7. Be familiar with designing graph algorithms.
8. Be exposed to average case analysis.

Most students in CSE 680 achieve mastery of analyzing simple iterative and recursive algorithms and solving simple recurrence relations (obectives 1-3). Many students master use of asymptotic notation as well (objective 4). However, some students demonstrate that they are able to use asymptotics in simple situations or in situations that are very similar to examples done in class but are unable to generalize to different problems.

Difficult, open-ended homework problems are a hallmark of any serious algorithms class. Many of these problems involve designing an algorithm to solve some problem (often with a stated run-time bound). As such, any student who successfully completes CSE 680 will be familiar with designing divide-and-conquer (objective 5) and graph (objective 6) algorithms. While students will have differing degrees of success at this task, most students are able to design reasonable algorithms for non-trivial problems.

In a typical offering of CSE 680 students will see average case analysis of the Quicksort algorithm and may work on a homework problem on that topic. 

Changes from the previous report

2.3 Relation to BS-CSE Program Outcomes

1. an ability to apply knowledge of computing, mathematics including discrete mathematics as well as probability and statistics, science, and engineering;
2. an ability to design and conduct experiments, as well as to analyze and interpret data;
3. an ability to design, implement, and evaluate a software or a software/hardware system, component, or process to meet desired needs within realistic constraints such as memory, runtime efficiency, as well as appropriate constraints related to economic, environmental, social, political, ethical, health and safety, manufacturability, and sustainability considerations;
4. an ability to function effectively on multi-disciplinary teams;
5. an ability to identify, formulate, and solve engineering problems;
6. an understanding of professional, ethical, legal, security and social issues and responsibilities;
7. an ability to communicate effectively with a range of audiences;
8. an ability to analyze the local and global impact of computing on individuals, organizations, and society;
9. a recognition of the need for, and an ability to engage in life-long learning and continuing professional development;
10. a knowledge of contemporary issues;
11. an ability to use the techniques, skills, and modern tools necessary for practice as a CSE professional.
12. an ability to analyze a problem, and identify and define the computing requirements appropriate to its solution;
13. an ability to apply mathematical foundations, algorithmic principles, and computer science theory in the modeling and design of computer-based systems in a way that demonstrates comprehension of the tradeoffs involved in design choices;
14. an ability to apply design and development principles in the construction of software systems of varying complexity.

CSE 541: The learning outcomes of this course are:

1. Master using IEEE single precision floating point arithmetic standard.
2. Master single variable root finding.
3. Master numerical differentiation.
4. Master numerical integration.
5. Master Gaussian elimination with scaled partial pivoting.
6. Be familiar with loss of significant digits in numerical calculations.
7. Be familiar with polynomial interpolation.
8. Be exposed to bounding errors in differentiation, integration and interpolation.
9. Be exposed to iterative solutions of linear systems.
10. Be exposed to least squares fitting.
11. Be exposed to Monte Carlo simulation.

Summary:  Recent POCATs have included a question on relative error directly related to 541 topics. About 70% of the students answer this question correctly.  Almost all the incorrect answers were mistakes in the calculation of relative error, not fundamental mistakes in the understanding of the concept.  We think student performance is satisfactory on this question.

1. Master using regular expressions, and finite state machines.
2. Master using context-free languages, and push-down automata.
3. Master using regular and context-free grammars.
4. Be familiar with the pumping lemma for regular languages and its use to show that certain languages are not regular.
5. Be familiar with using Turing machines as a general computational model.

Summary:  POCATs include two questions related to CSE 625, one on writing a regular expression for a language and one on writing a grammar for a language.   About 70% of the students answer the regular expression question correctly.  About 90% of the students answer the grammar question correctly.  We think student performance on these two questions is very good.

1. Master analyzing running time of for and while loops.
2. Master analyzing running time of simple iterative algorithms.
3. Master analyzing running time of simple recursive algorithms.
4. Master solving simple recurrence relations.
5. Master using asymptotic notation.
6. Be familiar with designing divide-and-conquer algorithms.
7. Be familiar with designing graph algorithms.
8. Be exposed to average case analysis.

2.4 Changes since last report

3. Conclusions

People involved in preparing this report: Misha Belkin, David Mathias, Ken Supowit, Rephael Wenger.