Syllabus for the course CS 4390/5390, Fall 2005

Instructor: Vladik Kreinovich, office COMP 215, email

Class time: MW 6:00-7:20 pm, COMP 322

Office hours: MW 12:00-12:30 pm, 1:30-2:00 pm, 5:30-6 pm, 7:30-8 pm, or by appointment

Prerequisite: the only pre-requisite is Data Structures. If a student has taken either Matrix Algebra or Probabilities this will help, but it is still OK if a student has not taken any of these two classes.


MOTIVATIONS: our department is heavily involved in geoinformatics research; the current software engineering class is studying the inverse problems in geosciences; in view of this, it is beneficial for our students to have a special topics class that goes into more detail.


  1. We start with the general introduction to the inverse problem, learn why it is important, and what are the related computational challenges and the open problems.
  2. Then, we will discuss Hole's algorithm, the most widely used algorithm for solving practical problem. We will discuss the existing implementation of Hole's algorithms, and ideas for modifying this algorithm. Some of these ideas come from Hole himself, some are new.
  3. After that, we will overview different sophisticated algorithms proposed for solving the inverse problem in geoinformatics, with a special emphasis on the algorithms which use the shortest path algorithms well known in computer science.
  4. A special emphasis will be placed on the use of expert knowledge in solving the inverse problems, and in estimating the uncertainty of the resulting solutions.
  5. If time allows, we will also discuss issues related to parallelization.
In all these topics, there will be programming assignments to implement the algorithms that we are learning - at least on toy examples.

PROJECTS. After a few lectures, you will be given a list of projects to choose from - or you may be smart enough to propose something on your own. Practically useful projects are especially welcome.


1. Knowledge and Comprehension

a. Understand the corresponding geophysical problems and their importance for geological sciences.

b. Understand the complexity of these problems -- NP-hardness of many practical problems, imprecise character of expert knowledge, etc.

c. Know and understand the basic mathematics behind the studied algorithms.

d. Know the main ideas behind the algorithms for solving the inverse problem.

f. Understand the limitations of the inverse problem.

2. Application and Analysis

a. Use the mathematics behind the studied algorithms, on simple examples

b. Trace the main algorithms, on simple examples

c. Apply advanced state-of-the-art techniques for solving inverse problems to solve given problems

3. Synthesis and Evaluation

a. Design new algorithms to solve problems similar to the ones studied in the class.

b. Design programs which use studied techniques to solve reasonable size problems

c. Apply studied techniques to fully solve a practice-oriented problem (ideally related to the student's area of research): from extracting an appropriate sub-problem from the general problem to selecting the most appropriate techniques to actually using these techniques

NO BOOK. There is no textbook that would cover the class material. Instead, we will rely on handouts and web-based material.

TESTS AND GRADES: There will be two tests and one final exam. The first test will be in the middle of the semester, the second test will be in the last week of classes. The final exam is scheduled to be on Wednesday December 8, 7:00-9:45 pm.

Each topic also means home assignments. Maximum number of points:

(smart projects with ideas that can turn into a serious scientific publication get up to 40 points).

A good project can help but it cannot completely cover possible deficiencies of knowledge as shown on the tests and on the homeworks. In general, up to 80 points come from tests and home assignments. So:

STANDARDS OF CONDUCT: Students are expected to conduct themselves in a professional and courteous manner, as prescribed by the Standards of Conduct. Students may discuss programming exercises in a general way with other students, but the solutions must be done independently. Similarly, groups may discuss project assignments with other groups, but the solutions must be done by the group itself. Graded work should be unmistakably your own. You may not transcribe or copy a solution taken from another person, book, or other source, e.g., a web page). Professors are required to - and will - report academic dishonesty and any other violation of the Standards of Conduct to the Dean of Students

DISABILITIES: If you feel you may have a disability that requires accommodation, contact the Disabled Student Services Office at 747-5148, go to Room 106 E. Union, or e-mail to