HomeQuestions?




The Undergraduate Syllabus in Computer Sciences

Department of Computer Sciences
The University of Texas at Austin
Austin, Texas 78712




Prepared by: James Bitner, Robert Chanon, Nell Dale, Jayadev Misra, Erna Pearson, James Peterson, and James Sneeringer




With assistance from

Alan Cline, Andy Sherman, Raymond Yeh




April 20, 1977






UNDERGRADUATE COURSES




Department of Computer Sciences The University of Texas at Austin




1. Introduction

Undergraduate offerings incorporate a course sequence covering introductory and intermediate topics in the properties of algorithms, machine organization, information structures and the structure of programming languages. Practice in programming in several computer languages, including an algorithmic language, an assembly language and a list processing language, is given as part of this course sequence. The undergraduate courses conform to the recommendations of the Association for Computing Machinery (ACM).

Additional upper-division undergraduate courses cover topics in introductory numerical analysis, non-numerical applications, computer and programming systems, computer system architecture, operating systems, systems modelling, computer graphics, automata theory, artificial intelligence and algorithmic languages and compilers.

This document has been prepared by the Undergraduate Studies Committee to provide basic information for instructors and students concerning the undergraduate curriculum.

2. Intent

Each undergraduate course is described briefly here. These descriptions will hopefully serve several functions. First, they should be helpful in advising students on courses and determining programs of study resulting in a Bachelor of Arts degree in Computer Sciences. These notes will help both the students and their advisors in this task.

Second, they are to be taken as guidelines for the instructors teaching these courses. Many of these undergraduate courses are prerequisites to later undergraduate and graduate courses. In order for the later courses to be able to build upon the content of earlier courses, it is necessary that the content of the courses at the undergraduate level be somewhat standardized. Any desire to vary widely from the published course content should be taken directly to the Undergraduate Studies Committee.

This document should not be taken, however, to limit an instructor in terms of order of material, method of presentation, assignments, examinations, texts, projects, or supplementary materials. The teaching of each class is properly left as the responsibility of the instructor who should conduct each class as appropriate, keeping in mind the overall educational goals of the University, the College of Natural Sciences and the Department of Computer Sciences.

3. Format of the Course Descriptions

Each course is described briefly and in a uniform manner. The categories for each course description are,

   1.   Catalogue Description

   2.   Intent

   3.   Curricular Position and Degree Relevance

        3.1  Prerequisites
        3.2  Courses Requiring This Course
        3.3  Degree Relevance

   4.   Format

   5.   Syllabus

   6.   Possible Texts

4. Course Numbering

As the Department and the study of computer sciences has changed, so have some of the course numbers assigned to courses. No course number can be reused, but old courses are sometimes redefined under new numbers.

The most prominent example of this starts with CS 340 and ends with CS 426 and CS 327 (so far). The original course CS 340, was split into two new courses, CS 316 and CS 317. After some experience, these courses were changed to CS 326 and CS 327 (making them upper division). The most recent change was to rename CS 326 as CS 426, to reflect the actual work load of the course.

Other changes to course numbers in this same vein are,

   CS 105   became CS 206 (Fortran) and CS 135 (Other languages)

   CS 310   became CS 410

The consequences of these changes relate only to students who have already taken one of these courses under the older, no longer used, course numbers. A student with credit for CS 310, cannot gain credit for CS 410. A student with credit for CS 340 cannot gain credit for CS 426 or CS 327. However, any course which requires these courses as prerequisites will assume that the student knows the content of the new course. Students with these problems should see the Undergraduate Advisor.

5. Degree Requirements

The requirements for a Bachelor of Arts degree in Computer Sciences have three main sources.

  1. The University of Texas at Austin

  2. The College of Natural Sciences

  3. The Department of Computer Sciences
To receive a degree, all of these requirements must be met. We paraphrase here the basic requirements. The complete, official requirements are published elsewhere and nothing stated here should be taken to alter those requirements. We simply list the general requirements which affect most CS students. For an official statement, check the University Catalogue.

5.1. University Requirements

  1. A total of 120 hours, GPA of at least 2.0

  2. At least 30 hours in residence

  3. At least 36 hours of upper-division.

5.2. College of Natural Sciences Requirements

  1. English. Either one of the following two sequences.
    1. 306, 307 and one of 310, 312L, 312M, 314K, or 317.

    2. 306, 308 and one of 312L, 312M, or 314K.
    We recommend the sequence 306, 307, 317. English 317, Technical Writing, is very useful for computer sciences majors due to the technical nature of most of computer sciences.

  2. Foreign Language. A proficiency level equivalent to two years of a foreign language. For students going on to graduate school, we would suggest French, German, or Russian. Spanish is a reasonable language for those intending to stay in the Southwestern U.S., or considering employment in Central or South America.
    It is strongly recommended that students start work on their foreign language requirement as soon as possible.

  3. Legislative Requirements.
    1. Six hours of American Government and

    2. Six hours of American History.


  4. Social Sciences. Two courses in social sciences, one each from any two of the following areas:
    	Anthropology		Linguistics
    	Economics		Psychology
    	Geography		Sociology
    


  5. Natural Sciences. Six hours from any of the following departments.
    	Astronomy		   Physical Anthropology
    	Biology			   Physical Geography
    	Botany			   Physical Science
    	Chemistry		   Physics
    	Experimental Psychology    Zoology
    	Geology			   Microbiology
    


  6. Culture. Six hours from the following areas.
    1. Architecture

    2. Classics: Classical civilization, Greek, Latin

    3. Fine Arts: Art, drama, music

    4. Philosophy

    5. Interdisciplinary courses
    PHL 344K, Symbolic Logic, is of interest to some computer science students.

5.3. Departmental Requirements

  1. Calculus (M 808a and M 808b, or M 608Ea, M 608Eb, and M 325) and M 311.

  2. CS 327

  3. Twenty-one hours of upper-division computer science, in addition to the hours in (2) above. (Total upper-division hours is thus at least 24).

  4. No more than one CS 370.

  5. A grade of C or better in all of the above.

6. Honors Program

Majors who are candidates for Special Honors in Computer Sciences should apply to the Undergraduate Advisor for admission to the Honors Program at least two semesters before their expected graduation (i.e., near the end of their junior year). An all-University average of 3.0 and an average of 3.5 in all courses taken in Computer Sciences and all other courses counting toward the computer sciences major requirement (i.e., Calculus and M 311) are required for admission to the Honors Program.

The requirements for graduation with Special Honors are,

  1. CS 379H, Honors Tutorial Course, with a grade of B, or better;

  2. an all-University average of 3.0, and an average of 3.5 in courses taken in computer science and all other courses counting toward the computer sciences major requirements;

  3. a thesis, written on the subject of a student's research and approved in comprehensive examination by a committee consisting of at least three faculty members, including the Honors Advisor; and

  4. at least sixty semester hours of course work completed at the University of Texas at Austin and counted toward the degree.

CS 301

1. Catalogue Description

301. Computers in the Modern World. - A survey course designed to give a basic knowledge of the computer and its uses to people who do not wish to specialize in computer sciences; after an introduction to basic concepts, a number of applications of computers are studied within the context of the modern world. This course does not lead to further work in computer sciences and may not serve as a prerequisite for any other computer sciences course.

2. Intent

This course is intended for students who desire some familiarity with the computer field, but who neither want a typical programming course nor intend to take any other computer sciences courses. The course acquaints students with:

  1. What a computer is, how it works and what it is used for.

  2. The vocabulary of computer sciences.

  3. The effects of computers and the computer industry on society, economics, other technologies, etc.

3. Curricular Position and Degree Relevance

3.1. Prerequisites

None

3.2. Courses Requiring This Course

None

