Second Exam

Search in Artificial Intelligence (AI) is a well known area of research with many real applications, such as expert systems, finding the shortest path to a location, two-person board games such as chess, Othello, checkers and related problems.  We describe the basic blind search techniques, such as the Depth-First Search (DFS), the Breadth-First Search (BFS) and the Depth-First Search with Iterative Deepening (DFSID) by Korf (1990).  We discussed the advantages and drawbacks of each approach.  Later we discuss and summarize diverse heuristic search algorithms and describe how these algorithms can overcome the drawbacks of blind search algorithms.  Some classes of heuristic search algorithms have been studied well.  However, the bidirectional heuristic search (BHPA) has mainly been a topic of limited research and application since it was introduced by Pohl (1971).  Different bidirectional search methods developed by Kaindl & Kainz (1997) are presented in the last section (5).  We conclude our discussion with AI programming languages used for heuristic search schemes.

Biological function of gene products such as proteins mediate through interactions they make with one another. In humans, a larger numbers of proteins are expected to engage in hundreds of thousands of interactions, many of which involve large assemblies and play key roles in cellular function and disease. Such assemblies are, however, still rather poorly represented in the Protein Data Bank (PDB). Computational procedures capable of reliably generating structural models of multi-protein assemblies starting from the atomic coordinates of individual components, the so-called “protein-protein docking” methods, will help in generating models of protein complexes. The 3D structures of protein complexes are pivotal for a full understanding of the mechanism of interactions because they provide specific interaction details at the atomic level. Such details are important for rational design of drug molecules to modulate protein interactions. In order to predict the interface regions one needs to know what distinguishes an interface region from the rest of the protein. Several attempts have been made in the literature using physicochemical properties like surface residue energy distributions, residue conservation and propensity information and salvation energies etc and also using numerical and probabilistic methods some of which uses these properties. However none of these are significantly successful in predicting or modeling the structures. This review paper gives an overview of the various methods developed in the literature for predicting the interaction sites on the protein surfaces over the last fifteen years.

This paper presents a review of the multitasking literature from the perspective of human-computer interaction(HCI).  Based on Norman's framework that describes the cycle of an action, this review is focused on the variations that emerge in terms of executing actions when users perform multiple tasks concurrently.  Users generally switch computer-based tasks either due to a personal decision to break from the current task or due to an external interruption, such as an electronic notification.  Therefore interruptions generated from notifications are addressed as well.  Studying user multitasking can assist HCI researchers in developing a more comprehensive understanding of how people actually interact with their computers.

Web services composition is an emerging paradigm for defining complex web services from standard web services.  The Web Services Business Process Execution Language (WS-BPEL) is the standard for specifying and executing workflow specification for web service composition.  As with any system that supports complex constructs such as currency, testing approach alone is not an effective method for detecting faults.  Hence there is a growing interest in formal modeling, analysis and verification of WS-BPEL in order to detect bugs, ensure correctness of desired properties among others.  Also maintaining a system of complex business processes with multiple business partners can be quite cumbersome.  Program slicing as a static analysis technique can be used in acquiring better understanding of a program.  In this paper, we provide an overview of program slicing, formal methods (model checking, theorem proveers) and formal analysis techniques that have been applied to WS-BPEL over the years.

Topology control in MANETs is an important current area of research.  The objectives of topology control include:  maintaining network connectivity, ameliorating energy efficiency, increasing throughput, reducing interference, providing mobility-resistance.  In this talk, I give an introduction to the problems and techniques of topology control algorithms, within the framework of taxonomy of power-based approaches.  Finally, I will describe recent developments and open problems in the area.

Phylogenetic inference is an important question posed in biological research: what are the ancestor-descendent relationships between modern organisms?  Modern techniques of phylogenetic inference employ an optimality criterion in hypothesis selection (Maximum Parsimony, Maximum Likelihood, and Bayesian analysis).  Maximum parsimony attempts to minimize the number of transformations required to explain the observed characteristics among living organisms.  Its computational counterpart is known as the Steiner tree problem.  We present an overview of the hardness, most important algorithms, and heuristics employed for the Steiner tree problem under biologically interesting spaces such as  hamming, manhattan, discrete, edition, breakpoint, inversion, and double cut and join.

Almost half a million Americans die of cardiac arrhythmias following a myocardial infarction (heart attack) every year, according to the American Heart Association. Arrhythmias are a consequence of the functional remodeling of ionic channels and gap junctional proteins that follow a myocardial infarction. Ionic channels are proteins embedded in the cell membrane. Our overall hypothesis is that changes in cell membrane lipid composition alter the function of ionic channel proteins.  We will use molecular dynamics computer simulations to quantify the equilibrating interactions between the ionic channel and the lipid molecules in the cell membrane.  We will test our hypothesis by evaluating the effects of changes in membrane lipid composition on the functional properties of hERG potassium protein channel ([hERGPO]. First, we will develop molecular based computer models consisting a hERGPO embedded in membranes with different lipid compositions. Second, we will use those computer models to evaluate the energy profiles along the ion channel pore and determine the effects of membrane lipid composition on channel permeability.  In this talk, we will present the use Nanoscale Molecular Dynamics (NAMD) to study ion channel/cell membrane molecular interactions, in a model consisting of the hERG channel embedded in a membrane with the lipid composition of rat myocytes. The simulation results explain the selectivity of hERG for K⁺ over Na⁺.

Locomotion is an important component of mobile robots. Wheeled locomotion is fast and easy to implement but unfortunately a large portion of our environment is inaccessible to wheeled robots. While legged locomotion may also be fast, as evidenced by the cheetah's top speed of around 70 mph, even the simplest implementations of legged gaits require extensive tuning and testing to maintain stability and propel the robot forward. An effective approach to optimizing gaits is to use autonomous learning which allows a large space of possible gaits to be searched with minimal human interaction. This survey provides an overview of different robotic subsystems and shows how robot locomotion may be classified based on the number of legs or wheels of the robot. Different methods of learning are explored and classified based on how they define the gait parameters, what learning method is used, and how the gait is evaluated.

Most optimization problems arising in an important application area to solve real world problems are NP-hard.  Due to the widely accepted belief that P ≠ NP, it is time consuming to find exact solutions for these problems.  Therefore, approximation algorithms have been implemented for the problems which solve them efficiently but not exactly.  However, finding some approximation results is as hard as finding exact results.  Computational Complexity Theory for the field of hardness of approximation states a limit of approximation results.  A Probabilistically Checkable Proof (PCP) is a type of proof that can be checked by a randomized verification algorithm with bounded query complexity.  With the development of “PCP Theorem” which states that PCP(log n, 1) = NP, many inapproximability results have been established.  This paper will review results of hardness of approximation proved in the last decade.

Parameterized complexity is a field of complexity theory pioineered in the 90's mainly by the works of Downey and Fellows and their coauthors.  In a nutshell, parameterized complexity challenges one of the main notions of traditional complexity theory, that a problem's complexity must be described as a function of the input size n, by introudicing a parameter, which is almost always denoted by k.  The role and meaning of the parameter vary wildly depending on the specific problem and application one might have in mind, but in general the parameter k is supposed to capture a property of the problem which helps us distinguish tractable from intractable instances.