Computer and Information Science Elective and Special Topics Course Descriptions

Spring 2009

Undergraduate Elective Offering
* denotes special topics offering

Graduate Elective Offering
* denotes special topics offering

We use computers to imitate, or simulate, the operations of a facility or process called a system. This imitation is a model of the system. Computer simulation has been used to analyze the operation and behavior of many kinds of systems, including computer networks, fast-food restaurants, city traffic, gold/silver mines, shipping ports, and the stock market.

This course introduces the tools and techniques for writing computer programs that model and simulate systems. First the students learn to implement discrete-event simulation programs using a general-purpose programming language, such as C, C++, or Java. Then the students learn to use two simulation programming languages, SIMSCRIPT and GPSS.

After completing this course, a student should be able to:

1. identify and model relevant characteristics and behaviors of system entities
2. understand the internals of a discrete-event simulation engine
3. select appropriate probability distributions for random-number generation
4. determine and collect meaningful statistics of system performance.

As the drive to increase clock speeds on traditional CPUs runs up against Moore's Law and the rules of physics, designers have increasingly turned to parallelism to improve performance. Cluster and Grid computing, multicore designs, and even programming on graphics cards are all recent examples of parallel approaches to computation. However, programming for these architectures is very different from the serial case, requiring new algorithms, tools, and programming methodologies. This course will explore the design and implementation of parallel programs on several different architectures.

Upon successful completion of this course, the students should be able to:

1. Understand the architectural differences between various parallel platforms and how the differences affect performance.
2. Design an efficient parallel solution to a significant problem for various architectures.
3. Implement parallel programs for shared memory machines using Java threads.
4. Implement parallel programs for distributed architectures using MPI and C.
5. Implement parallel programs for a GPU using the CUDA C environment.

An operating system is the fundamental software that runs on modern personal computers, servers, and embedded devices. Understanding the functionality and limitations of modern operating systems is integral to the design and implementation of computer software, as well as, the design and production of computer hardware. This course is an ideal complement to any graduate or undergraduate computer science program of study. For that matter, the course would be valuable for any student wishing a deeper understanding of how computing systems work or who want to use computers to monitor or control other processes.

This course uses lecture and readings to examine the traditional theoretical aspects of operating systems including: processes, interprocess communication (IPC), scheduling, synchronization, memory management, virtual memory, input/output systems, and file systems.

Additionally, the course augments the theory with an innovative hands-on project. The project includes the study and implementation a version of the Xinu operating system for a commodity embedded device (the Linksys WRT54GL router). Students will utilize a laboratory including 12 WRT54GL routers to implement functionality for the following parts of the Xinu operating system: synchronous and asynchronous input/output device driver, process creation, context switch, process scheduling mechanism, process scheduling algorithms, memory management, and a file system.

The project is both accessible to students and provides familiarity with increasingly prolific embedded devices. The accessibility is a result of using the simple, but fully functional, Xinu operating system in combination with the WRT54GL router's simple RISC MIPS architecture. Further, the use of a WRT54GL router gives students valuable hands-on experience programming real embedded devices.

For more information see the University of Mississippi's Xinu Laboratory web site (http://www.cs.olemiss.edu/~ruth/xinu) or contact Dr. Ruth (ruth at cs dot olemiss dot edu).

This course introduces the basic concepts in robotics and artificial intelligence (AI). This course will also provide students hands-on experience in the design, constructing, and programming robots that are driven by a micro-controller (LEGO NXT mobile robots).

Upon completion of this course, students should be able to explain the basic knowledge representation, problem solving, and learning methods of AI; develop intelligent systems by assembling solutions to concrete computational problems; understand the role of knowledge representation, problem solving, and learning in intelligent-system engineering, and appreciate the role of problem solving, vision, and language in understanding human intelligence from a computational perspective.

This course covers the fundamental computational methods of computer-generated 3D animations for applications in film production and computer games. The focus of the course is on understanding and implementing fundamental algorithms used in animation softwares. This course will not cover writing animation scripts using any particular animation softwares, nor the production pipeline of generating computer animation films such as story-boarding, scene composition, lighting, and sound track generation. By the end of the course, the students should be able to:

