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: CS 260 Design and Analysis of Algorithms,
CS 220 Data Analytics.
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.