Foundations Course Group Status Report

1. Summary

2. Detailed Analysis

Section 2.1 describes the individual courses in the group. Section 2.2 explains how the group is related to the rest of the CSE program. Section 2.3 explains how the group helps meet a range of CSE and ABET objectives. Section 2.4 provides information on the feedback we have received from students, recruiters, etc. about the courses in the group. Section 2.5 summarizes the changes we are considering in the various courses.

2.1 Summary of the courses

CIS541: Elementary Numerical Methods  is a survey of basic numerical methods.  The course covers number systems and errors of finite representation, solution of a single non-linear equation, interpolation numerical integration, and solution of linear systems.  In the final weeks, either interval arithmetic or least squares curve fitting are covered.

CIS625: Introduction to Automata and Formal Languages is a standard undergraduate course in automata theory and formal languages.  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.

CIS642: Numerical Linear Algebra is a continuation of CIS541 focusing on numerical linear algebra.  It covers iterative methods for the solution of linear systems, computation of eigenvalues and eigenvectors, linear programming-simplex method and use of standard mathematical software libraries.

CIS680: Data Structures is a course in advanced data structures, although the course content has varied somewhat depending on the instructor.  It is currently under revision.  The proposed revision refocuses the course on basic algorithm analysis, with analysis of data structures as a subtopic.  In particular, undergraduate students should be able to analyze the  asymptotic running time of while and for loops, simple recursive programs, operations on binary search trees, and simple graph algorithms.

CIS725: Computability and Unsolvability is a graduate course in decidability and NP-completeness.  It is required of all CIS graduate students.  The course covers Turing machines, Church's thesis, recursive and recursively enumerable languages, self replicating programs, polynomial time and NP-completeness.  The material on  NP-completeness was recently moved from CIS 780 to CIS 725 where it naturally fits.  Recursive function theory was dropped from CIS 725.

CIS727: Computational Complexity is a continuation of complexity theory from CIS 725.  It covers a variety of complexity classes, including space complexity, randomized complexity classes, public key cryptosystems and PSPACE.  The course is offered every other year.

CIS780: Analysis of Algorithms is a graduate course in algorithms.  It is required of all CIS graduate students.  The course covers divide and conquer algorithms, greedy algorithms, dynamic programming, and graph algorithms. The material on NP-completeness was recently moved from CIS 780 to CIS 725 where it naturally fits.

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

CIS541: Elementary Numerical Methods: Prerequisites for CIS 541 are CIS 221, computer programming, and Math 153, third quarter calculus.  Non-CIS majors also take this course and substitute CIS 201 or EG 167 for the CIS 221 requirement.

CIS625: Introduction to Automata and Formal Languages: Prerequisites for CIS 625 are CIS 321 and Math 366. CIS 625 is a prerequisite for CIS 655, programming languages, and CIS 725, computability and unsolvability.  CIS 725 is a continuation of the material in CIS 625.  Students in CIS 655 need to be familiar with formal languages, particularly with formal grammars.

CIS642: Numerical Linear Algebra: Prerequisites for CIS 642 are CIS 541 and Math 568 or 571, linear algebra.

CIS680: Data Structures: Prerequisites for CIS 680 are CIS 560 and CIS 570, Stat 427 and Math 366.  CIS 680 is a prerequisite for CIS 780.

CIS725: Computability and Unsolvability: The prerequisite for CIS 725 is CIS 625.  CIS 725 is continuation of the material in CIS 625.

CIS727: Computational Complexity: The prerequisite for CIS 727 is CIS 725.  CIS 727 is a continuation of the material for CIS 725.

CIS780: Analysis of Algorithms: The prerequisite for CIS 780 is CIS 680.

2.3 Relation to CSE and ABET objectives

The courses in this group play a key role in meeting both CSE program objectives as well as ABET Criterion 3 objectives. In Section 2.3.1 we consider the CSE objectives that this course group helps us meet, and in Section 2.3.2 we consider the ABET objectives.