3.3. Degree Relevance

This lower-division course cannot be used to fulfill the computer sciences major requirement or to serve as a prerequisite for any other computer sciences course. It is not recommended even as an elective on the computer sciences degree. Because of overlap of content, students should not take both STAT 310 (College of Business Administration) and CS 301.

4. Format

Three hours of lecture per week with extensive use of visual aids, guest lecturers and demonstrations. In addition, students may use the facilities of the Undergraduate Programming Laboratory to learn to program and to solve problems using the BASIC language.

5. Syllabus

Topics to be covered (Sequence will vary)

Origins of the computer
      A brief historical introduction.

Basic Computer Organization

     1)  Input Unit
     2)  Output Unit
     3)  Memory Unit
     4)  Arithmetic Unit
     5)  Control Unit

Construction (historical perspective)


Logic   1)  Mechanical
        2)  Electrical
        3)  Electronic:
                   a)  Vacuum tube
                   b)  discrete (diodes and transistors)
                   c)  integrated circuits
                   d)  large scale integration

Memory   1)  Early (delay line, electrostatic, etc.)
         2)  Core
         3)  Recent developments

Basic Computer Operations

Computer Languages

     1)  Machine language
     2)  Assembly language
     3)  Procedural language (BASIC)

Production of a Computer Program

       1)  Defining the problem
       2)  Planning:
                        a.  Flow-charting, looping
                        b.  Conversion to statements
                            in a procedural language
       3)  Translation to machine language (compilation)
       4)  Checkout (debugging)
       5)  Production runs
       6)  Documentation and maintenance

Computer Applications

       1)  Data Processing, File Maintenance

                      a.  Preparation and maintenance
                          of files on magnetic tape
                      b.  Use of discs, drums

       2)  Engineering arithmetic
             Fixed and floating point
             Iteration
             Computational Precision

       3)  Software:

              Assemblers, compilers and interpreters

              Operating systems
                       a.  Concepts and problems concerning
                           batch, multi-processing, multi-
                           programming, conversational time
                           sharing systems and real-time
                           control systems

              Service routines

       4)  Real time applications

       5)  Miscellaneous applications
               a)  Language processing
               b)  Computer-Aided Instruction (CAI)
               c)  Computer graphics
               d)  Artificial intelligence
               e)  Information retrieval
               f)  System modelling

A Look into the Future

       a)  Hardware
       b)  Software
       c)  Applications

Moral Problems and Legal Problems

	a) Immoral applications
	b) The privacy issue

6. Possible Texts

Dorf, "Computers and Man", Boyd and Fraser, 1974.
Smith, "BASIC User's Manual", UT Computation Center, 1975.
Spencer, "Guide to BASIC Programming", Addison-Wesley, 1975.

CS 404

1. Catalogue Description

404. Introduction to Computer Sciences. - Basic concepts and properties of algorithms for solution of numerical and nonnumerical problems, including running of programs on a computer; survey of computer applications. Prerequisite: Three hours of mathematics or consent of course coordinator. Three lecture and two laboratory hours a week for one semester. Laboratory fee, $4.

2. Intent

CS 404G is intended to provide the basic knowledge and experience necessary to use computers effectively in problem solving. It is a service course for students in other fields as well as an introductory course for computer sciences majors.

Among the primary goals of this course are to teach the student:

  1. about computers, how they are organized and how they represent and manipulate information;

  2. how to analyze problems and how to develop and analyze algorithms to solve these problems;

  3. how to program, in the sense of choosing data structures and control organization, debugging, etc.;

  4. how to code in FORTRAN;

  5. about various applications of computers and various standard programming devices.

CS 404A is an advanced version of CS 404G, intended mainly for computer sciences majors and those students with previous exposure to computing. Both courses cover the same basic material, but 404A may go into additional depth and supplement the basic material with additional topics, covering this greater material at an accelerated pace.

3. Curricular Position and Degree Relevance

3.1. Prerequisites

A good foundation (3 years) in high school mathematics or three hours of college mathematics.

3.2. Courses Requiring This Course

        Course      Content/Skill From CS 404

         CS 410       Problem analysis and algorithm design;
                      elements of high-level language programming;
                      binary, octal and decimal number
                      representations and conversions.

         CS 325

	 CS 426

         CS 348       FORTRAN programming.

3.3. Degree Relevance

This lower-division course cannot be used to fulfill the computer sciences major requirement. It may be used to fulfill non-major requirements of the CS degree. It is important to recognize, however, that almost all upper-division CS courses depend on material covered in this course.

4. Format

Three hours of lecture and one two-hour laboratory per week. Lecture sections are large (50-150 students); laboratory sections have a maximum size of 25 students.

A large portion of teaching the selected programming language is delegated to the laboratory, which also provides help and information on the use of equipment, job submission, assigned projects, etc. From 8 to 10 programming problems are assigned as laboratory assignments.

Both laboratory and lecture must be passed to pass the course.

5. Syllabus

     Introduction to computers
            history
            general organization (memory, CPU, I/O)
            machine level (example of simple assembly language)
            levels of languages

     Problem solving*
            problem definition
            top-down problem solution
            concept of an algorithm
            flow chart language
            algorithm construction

     Programming techniques* - FORTRAN
            data structures (variables, arrays, strings, I/O)
            flow of control (loops, branching),
            subprograms (local versus global variables,
                             parameters and arguments)

     Software
            compilers (example of compiling simple FORTRAN
                  assignment and if statements into the
                  assembly language mentioned at the beginning)
            operating systems (loaders, assemblers, JCL)

* Problem solving and programming techniques are not
  distinct but interwoven.

6. Possible Texts

Conway, Gries and Zemmerman, "A Primer on Pascal", Winthrop, 1976.
Baldwin, J. and Baldwin, L., "Introductory Fortran for the Beginning Programmer", UT Computer Sciences Department, 1972.
Kennedy and Solomon, "Ten Statement Fortran", Prentice Hall, 1975.
Gear, C.W., "Introduction to Computer Science", SRA, 1973.
North, T., "Non-technical Fortran", Prentice Hall, 1976.

CS 206

1. Catalogue Description

206. FORTRAN Programming. - May not be used to fulfill the computer sciences major requirement. Training in the FORTRAN programming language for persons with no previous programming experience. No previous technical or mathematical training is necessary. Two lectures a week for one semester. Laboratory fee, $4.

2. Intent

This course teaches FORTRAN programming to persons who have no previous programming experience and who do not intend to continue in computer sciences.

3. Curricular Position and Degree Relevance

3.1. Prerequisites

None.

3.2. Courses Requiring This Course

None.

3.3. Degree Relevance

This lower-division course cannot be used to fulfill the computer sciences major requirement and does not serve as a prerequisite for any other course. It is not recommended even as an elective on the computer sciences degree.

4. Format

Two lectures per week for one semester, or three lectures per week for two-thirds of a semester, depending upon the instructor.

5. Syllabus

To be developed by the instructor

6. Possible Texts

Silver, G.A. and Silver, J.B., "Simplified ANSI FORTRAN IV Programming", (Second Edition), Harcourt, Brace, Jovanovich, 1976.

CS 410

1. Catalogue Description

410. Computer Organization and Programming - Basic computer organization; machine representation of instructions and data; machine language, assembly and macro-assembly languages, assemblers and loaders. Prerequisite:

Computer Sciences 404. Three lecture and two laboratory hours a week for one semester. Laboratory fee, $4.

2. Intent

This course broadens the foundation laid in CS 404 by familiarizing students with the fundamental operations of computers. This is the second course for computer sciences majors and for non-majors who want more knowledge of computers than is provided by the CS courses particularly designed for non-majors.

