Graduate Catalog

2012-2013

COMPUTER SCIENCE

Department website: http://www.cs.nmsu.edu

(575) 646-3723

csoffice@cs.nmsu.edu

E. Pontelli, department head, Ph.D. (New Mexico State University) – parallel processing, logic programming, knowledge representation, bioinformatics, assistive technologies; H. Cao, Ph.D. (Hong-Kong) – data mining, databases, data integration; J. Cook, Ph.D. (Colorado) – software engineering, component-based systems; Y. Jin, Ph.D. (Texas A&M University) – computer architectures, interconnection networks, multicore architectures; H. Leung, Ph.D. (Penn State-University Park) – automata theory; S. Misra (Arizona State) – communication networks, social networks, high performance computing, security and privacy; I. Pivkina, Ph.D. (Kentucky) – artificial intelligence, computer science education, data mining; M. Song, Ph.D. (Washington) – statistical computing, systems biology, computer vision; S. C. Tran, Ph.D. (Texas-El Paso) – artificial intelligence, knowledge representation, planning, logic programming, non-monotonic reasoning; K. Villaverde, Ph.D. (New Mexico State) – interval computations, educational computer gaming

Support and Adjunct Faculty:

S. Cooper, Ph.D. (New Mexico State) – computer networks; J. Cowie, Ph.D. (Strathclyde) – natural language processing; R. T. Hartley, Ph.D. (Brunel) – programming systems, computer music; J.J. Pfeiffer, Jr., Ph.D. (Washington) – visual programming; E. Steiner, Ph.D. (Oklahoma State) – computer science education

DEGREE: Master of Science
MAJOR: Computer Science

DEGREE: Master of Science
MAJOR: Bioinformatics

DEGREE: Doctor of Philosophy
MAJOR: Computer Science

MINOR: Computer Science

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 several 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 Game Design 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. Deficiencies should be satisfied as early in the student graduate program as possible, through the regular undergraduate courses, the C S 460- 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. Instructions for prospective applicants can be found at http://www.cs.nmsu.edu.

Entrance Requirements for Graduate Study in Bioinformatics

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. Students wishing to enroll in the Master program in Bioinformatics must meet the following criteria:

1. Hold a BS degree, from an accredited institution of higher learning, in either a computational field (e.g., Computer Science) or in life sciences (preferably Biology, Biochemistry, or Environmental Sciences)
2. Hold a minimum grade point average of 3.2

Applicants will be expected to provide a Career statement, motivating the interest in bioinformatics and a minimum of three letters of reference.

DEGREE: Doctor of Philosophy
MAJOR: 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 additional 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. Doctoral students are required to take the qualifying examination on or before the date indicated in their departmental admission referral.
• The comprehensive examination evaluates depth of knowledge in the specific research area selected by the candidate. The comprehensive exam includes both a written part, in the form of an extensive survey paper and an annotated bibliography, and an oral examination.
• 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/).

DEGREE: Master of Science
MAJOR: 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 bring equal weight.

In no case may a C S course numbered below 500 be counted towards the number of credits. In particular, graduate students are expected to register for C S 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/).

With the advisor's consent, the student may instead complete a coursework-only Master degree; this requires 36 credits of regular course work, satisfying the same requirements listed above, except that the 6 credits of thesis or project are replaced by 9 credits of courses numbered 550 or above and distinct from C S 589, C S 598, and C S 599. Students pursuing a coursework-only degree are expected to complete a written exam covering a selected subset of the students' plan of study. Further details can be found in the on-line Graduate Handbook (http:www.cs.nmsu.edu/)

DEGREE: Master of Science
MAJOR: Bioinformatics

The degree requirements include 30 graduate credit hours. The requirements are structured as follows:

1. Introductory Courses (9 credit hours): these courses provide foundational preparation in biological sciences and computational sciences. They will be organized along two tracks.
• Computational Track: these courses are intended for students with a Bachelor's degree in life sciences; the required courses are C S 462, C S 468, and C S 469.
• Life Sciences Track: these courses are intended for students with a Bachelor's degree in computer sciences; the required courses are BIOL 520, MOLB 542 and MOLB 545.

These courses can be replaced by more advanced courses with written permission of the graduate advisor.

2. Core Courses (9 credit hours): The goal of these courses is to expose the students to the central issues and techniques in the field of bioinformatics. The core courses are:
• C S 516
• MOLB 470 or GENE 452 (Bioinformatics and Genome Analysis) or GENE 452 (Applied Bioinformatics) or BIOL 550 (Bioinformatics Applications and Databases)
• C S 502 or C S 579 (Data Mining)
3. Elective Courses (6 credit hours): The goal of these courses is to allow students to specialize in a specific branch of bioinformatics. The courses can be selected among the following: C S 502, C S 521, C S 570, C S 572, C S 575, C S 579, C S 581, BIOL 470, AGRO/HORT 506, BIOL 474, BIOL 475, BIOL 490, BIOL 557, BIOL 567, BIOL 569, BIOL 586, BIOL 550.
4. Master's Project / Thesis (6 credit hours): Each master's student must write a thesis (C S 559) or, with the advisor's permission, undertake a research project (C S 598). In either case, the number of required graduate credits is 6 for the thesis or project. In all cases, the students are required to sustain a final exam, covering the thesis / research project.

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 450. C Programming 3 cr. (2+3P)

