Graduate Catalog

2008-2009

COMPUTER SCIENCE

Department website: http://www.cs.nmsu.edu
(575) 646-3723
csoffice@cs.nmsu.edu

D. Ranjan, department head, Ph.D. (Cornell)- algorithms, bioinformatics, computational complexity; A. Bhattacharya, Ph.D. (Texas-Arlington)-wireless networks, mobile computing; J. Cook, Ph.D. (Colorado)-software engineering, component-based systems; R. T. Hartley, Ph.D. (Brunel)-programming systems, computer music; J. He, Ph.D. (Baylor College of Medicine)-computational biology; H. Leung, Ph.D. (Penn State-University Park)-automata theory; J. J. Pfeiffer, Jr., Ph.D. (Washington)-visual programming; I. Pivkina, Ph.D. (Kentucky)-artificial intelligence, knowledge representation, logic programming; E. Pontelli, Ph.D. (New Mexico State)- parallel processing, logic programming, knowledge representation, bioinformatics, assistive technologies; M. Song, Ph.D. (Washington)- statistical computing, systems biology, computational neuroscience, computer vision; S. C. Tran, Ph.D. (Texas-El Paso)-artificial intelligence, logic programming, nonmonotonic reasoning; K. Villaverde, Ph.D. (New Mexico State)-interval computations, computer gaming

Support and Adjunct Faculty:

S. Cooper, Ph.D. (New Mexico State)-computer networks; J. Cowie, Ph.D. (Strathclyde)-natural language processing; D. Farwell, Ph.D. (Illinois-Urbana)-artificial intelligence, linguistics, natural language processing; S. Helmreich, Ph.D. (Illinois)-natural language processing, machine translation; W.C. Ogden, Ph.D. (New Mexico State)-human computer interaction, natural language processing; E. Steiner, Ph.D. (Oklahoma State)-computer science education; C. Strauss, Ph.D. (Cornell)-computational biology; M. Wolinski, Ph.D. (MIT)-computational biology

Mission of the Department

The mission of the Department of Computer Science at New Mexico State University is to provide formal education in the core disciplines of computer science as well as to prepare our graduates for research, development, and academic careers. The department offers specific expertise in specialized research areas, such as bioinformatics, artificial intelligence and knowledge representation, software engineering and programming languages, computer and wireless networks, parallel computing, interval computations, algorithms and theory of computing. A number of laboratories have been established to coordinate research activities, including the Knowledge representation, logic, and advanced programming (KLAP) laboratory, the Programming languages, environments, and automated software engineering (PLEASE) laboratory, and the Pervasive Embedded Computing and Networking (PECaN) laboratory. The Department members are also directing the CREST Center for Research Excellence in Bioinformatics and Computational Biology, offering educational and research opportunities in bioinformatics.

Entrance Requirements for Graduate Study in Computer Science

The Graduate Record Exam (GRE) General Test is not required for admission; however, high GRE scores will strengthen a candidate's application and are highly regarded in the awarding of Graduate Assistantships. To be admitted without undergraduate deficiencies, an entering student must have completed undergraduate preparation substantially equivalent to that required for the Bachelor of Science degree in computer science at New Mexico State University, including the courses C S 471, C S 473, C S 474, and others. Deficiencies should be satisfied as early in the student graduate program as possible, through the regular undergraduate courses, the C S 469 transition courses, or through tests administered by faculty members in the relevant areas. Students should consult with their Graduate Advisor to address issues related to deficiencies. Deficiencies are also assigned to applicants whose transcripts denote low grades in selected areas. Admission is often denied to candidates with little background in Computer Science.

Doctor of Philosophy in Computer Science

Doctoral students may specialize in any of the areas in which computer science faculty have active research interests. Through interdisciplinary arrangements with other doctoral departments at New Mexico State University, doctoral students may also specialize in such areas as computational biology, computer networks, and cognitive science.

Doctoral students are expected to join the program with a preparation equivalent to that required for the Master's degree in computer science at New Mexico State University. The requirements for the degree are as specified in the NMSU graduate catalog, with the following specific considerations:

The qualifying examination is implemented as a written examination, which examines the depth of knowledge in five areas of computer science. The five areas are Formal Languages and Computability, Analysis of Algorithms, Programming Languages, one between Operating Systems and Computer Architecture, and a fifth area agreed between the student and the department's Graduate Committee.
The comprehensive examination evaluates depth of knowledge in the specific research area selected by the candidate.
The student is required to submit and defend a prospectus, at the same time or after completing the comprehensive examination. The prospectus describes and motivates the specific research problem to be addressed in the doctoral dissertation.

