This course covers four special topics in advanced algorithms: algorithmic robotics, string algorithms, geometric algorithms and randomized algorithms.
Algorithmic robotics focuses on algorithm issues relating to planning problems in robotics. These include motion planning, discrete planning, planning under uncertainty, sensor-based planning, visibility, decision-theoretic planning, game theory, information spaces, reinforcement learning, nonlinear systems, trajectory planning, nonholonomic planning, and kinodynamic planning, this module is presented by S. Lavalle.
String algorithms focuses on algorithms that process sequences of symbols being these sequences text, proteins, DNA, images, etc. In this module some exact string algorithms (string matching, suffix trees, suffix arrays, automata theory, etc) and some approximation string algorithms (pattern matching with mismatches, dictionary problems, FFT) are studied, this module is presented by Y. Pinzon.
Geometric algorithms study efficient algorithms and data structures to solve problems stated in terms of geometry, i.e. problems stated in terms of basic geometrical objects: points, line segments, polygons, polyhedra, etc. Some of these problems are classical problems in geometry but many others come from autonomous vehicles route planning (motion planning and visibility problems), geographic information systems (GIS) (geometrical location and search, route planning), integrated circuit design (IC geometry design and verification), computer-aided engineering (CAE) (programming of numerically controlled (NC) machines), telecommunications (location of mobile phone stations). This module starts from basic geometric algorithms (convex hull, neartest neighbors, segment intersections) to much more complex topics such as voronoi diagrams, minimum spanning trees, geometric spanners, metric embeddings, randomization, divide-and-conquer, conquer-and-divide, range trees, skip lists, plane sweep, etc. and is presented by G. Narasimham.
Randomized algorithms focuses on algorithms that employ a degree of randomness as part of its logic as a mean of reduce, in average, the complexity of solving an algorithmic problem, Quicksort is probably the most familiar "real-world" algorithm in which randomness is very useful, currently for many algorithmic problems the best behaved algorithm is a randomized algorithm, this module is presented by G. Hernandez.
Systems and Industrial Engineering Department
Dr Hernandez received a BSc Computer Systems Eng, a MSc. in Mathematics and a MSc in Statistics form the National University of Colombia. Also received a Ph.D. and MSc in Computer Science form the University of Memphis, TN, USA. His main interest is the analysis and application of evolutionary algorithms and randomized algorithms. He is the author of multiple publications in international journal and conferences.
School of Computer Science
Florida International University
Dr Narasimhan received a B. Tech. degree in Electrical Engineering at the Indian Institute of Technology (1982) and his Phd degree in Computer Science at the University of Wisconsin (1989). He has worked as an Associate Professor in Florida International University and The University of Memphis and as a Visiting Professor in the University of Copenhagen, Lund University, University at StonyBrook, University of Maryland and University of Magdeburg. Currently, he is Professor in the School of Computer Science at Florida International University. His research areas are Computational Biology, Bioinformatics, Biotechnology and Biomedical Engineering, Design and Analysis of Geometric Algorithms, Experimental Algorithmics, Computational Statistics, Neural Networks and Genetic Algorithms, Graph Theory and Combinatorics. He has astonishing professional and academic honors and many publications in different journals and international conferences. He has produced high quality software packages and currently he is preparing a book on algorithms.
Department of Computer Science
University of Illinois, Urbana
Dr LaValle received his B.S. (Highest Honors) degree in Computer Engineering at the University of Illinois (1990), a M.Sc. degree in Electrical Engineering at the University of Illinois (1993) and a Ph.D. degree in Electrical Engineering at the University of Illinois (1995). He worked as an Assistant Professor in the Dept. of Computer Science at University of Illinois and Iowa State University. Currently he works as an Associate Professor in the Dept. of Computer Science at University of Illinois. He was a Post-Doctoral Researcher in the Computer Science Dept at Stanford University, and a Research Assistant at the Beckman Institute at University of Illinois. He has received several awards and honors in research, teaching and academic areas. Dr LaValle has a strong research interest in areas as Robotics, planning algorithms, computational geometry, artificial intelligence, computational biology, computer vision, computer graphics and control theory. Professor LaValle is author of the book Planning Algorithms of Cambridge University Press.
Universidad Nacional de Colombia
Dr Pinzon received a BSc Computer Systems Eng., a BSc Industrial Eng. and Specialist on Software Engineering from Industrial University of Santander. Also received a PhD. and MSc in Computer Science form the King´s College, University of London, UK .