Programming in the C language. More advanced than C S 167. Recommended for nonmajors only. Prerequisite(s): Graduate standing. Restricted to: Main campus only.

C S 451. C++ Programming 3 cr.

Programming in the C language. More advanced than C S 177. Recommended for nonmajors only. Prerequisite(s): Graduate standing.

C S 452. Java Programming 3 cr. (2+2P)

Programming in the Java language. More advanced than C S 187. For nonmajors only. Prerequisite(s): Graduate standing. Restricted to: Main campus only.

C S 457. Topics in Software Programming and Applications 3 cr. (2+2P)

Current topics in computer programming and software applications. Topic announced in the Schedule of Classes. More advanced than CS 157. recommended for non-majors only. May be repeated if subtitle is different. Prerequisite(s): Graduate standing.

C S 460. Computer Science I Transition 3 cr.

Computational problem solving; problem analysis; implementation of algorithms. Recursive structures and algorithms. For CS graduate students only; cannot be used in a student's program of study. Taught with C S 172. Consent of instructor required.

C S 462. Object Oriented Programming Transition 3 cr.

Introduction to problem analysis and problem solving in the object-oriented paradigm. Practical introduction to implementing solutions in the C++ language. Hands-on experience with useful development tools. For C S graduate students only; cannot be used in a student's program of study. Consent of instructor required. Prerequisite(s): At least a C in CS 172 or CS 460 or consent of instructor.

C S 463. Introduction to Data Structures Transition 3 cr.

Design, implementation, use of fundamental abstract data types and their algorithms: lists, stacks, queues, deques, trees; imperative and declarative programming. Internal sorting; time and space efficiency of algorithms.For C S graduate students only; cannot be used in a student's program of study. Consent of instructor required. Prerequisite(s): At least a C in CS 172 or CS 460 or consent of instructor.

C S 464. Machine Programming and Organization Transition 3 cr.

Computer structure, instruction execution, addressing techniques; programming in machine and assembly languages. For C S graduate students only; cannot be used in a student?s program of study. Consent of instructor required. Prerequisite(s): At least a C in C S 172 or C S 460 or consent of instructor.

C S 465. Discrete Math for Computer Science Transition 3 cr.

Logical connectives, sets, functions, relations, graphics, trees, proofs, induction, and application to computer science. For C S graduate students only; cannot be used in a student?s program of study. Consent of instructor required. Prerequisite(s): At least a C in C S 172 or C S 460 or consent of instructor.

C S 466. Compilers and Automata Transition 3 cr.

Methods, principles, and tools for programming language processor design; basics of formal language theory (finite automata, regular expressions, context-free grammars); development of compiler components. For C S graduate students only; cannot be used in a student?s program of study. Consent of instructor required. Prerequisite(s): At least a C in C S 271 or C S 462, in C S 272 or C S 463, in C S 273 or C S 464, in C S 278 or C S 465, or consent of instructor.

C S 468. Software Development Transition 3 cr.

Software specification, design, testing, maintenance, documentation; informal proof methods; team implementation of a large project. For C S graduate students only; cannot be used in a student?s program of study. Consent of instructor required. Prerequisite(s): At least a C in C S 271 or C S 462, in C S 272 or C S 463, or consent of instructor.

C S 469. Data Structure and Algorithms Transition 3 cr.

Introduction to efficient data structure and algorithm design. Order notation and asymptotic run-time of algorithms. Recurrence relations and solutions. Abstract data type dynamic set and red-black trees. Classic algorithm design paradigms: divide-and-conquer, dynamic programming, greedy algorithms. For C S graduate students only; cannot be used in a student?s program of study. Consent of instructor required. Prerequisite(s): At least a C in C S 272 or C S 463, in C S 278 or C S 465, or consent of instructor.

C S 470. 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. Prerequisite(s): At least a C in C S 272 and C S 278.

C S 471. Programming Language Structure I 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. 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. Prerequisite(s): At least C in C S 272 and C S 278.

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 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. 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 291G.

C S 478. Computer Security 3 cr.

Introduction to the art and science of computer security.Fundamentals of computer security including elementary cryptography, authentication and access control, security threats, attacks, detection and prevention in application software, operating systems, networks and databases. Prerequisite(s): At least a C in CS 273 or consent of instructor.

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 480. Linux System Administration 3 cr.

Basic system administration for Linux environments. Topics include user managements, file systems, security, backups, system monitoring, kernel configuration and other relevant aspects of system administration. Not for Computer Science graduate students.

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 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 470.

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 472. Prerequisite(s): 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 compilers; 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 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 in computer networks. Covers advanced topics in networking, with emphasis on wireless, and IP networks. Prerequisite(s): C S 484 or C S 504, STAT 371 or STAT 470 or by consent of instructor.

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.