Students should contact the department for information on additional graduation requirements, or visit the on-line Graduate Handbook (http://www.cs.nmsu.edu/~gradrep/handbook/handbook.html).

Master of Science in Computer Science

Each master's student normally must write a thesis (C S 599) or, with the advisor's permission, undertake a research project (C S 598). In either case, the number of required graduate credits is 33, including 6 for the thesis or project. In all cases, the students are required to sustain a final exam, covering the thesis/research project and the graduate course-work. The two parts of the exam brings equal weight.

With the advisor's and department head's written consent, the student may instead take 36 credits of regular course work.

In no case may C S 469, C S 471, C S 473, or C S 474, or any of the graduate service courses (C S 467, C S 477, and C S 487) be counted towards the number of credits. In particular, graduate students are expected to register for CS classes numbered 500 or above. The student's program must include:

C S 510
C S 570
One of: C S 573, C S 574, C S 584
One of: C S 571, C S 575, C S 580, C S 581, C S 582
One additional course selected between: C S 550, C S 571, C S 572, C S 573, C S 574, C S 575, C S 580, C S 581, C S 582, C S 584,
One additional computer science course numbered above 550 and
different from C S 598, C S 599, C S 600, and C S 700.

Courses not in Computer Science can be included in the student's program of study only if prior written approval has been obtained from the student's advisor and the departmental Graduate Committee. Further details can be found in the on-line Graduate Handbook (http://www.cs.nmsu.edu/~gradrep/handbook/handbook.html).

Assistantships

Graduate assistantships — in the form of Teaching and Research assistantships — are expected to be available during the academic year. Inquiries should be addressed to the departmental Graduate Committee. Research assistantships are available at the discretion of individual research project leaders in the Department or elsewhere on campus. Submitting detailed vitae, letters of reference, and GRE test scores is encouraged when applying for any assistantship.

COMPUTER SCIENCE

C S 451. Functional Programming 3 cr.: Applicative programming techniques: higher order functions, infinite data structures, lambda calculus, universal functions. Survey of functional languages including Miranda and ML. Not for C S graduate students. Prerequisites: At least a C in C S 272 and C S 278.

C S 461. Logic and Constraint Logic Programming 3 cr.: Declarative programming techniques; foundations of logic programming; programming in Prolog; constraint logic programming; applications of logic and constraint programming. Not for C S graduate students. Prerequisites: at least C in C S 272 and C S 278.

C S 467. C Programming 3 cr. (2+3P): Programming in the C language. More advanced than C S 167. Recommended for nonmajors only. Prerequisite: graduate standing.

C S 469. Computer Science Graduate Transition 3 cr.: C S students should register for this course to meet assigned deficiencies. For C S graduate students only; cannot be used in a student's program of study; may be retaken to meet multiple deficiencies. Prerequisite: corresponding assigned deficiency.

C S 471. Progamming Language Structure 1 3 cr.: Syntax, semantics, implementation, and application of programming languages; abstract data types; concurrency. Not for C S graduates. Prerequisites: C or better in C S 370 and C S 371.

C S 472. Introduction to Data Structures 4 cr. (3+3P): Design, implementation, and use of fundamental abstract data types and their algorithms; lists stacks, queues, trees; searching and sorting; time and space efficiency of algorithms. Prerequisite: graduate standing.

C S 473. Architectural Concepts I 3 cr.: Comparison of architectures to illustrate concepts of computer organization; relationships between architectural and software features. Not for C S graduate students. Prerequisites: at least a C in C S 273 and C S 370.

C S 474. Operating Systems I 3 cr.: Operating system principles and structures, and interactions with architectures. Not for C S graduate students. Prerequisites: at least a C in C S 273, C S 371, and C S 372.

C S 475. Artificial Intelligence 1 3 cr.: Fundamental principles and techniques in artificial intelligence systems. Knowledge representation formalisms; heuristic problem solving techniques; automated logical deduction; robot planning methods; algorithmic techniques for natural language understanding, vision, and learning. Not for C S graduate students. Prerequisites: At least a C in MATH 330 and C S 372.

C S 476. Computer Graphics I 3 cr.: Languages, programming, devices, and data structures for representation and interactive display of complex objects. Not for C S graduate students. Prerequisites: at least C in C S 272 or C S 273, MATH 280, MATH 291.

C S 477. C Programming 3 cr.: Programming in the C language. More advanced than C S 177. Recommended for nonmajors only. Prerequisite: graduate standing.

C S 479. Special Topics 1-3 cr.: Topic announced in the Schedule of Classes. May be repeated if subtitle is different. Not for C S graduate students. Prerequisite: written agreement with instructor.

C S 481. Visual Programming 3 cr.: Design and implementation of languages using visual but nontextual means to specify programs. Not for C S graduate students.

C S 482. Database Management Systems I 3 cr.: Database design and implementation; models of database management systems; privacy, security, protection, recovery. Not for C S graduate students. Prerequisites: at least a C in C S 272 and either C S 278 or MATH 279 or MATH 330.

C S 483. Introduction to Robotics 3 cr.: Basic AI-based robotic architecture and concepts, with an emphasis on building and programming mobile robots. Not for C S graduate students.

C S 484. Computer Networks I 3 cr.: Fundamental concepts of computer communication networks: layered network architecture, network components, protocol stack and service. Example of application, transport, network and data link layers, protocols primarily drawn from the Internet (TCP, UDP, and IP) protocol multimedia networks; network management and security. Not for C S graduate students. Prerequisites: At least a C in C S 272 and CS 273, senior or graduate standing or consent of instructor. STAT 371 or STAT 470 recommended.

C S 485. User Interface Design 3 cr.: Interface design, conceptual models formed by users, computer aided instruction, natural and query languages, graphical representations. Not for C S graduate students. Prerequisite: at least C in C S 371.

C S 486. Bioinformatics 3 cr.: Introduction to bioinformatics and computational biology. Computational approaches to sequences analysis, protein structure prediction and analysis, and selected topics from current advances in bioinformatics. Not for C S graduate students.

C S 487. Java Programming 3 cr. (2+2P): Programming in the Java language. More advanced than C S 187. For nonmajors only. Prerequisite: graduate standing.

C S 491. Parallel Programming 3 cr.: Programming of shared memory and distributed memory machines; tools and languages for parallel programming; techniques for parallel programming; parallel programming environments. Not for C S graduate students. Prerequisite: C or better in C S 370 or consent of instructor.

C S 492. Computer Systems Modeling and Simulation 3 cr.: Basic concepts of modeling computer systems: continuous and discrete time models, states and transition, probabilistic models. Structure of simulation programs, time driven and event driven simulation on captured and synthetic traces, generation of random variables, queuing models, Markov chains, random walks, Poisson, Markov, renewal branching and Brownian motion processes, model validation and data analysis. For C S undergraduate students and non-C S graduate students only.

C S 501. Functional Programming 3 cr.: Applicative programming techniques: higher order functions, infinite data structures, lambda calculus, and universal functions. Survey of functional languages including Miranda and ML; requires more advanced graduate work than C S 451.

C S 502. Database Management Systems I 3 cr.: Database design and implementation; models of database management systems; privacy, security, protection, recovery; requires more advanced graduate work than C S 482. Prerequisite: At least a C in C S 272 and either C S 278, MATH 279, or MATH 330.

C S 503. Introduction to Robotics 3 cr.: Basic AI-based robotic architectures and concepts, with an emphasis on building and programming mobile robots; requires more advanced graduate work than C S 483.

C S 504. Computer Networks I 3 cr.: Fundamental concepts of computer communication networks: layered network architecture, network components, protocol stack and service. Example of application, transport, network and data link layers, protocols primarily drawn from the Internet (TCP, UDP, and IP) protocol suite; local and wide area networks, wireless and mobile networks, multimedia networks; network management and security; requires more advanced graduate work than C S 484.

C S 505. Artificial Intelligence I 3 cr.: Fundamental principles and techniques in artificial intelligence systems. Knowledge representation formalisms; heuristic problem solving techniques; automated logical deduction; robot planning methods; algorithmic techniques for natural language understanding, vision and learning; requires more advanced graduate work than CS 475.

C S 506. Computer Graphics I 3 cr.: Languages, programming, devices, and data structures for representation and interactive display of complex objects.

C S 507. Visual Programming 3 cr.: Design and implementation of languages using visual but non-textual means to specify programs; requires more advanced graduate work than C S 481.

C S 510. Automata, Languages, Computability 3 cr.: Regular and context-free languages, pushdown and finite-slate automata, turing machines, models of computation, halting problems. Prerequisite: at least C in C S 370 and C S 372.

C S 511. Logic and Constraint Logic Programming 3 cr.: Declarative programming techniques; foundations of logic programming; programming in Prolog; constraint logic programming; application of logic and constraint programming; requires more advanced graduate work than C S 461. Prerequisite: At least a C in C S 272 and C S 278, or consent of instructor.

C S 512. Computer Systems Modeling and Simulation 3 cr.: Basic concepts of modeling computer systems: continuous and discrete time models, states and transition, probabilistic models. Structures of simulation programs, time driven and event driven simulation, simulation on captured and synthetic traces, generation of random variables, queuing models, Markov chains, random walks, Poisson, Markov, renewal branching and Brownian motion processes, model validation and data analysis; requires more advanced graduate work than C S 492.

C S 515. User Interface Design 3 cr.: Interface design, conceptual models formed by users, computer-aided instruction, natural and query languages, graphical representations; requires more advanced graduate work than C S 485.

C S 516. Bioinformatics 3 cr.: Introduction to bioinformatics and computational biology. Computational approaches to sequences analysis, protein structure prediction and analysis, and selected topics from current advances in bioinformatics; requires more advanced graduate work than C S 486.

C S 521. Parallel Programming 3 cr.: Programming of shared memory and distributed memory machines; tools and languages for parallel programming; parallelizing compiliers; parallel programming environments; requires more advanced graduate work than C S 491.

C S 550. Complexity Theory 3 cr.: Polynomially bounded, NP-complete, exponentially hard, and undecidable problems; reducibility. Prerequisite: C S 510.

C S 552. Introduction to Computational Science and Engineering 3 cr.: Modeling of scientific and engineering problems; computational methods for solving such problems including data structure design and relevant discrete and numerical algorithms. Prerequisite: consent of instructor.

C S 560. Graph Theory 3 cr.: Graph theoretic models in all areas of computer science including computer architectures, computation geometry, fault tolerance, databases. Includes connectivity, colorability, factorization, topological embeddings in surfaces, reconstruction, groups and matrices associated with graphs.Prerequisite: consent of instructor.

C S 562. Advanced Computational Science and Engineering 3 cr.: Introduction to high-performance computing, parallel programming, computational methods using high-performance computers. In-depth study of applications from science and engineering including mathematical modeling, sequential and parallel algorithm design, implementation, and performance tuning. Prerequisite C S 552.

C S 570. Analysis of Algorithms 3 cr.: Techniques for design and analysis of algorithms; time and space complexity; proving correctness of programs. Particular algorithms such as sorting, searching, dynamic programming. NP complete problems. Prerequisite: at least C in C S 372.

C S 571. Programming Language Structure II 3 cr.: Formal semantics of programming languages. Prerequisites: C S 372, C S 471.

C S 572. Advanced Algorithms 3 cr.: Design, analysis, and use of important algorithms and data structures. Prerequisite: C S 570 or consent of instructor.

C S 573. Architectural Concepts II 3 cr.: Advanced topics related to computer architecture, guided by the current literature. Prerequisites: C S 473, C S 474.

C S 574. Operating Systems II 3 cr.: Advanced topics related to operating system principles, guided by the current literature. Prerequisites: C S 473, C S 474.

C S 575. Artificial Intelligence II 3 cr.: Covers advanced theory and application of artificial intelligence. Concentration on several specific research areas, such as knowledge representation, problem solving, common-sense reasoning, natural language understanding, automated tutoring systems, learning systems. Prerequisites: C S 475 or CS 505 or consent of instructor.

C S 579. Special Topics 1-6 cr.: Topic announced in the Schedule of Classes. Prerequisite: written agreement with instructor. May be repeated if subtitle is different.Prerequisite: consent of instructor.

C S 580. Compiler Construction 3 cr.: Current methods in the design and implementation of compilers; construction of components of an actual compiler as a term project. Prerequisites: C S 471, C S 510.

C S 581. Advanced Software Engineering 3 cr.: Advanced tools and methods for developing large software systems. Topics include object-oriented modeling and design, component architectures, templates and generic programming, software configuration and revision control, static and dynamic analysis tools, model, checking, advanced testing, and verification. Prerequisite: C S 371.

C S 582. Database Management Systems II 3 cr.: Advanced data models and abstractions, dependencies, implementations, languages, database machines, and other advanced topics. Prerequisite: C S 482 or 502 or consent of instructor.

C S 584. Computer Networks II 3 cr.: Advanced topics related to computer networks, guided by current literature. Prerequisite: C S 484 or C S 504, one of C S 492 or C S 512 or I E 467 and I E 515 or STAT 470 and STAT 535.

C S 589. Special Research Problems 1-6 cr.: Faculty-supervised investigation, to culminate in a written report. Prerequisite: written agreement with faculty supervisor. May be repeated; maximum of 6 credits may be applied toward M.S. degree. Restricted to majors.

C S 598. Master's Project 1-6 cr.: Project-oriented capstone course to be completed by M.S. students under supervision of their advisor. Maximum of 6 credits may be applied toward M.S. degree. Prerequisite: written agreement with instructor. Restricted to C S majors.

C S 599. Master's Thesis 1-6 cr.: Thesis to be developed by M.S. Students under supervision of their advisor. Prerequisite: consent of instructor. May be repeated for a maximum of 6 credits. Restricted to majors.

C S 600. Pre-dissertation Research 1-88 cr.: Pre-dissertation research.

C S 629. Selected Topics in Computer Science 1-3 cr.: Topics of current interest designated by subtitle. May be repeated.

C S 700. Doctoral Dissertation 0-88 cr.: Dissertation.