Courses
and Programs 1995-1997 Courses
and Programs 1995-1997Com S 101. Orientation. (1-0) Cr. R. F.S. Introduction to the policies of Iowa State University and the Department of Computer Science. Issues relevant to student adjustment to college life will be discussed. A thorough review of regulations and registration procedures is also included. Review of college and university requirements, transfer credits, academic planning, university policies and deadlines, preregistration. Offered on a satisfactory-fail basis only.
Com S 103. Computer Applications. (3-2) Cr. 4. F.S. Introduction to microcomputer literacy and applications. Applications: word processing, spreadsheets, database management. Literacy: the history of computing, algorithm development, structure of computers, telecommunications, computer ethics, and computer crime. No prior computer experience necessary.
Com S 107. Applied Computer Programming. (3-0) Cr. 3. F.S. Prereq: Math 104 or 140 or 150. Introduction to computer programming for non-majors using a PASCAL-like language. Basics of good programming, computer systems, files, use of an editor and a command language.
Com S 201. Computer Programming in COBOL. (3-0) Cr. 3. F.S. Prereq: 107 or 207 or 227. Computer programming using the COBOL language. Emphasis on the design, writing, debugging, and testing of business applications programs in a transaction-oriented environment.
Com S 205. Computer Programming in FORTRAN. Same as Math 205. (3-0) Cr. 3. F. Prereq: Credit or enrollment in Math 166. Introduction to computer programming using the FORTRAN language. Emphasis on design, debugging, and testing of numerical algorithms. Engineering and physical science applications stressed. For students in engineering and physical science.
Com S 207. C Programming I. (3-1) Cr. 3. F.S. Prereq: 2 years high school algebra and 1 year high school geometry. An introduction to computer programming using the C and/or C++ programming language. Emphasis on basics of good C and/or C++ programming techniques and style through extensive practice in writing, running, and debugging programs. This course is designed for nonmajors; those contemplating a major in computer science should take 227.
Com S 208. C Programming II. (3-1) Cr. 3. F.S. Prereq: 207, credit or enrollment in Math 151, 160, or 165. An introduction to data structures and algorithm analysis using C or C++ languages. Recursion. List and file processing. Dynamic data structures. Emphasis on writing and running programs. This course is designed for nonmajors. Credit may not be applied toward graduation for both 208 and 228.
Com S 227. Introduction to Computer Programming. (3-1) Cr. 3. F.S. Prereq: 2 years high school algebra and 1 year high school geometry. An introduction to computer programming. Symbolic and numerical computation. Recursion and iteration. Modularity and data abstraction. Functional and interactive programming. Imperative programming. Emphasis on principles of programming and program design through extensive practice in writing, running, and reasoning about programs. This course is designed for majors.
Com S 228. Introduction to Data Structures. (4-1) Cr. 4. F.S. Prereq: 227, credit or enrollment in Math 165. An object-oriented approach to data structures and algorithms using C++ language. Object-oriented programming. Program correctness. Stacks, queues, trees, searching, sorting, analysis of algorithms, graphs, and file processing. Emphasis on writing and running programs. This course is designed for majors. Credit may not be applied toward graduation for both 208 and 228.
Com S 290. Independent Study. Cr. arr. F.S. Prereq: Permission of instructor. Offered on a satisfactory-fail basis only.
H. Honors
Com S 301. Careers in Computer Science. (1-0) Cr. R. Half semester. F.S. Computer science as a profession. Introduction to career fields open to computer science majors. Relationship of coursework to careers. Presentations by computer science professionals. Offered on a satisfactory-fail basis only.
Com S 311. Data Structures and Algorithm Analysis. (3-1) Cr. 3. F.S. Prereq: 208 or 228, 330 or Cpr E 310. Basic techniques for design and analysis of efficient algorithms that act on data structures. Set manipulation, sorting, graph processing, and memory management algorithms. Open to graduate students for minor graduate credit only.
Com S 321. Introduction to Computer Architecture and Machine-Level Programming. (3-2) Cr. 4. F.S. Prereq: 107 or 207 or 227; and credit or enrollment in Cpr E 210. Introduction to computer architecture with emphasis on instruction sets and addressing modes. Machine-level programming including assembly language. Techniques for improving program performance. Input/output and interrupts. Laboratory-based introduction to modern development tools and performance measurement systems. Open to graduate students for minor graduate credit only.
Com S 330. Discrete Computational Structures. (3-1) Cr. 3. F.S. Prereq: 207 or 227 and Math 165. Concepts in discrete mathematics as applied to computer science. Logic, set theory, relations, graphs, combinatorics and their computational aspects. Open to graduate students for minor graduate credit only.
Com S 331. Theory of Computing. Same as Ling 331. (3-1) Cr. 3. F.S. Prereq: 330 or Cpr E 310. Models of computation: finite state automata, pushdown automata and Turing machines. Study of grammars and their relation to automata. Limits of digital computation, unsolvability and Church-Turing thesis. Chomsky hierarchy and relations between classes of languages. Open to graduate students for minor graduate credit only.
Com S 342. Principles of Programming Languages. (3-1) Cr. 3. F.S. Prereq: 321, 331, 361. Organization of programming languages emphasizing language design concepts and run time implementation. Study of major features of various programming languages. Open to graduate students for minor graduate credit only.
Com S 352. Introduction to Operating Systems. (3-1) Cr. 3. F.S. Prereq: 321, 361, Cpr E 305. Survey of operating system issues. Introduction to hardware and software components including: processors, peripherals, interrupts, process and memory management, deadlocks, file systems, protection, virtual machines and system organization. Open to graduate students for minor graduate credit only.
Com S 361. File Organization and Processing. (3-1) Cr. 4. F.S. Prereq: 208 or 228. Concepts and techniques of structuring and processing data on external storage devices. Hardware and its parameters. Basic file organization including: sequential, indexed, indexed sequential, and hash files. Hybrid file organization. Open to graduate students for minor graduate credit only.
Com S 398. Cooperative Education. Cr. R. Required of all cooperative students. Prereq: Permission of department chair. Students must register for this course prior to commencing each work period.
Com S 401. Computer Based Information Systems. (2-2) Cr. 3. F. Prereq: 361 and an additional 9 credits in Com S at the 200 level or above. Systems concepts and implementations for supporting production-oriented information systems; data and terminal access methods; operating systems implementations; data base management systems implementations; data dictionary considerations; data communication considerations; lab experiments and implementations. Open to graduate students for minor graduate credit only.
Com S 403. Computer Based Instructional Systems. (2-0) Cr. 2. F. Prereq: 208 or 228. Principles, techniques, languages, and support systems for development and delivery of instructional software used in education and industry. Programming project emphasizing computer scientist's role on a development team. Open to graduate students for minor graduate credit only.
Com S 411. Specification and Design in Software Engineering. (3-1) Cr. 3. F. Prereq: 311 or Cpr E 305. Principles and techniques for methodical construction of quality software. Software requirements specification; programming paradigms; module specification techniques; testing and validation procedures; proof of program correctness. Emphasis on team projects. Open to graduate students for minor graduate credit only.
Com S 425. High Performance Computing for Scientific and Engineering Applications. (3-1) Cr. 3. S. Prereq: 330, 352. Introduction to high performance computing using different architectures, vector processors, and parallel computers. Discussion of performance issues. Sample applications from science and engineering. Practical issues in high-performance computing will be emphasized via a number of programming projects and case studies. Open to graduate students for minor graduate credit only.
Com S 440. Principles of Compiling. This course is dual listed with 540. (3-1) Cr. 3. S. Prereq: 342. Techniques of lexical analysis, top-down and bottom-up parsing, semantic analysis and code generation. Principles are reinforced through a number of programming projects. Different projects will be assigned to students depending on whether they have enrolled for 440 or 540. Open to graduate students for minor graduate credit only.
Com S 454. Implementation of Operating Systems. This course is dual listed with 554. (3-1) Cr. 3. S. Prereq: 352. Laboratory course emphasizing the practical issues of operating system design and implementation through the examination of a fully functional operating system, including device drivers, interrupt and signal handlers, file systems, memory, and process management. Graduate credit requires additional in-depth study of design and implementation issues for advanced operating systems and networking operating systems. Open to graduate students for minor graduate credit only.
Com S 461. Introduction to Database Systems. (3-1) Cr. 3. F. Prereq: 311, 352. Introduction to database concepts, data models (relational, hierarchical, and network models), data manipulation languages, data description languages, system implementation issues, security and data integrity. Open to graduate students for minor graduate credit only.
Com S 471. Computational Linear Algebra and Fixed Point Iteration. Same as Math 471. See Mathematics.
Com S 472. Principles of Artificial Intelligence. This course is dual listed with 572. (3-1) Cr. 3. F. Prereq: 208 or 228, 330 or Cpr E 310. Overview of foundations, scope, and problems of artificial intelligence and cognitive science. State-space search techniques for problem solving. Knowledge representation and automated inference. Machine learning. Introduction to neural and evolutionary approaches to AI. Selected applications in planning, machine perception, analysis, design. AI programming using Common LISP. Open to graduate students for minor graduate credit only.
Com S 474. Neural Computation. (3-1) Cr. 3. S. Prereq: Math 165, Com S 208 or 228. Introduction to the basic concepts and techniques of neural computation and computational and cognitive neuroscience. Computational models of biological neurons, micro-circuits, and network models of memory and learning and their relations to artificial neural network models are emphasized. Selected applications in biology, psychology (neurobiological and psychological modeling), computer science (e.g. pattern recognition, diagnosis). Hands-on experience with neural computation as a problem solving and modeling paradigm. Open to graduate students for minor graduate credit only.
Com S 481. Numerical Solution of Differential Equations and Interpolation. Same as Math 481. See Mathematics.
Com S 484. Computer Organization and Design II. Same as Cpr E 484. See Computer Engineering.
Com S 490. Independent Study. Cr. arr. F.S. Prereq: 6 credits in computer science, permission of instructor. No more than 9 credits of 490 may be counted toward graduation. Offered on a satisfactory-fail basis only.
H. Honors
Com S 495. Seminar. Cr. arr. F.S. Prereq: Permission of instructor. Offered on a satisfactory-fail basis only.
Com S 507. Numerical Solution of Ordinary Differential Equations. Same as Math 507. See Mathematics.
Com S 509. Computational Methods of Linear Algebra. Same as Math 509. See Mathematics.
Com S 511. Design and Analysis of Algorithms. (3-0) Cr. 3. F. Prereq: 311, 330. Design, analysis, and complexity of algorithms. General techniques for solving problems (divide and conquer, backtracking, etc.) Sorting algorithms, graph algorithms, algebraic algorithms, fast Fourier transform, and NP-completeness.
Com S 512. Formal Methods in Software Engineering. (3-0) Cr. 3. S. Prereq: 311, 330. A survey of formal topics relevant to the software life-cycle process including requirements, specifications, design, implementation, testing, and maintenance. Implications of formal results for software prototyping and automated testing.
Com S 524. Computer System Architecture. (3-0) Cr. 3. F. Prereq: 352, 384. Fundamentals of computer design, performance and cost, instruction set design, basic processor implementation techniques, pipelining, memory design, caches, I/O systems, multiprocessor systems, interconnection networks.
Com S 525. Numerical Analysis of High Performance Computing. Same as Cpr E 525, Math 525. See Computer Engineering or Mathematics.
Com S 531. Theory of Computation. (3-0) Cr. 3. F. Prereq: 331. A systematic study of the fundamental models and analytical methods of theoretical computer science. Computability, the Church-Turing thesis, decidable and undecidable problems, and the elements of recursive function theory. Time complexity, Boolean circuits, and NP-completeness. Finite-state and pushdown computation.
Com S 540. Principles of Compiling. This course is dual listed with 440. (3-1) Cr. 3. S. Prereq: 342. Techniques of lexical analysis, top-down and bottom-up parsing, semantic analysis and code generation. Principles are reinforced through a number of programming projects. Different projects will be assigned to students depending on whether they have enrolled for 440 or 540.
Com S 541. Programming Languages I. (3-1) Cr. 3. S. Prereq: 342 or 440. Survey of the goals and problems of language design. Formal and informal studies of a wide array of programming language features including type systems, naming, state, and control. Creative use of functional, object-oriented, declarative, concurrent, and other programming paradigms.
Com S 542. Programming Languages II. (3-0) Cr. 3. Alt. F., offered 1996. Prereq: 440. Compilation theory and techniques, emphasis on high-level software tools to facilitate compiler construction. Lexical analysis, parsing, attribute grammars, code generation and optimization for traditional and nontraditional languages and architectures.
Com S 552. Principles of Operating Systems. (3-0) Cr. 3. S. Prereq: 352. A comparative study of high-level language facilities for process synchronization and communication. Formal analysis of deadlock, memory management policies, and system performance. Protection issues including capability-based systems, access and flow control, encryption, and inference control.
Com S 554. Implementation of Operating Systems. This course is dual listed with 454. (3-1) Cr. 3. S. Prereq: 352. Laboratory course emphasizing the practical issues of operating system design and implementation through the examination of a fully functional operating system, including device drivers, interrupt and signal handlers, file systems, memory, and process management. Graduate credit requires additional in-depth study of design and implementation issues for advanced operating systems and networking operating systems.
Com S 561. Principles of Database Systems. (3-0) Cr. 3. S. Prereq: 311 and 352. Introduction to database system concepts. Physical data organization. The network model and the DBTG proposal. The hierarchical model. The relational model. Relational query languages. Functional dependencies. Multivalued dependencies. Decomposition of relation schemes. Normal forms. Query systems. Query optimization. Concurrence control. Distributed database systems.
Com S 572. Principles of Artificial Intelligence. This course is dual listed with 472. (3-1) Cr. 3. F. Prereq: 208 or 228, 330 or Cpr E 310. Overview of foundations, scope, and problems of artificial intelligence and cognitive science. State-space search techniques for problem solving. Knowledge representation and automated inference. Machine learning. Introduction to neural and evolutionary approaches to AI. Selected applications in planning, machine perception, analysis, design. AI programming using Common LISP. Graduate credit requires a research project and a written report.
Com S 573. Computational Models of Learning. (3-0) Cr. 3. S. Prereq: 572 and mathematical maturity expected of beginning graduate students in the sciences. Biological, psychological, and computational models of learning. Parametric and nonparametric statistical methods. Similarity-difference based algorithms, representational and inductive biases. Neural network models. Evolutionary search and genetic algorithms. Computational learning theory. Deductive learning. Computational models of scientific, mathematical, and conceptual discovery.
Com S 586. Computer Network Architectures. (3-0) Cr. 3. F. Prereq: 511, 524 or Cpr E 489. Design and development of advanced computer communication networks: distributed and failsafe routing in large and dynamic networks, gateways and interconnection of heterogeneous networks, flow control and congestion avoidance techniques, network architectures, computer and communication security, communication protocol standards, formal specification and verification of protocols, implementation and conformance testing of protocol standards, network partitioning and intelligent reconfiguration of networks.
Com S 590. Special Topics. Cr. arr. Prereq: Permission of instructor. Offered on a satisfactory-fail basis only.
Com S 591. Faculty Research Interests. (1-0) Cr. 1. S. Prereq: Graduate classification. Discussion of research interests and projects by members of the graduate faculty. Students select and prepare a written report on some topic of interest. This class is mandatory for the M.S. degree and is taken during the second semester of a normal M.S. program. Offered on a satisfactory-fail basis only.
Com S 599. Creative Component. Cr. arr. Offered on a satisfactory-fail basis only.
Com S 610. Seminar. Cr. arr. Offered on a satisfactory-fail basis only.
Com S 611. Advanced Topics in Analysis of Algorithms. (3-0) Cr. 3. Alt. S., offered 1997. Prereq: 511, 531. Advanced algorithm analysis and design techniques. Graph algorithms, algebraic algorithms, NP-completeness, probabilistic and parallel algorithms, intractable problems.
Com S 612. Parallel and Distributed Algorithms. (3-0) Cr. 3. Alt. S., offered 1996. Prereq: 511. An advanced course in the theory of parallel and distributed computation. Models of parallel and distributed computation. Parallel sorting, graph, geometric, algebraic, and number-theoretic algorithms. The parallel computation thesis. NC-algorithms and P-complete problems. Agreement problems. Mutual exclusion and resource allocation. Implementation of wait-free registers. Network problems. Lower bounds and impossibility results. Fault-tolerance. Randomized computation.
Com S 624. Advanced Topics in Computer Architecture. (3-0) Cr. 3. Alt. S., offered 1996. Prereq: 524. A study of different computer architectures, including various models of parallel computers. Tradeoffs between different architectural models. Architecture-specific algorithm designs and optimization techniques to achieve high performance. Performance evaluation of specific architectures for scientific and engineering applications.
Com S 625. Issues in Parallel Programming and Performance. (3-0) Cr. 3. Alt. S., offered 1997. Prereq: 511, 524. Parallel solutions of numerical and non-numerical problems, implementation of parallel programs on parallel machines, performance and other computational issues in parallel programming.
Com S 631. Computational Complexity. (3-0) Cr. 3. Alt. F., offered 1996. Prereq: 531. Advanced study in the quantitative theory of computation. Time and space complexity of algorithmic problems. The structure of P, NP, PH, PSPACE, and other complexity classes, especially with respect to resource-bounded reducibilities and complete problems. Complexity relative to auxiliary information, including oracle computations and relativized classes, randomized algorithms, advice machines, and Boolean circuits. Kolmogorov complexity and randomness.
Com S 632. Circuit Complexity and Parallel Complexity. (3-0) Cr. 3. Alt. S., offered 1997. Prereq: 531. An advanced course in the complexity of Boolean functions and parallel computation. General circuits, bounded-depth circuits, threshold circuits, and monotone circuits. Parallel complexity, including uniform circuits, alternating Turing machines, and parallel RAMs. Additional topics chosen from communication and sorting networks, communication complexity, VLSI complexity, cellular automata, neural networks, and general purpose parallel architectures.
Com S 633. Randomness in Computation. (3-0) Cr. 3. Alt. S., offered 1996. Prereq: 531. Advanced study of the role of randomness in computation. Randomized algorithms, random oracles, and probabilistic complexity classes. One-way functions and pseudorandom generators. Kolmogorov complexity, algorithmic information theory, and algorithmic randomness. Applications chosen from cryptography, interactive proof systems, computational learning, lower bound arguments, mathematical logic, and the organization of complex systems.
Com S 641. Semantic Models for Programming Languages. (3-0) Cr. 3. Alt. F., offered 1996. Prereq: 531, 541. Interpretive, denotational, and logically based models of semantics; application of semantics to program correctness, language specification, and translation.
Com S 642. Advanced Topics in the Design and Implementation of Programming Languages. (3-0) Cr. 3. Alt. F., offered 1995. Prereq: 540 or 440, and 541. In-depth discussion of research in the design and implementation of a single programming language or group of related language features. Intimate familiarity with the use and implementation of experimental language systems. General principles and techniques of experimental systems research.
Com S 652. Topics in Distributed Operating Systems. (3-0) Cr. 3. Alt. F., offered 1995. Prereq: 552. Concepts and techniques for network operating systems: high-level languages and communication protocols, name and object management, concurrency control for consistent distributed data, design of reliable software, protection, performance analysis.
Com S 661. Advanced Topics in Database Systems. (3-0) Cr. 3. Alt. F., offered 1996. Prereq: 561. Advanced topics chosen from the following list: Data dependencies. Data models. Query systems. Query optimization. Null values, partial information and database semantics. Acyclic database schemes. Concurrency control mechanisms. Distributed database systems. Logic and databases.
Com S 672. Computational Models of Learning. (3-0) Cr. 3. Alt. S., offered 1997. Prereq: 472 or 572. Advanced study of artificial intelligence, statistical, neural, syntactic, evolutionary models and algorithms for machine learning. Inductive learning, classification, grammar induction, function approximation, program induction (inductive logic programming). Deductive learning. Discovery. Elements of computational learning theory. Selected applications.
Com S 673. Advanced Topics in Artificial Intelligence and Cognitive Modeling. (3-0) Cr. 3. Alt. S., offered 1996. Prereq: 472 or 572. Advanced study of selected topics from among the following: parallel and distributed architectures and algorithms for artificial intelligence; computational models of discovery; machine learning; neural networks and neural modeling; genetic algorithms, genetic programming and artificial life. Computational learning theory. Selected applications of AI.
Com S 699. Research. Offered on a satisfactory-fail basis only.