This course provides a fairly detailed introduction to the organization and structure of various types of computers; assembly language programming techniques using accumulator and index registers, indirect addressing, masking, shifting, character handling and I/O equipment; and the use and design of an assembler is used as an example.

3. Curricular Position and Degree Relevance

3.1. Prerequisites

CS 404 is the only required prerequisite. The specific knowledge needed from CS 404 is (l) how to design and write programs for solution of problems suitable to computer solution; (2) how to physically prepare and submit programs; (3) at least one higher level language (such as FORTRAN); (4) basic higher level language programming techniques such as loops, conditionals, I/O, data types, arrays, assignments, etc.; (5) elementary concepts of machine structure, binary number systems, memory, etc.
Note: Courses such as STAT 310, CS 301 and CS 206 are not acceptable as equivalents to the CS 404 prerequisite.

3.2. Courses Requiring This Course

CS 410 is a listed prerequisite for CS 345 and CS 352 and through these two courses provides background for additional courses also. Specifically, CS 410 must provide the following:

  1. Concepts of number representation and composition of data in computer memory, masking, packing, shifting (CS 426 and CS 352).

  2. Machine organization concepts (memory, ALU, registers, bits, interrupts, addressing calculations and modes) and different ways to organize a computer (CS 352).
  3. Assembly language programming, macros, subroutines (CS 426 and courses dependent on CS 426 such as 327, 345, 372 and 375).
  4. Systems programming techniques (CS 372).
  5. Basic language translation concepts (CS 345 and CS 375).

3.3. Degree Relevance

This lower-division course cannot be used to fulfill the computer sciences major requirement. It may be used to fulfill non-major requirements of the CS degree. It is important to recognize, however, that almost all upper-division CS courses depend on material covered in this course.

4. Format

Three hours of lecture and one two-hour laboratory per week. The lecture sections are large (50-150 students); laboratory sections have a maximum of 25 students.

The laboratories are used to provide detailed instruction in the machine and assembly language and to assign 6-7 programming problems. Programming problems begin with one designed to give familiarity with the format of assembly language statements and listings and with job submission, and proceed through problems covering character manipulation, table searching, I/O, loader and assembler. Laboratory and lecture are coordinated as to order and time of presentation of material, in so far as possible.

Students must pass both lecture and laboratory to pass the course.

5. Syllabus



Review of basic Machine Organization: memory, arithmetic logic unit (ALU), number representation, instruction interpretation.

The MIX machine: instruction set, machine memory, registers, I/O devices, effective address calculation.

The MIXAL assembly language: Symbolic opcodes and addressing, pseudo-ops

Program examples in Assembly Language: simple computations, looping indexing, searching, character handling, masking, shifting, packing, unpacking.

I/O programming: instructions, device characteristics, buffering, overlap of I/O and CPU operations, blocking, interrupts.

Subroutines and Parameters: call by value, reference and name; procedure and function parameters; where to pass parameters: registers, inline, tables, global; reentrant, recursive and pure code.

Loaders and Linkers: Absolute, relocatable, linking, entries and externals, bootstrap loaders.

Assemblers: One and Two pass, lexical scanning, opcode and symbol table structures, Pass I, Pass II, expression evaluation.

Macros: Macro usage, definition, macro-assembler structure, conditional assembly.

Other Machine Structures: IBM 360, CDC 6600, stack, microprogrammed, interpreters for other machines.

6. Possible Texts

Knuth, D.E., "MIX", Addison-Wesley, 1970.
"UT MIX Manual", UT Computer Sciences Department, 1972.
Peterson, J.L., "Notes on MIX", UT Computer Sciences Department, 1976.

CS 325

1. Catalogue Description

325. Discrete Mathematics. - Mathematical formalism, sets and binary relations, graphs, algebraic structures. Boolean algebras and logic, linearly ordered sets, elementary number theory, algorithms and computation. Prerequisite: CS 404 and M 808 or the equivalent.

2. Intent

The purpose of this course is to introduce the student to the basic mathematical techniques and structures that will be needed in order to build, analyze and evaluate programs and to understand the theory presented in other courses. Instead of going deeply into the various concepts, the instructor should show how they apply to computer science and discuss basic algorithms using them. These algorithms should be discussed at a conceptual level independent of any programming language, with emphasis given to their top-level design.

3. Curricular Position and Degree Relevance

3.1. Prerequisites

CS 404 is a prerequisite to assure that the student has an introduction to programming, algorithms and problem-solving, as well as the background to at least vaguely understand why these subjects are relevant to computer science. M 808 is required for mathematical maturity.

3.2. Courses Requiring This Course

CS 333 requires this course for its introduction to proofs, sets, and graphs.

3.3. Degree Relevance

This upper-division course (with a grade of C or better) may be used to fulfill the computer sciences major requirement. It is not required.

This course is recommended for students with an interest in mathematics and the formal theory of computer science.

4. Format

Three hours of lecture per week.

5. Syllabus

I. Algorithms
	effective procedures
	flow of control
	top-down designing of algorithms
	flowcharts
	Turing machines

II. Formal Proofs
	need for proofs
	principle of induction
	inductive assertion method for proving algorithm correctness
	proof by contradiction

III. Sets and Their Structure
	sets
	functions
	relations
	order relations
	sorting, consistent enumerations
	equivalence relations and partitions

IV. Combinatorics
	permutations and combinations
	recurrence equations
	generating functions
	cardinality of the union of sets

V. Graphs
	directed graphs
	undirected graphs
	connectedness
	minimal and critical paths
	labelled graphs
	trees and spanning trees
	graph searching and manipulation

VI. Finite Groups
	groups
	normal subgroups
	permutation, cyclic, quotient groups
	homomorphisms, isomorphisms

6. Possible Texts

Preparata and Yeh, "Introduction to Discrete Structures", Addison-Wesley, 1973.

CS 426

1. Catalogue Description

426. Data structures and Programming Concepts. - Only one of the following may be counted: Computer Sciences 426, 326, 316, 340.

Study of information representations and their relation to processing techniques; representations in various storage media and in various languages; file, list and string processing techniques; programming in a list structure language. Prerequisites: CS404. Three lecture and two laboratory hours a week for one semester. Laboratory fee, $4. (Prior to 1974-1975, given as Computer Sciences 340; in 1974-1975, given as Computer Sciences 316; in 1975-1976, given as Computer Sciences 326.)

2. Intent

This course introduces students to the types of structures inherent in and/or imposed on data; methods of representing these structures in storage; and techniques for operating on these structures. Students are introduced to languages (such as PASCAL and LISP) which are designed to facilitate defining and manipulating certain types of structures. In addition, program structure and systematic programming are emphasized.

3. Curricular Position and Degree Relevance

3.1. Prerequisites

CS 404 is required to ensure that students understand the use of computers and their programming.

CS 410 is suggested to ensure that students understand the structure of computers and computer memories and the digital representation of data and instructions.

3.2. Courses Requiring This Course

       Course       Content/Skills Furnished by CS 426

       CS 327       Data structure types and implementation
                    techniques; additional programming facility.
       CS 369

       CS 347

       CS 343       LISP programming concepts.

       CS 345       LISP and PASCAL language concepts.

3.3. Degree Relevance

Beginning with the 1977 Catalogue, this upper-division course (with a grade of C or better) may be used to fulfill the computer sciences major requirement. It is not specifically required on the computer sciences degree, but is a prerequisite to the required course CS 327 and other upper-division computer sciences courses. This course is strongly recommended for students who want to obtain programming training and experience without majoring in computer sciences.

4. Format

Three hours of lecture and one two-hour laboratory per week.

The laboratory is used for more detailed discussion of lecture material and programming assignments.

5. Syllabus