The courses in this group play a key role in meeting both CSE program objectives as well as ABET Criterion 3 objectives. In Section 2.3.1 we consider the CSE objectives that this course group helps us meet, and in section 2.3.2 we consider the ABET objectives.

2.3.1 CSE Objectives

Objective 1.To provide graduates with a thorough grounding 
in the key principles and practices of computing, and in 
the basic engineering, mathematical, and scientific principles
that underpin them. Students will: 
  a.Demonstrate proficiency in the areas of software 
    design and development, algorithms, operating systems, 
    programming languages, and architecture. 
  b.Demonstrate proficiency in relevant aspects of mathematics, 
    including discrete mathematics, as well as the appropriate 
    concepts from physics and electrical circuits and devices. 
  c.Successfully apply these principles and practices to a 
    variety of problems. 

Objective 2.To provide graduates with an understanding 
of additional engineering principles, and the mathematical 
and scientific principles that underpin them. Students will: 
   a.Demonstrate an understanding of differential and 
     integral calculus, differential equations, physics 
     and several areas of basic engineering sciences. 
   b.Have the ability to work with others and on 
     multi-disciplinary teams in both classroom and 
     laboratory environments.

Objective 3.To provide graduates with an understanding of 
the overall human context in which engineering and 
computing activities take place. Students will: 
  a.Demonstrate an ability to communicate effectively. 
  b.Obtain familiarity with basic ideas and contemporary 
    issues in the social sciences and humanities. 
  c.Obtain an understanding of social, professional 
    and ethical issues related to computing. 

Objective 4.To prepare graduates for both immediate 
employment in the CSE profession and for admission to 
graduate programs in computing. 
   a.A large fraction of graduates will be immediately 
     employed in high-technology companies that utilize 
     their computing education. 
   b.Strong graduates from the program will be prepared 
     to enter good graduate programs in CSE

2.3.2 ABET Criterion 3: Program Outcomes and Assessment

Engineering programs must demonstate their graduates have:

   a.  an ability to apply knowledge of mathematics, science, and engineering
   b.  an ability to design and conduct experiments, as well as analyze and interpret data
   c.  an ability to design a system, component, or process to meet desired needs
   d.  ability to function on multi-disciplinary teams
   e  an ability to identify, formulate, and solve engineering problems
   f.  an understanding of professional and ethical responsibility
   g.  an ability to communicate effectively
   h.  the broad education necessary to understand the impact of engineering solutions in a global and societal context
   i.  a recognition of the need for, and an ability to engage in life-long learning
   j.  a knowledge of contemporary issues
   k.  an ability to use techniques, skills, and modern engineering tools necessary for engineering practice.

The foundation courses contribute strongly to ABET criterion 3a; and moderately to criteria 3c, 3e, 3i and 3k.   The numerical analysis courses contribute strongly to criterion 3a;  and moderately to criteria 3b, 3c, 3e, 3i, and 3k.  The foundation courses and the numerical analysis courses are heavily oriented toward learning and applying mathematics to problems computer science.  They involve a substantial amount of problem solving on homeworks and exams.
 

2.4 Feedback

2.5 Possible changes

The recent revision in the beginning software sequence (CIS 221, 222, 321) has moved a considerable amount of software engineering material that had to be covered in CIS 680 to the beginning sequence, especially CIS 321. A proposed revision focuses CIS 680 more sharply on algorithm design and analysis issues.  The proposed revision makes CIS 680 and CIS 780 more cohesive, similar to other 600 and 700 level pairs.

CIS 725 and CIS 780 recently underwent minor changes with material on NP-completeness moved from CIS 780 to CIS 725.
 

3. Conclusions

People involved in preparing report: Tamal Dey, Steve Lai, Ken Supowit, Rephael Wenger

Date of report: Nov. 2, 1999