Design and Analysis of Algorithms (5 cu) Analysis techniques. Design techniques. Models of computation and lower bounds. Algorithms on sets. Graph algorithms. Approximation algorithms for NP-complete problems. Probabilistic algorithms. Parallel algorithms.
String Processing Algorithms (5 cu) Exact string matching. Approximate string matching. Pattern matching in static strings. Text databases and hypertext. Algorithm implementation and comparison project.
Machine Learning (5 cu) History. Inductive learning: Learning in the blocks world, identification in the limit, version spaces. Learning classifiers: Finite automata, case-based, rules, decision trees, neural networks, genetic algorithms. PAC-learning: basics, Occams Razor, Vapnik-Chervonenkis dimension, learning by queries, PAC and noise, relation of different models. PAC and classifier learning. Inductive logic programming. Real-world applications.
Parallel Algorithms (3 cu) Parallel processors and computers. Arrays and trees: elementary sorting and counting, integer arithmetic, matrix computations, retiming and systolic conversion, graph algorithms, sorting revisited, packet routing, higher dimensional arrays. Meshes of trees: two-dimensional mesh of trees, O(log N)-step algorithms. Hypercubes and related networks: hypercubes, variations with bounded branching degree (butterflies, cube-connected-cycles).
Computational Complexity Theory (3 cu) Review of Turing machines and complexity classes. Space complexity. Alternating Turing machines and the polynomial time hierarchy. Oracle Turing machines and relativization. Structure theorems for NP-complete sets. Structure within NP. Probabilistic Turing machines and complexity. Nonuniform complexity measures. Kolmogorov complexity.
Complex Computational Systems (4 cu) Cellular automata. Simulated annealing. Recurrent neural networks. Genetic algorithms. Molecular computation. Thermodynamics of computation. Artificial life.
Advanced Computer Graphics (4 cu) Selection of advanced topics such as tray tracing, radiosity, solid modeling, illumination and color, scientific visualization, etc. are taken as a theme of the course. Individual and group work, report writing and oral presentations by the participants.
Robotics (4 cu) Types and applications of robots. Components of a robot. Architectures. Autonomous mobile robots: Navigation and motion planning. Robot learning: Reinforcement learning, Q learning.