* Programming language Pascal: Elementary data and control structures; advanced data structuring mechanism (scalar and subrange type, arrays, records, pointers): procedures and functions; input and output.

* Systematic programming: Modular programming; bottom up and top down development; stepwise refinement; program validation; documentation rules.

* Linear lists: stack, queue, deque; sequential and linked allocation; traversals and searches on linked lists (ordered and unordered); circular, double linked lists; arrays.

* Trees: Basic terms; traversals of binary trees; representation of arithmetic expression; binary search trees; B-trees.

* Recursion and LISP: Notion of recursion; implementation of recursion; introduction to basic LISP.

* Searching: Sequential; binary; tree; digital; hashing

* Sorting (internal): Insertion; exchange; selection; merging; distribution.

* Dynamic storage allocation: first-fit, best-fit; buddy system.

6. Possible Texts

Horowitz, E. and Sahni, S., "Fundamentals of Data Structures", Computer Science Press, 1976.
Jensen, K. and Wirth, N., "PASCAL User Manual and Report", Springer Verlag, 1975.
Siklossy, L., "Let's Talk LISP", Prentice Hall, 1976.

CS 327

1. Catalogue Description

327. Programming Applications and Practice. - Computer Sciences 327 and 317 may not both be counted. Analysis, specification, program design, coding, debugging and documentation of selected programming problems; topics selected from simulation, text processing, content analysis, file management, graphics, or other current computer applications. Prerequisite: Computer Sciences 426. Laboratory fee, $6. (Prior to 1975-1976, given as Computer Sciences 317.)

2. Intent

This course is primarily concerned with developing good techniques in all phases of the design and implementation of programs. Students are intended to acquire greater programming breadth and facility and to experience individual and team participation on projects of larger dimension than are feasible in earlier courses. Structured programming and design methods are emphasized heavily. No new programming language is introduced in this course.

3. Curricular Position and Degree Relevance

3.1. Prerequisites

CS 426 is the only listed prerequisite for this course. Material needed from 426 covers data structure types and implementation techniques, PASCAL programming and additional maturity in the design and implementation of programs.

It should be understood, however, that CS 327 may also rely heavily on topics from 404.

3.2. Courses Requiring This Course

CS 372 and 375 require CS 327 as a prerequisite, since they both involve the design and implementation of large projects involved in systems.

3.3. Degree Relevance

This course (with a grade of C or better) is required for the CS degree. It is also highly recommended to non-majors who want to acquire considerable programming proficiency.

4. Format

Three hours of lecture per week. At the discretion of the instructor, lecture hours may be used for discussions, for team meetings, etc., after the major lecture material has been covered. A considerable amount of out-of-class work is required from the students.

5. Syllabus

Course lectures should include at least an introduction to the material indicated below. Additional lectures on the programming projects may be necessary. The intent of the projects for this course is to apply the lecture material to large projects providing both experience and reinforcement. The number of projects used within the course will vary from one to many; however, the number and size should allow students to complete their projects at a highly polished level, thus reinforcing the techniques involved.

I.  Program Design
          modular programming
          bottom-up versus top-down
          structured programming
          step-wise refinement
          decision-hiding decomposition
          goto controversy

II.  Program Style

III. Program Correctness

IV.  Program Efficiency
          execution time profile
          methods

V.   Program Testing and Debugging

VI.  Program Documentation

6. Possible Texts

Kernighan, B.W. and Plauger, P.J., "Software Tools", Addison-Wesley, 1976.
Jensen, K. and Wirth, N., "PASCAL User Manual and Report", (Second edition), Springer Verlag, 1974.
Yourdon, E., "Techniques of Program Structure and Design", Prentice Hall, 1975.

CS 333

1. Catalogue Description

333. Automata Theory. - Regular grammars and finite state automata; state graphs, syntactic monoids; context-free grammars and pushdown automata; ambiguity; context-sensitive grammars and Turing machines; halting problem. Prerequisite: Computer Sciences 325.

2. Intent

CS 333 provides an introduction to automata theory and discusses its applications in areas such as parsing, pattern recognition, and natural language processing.

3. Curricular Position and Degree Relevance

3.1. Prerequisites

CS 325 is required, to give the student additional mathematical maturity and familiarity with mathematical proofs and symbolism.

3.2. Courses Requiring This Course

None at the undergraduate level; CS 385 at the graduate level.

3.3. Degree Relevance

This upper-division course (with a grade of C or better) may be used to fulfill the computer sciences major requirement. It is not required.

This course is recommended for students who intend to do graduate work, or who are interested in the areas of artificial intelligence and natural or computer language processing.

4. Format

Three hours of lecture per week.

5. Syllabus

A. Brief Introduction to Automata Theory (5-6 weeks)

  Definition of grammar

  Types of grammars

  Type 3 grammars
	Definition of Finite State Machines
	Correspondence between Finite State Machines
	     and Type 3 languages.
	Correspondence between deterministic and
	     non-deterministic Finite State Machines
	Correspondence between Regular Languages
	     and Type 3 languages
	Equivalence of Finite State Machines
	Pumping Lemma
	Closure properties of regular languages

   Type 2 grammars
	Derivation trees
	Ambiguity
	Definition of Pushdown Automaton
	Correspondence between Pushdown Automata
	     and Type 2 languages
	Chomsky Normal Form
	Pumping Lemma
	Closure properties of context-free languages
	Deterministic PDA
	Pushdown Transducers
	Syntax Directed Translation Schemes

   Type 0 languages
	Definition of Turing machine
	Correspondence between Turing machines
	     and Type 0 languages
	Correspondence between deterministic and
	     non-deterministic Turing Machines

   Type 1 languages
	Definition of Linearly Bounded Automaton
	Correspondence between LBA and
	     type 1 languages

   There is a language which is not Type 0.

   More about Turing Machines
	Universal Turing Machine
	Halting Problem

B.  Application to Parsing (Chapter 6, 2-3 weeks)

	LL parsing
	LR parsing

C.  Application to Pattern Recognition (Chapter 4, 2 weeks)

D.  Application to Natural Language Processing (Chapter 10, 2 weeks)

E.  Application to Computer Vision (Chapter 11, 1 week)

F.  Application to Biology (Chapter 12, 1 week)

6. Possible Texts

Yeh, R.T., "Applied Computation Theory: Analysis, Design, Modeling", Prentice Hall, 1976.

CS 135

1. Catalogue Description

135. Computer Programming. - May be repeated for credit when the languages vary. Not intended to fulfill a prerequisite of any computer sciences course. Details of programming in a particular computer language; problems will be coded and run on a computer. Prerequisite: Some programming experience and consent of the instructor. Two laboratory hours a week for one semester. Laboratory fee, $4.

2. Intent

This course is intended for students who want to learn a programming language either not taught in another course or independent from the other content of the core course in which it is taught. CS 135 is intended to introduce students who already have programming experience to another programming language and hence is not an introduction to programming.

3. Curricular Position and Degree Relevance

3.1. Prerequisites

Programming experience and consent of the instructor or the CS undergraduate advisor.

3.2. Courses Requiring This Course

None.

3.3. Degree Relevance

This upper-division course (with a grade of C or better) may be used to fulfill the computer sciences major requirement, except that not both of the following may be used:

	a.  CS 135 - APL and CS 345
	b.  CS 135 - LISP and CS 426
	c.  CS 135 - PASCAL and CS 426
	d.  CS 135 - COBOL and STAT 333

CS 135 COBOL (or STAT 333) is highly recommended for students who intend to terminate their studies with a Bachelor's degree and look for employment in computer programming.

4. Format

Two laboratory hours per week.

5. Syllabus

The syllabus depends upon the language covered and is to be defined by the instructor.

6. Possible Texts

6.1. CS 135 - COBOL

