CS255 Spring 2019 Sec1 Home Page/Syllabus

Design and Analysis of Algorithms

Prerequisites

To take this class you must have taken:
CS155
with a grade of C- or better.

Texts and Links

Description

This course covers the basics of randomized algorithms, parallel algorithms, distributed algorithms, algorithms related to the theory of NP-completeness, and approximation algorithms. Randomized algorithms are algorithms which make use of a random number generator. For instance, one fast way to check if a number is prime makes of such a generator. Parallel algorithms are algorithms which are designed to be partitionable with minimal overhead among many processors who share a global clock. Distributed algorithms are algorithms designed to work on multiple processors which don't share a global clock. An example situation might be to get an algorithm to get a bunch of computers on a network to agree on a common value. NP problems are languages with polynomial time proofs of membership. For instance, given a potential factorization of a number we can in polynomial time check whether it is correct. NP-complete problems are problems in NP to which any other problem in NP can polynomially time reduced. We will consider different algorithms for during this kind of reduction. Approximations algorithms are usually efficient algorithms which approximately solve some optimization problem which is not known to have a efficient solutions. For instance, one might have an algorithm which approximately finds a traveling salesman tour. In addition to these algorithms, we will also go over the computer algebra algorithms neccessary to do basic cryptographic protocols such as RSA. By the end of this course, you should be able to code one example of a randomized algorithm, parallel algorithm, distributed algorithm, a polynomial time reduction, an approximation algorithm, and a computer algebra algorithm.

Course Learning Outcomes (CLOs)

By the end of this course, a student should be able to:

CLO1 -- Analyze or code a randomized algorithm

CLO2 -- Analyze or code a parallel algorithm using a thread library

CLO3 -- Analyze or code a parallel algorithm using a library such as OpenCL

CLO4 -- Analyze the correctness and run time of a distributed algorithm

CLO5 -- Given a problem within NP that is promised to be either in P or NP-complete prove which it is

CLO6 -- Analyze or code a number theoretic algorithm

CLO7 -- Analyze or code an approximation algorithm for a optimization problem whose decision problem is NP-complete.

Course Schedule

Below is a tentative time table for when we'll do things this quarter: