Scientific Computation

CSC 340

(DRAFT syllabus revision, 30 July 2016)

Introduction

CSC 340 will focus on the design, implementation, application, and performance of numerical algorithms that are fundamental to scientific computation. Skills gained from this course will allow students to bring together concepts gained in their science, mathematics and computer science courses and apply them to real problems.

 

CSC 340 is a course which seeks to integrate Science, Technology, Engineering and Mathematics (STEM) content. It is a part of the upper division course requirements for students taking the ABET (legally, the Accreditation Board for Engineering and Technology, Inc.) accredited Systems Option for a Bachelor of Science (BS) in Computer Science (CS). Students enrolled in CSC 340 are required to have taken calculus and data structures previously. In addition, many have fulfilled general education, degree requirements for the CS degree and have therefore taken a full year of a science, such as Biology, Chemistry or Physics, with a laboratory component. Many students have also fulfilled a general education requirement that they take an additional semester of a science in a discipline other than that used to fulfil the laboratory science requirement.

 

CSC 340 requires that students build computational tools (Technology) and then apply those tools to find solutions for common practical problems (Science, Engineering and Mathematics--SEM). Typical problem areas include machine learning to automate classification (Mathematics/Statistics), optimization (SEM), and signal processing (SEM). Example problems include automatically creating machines that can:

1.      Minimize error while classifying objects using only data measurements,

2.      Reduce the travel distance of a robot arm whose work involves placing chips in a printed circuit board, and

3.      Echolocate to find the distance to a target, such as prey.

In each case, there is an underlying scientific problem that motivates a mathematical model and an engineering implementation of a computational machine.

P1

Consider a problem illustrated in Fig.1. The blue diamonds and red squares are located at points corresponding to two measurements of objects. It is clear that the measurements are clustered around distinct central areas and dispersed differently with respect to the horizontal and vertical axes. For example, notice that the diamonds seem centered near (2,0) and they are spread out further horizontally than vertically.

 

Notice also that is difficult to describe a simple contour that would delineate a boundary between the diamonds and squares. Accordingly, one might seek parameters for a simple boundary that would minimize misclassifications and remain sensitive to the structure evident. Fortunately, if the measurements are multivariate normally distributed, there is mathematical tool that can enable one to form such boundaries. Specifically, the functions: 

grade the degree to which the measurements given in x correspond to those of object known to be in class i, where  is the mean of class i,  is the a priori probability for class i, and is the covariance matrix for class i. There is a function gi for each class i, and one need only calculate the necessary means, covariance matrix, covariance matrix inverse and covariance matrix determinant, and then compare values of gi in order to classify previously unobserved examples x. The class function g that gives the largest value for x identifies the class into which x should be classified. By creating the computational components to perform these matrix operations and comparisons (Technology), students gain practical experience with mathematical tools (Mathematics), such as matrices, in the context of a prototypical scientific or engineering application (Science and Engineering).

 

Fig. 1. Data representing a machine learning classification problem.

 

P2

A second example problem is that of minimizing the distance traveled by a robot arm as it loads with electrical components, places the components on a printed circuit board and then returns to reload in preparation to populate another board. Suppose that Fig.2 illustrates a map of component positions on a printed circuit board. One may seek to find a minimum length path that would take the part dispenser to every one of the 14 points on the map and then return to reload. Various techniques may be applied to find such a path. A naïve approach might seek to enumerate all possible paths (Technology and some Engineering) and then simply pick the shortest; however, with 14 positions, there are 13!/2 distinguishable paths, and in general, with n sites there are n!/2 distinct paths to consider. For small instances, exhaustive enumeration is reasonable but for many practical problems, it is not.

Thus, students explore a benchmark problem with a variety of approaches (Engineering and Technology) or heuristics including randomly creating candidate paths, simulating (Technology) an annealing process (Science and Engineering) and mimicking the computation possible through an evolutionary process such as a genetic algorithm (Science, Engineering and Technology). Thereupon, students are required to implement alternative algorithms and then to assess the relative merits of each approach (STEM is blended).

Fig. 2. A map of component positions on a printed circuit board.

 

P3

A third example studied in CSC 340 arises naturally in the echolocation techniques employed by dolphins or bats, and it has been widely implemented in electronic and computational machinery for sonar (sound ranging) and radar (radio ranging). The basic idea is that a signal is transmitted, such as an acoustic pulse, and a receiver “listens” for an echo of the signal. This scenario is illustrated in Fig. 3, which shows a pulse on the left and a received signal on the right. As one would expect, the returned signal (echo) is a noisy approximation to that which was transmitted and is embedded in ambient noise. Thus, one should seek a “good” match rather than an exact match to occur within the received signal. That match is measured using mathematical correlation and the computation of a measure of correlation may be done in a variety of ways. During the course students implement (Technology) the fast Fourier transform (FFT) and then apply their implementation to find not only correlation (Mathematics), but also to perform convolution, to smooth out noisy signals, and to model periodic data (Science and Engineering).

       

Fig. 3. A transmitted pulse and a noisy received signal containing an echo of the pulse.

 

