# PG Courses

**Computational Complexity CSL601 3 (3-0-0) **

Diagonalization, space complexity, time complexity, polynomial hierarchy and alternations, boolean Circuits, interactive Proofs, cryptography and one-way functions, introduction to PCP Theorem and hardness of approximation, lower bounds for decision trees, circuit lower bounds, proof complexity, lower bounds in algebraic models of computation, complexity of counting, natural proofs, pseudorandom constructions : expanders and extractors, research topics of instructor’s choice.

**Computational Geometry CSL602 4 (3-0-2) **

Duality between points and lines, geometric searching, point location, slab and chain methods, planar separator methods, multidimensional binary tree (k-D trees), segment trees, range trees, iterated search and fractional cascading, convex hulls, Graham's scan, Jarvis's march, divide-and-conquer algorithms, gift-wrapping method, convex hulls in three and more dimensions, clustering, closest pair problem, locus approach, Voronoi diagrams, computational aspects of Voronoi diagrams, higher-order Voronoi diagrams, euclidean minimum spanning tree problem, euclidean traveling salesman problem, hidden surface problem, linear programming, rectangle intersection problem, randomized algorithms in computational geometry, random sampling, incremental construction and backward Analysis, combinatorial and discrete geometry.

**Real-Time Systems CSL611 4 (3-0-2)**

This course will discuss a number of important topics concerning time critical real-time systems such as: Typical Real-Time applications, hard versus soft real-time systems, a reference model of Real-Time systems, Real-Time scheduling, priority-driven scheduling of periodic tasks, scheduling aperiodic and sporadic jobs in priority-driven systems, multiprocessor scheduling, real-time communication and operating systems.

**Artificial Intelligence CSL612 4 (3-0-2)**

Search methods: A*, heuristic functions, local search. search trees: game playing (minimax search), constraint satisfaction, knowledge representation (propositional, first order), knowledge inference, planning, reasoning with uncertainty, bayesian networks, Dempster-Shafer theory, HMMs, learning: PAC learning: artificial neural networks, inductive logic programming, statistical learning, recent research topics.

**Algorithms in Bioinformatics CSL613 4 (3-0-2)**

Primer on molecular biology, motif finding, median string, global and local sequence alignment, partial and double digest problem, genome rearrangements, phylogeny problems (large and small parsimony), RNA folding, protein folding, comparative genomics, SNPs, analysis of microarray data. Activities will include implementing various algorithms on GPUs.

** **

**Approximation Algorithms CSL701 4 (3-0-2)**

Combinatorial algorithms: set cover, steiner tree, traveling salesman problem, multiway cut, knapsack, bin packing, scheduling, euclidean traveling salesman problem, LP-based algorithms: introduction to linear programming, duality and primal dual schema, set cover, maximum satisfiability, scheduling, multicut and integer multicommodity flow, multiway cut, sparsest cut, steiner forest, Semidefinite programming: max cut, 2-satisfiability, approximation of counting problems, hardness of approximation, research topics of Instructor’s choice.

** **

**Randomized Algorithms CSL702 4 (3-0-2)**

Moments and deviations, tail inequalities, probabilistic method, Markov chains and random walks, polynomial identity testing, perfect matchings, interactive proof systems, randomized data Structures: skip lists, hash tables, universal hash functions and their applications, randomization in geometric algorithms, randomized algorithms for minimum spanning tree, min-cut and all-pairs shortest paths, approximate counting : counting perfect matchings in bipartite graphs, randomized parallel and distributed algorithms : maximal independent set, randomized primality testing, research topics of instructor's choice.

**Combinatorial Optimization CSL703 4 (3-0-2)**

Linear programming, simplex Algorithm, duality, computational considerations for the simplex algorithm, primal-dual algorithm, primal-dual algorithms for maximum flow and shortest paths, Dijkstra’s algorithm, ellipsoid algorithm, interior-point methods, minimum spanning trees, matroids, maximum flow: Ford-Fulkerson algorithm, Edmonds-Karp Algorithm, push-relabel maximum flow algorithms, minimum cost flow, primal-dual algorithms, bipartite matching, algorithms for matching in general graphs, weighted bipartite matching, non-bipartite weighted matching problem, integer programming, total unimodularity, gomory cuts, cutting plane methods and branch-and-bound, research topics of Instructor’s choice.

**Advanced Operating Systems CSL704 4 (3-0-2)**

This course will discuss the state of the art in operating systems research. Topics include, but are not limited to: distributed operating systems, virtual memory, file systems, fault tolerance, synchronization, communication, distributed and shared memory. Students will study the recent research breakthroughs in operating systems research. An integral part of this course will involve the reading of a number of relevant research papers in this field and making class presentations. Each student will be expected to read each presentation paper and prepare a summary. Students will also be assigned a survey paper and a group project.

**Constraint Programming CSL705 4 (3-0-2)**

Constraint satisfaction problems, propagation, arc-consistency, k-consistency, from local to global consistency, interval constraints, propagation algorithms for intervals constraints, symmetry handling in constraint satisfaction problem, constraint programming (prolog II), search, backtracking, variable ordering, value ordering, phase transition in constraint satisfaction problems, constraint logic programming, applications to scheduling, planning, computational biology, numerical analysis, recent research topics.

**Independent Study CSL711 4 (3-0-2)**

The objective is to learn material that is normally not part of regularly offered courses. A course outline along with details of the work to be performed are to be submitted by the student to the head of the department prior to the start of the course. The courses will be conducted under the guidance of a faculty. At most one independent study can count towards the degree requirements.

** **

**Physics of Medical Imaging CSL631 3 (3-0-0)**

The course provides the necessary physics background that underpins day-to-day medical imaging physics activities. It is aimed primarily at new entrants to the profession, but should be of benefit to post-graduate students or post-doctoral research workers, wishing to deepen or re-establish their understanding of the physics of medical imaging. This course introduces the physics behind most of the common medical imaging modalities including x-ray, ultrasound, CT, PET, SPECT, optical imaging and MRI. There is emphasis on the physics of MR in this course as this is an active area of research in the field. Some math is required, Fourier Transform theory is helpful, but it will be reviewed in the course. The course will provide the student with a good understanding of the strengths and weaknesses of the different imaging modalities, what areas are still being developed, and the key applications of each modality.