Course Number *: 765-433                Effective: FALL 2001

Course Title: Theory of Algorithms
15 Character Abbreviation: Algorithms
25 Character Abbreviation: Theory of Algorithms

Sponsor: Jonathan Kane
E-mail Address: kanej@mail.uww.edu
Department: Mathematical and Computer Sci.
College: Letters & Sciences

Other Programs Affected: Mathematics Major, Computer Science Minor

Check if course is to meet any of the following requirements:
None Writing Computer Diversity General Ed and Area

Contact hours/credits: 16          Total lecture hours: 48
Total lab hours: 0                      Total contact hours: 48
Number of credits 3

Check if course is repeatable: No Yes (if yes answer the following questions)
No of times in major                 No of credits in major
No of times in degree               No of credits in degree

Enter the appropriate titles if the course is required in any of the following:
Major Title(s)
Minor Title(s)
Emphasis Title(s) Computer Mathematics Major

Course justification:
A course in algorithms is essential for the student of computer science to understand how to determine the efficiency of an algorithm. It is also import in that it shows a student that some problems succumb to many natural solution methods which need to be compared in order to select a method either efficient in time or in memory usage (space). Although many students of computer programming may not see this material, one would want a student receiving a degree in theoretical computer science to have a firm grasp of this material. For this reason this course is necessary for the proposed Computer Mathematics emphasis in the Mathematics Major and would be valuable as an elective course in both a future major in Computer Science and the current Computer Science minor.

Relationship to program assessment objectives:
This course not only gives the student many problem solving techniques, it gives the student tools necessary to compare these techniques in order to determine the best solution possible for a particular computational problem. Thus, this course meets the objective of covering practical problem solving skills and, beyond this, covers methods by which those problem solving techniques can be analyzed.

Budgetary impact:
The Department of Mathematical and Computer Sciences currently has faculty prepared to teach this course. If the Computer Mathematics emphasis in the Mathematics major is approved, this course would have to be taught on a biannual basis. The department is currently involved in searches for three new faculty with expertise in Computer Science. The filling of these positions will allow this new course to be offered.

Course description:
This course is a survey of algorithms needed for searching, sorting, pattern matching, analyzing graphs, and a variety of other problems of discrete mathematics. Analysis of algorithm efficiency and space/time tradeoffs are discussed.

Course requisites:
Prerequisites 760-280 and either 765-372 or 950-231

Course objectives and tentative course syllabus:
In this course students will learn many common algorithms needed to solve standard problems with computers. We will discuss methods of searching and sorting data. We will look at standard algorithms to perform common mathematical operations. Time will be spent discussing algorithms needed to solve many of the graph theory and combinatorial problems of discrete mathematics. Moreover, we will discuss the efficiency of these algorithms and learn to compare algorithms to see which are either the fastest or the best use of computer memory.

Topics
Week 2:    Models of Computation and basic efficient algorithms
Week 2:    Sorting
Week 1:    Set Manipulation
Week 3:    Graph Algorithms
Week 1:    Searching and Pattern Matching
Week 4:    Mathematical Problem Solving
Week 2:    Algorithm efficiency

Bibliography:
Aho, Alfred, John Hopcroft, and Jeffrey Ullman The Design and Analysis of Computer Algorithms Addison-Westley 1974.
* Atallah, Mikhail J. Algorithms and theory of computation handbook CRC Press, 1999.
*Lewis, Harry R. and Christos H. Papadimitriou Elements of the theory of computation Prentice-Hall, 1981.
*Hopcroft, John E. and Jeffrey D. Ullman Introduction to automata theory, languages, and computation Addison-Wesley, 1979.
*Machtey, Michael and Paul Young An introduction to the general theory of algorithms North-Holland, 1978.
*Denning, Peter J., Jack B. Dennis, and Joseph E. Qualitz Machines, languages, and computation Prentice-Hall,1978
Alavi, Yousef Graph theory, combinatorics, algorithms, and applications Society for Industrial and Applied   Mathematics, 1991.
Thulasiraman, K. and M.N. S. Swamy Graphs : theory and algorithms Wiley, 1992.
Nishizeki, Takao and N. Chiba Planar graphs : theory and algorithms Elsevier Science Pub. Co., 1988.
Markov, Andrei Andreevich The theory of algorithms Kluwer Academic, 1988.
Machtey, Michael and Paul Young An introduction to the general theory of algorithms North-Holland, 1978.

*Currently available in the UW-Whitewater library