• Read and evaluate state-of-the-art computer animation techniques in the literature
• Write software or plug-ins using various animation techniques that can produce animated sequences.

Currently, the instructor plans to cover the following topics in computer animations:

• Mathematical models of smooth curves including Bezier, Hermite splines, B-Splines, and NURBS applied to key-framing techniques for animations
• Forward and backward kinematics using optimization algorithms, with the application of articulated rigid object animations
• Physical-based models with applications on particle systems for sand, water, or hair simulations
• Extension of particle systems on collision detections and crowd systems
• Motion capture techniques and data-driven deformations based on radial basis functions with the application on facial animations
• Animations generated from camera motions, and motion blur algorithms

There will be four computer assignments, including:

• Basic programing environment setup using OpenGL and C/C++
• A simple animation tool based on key-framing and inverse-kinematics
• A simple simulation of sand with a particle system
• A simple talking face animation using motion capture data

Please note that all the programming assignments will be built on top of an existing rendering system, so the students can focus on the animation engine only. The fundamentals of OpenGL will be reviewed at the beginning of the course.

There will be a final project, preferably in teams of two people, producing a character animation sequence with a minimum length of 30 seconds. The animation needs to be generated from algorithms that involve at least three techniques covered in the course (e.g. inverse kinematics, key-frame blending, particle simulations, crowd, MoCap data-driven).

There will be a final exam in the form of a series of short questions to let the students show their knowledge on the theoretical concepts of computer animation.

Computer animations have been widely used in film productions and games, yet there are still many challenges to improve the automation of computer-generated animations. This study opens the door for research and development in the field of computer animation and simulations.

In recent years, interest in domain-specific languages (DSLs) and language-oriented programming has grown in both industry and academia. For example, the popular Ruby on Rails web framework consists of several DSLs embedded in Ruby. Microsoft also supports DSL development in its Visual Studio toolset. On the Java platform, JMock is an example of an internal DSL to support software unit testing.

This study focuses on the design and implementation of external and internal DSLs. A DSL is a simple language with a syntax and semantics focused on a specific application area, perhaps meant to be used by experts on that application who are not necessarily expert programmers. An external DSL consists of a language separate from the DSL processor's host language. An internal DSL consists of the restricted usage of the host language itself to create the specialized language syntax and semantics.

Likely topics consist of the principles and practice of DSL development including the use of techniques such as commonality/variability analysis to design languages, syntactic processing to build abstract syntax trees (ASTs), and implementation of simple interpreters to evaluate the ASTs. The study will use an evolving set of design patterns identified by experts on DSLs and utilize language or API features such as parser combinators, function closures, algebraic types, and metaprogramming.

The course's case studies and projects will use one or two contemporary languages with good support for DSLs. These include the statically typed, multiparadigm language Scala and the dynamically typed application languages Ruby and Groovy. Scala includes a flexible syntax, type inferencing, closures, a powerful set of parser combinators, built-in support for XML processing, and other features of interest for language processing or DSL construction. Ruby and Groovy are also very flexible languages with powerful reflexive metaprogramming facilities (i.e., the ability of a program to inspect and modify itself) that are useful in DSL implementation.

Upon successful completion of this course, the students should:

• understand the concepts of domain-specific languages
• be able to analyze a problem and apply the DSL concepts to design a DSL solution, if appropriate to the problem and environment
• be able to implement an external DSL using appropriate language-processing tools
• be able to implement an internal DSL using an appropriate host language.

This is a course on algorithms, with interesting applications drawn from the biological domain.

Computing topics covered include: algorithm analysis, exhaustive search, greedy algorithms, dynamic programming, divide-and-conquer techniques, graph algorithms, combinatorial pattern matching, randomized algorithms, and hidden Markov models.

The biological problems considered will include: mapping DNA, sequencing DNA, comparing sequences, gene prediction, finding signals, protein identification, DNA microarray analysis, and molecular evolution.

[ Home | Site Map ]