Smith, Marilyn Z., "Standard COBOL: A Problem-Solving Approach",

6.2. CS 135 - LISP


Siklossy, L. "Let's Talk LISP", Prentice Hall, 1976.

6.3. CS 135 - PASCAL

Jensen, K. and Wirth, N., "PASCAL User Manual and Report", (Second edition), Springer Verlag, 1974.
Conway, Gries and Zemmerman, "A Primer on Pascal", Winthrop, 1976.

6.4. CS 135 - APL

Geller, D.P. and Freedman, D.P., "Structured Programming in APL", Winthrop, 1976.

CS 343

1. Catalogue Description

343. Artificial Intelligence. - Computer Science 343 and 381K may not both be counted. A survey of current AI technologies; game-playing, theorem proving, problem-solving, natural language processing, pattern recognition, picture processing, heuristic programming. A typical AI programming project will be required. Prerequisite: CS 426. Laboratory fee, $5.

2. Intent

This course is intended as an introduction to the field of artificial intelligence, giving a survey of the problems considered, the objective sought and the techniques used. Programming assignments are intended to give an appreciation of AI programming and experience in the use of a programming language suitable for AI work, such as LISP.

3. Curricular Position and Degree Relevance

3.1. Prerequisites

CS 426 is required. Content needed from CS 426 includes elementary LISP programming and the definitions, representations, and uses of various data structures.

3.2. Courses Requiring This Course

None at the undergraduate level; CS 389 at the graduate level.

3.3. Degree Relevance

This upper-division course (with a grade of C or better) may be used to fulfill the computer sciences major requirement. It is not required.

4. Format

Three hours of lecture per week. Programming assignments are completed out of class.

5. Syllabus


I.  Computers and intelligence

II.  Problem Solving
	state-space searching (breadth first, depth first, heuristic)
	problem reduction (GPS, STRIPS)
	AI languages (LISP, PLANNER, QA-4, SAIL, etc.)
	examples

