Courses

CS 260 Design and Analysis of Algorithms

Prerequisites: computer programming skills, probability, basic data structures and algorithms, basic discrete mathematics.

The course covers main approaches to design and analysis of algorithms including important algorithms and data structures, and results in complexity and computability. 

The main contents are: review of algorithm analysis (search in ordered array, binary insertion sort, merge sort, worst-case and average-case time complexity, minimum complexity of sorting n elements for small n, 2-3 trees, asymptotic notation); divide and conquer algorithms (master theorem, integer multiplication, matrix multiplication, fast Fourier transform); graphs (breadth-first search, connected components, topological ordering, depth-first search, way from planar graphs to Robertson-Seymour theorem); dynamic programming (chain matrix multiplication, shortest paths, edit distance, sequence alignment, extensions of dynamic programming); greedy algorithms (binary heaps, Dijkstra’s algorithm, minimum spanning tree, Huffman codes, matroids); randomized algorithms (selection, quick sort, global minimum cut, hushing); P and NP (Cook’s theorem, examples of NP-complete problems); approximate algorithms for NP-hard problems or polynomial algorithms for subproblems of NP-hard problems (set cover, vertex cover, maximum independent set, 2-SAT); partial recursive functions (theorem of Post, Diophantine equations); computations and undecidable problems (existence of complex problems, undecidability of halting problem, theorem of Rice, semantic and syntactical properties of programs).​

CS 361 Combinatorial Machine Learning

Prerequisites: basic knowledge in discrete mathematics and algorithms.

The course covers tools for design and analysis of decision trees, decision rules and tests, their applications to supervised machine learning, and related topics including current results of research. 

The main contents are: introduction (basic notions and examples from applications); tools (relationships among decision trees, rules and tests, bounds on complexity of tests, decision rules and trees, algorithms for construction of tests, decision rules and trees); applications (supervised machine learning); some of the additional topics (decision tables with many-valued decisions, approximate decision trees, rules and tests, global and local approaches to the study of problems over infinite sets of attributes, applications to combinatorial optimization, fault diagnosis, pattern recognition, analysis of acyclic programs, data mining and knowledge representation); current results of research.

Enrolled students can access course material through KAUST's Blackboard via http://portal.kaust.edu.sa