Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site watrose.UUCP
Path: utzoo!watmath!watnot!watrose!jsgray
From: jsgray@watrose.UUCP (Jan Gray)
Newsgroups: net.cse
Subject: Re: Exams vs. Programming Assignments (really CS curricula (long))
Message-ID: <7595@watrose.UUCP>
Date: Mon, 7-Oct-85 11:10:38 EDT
Article-I.D.: watrose.7595
Posted: Mon Oct  7 11:10:38 1985
Date-Received: Tue, 8-Oct-85 03:23:54 EDT
References: <823@dataio.Dataio.UUCP> <6358@duke.UUCP> <827@dataio.Dataio.UUCP> <556@uwmcsd1.UUCP>
Reply-To: jsgray@watrose.UUCP (Jan Gray)
Organization: U of Waterloo, Ontario
Lines: 94
Summary: 

In article <556@uwmcsd1.UUCP> jerry@uwmcsd1.UUCP (Jerry Lieberthal) writes:
>> In reference to <6358@duke.UUCP> crm@duke.UUCP (Charlie Martin):
>> 
>> So you graduate, and you know specifics: 
>> 	1. Unix
>> 	2. recursive descent
>> 	3. quick-sort
>> 	4. linked lists.
>> 
>> 				Opinions from the keyboard of
>> 					Bjorn Benson
>
>Although I have no real argument against the above, from what I have seen,
>most of the course offerings that would solve some of the deficiencies are
>NOT at the undergraduate level.  Courses on algorithms, parsers, etc., are
>usually reserved for the graduate level (note that I am not making a comment
>on whether that is correct or not).
>
>	- jerry     University  of Wisconsin-Milwaukee
>		    Computing Services Division
>		    {ihnp4, uwvax, uwmacc}!uwmcsd1!jerry
>		    uwmcsd1!jerry@wisc-rsch.ARPA

At the University of Waterloo, all CS undergrads take:

CS360	Introduction to the Theory of Computing
	Models of computers include finite automata and Turing machines.
	Basics of formal languages with applications to syntax of programming
	languages.  Unsolvable problems and their relevance to the semantics
	of programming.  Concepts of computational complexity including
	algorithm optimality.

CS undergrads may take:

CS462	Formal Languages and Parsing
	Languages and their representations.  Grammars - Chomsky hierarchy.
	Regular sets and sequential machines.  Context free grammars -
	normal forms, basic properties.  Pushdown automata and transducers.
	Operations on languages.  Undecidable problems in language theory.
	Applications to the design of programming languages and compiler
	construction.

CS464	Computability and Recursive Function Theory
	Models of the computational process as reflected by computers,
	linguistic systems, functional specifications, transformational
	systems, formal logic, etc.  Equivalence of these models.
	Computational complexity for specific models and abstractions
	fitting all models.  Formal reducibilities between computational
	problems, and the complexity of theser reducibilities.

CS466	Algorithm Design and Analysis
	Design of good algorithms and analysis of the resources they consume.
	Lower bounds on the resource requirements of algorithms to compute
	certain functions.  Problems from the following areas are discussed
	in this light: sorting and order statistics, data structures,
	arithmetic computations, the NP-complete problems.

CS468	Program Verification
	Methods of program verification.  Implications for structured
	programming.  Inductive reasoning about recursive programs and
	recursively defined data structures.

Not every graduating CS student takes all of these 46x courses.  I have
a suspicion that most don't take any of them.  But they *are* offered
to those who *do* wish to learn more about CS theory.

On the other hand, almost all UW CS students take the following: (although
it is not a required "core" course)

CS180	Introduction to File Processing
	Introduction to the use of computers.  Concept of an algorithm.
	Language and the notation for describing algorithms.  Analysis
	and solution of problems dealing with files.  Introduction to
	a procedure-oriented language (usually COBOL).  The preparation
	and debugging of programs in such a language.  Topics include:
	file processing and maintenance, sorting, report generation,
	and file design.

This course allows UW CS students to compete with Bill's Business
School for summer jobs (Co-op jobs, as we say around here).  Freshmen
can take this course, or *no* CS course, in either their 1A or 1B term;
there is also a fairly good introduction to CS course, CS140, that *is*
taken by all CS freshmen.

It is my contention that if this course didn't exist, and the courses
in second and later years were moved forward one term, students would
be more advanced by the time they reached fourth year and would take
more of the CS46x (CS theory) type courses.

Sigh.

[Disclaimer: I am a CS undergraduate at UW]

Jan Gray   (jsgray@watrose)   University of Waterloo   (519)-885-1211 x3870