III.  Game Playing (students are easily attracted to game playing;
                    don't let it get over-emphasized)
	alpha-beta and minimax procedures
	learning (Samuel, Waterman)
	examples

IV.  Vision
	perceptrons
	scene analysis and learning (Guzman, Waltz, Winston)

V.  Theorem Proving
	logic
	resolution
	non-resolution theorem proving (Fisher Black, PLANNER)
	applications to problem solving and question answering

VI.  Natural Language Processing
	parsing (Woods, Winograd)
	question answering
	speech perception
	psychological simulation (ELIZA, PARRY)
	semantic representations (logic, case structures,
	     conceptual dependency, procedures, semantic networks)

VII.  Robots
	mobile (Shakey, Turtles)
	hand-eye systems (Freddy, Butterfingers)
	industrial robots

6. Possible Texts

Raphael, B., "The Thinking Computer", Freeman, 1976.

CS 345

1. Catalogue Description

345. Programming Languages. - Survey of significant features of existing programming languages with emphasis on underlying concepts; structure of simple statements; algorithmic languages; list processing; string manipulation; simulation. Prerequisites: CS 410 and CS 426. Laboratory fee, $6.

2. Intent

This course is intended to give the survey of significant programming language features and concepts as described in the catalogue description above.

3. Curricular Position and Degree Relevance

3.1. Prerequisites

CS 410 and CS 426 are required. The content needed includes elementary LISP and PASCAL programming and the definitions, representations, and uses of various data structures. The student is expected to know FORTRAN and some assembly language.

3.2. Courses Requiring This Course

CS 375 requires CS 345. The content needed from CS 345 includes a familiarity with BNF notation and syntax diagrams and with the concepts of binding time, dynamic storage, block structured languages and scopes of variables and labels.

The graduate course CS 386L also requires this course.

3.3. Degree Relevance

This upper-division course (with a grade of C or better) may be used to fulfill the computer sciences major requirement. It is not required.

This course is recommended for students intending to do graduate work in computer sciences or interested in the basic concepts of computer languages.

4. Format

Three hours of lecture per week. Some programming in several different programming languages.

5. Syllabus


* Context-free BNF and syntax diagrams and their relation to order of evaluation
* Interpretation and compilation
* Binding, various binding times, static and dynamic variable types, binding of array bounds, efficiency versus flexibility, link editing
* APL, learning to program without goto's or recursion
* APL run-time organization (accessing of variables, storage management, etc.)
* Pascal (or Algol or PL/1) run-time organization (accessing of variables, storage management, stacks, own variables, etc.)
* Contrast primitive types of Pascal (or Algol, Fortran, etc.) with those of APL (or LISP or other interpretive language), observe that Pascal types were chosen to correspond closely to the machine, observe that arrays are the primitive data structuring mechanism provided by the machine and that Pascal pointers and records and sets all map easily onto arrays.
* Pattern matching
* Security
* LISP as an example of programming with only recursion and conditional (i.e., without assignment or goto). Note: theoretically, they already know LISP from CS 426.
* Programming language features for segmenting programming problems --

  1. Procedures,
  2. block structure (including a method of limiting access to variables outside a block),
  3. class (Simula 67) or cluster (CLU) or some other notation by which the compiler recognizes the creation of new data types with limited access.

6. Possible Texts

Pratt, T., "Programming Languages: Design and Implementation", Prentice Hall, 1975.

CS 347

1. Catalogue Description

347. Data Management. - CharacteristiCS of mass storage hardware; file structures, capabilities and limitations; data definition languages; design of a business data base system and a document retrieval system. Prerequisite: CS 426. Laboratory fee, $4.

2. Intent

This course is an introduction to data base management systems, including the rationale behind them; their architecture, capabilities and implementation; and current systems.

3. Curricular Position and Degree Relevance

3.1. Prerequisites

CS 426 is required for its content on data structures.

3.2. Courses Requiring This Course

None at the undergraduate level; CS 386 at the graduate level.

3.3. Degree Relevance

This upper-division course (with a grade of C or better) may be used to fulfill the computer sciences major requirement. It is not required.

This course is recommended for students who are interested in or intend working in the field of data management/retrieval. It is particularly recommended for students who intend to go into computer programming for business applications.

4. Format

Three hours of lecture per week.

5. Syllabus


I.  The rationale of data base management

	1. What is generalized data base management?
		Data Sharing
		Program sharing
		Data independence

	2. Some consequences of the technology
		Programmer productivity
		Information control
		System control

	3.  The user spectrum
		Programmer users
		Non-programmer users
		Casual users
		User levels and system design

II.  DBMS in action - case studies

III. DBMS architecture and capabilities

	1.  The gross anatomy of a DBMS

	2.  Functional capabilities of a DBMS
		Defining a data base
		Loading
		Retrieval/Report generation
		Updating
		Software utilities

	3.  Alternative design considerations for a DBMS

	  3.1  Alternative data models
		Hierarchical models
		Network models
		Relational Models
		Entity set models

	  3.2  Language interfaces
		Procedural
		Non-procedural

	  3.3  Implementation environment
		Host language versus self-contained systems
		Batch versus interactive systems
		Distributed versus central systems

	  3.4  Application environment
		Query oriented systems
		Update oriented systems
		Transaction oriented systems

IV.  Definition languages, schemas and data models:
          Organizing a data base

	A hierarchical: System 2000
		Data definition language
		Data model constructs
		Schemas from the case studies

	A network system:  Data Base Task Group
		Data definition language
		Data model constructs
		Schemas from the case studies

	A relational system
		Data definition language
		Data model
		Schemas from the case studies

V.  Data manipulation languages:  interacting with a data base

	System 2000 - an eclectic approach
		Nonprocedural interface language and operations
		Procedural language interface
		Examples from the case studies

	DBTG
		Subschema concept
		The applications context
		The data manipulation language
		Examples from the case studies

	Relational systems - the casual user
		SEQUEL
		LSL
		Examples from the case studies

VI.  Implementing a DBMS

	Internal schemas and storage structure
		A DBTG implementation
		A hierarchical implementation - RFMS
		A relational implementation - LSL

	Memory management and DBMS requirements

VII.  Hardware for DBMS

	Processor and mass storage technology
	Associative processing
	Distributed computing systems
		Distributed files
		Distributed functions

VIII.  The DBMS in an operating environment

	The emergent data base administrator function
	Control over applications
	Data base integrity
	Data base security

IX.  Evaluating a DBMS

	Evaluation methodology
	Evaluation criteria

6. Possible Texts

Date, C.J., "An Introduction to Database Systems", Addison-Wesley, 1975.

CS 348

1. Catalogue Description

348. A Survey of Numerical Techniques. - CS 348 and M 348 may not both be counted. Meets with M 348. Emphasizes the derivations and applications of numerical techniques most frequently used by scientists and enginers; interpolation; approximation; numerical differentiation and integration; differential equations; zeros of functions; solution of linear systems; material supplemented by problems to be solved on a high speed computer. Prerequisite: At least 8 hours of calculus, and Fortran programming at the level of 404; or consent of the intructor. Laboratory fee, $3.

2. Intent

This course gives a survey of computational problems arising in applications and representative numerical techniques for solving such problems. The course is intended to emphasize techniques and uses of numerical methods rather than the theory and proofs of theorems giving rise to these methods.

3. Curriculum Position and Degree Relevance

3.1. Prerequisites

CS 404 is required for its content on algorithms and FORTRAN programming.

M 808 or (M 608E and M 325) are required for a basic knowledge of calculus. Some knowledge of ordinary differential equations is helpful.

3.2. Courses Requiring This Course

CS 368K and (through CS 368K) CS 368L require this course.

3.3. Degree Relevance

This upper-division course (with a grade of C or better) may be used to fulfill the computer sciences major requirement. It is not required.

CS 348 is recommended for students who intend to terminate with a Bachelor's degree.

4. Format

Three hours of lecture per week

5. Syllabus


  1. Introduction

    1. Pitfalls of computation.
    2. CDC 6600 series computer arithmetic (floating point and fixed point numbers and their arithmetic operations)

  2. Function evaluations
  3. Solving nonlinear equations (mainly in one unknown)
  4. Solving systems of linear equations
  5. Polynomial interpolation
  6. Numerical differentiation and integration
  7. Numerical solution of initial value problems for ordinary differential equations
  8. Linear least square problems

Course content will include discussion, explanation and use of realistic methods for (at least) linear systems, function approximation, integration (quadrature), and initial-value problems for ordinary differential equations. Realistic methods include Gauss elimination with partial pivoting, adaptive Simpson's, Runge-Kutta-Fehlberg with step-size control, etc.

6. Possible Texts

Conte, S.D. and deBoor, C., "Elementary Numerical Analysis", (Second Edition), McGraw-Hill, 1972.

CS 352

1. Catalogue Description

352. Computer Systems Architecture. - Elementary logic design; structural and functional characteristiCS of computer system components; hardware features of modern computer systems. Prerequisite: CS 410.

2. Intent

This is a survey course intended to give an understanding of the hardware necessary for various computer sciences. The course explores the technology necessary for arithmetic operations, memory, instruction sequencing, and communications with the outside world. Microprogramming is covered in some depth as an aid to understanding control sequencing and instruction-set implementation. Examples of currently available machines are discussed, including microcomputers, minicomputers, mainframes and supercomputers.

3. Curricular Position and Degree Relevance

3.1. Prerequisite

CS 410 is required for its content on basic computer organization, computer instructions, instruction execution, representation of numbers, and characters and binary arithmetic.

3.2. Courses Requiring This Course

CS 372 requires either this course for an understanding of elementary logical and computer architecture, particularly interrupts, I/O device characteristiCS (drum, disc) and associative registers.

3.3. Degree Relevance

This upper-division course (with a grade of C or better) may be used to fulfill the computer sciences major requirement. It is not required.

This course is highly recommended to all students for gaining the basic knowledge of computer hardware needed in most applied and research areas.

4. Format

Three hours of lecture per week, in small to medium sized classes. A small amount of extra-class work in the computer hardware laboratory and a term paper requiring library research are required.

5. Syllabus


I.  Review
	Basic machine organization
	instruction execution
	number and character representation
	binary arithmetic

II. Basic Digital Circuits
	Basic gates
	switching algebra
	rudimentary minimization
	Karnaugh maps
	flip flops
	busses
	registers and information transfer
	decoders
	shift registers
	clocks, arithmetic and logic units
	serial and parallel adders
	simple multipliers
	a look at a standard ALU (e.g. 74181 integrated circuit)

III.  Memory
	Technology and organization of core and semiconductor memories
	past technologies (delay lines, Williams tubes, rotating drums)
	emerging technologies (charge-coupled devices, magnetic bubbles,
	                        beam-addressable memories)
	content-addressed memories
	memory hierarchies
	moving magnetic technologies (discs, tapes, strips)
	magnetic recording techniques
	archival memories

IV.  Control and Sequencing
	Description of a simple machine in gate logic
	A simple microprogrammed machine
	Excruciatingly detailed examples of instruction decode
	               and execution
	development of more complicated instructions
	survey of microprogramming

V.  Addressing Modes
	indexing
	indirection
	stacks
	base registers
	paging and segmentation
	interprocess protection

VI.  I/O and interrupts
	Gate logic for simple accumulator I/O
	Interrupt-driven I/O
	Interrupts for error handling, traps
	process control and real-time applications
	channel controllers and cycle-stealing
	DMA channels
	asynchronous communication

VII.  Microprocessors
	Trend toward general-purpose logic
	ROMs
	Programmable logic arrays
	the microprocessor as general purpose logic
	microprocessor architecture at PLA-ROM level
	currently prevalent microprocessors

VIII.  Minicomputers
	1 or 2 common minicomputers discussed in detail

IX.  Larger General-Purpose Computers
	(Usually a discussion of IBM 360/370)

X.  Number-Crunchers
	CharacteristiCS of machines for large scientific applications
	Discussion of typical machine (Usually CDC 6600/7600)

XI.  Advanced Topics
	Stack machines and high-level-language architectures
	concurrency in memories and processors
	distributed machines and networks
	etc.

6. Possible Texts

Mano, M.M., "Computer System Architecture", Prentice Hall, 1976.

CS 360

1. Catalogue Description

360. Digital Systems Engineering 1. - CS 360 and EE 360L may not both be counted. Meets with EE 360L. Combination switching theory; gates and storage elements; minimization of switching networks; elements of synchronous sequential circuit theory. Prerequisite: CS 404 and nine additional hours of computer sciences or mathematics; or EE 338; or upper-division standing and consent of instructor.

2. Intent

This course is intended as an introduction to switching theory and its application to digital computer design.

3. Curricular Position and Degree Relevance

3.1. Prerequisites

CS 404 and nine additional hours of computer sciences or mathematics (to assure that a basic knowledge of the applications of computers are known); or EE 338; or upper-division standing and consent of instructor.

3.2. Courses Requiring This Course

None, in Computer Sciences.

3.3. Degree Relevance

This upper-division course (with a grade of C or better) may be used to fulfill the computer sciences major requirement. It is not required.

CS 360 and EE 360L may not both be counted on any degree.

4. Format

This course is taught on a self-paced basis without lectures. Students must complete 19 study units and pass a test on each unit. Two laboratory units are also required. CS 360 meets with EE 360L.

5. Syllabus

	Combinational Logic
		number systems and conversion
		Boolean algebra
		algebraic simplification
		diode and transistor logic
		derivation of truth tables and logic equations
		Quine-McCluskey procedure
		Karnaugh maps
		multi-level and multi-output gate networks
		NAND and NOR gates
		combinational network design (lab problem)

	Sequential Logic
		flip-flops
		counters and similar sequential networks
		analysis of clocked sequential networks
		derivation of state tables
		state equivalence and reduction of state tables
		state assignment
		sequential network design (lab problem)
		iterative networks

	Applications
		networks for addition and subtraction
		networks for multiplication and division
		control networks

6. Possible Texts

Roth, C. H., "Fundamentals of Logic Design", West, 1975.
Hoernes and Heilweil, "Introduction to Boolean Algebra and Logic Design", McGraw-Hill, 1964.

CS 368K

1. Catalogue Description

368K. Introduction to Numerical Analysis. - CS 368K and M 368K may not both be counted. Meets with M 368K. A thorough mathematical treatment of basic numerical techniques; interpolation and approximation; numerical differentiation and integration; solution of ordinary differential equations; zeros of functions; material supplemented by problems to be solved on a high-speed digital computer. Prerequisite: CS 348, or its equivalent, and M 665A, or consent of instructor. Laboratory fee, $3.

2. Intent

This course is intended to give a rigorous development of basic numerical methods and to evaluate these methods from the standpoint of efficiency, accuracy and suitability for use on digital computers.

3. Curricular Position and Degree Relevance

3.1. Prerequisites

This course requires CS 348, for Fortran programming and algorithm design and M 665A, for concepts of advanced calculus; or the consent of instructor.

3.2. Courses Requiring This Course

CS 368L requires this course.

3.3. Degree Relevance

This upper-division course (with a grade of C or better) may be used to fulfill the computer sciences degree requirement. Both CS 368K and M 368K cannot be counted towards the degree since they are the same course.

This course is recommended to students who intend doing graduate work or mathematical programming.

4. Format

Three hours of lecture per week. This course meets with M 368K.

5. Syllabus

Not available.

6. Possible Texts

Not available


CS 368L

1. Catalogue Description

368L. Introduction to Numerical Linear Algebra. - CS 368L and M 368L may not both be counted. Meets with M 368L. A survey of computational methods in linear algebra; the necessary matrix theory will be developed in the course; direct solution of linear systems; norms and condition numbers; the linear least square problem; eigenvalues and eigenvectors; material supplemented by problems to be solved on a high-speed digital computer. Prerequisite: CS 368K or its equivalent; or consent of the instructor.

2. Intent

This course is a survey of computational methods in linear algebra.

3. Curricular Position and Degree Relevance

3.1. Prerequisites

This course requires CS 368K.

3.2. Courses Requiring This Course

None at the undergraduate level.

3.3. Degree Relevance

This upper-division course (with a grade of C or better) may be used to fulfill the computer sciences degree requirement. Both CS 368L and M 368L cannot be counted, since they are the same course.

This course is recommended to students who intend doing graduate work or mathematical programming.

4. Format

Three hours of lecture per week. This course meets with M 368L.

5. Syllabus

Not available.

6. Possible Texts

Stewart, G.W., "Introduction to Matrix Computations", Academic Press, 1974.

CS 369

1. Catalogue Description

369. Systems Modeling I. - An introduction into analytic and simulation models for stochastic systems with emphasis on computer systems. Prerequisites: CS 426.

2. Intent

This course introduces the elements of stochastic processes, queueing theory and simulation, to give the student the ability to make reasoned decisions on probabilistic problems, with emphasis on scheduling decisions in computer and communication systems.

3. Curricular Position and Degree Relevance

3.1. Prerequisites

This course requires CS 426, for an understanding of the structures and programming required in simulation and M 808 for the mathematical background required for probability theory.

3.2. Courses Requiring This Course

None at the undergraduate level. Graduate courses in the theory of Operating Systems and Systems Modeling require CS 369.

3.3. Degree Relevance

This upper-division course (with a grade of C or better) may be used to fulfill the computer sciences major requirement. It is not required.

This course is relevant to operating systems, problem solving, and to some extent data base systems. It is recommended to students interested in systems analysis.

4. Format

Three hours of lecture per week. The course material is primarily learned through discussion and solution of a sequence of problems which propose questions of increasing difficulty.

5. Syllabus

Axioms of Probability Theory
Simulation: a tool for solving simple stochastic problems
Discrete and Continuous Random Variables
Generating random variables on a digital computer; An introduction to the Chi-Square
Bernoulli and Poisson Processes
Simulation of Bernoulli and Poisson Processes
Markov Processes
Simulation of queueing systems with an emphasis on understanding the impact of service disciplines and distributions on systems behavior
Elements of queueing network theory. Use of queueing network program packages. Application to operating systems. A non-trivial simulation of a computer and/or communication system

6. Possible Texts

Drake, A. W., "Fundamentals of Applied Probability Theory", McGraw-Hill, 1967.

CS 370

1. Catalogue Description

370. Undergraduate Reading and Research. - May be repeated for credit when the topics vary. Supervised study of selected problems in computer sciences by individual arrangement with supervising instructor. Prerequisite: Upper-division standing and consent of the supervision instructor and the undergraduate advisor.

2. Intent

This course is intended to give students an opportunity to study in areas not offered in the normal undergraduate curriculum.

3. Curricular Position and Degree Relevance

3.1. Prerequisites

Upper-division standing and consent of the supervising instructor and the undergraduate adviser. A student wanting to take this course must propose the topic and find an instructor willing to supervise the student's study.

3.2. Courses Requiring This Course

None

3.3. Degree Relevance

This upper-division course (with a grade of C or better) may be used to fulfill the computer sciences degree requirement. It is not required and although the course may be repeated for credit when the topics vary, no more than one CS 370 course may be used to fulfill the computer sciences degree requirement.

This course is recommended only when the student has fulfilled most of the degree requirements and wants to work in an area not available in the undergraduate curriculum.

4. Format

By individual arrangement with the supervising instructor. It is recommended that at least one meeting or progress report be required each week. The result of this course is generally a paper or report by the student surveying the field of study and sometimes may include a major programming project.

5. Syllabus

Determined by the supervising instructor.

5.1. Possible Texts

To be determined by the supervising instructor.


CS 372

1. Catalogue Description

372. Introduction to Operating Systems. - Hardware and software organization of complete computer systems, basic concepts of operating systems, multiprogramming, multiprocessing and time-sharing systems, interpreters, assembly systems, macroassemblers. Prerequisite: CS 327 and CS 352. Laboratory fee, $6.

2. Intent

This course is an introduction to the practical use of operating systems and theoretical issues of their design and construction. The major algorithms of operating systems are presented in some detail. Programming problems give experience in both the use and construction of operating systems.

3. Curricular Position and Degree Relevance

3.1. Prerequisites

CS 327 is required for programming skills and CS 352 is required for a background in computer hardware.

3.2. Courses Requiring This Course

CS 379H at the undergraduate level. At the graduate level, CS 380L requires CS 372 or EE 380L.

3.3. Degree Relevance

This upper-division course (with a grade of C or better) may be used to fulfill the computer sciences degree requirement. It is not required.

This course is strongly recommended to all computer sciences students for a basic understanding of computer operating systems.

4. Format

Three hours of lecture per week. Large programming projects are assigned for completion out of class.

5. Syllabus

I.  Introduction
	history and goals of operating systems
	types of operating systems.

II. Input/Output control systems, batch systems, spooling,
	multiprogramming, time-sharing, multiprocessor, networks.
	Job control languages, user services.

III. CPU Scheduling, interrupt handling, long-term and short-term
	scheduling, FCFS, SJF, priority, round-robin, multi-level
	queues.  Deterministic scheduling, list scheduling, Hu's
	algorithm.

IV.  Processes, concurrent programs, communication primitives,
	mutual exclusion problem, P/V, message systems,
	coordination.

V. Memory Management
	Overlays, Relocation, Base-Bounds, Paging, Segmentation,
	Paged-Segmented, Swapping, Demand Paging, Virtual Memory
	Replacement algorithms, Allocation algorithms, Memory
	Hierarchies

VI.  File systems
	Device Characteristics, space allocation techniques, access
	methods, disc and drum scheduling, directory structures,

VII.  Resource Allocation
	Deadlocks

VIII.  Protection and Security
	Hardware protection mechanisms, access matrix, access lists,
	capabilities, policies versus mechanisms, passwords.

IX.  Design concepts
	layering, modules, virtual machines
	reliability
	performance evaluation and measurement

6. Possible Texts

Shaw, A., "The Logical Design of Operating Systems", Prentice Hall, 1975.
Tsichritzis, D.C. and Bernstein, P.A., "Operating Systems", Academic Press, 1974.

CS 374

1. Catalogue Description

374. Computers in the Humanities. - May not be used to fulfill the computer sciences major requirement. Not intended for students with prior programming experience. Elementary introduction to computers and programming; survey of computer uses in language, literature, art, music, anthropology, etc. Prerequisite: Upper-division standing and consent of the instructor. Laboratory fee, $5.

2. Intent

This course is intended to introduce humanities students to the use and applications of computers in their areas. It is not intended for students with prior programming experience

3. Curricular Position and Degree Relevance

3.1. Prerequisites

Upper-division standing and consent of the instructor or computer sciences undergraduate advisor.

3.2. Courses Requiring This Course

None

3.3. Degree Relevance

This upper-division course cannot be used to fulfill the computer sciences major requirement. It can be used as an upper-division elective.

4. Format

Three hours of lecture per week, with programming assignments which are completed outside of class.

5. Syllabus

I. Introduction to a suitable programming language, such as
   SNOBOL, LOGO, or SPSS.

II. Survey of work done in the Humanities, including the
    following,

	A. Concordances

	B. Stylistic Analysis
		1. Authorship studies (inter-author analysis)
		2. Literary stylistiCS (intra-author analysis)

	C. Content Analysis (General Inquirer)

	D. Information Storage and Retrieval
		1. Production systems (ERIC, NEW YORK TIMES, MEDLARS)
		2. Experimental work
		   a. automatic abstracting
		   b. automatic indexing
		   c. automatic classification

6. Possible Texts

Lynch, R.E. and Rice, J.R., "Computers: Their Impact, Use and Basic Languages", Holt, Rinehart Winston, 1975.
Klecka, Nie and Hull, "SPSS Primer", McGraw-Hill, 1975.

CS 375

1. Catalogue Description

375. Algorithmic Languages and Compilers. - Formal descriptions of algorithmic languages, compilation techniques, syntactic analysis, code generation, storage allocation, syntax-directed compilers, compiler-building systems. Prerequisite: CS 327 and CS 345 or consent of instructor. Laboratory fee, $5.

2. Intent

This course is designed to teach the basic concepts of the construction of compilers for algorithmic languages. During the course, an actual compiler is implemented by the students, utilizing the material taught in the course.

3. Curricular Position and Degree Relevance

3.1. Prerequisites

CS 327 is required for programming skills and CS 345 is required for the concepts underlying the structures of algorithmic languages, including dynamic storage.

3.2. Courses Requiring This Course

CS 379H at the undergraduate level.

3.3. Degree Relevance

This upper-division course (with a grade of C or better) may be used to fulfill the computer sciences degree requirement. It is not required.

This course is recommended for students intending to do graduate work.

4. Format

Three hours of lecture per week, with a major project completed out of class.

5. Syllabus

The construction of an actual compiler is a major project which requires some amount of class discussion. The syllabus presented below covers only the project-independent lecture material for the course and does not include topics related to the project.

I.  Introduction
	general overview

II.  Language Theory Foundations
	finite-state grammars and regular expressions
	context-free grammars, syntax trees, ambiguity, relations,
		BNF-notation
	restricted context-free grammars, precedence, LR, parsing

III. Analysis
	symbol tables
	approaches, syntax-driven, top-down, bottom-up,
		recursive descent
	lexical scanning, regular expressions
	syntactic parsing, precedence or LR, generation of tables
	semantic analysis, table information, timing of checks
	error recovery
	internal forms, tuples, trees

IV. Synthesis
	code optimization, folding, eliminating redundant
		expressions, invariant operations.
	storage allocation, temporaries, static, dynamic, common
	run-time support, input/output, stacks
	code generation, addressing operands, register allocation

6. Possible Texts

Gries, D., "Compiler Construction for Digital Computers", John Wiley and Sons, 1971.

CS 378

1. Catalogue Description

378. Undergraduate Topics in Computer Sciences. - May be repeated for credit when the topics vary. Prerequisite: Upper division standing and consent of instructor and the undergraduate adviser. Laboratory fee, $5.

2. Intent

Topics courses are intended to permit faculty to give courses covering areas not regularly included in the undergraduate curriculum or to introduce proposed new courses on a trial basis.

3. Curricular Position and Degree Relevance

3.1. Prerequisites

Upper-division standing and consent of the instructor and the undergraduate adviser. Given topics may require certain prerequisites defined when the topics course is announced.

3.2. Courses Requiring This Course

None.

3.3. Degree Relevance

This upper-division course (with a grade of C or better) may be used to fulfill the computer sciences degree requirement. It is not required. Provided the topics differ, CS 378 may be counted more than once.

4. Format

The format depends on the topic, but is usually three hours of lecture per week, often with outside assignments or labs.

5. Syllabus

To be determined by the course instructor.

6. Possible Texts

To be determined by the course instructor.


CS 379H

1. Catalogue Description

379H. Computer Sciences Honors Course. - Directed reading, research and/or projects in areas of computer sciences, under supervision of a faculty member, leading to an honors thesis. The thesis must be approved by a committee of two readers. By arrangement with a faculty member. Prerequisite: Admission to the Honors Program, CS 372, CS 375 and approval of the Undergraduate Advisor.

2. Intent

This course is intended for students who want to graduate with Honors in computer sciences, to indicate that such students are capable of independent (although supervised) work in the field.

3. Curricular Position and Degree Relevance

3.1. Prerequisites

Admission to the Honors Program, CS 372, CS 375 and approval of the Undergraduate Advisor. Majors who are candidates for Special Honors in Computer Sciences should apply to the Undergraduate Advisor for admission to the Honors Program before registering for their final semester.

Whenever possible, students should make their own arrangements with a faculty member in the area of interest to the student.

3.2. Courses Requiring This Course

None.

3.3. Degree Relevance

This upper-division course (with a grade of B or better) is required for graduation with Special Honors in Computer Sciences. It is not required otherwise.

The requirements for graduation with Special Honors, which are in addition to the requirements for the major, are:


  1. CS 379H with a grade of B or better,
  2. an all-University grade point average of 3.0 and an average of 3.5 in courses taken in computer sciences and all courses counting toward the computer science major requirement (i.e., M 808 and M 311),
  3. at least sixty semester hours of course work completed at the University of Texas at Austin and counted toward the degree.

4. Format

By individual arrangement with the supervising faculty member. It is recommended that at least one meeting or progress report be required each week.

5. Syllabus

Determined by supervising instructor. The Honors thesis must be submitted to the reading committee at least one week before the final examination period begins, to permit time for the readers to read and evaluate it.

6. Possible Texts

To be determined by the supervising instructor.
HomeComments?