Student Learning Outcomes (SLOs)

  1. Students develop knowledge of computer data representation and its relationship to computational error and error propagation.
  2. Students demonstrate knowledge of vector and matrix operations including addition, subtraction, transpose, multiplication, and inverses by implementing and applying algorithms for each.
  3. Students learn how to find and use eigenvectors and eigenvalues and students implement programs to find these.
  4. Students implement and learn to use signal processing algorithms.
  5. Students implement and learn to use programs to fit data using both linear and nonlinear functions.
  6. Students develop a knowledge of algorithm and implementation alternatives that enables them to choose appropriately.
  7. Students develop skills in writing technical reports that describe findings that arise from application of software that they develop.
  8. (iSTEM) Students demonstrate knowledge from two or more STEM disciplines.
  9. (iSTEM) Students apply STEM problem solving methodologies, such as the scientific method, the engineering design process, or modeling, to real-world problems.

Schedule

This semester, the course meets Tuesday and Thursday from 9:30-10:45 AM in CIS 2006. A detailed schedule of topics that will be presented week-by-week, as well as all project due dates and requirements, may be found by following the “schedule” link above.

Text

Robert J. Schilling and Sandra L. Harris, Applied Numerical Methods for Engineers Using Matlab and C, Brooks/Cole Publishing Company, New York, NY, 1999, ISBN 0-534-37014-4.

Grading

Routine

Notice the SLOs given above. The SLOs make this an algorithms-oriented course. For you to have a context in which to demonstrate clearly and unequivocally that you have mastery of the algorithms, the grading scheme reflects a strong emphasis on implementing computer algorithms and applying them to various problems. Thus, you will be asked to engage three projects for which you may apply your personal implementations of the studied algorithms: one is a machine learning task (creating a classifier), the second involves methods for finding solutions for optimization problems (e.g. the traveling salesman problem), and the third focuses upon digital signal processing (for classification, filtering and sonar or radar ranging). Grading will be based upon performance on the projects, identified hereafter as examinations. The first two projects/examinations will be worth a total of 60% (each worth 30%) and the final project/examination will be worth 40% of the final grade. The projects will demand implementation, validation, demonstration, and application algorithms taught during the course and for these, you are required to employ your own personal implementations of each of the algorithms and methods studied.

 

Notice that correct, personally programmed implementation is a central component of this course, critical to validation, demonstration, and application, and therefore, must be taken very seriously. You may NOT use the library features of any programming language as a source for the analytical results you submit. For example, many languages possess libraries for matrix operations (e.g., NumPy) and you may use such built in functions to verify your implementations; however, you are required to implement all specified algorithms yourself and except for test/verification purposes, use of NumPy is specifically prohibited, except to verify your personal implementations of various algorithms. The point is to show what you can do, not to showcase what language library authors can do.

Incomplete grades

Incomplete grades are given only very rarely and only when the student is

-        otherwise passing the course,

-        able to complete the work of the course entirely on his/her own, and

-        prevented from completing the course by verified unforeseen circumstances beyond the control of the student. 

The instructor MUST be able to certify all three of these factors to the chair before assigning a grade of "I".

Contact Information

Instructor:

Gene A. Tagliarini, PhD

Professor of Computer Science

Office:

CIS 2038

Phone:

962-7572

Office Hours:

M&W, 9:00-11:30 AM, and T&R 3:30-4:30 PM

Other office hours are available by appointment. Please email for confirmation.

E-mail:

tagliarinig@uncw.edu

Other Administrative Matters

Attendance Policy

Regular attendance and vigorous participation in class are expected but not required.  However, if you desire the "benefit of the doubt" in any matter related to your grade in the class, you will routinely be present, ask relevant questions, and cooperate with the instructor as well as the course objectives.  Each student is individually and personally responsible for all material covered during each class meeting.

Americans with Disabilities Act

If you have a disability and need reasonable accommodation in this course, you should inform the instructor of this fact in writing within the first week of class or as soon as possible.  If you have not already done so, you must register with the Office of Disability Services in Westside Hall (ext. 3746) and obtain a copy of your Accommodation Letter.  You should then meet with your instructor to make mutually agreeable arrangements based on the recommendations of the Accommodation Letter.

Course Assessment Plan

Course Student Learning Outcomes and Course Assessment Plan

Assessment Instruments

Course Student Learning Outcomes

Project 1

Project 2

Project 3

Final Exam

1

Students develop knowledge of computer data representation and its relationship to computational error and error propagation.

X

2

Students develop knowledge of vector and matrix operations (e.g., addition, subtraction, transpose, multiplication, inverse).

X

3

Students learn how to find and use eigenvectors and eigenvalues and students implement programs to find these

X

4

Students implement and learn to use signal processing algorithms.

X

5

Students implement and learn to use programs to fit data using both linear and nonlinear functions.

X

6

Students develop a knowledge of algorithm and implementation alternatives that enables them to choose appropriately.

X

7

Students develop skills in writing technical reports that describe findings that arise from application of software that they develop.

X

8

(iSTEM) Students demonstrate knowledge from two or more STEM disciplines.

 

X

X

X

9

(iSTEM) Students apply STEM problem solving methodologies, such as the scientific method, the engineering design process, or modeling, to real-world problems.

 

X

X

X