´ºË®ÌÃÊÓƵ

Duration: 4Ìýhours

This module introduces the basics of linear programs and shows how some algorithm problems (such as the network flow problem) can be posed as a linear program. We will provide hands-on tutorials on how to pose and solve a linear programming problem in Python. Finally, we will provide a brief overview of linear programming algorithms including the famous Simplex algorithm for solving linear programs. The problem set will guide you towards posing and solving some interesting problems such as a financial portfolio problem and the optimal transportation problem as linear programs.

Students can expect a quiz and a problem set assignment at the end of this module. This assignment involves linear programming. You will be asked to design linear programming formulation on paper and program them to solve algorithmic problems. Programming in python is required for this assignment. We will be using the PuLP library for setting up and solving the linear program.

Duration: 4Ìýhours

This module will cover integer linear programming and its use in solving NP-hard (combinatorial optimization) problems. We will cover some examples of what integer linear programming is by formulating problems such as Knapsack, Vertex Cover and Graph Coloring. Next, we will study the concept of integrality gap and look at the special case of integrality gap for vertex cover problems. We will conclude with a tutorial on formulating and solving integer linear programs using the python library Pulp.

Students can expect a quiz and a problem set assignment at the end of this module. This programming assignment requires you to formulate algorithmic problems as integer linear programs and solve them. You will need to use the PULP library as in the previous assignment.

Duration: 6Ìýhours

We will introduce approximation algorithms for solving NP-hard problems. These algorithms are fast (often greedy algorithms) that may not produce an optimal solution but guarantees that its solution is not "too far away" from the best possible. We will present some of these algorithms starting from a basic introduction to the concepts involved followed by a series of approximation algorithms for scheduling problems, vertex cover problem and the maximum satisfiability problem.

Students can expect a quiz and a problem set assignment at the end of this module. This problem set focuses on designing approximation algorithms, implementing and analyzing them. We will have a combination of problems for designing algorithms (these will not be graded and answers are provided at the very end) to help you think through the material and programming assignments with test cases that will be graded.

Duration: 3Ìýhours

We will present the travelling salesperson problem (TSP): a very important and widely applicable combinatorial optimization problem, its NP-hardness and the hardness of approximating a general TSP with a constant factor. We present integer linear programming formulation and a simple yet elegant dynamic programming algorithm. We will present a 3/2 factor approximation algorithm by Christofides and discuss some heuristic approaches for solving TSPs. We will conclude by presenting approximation schemes for the knapsack problem.

Students can expect a quiz and a problem set assignment at the end of this module. This assignment requires you to design algorithms for variants of TSP and program them to pass test cases. It is important that your solution be efficient. There is usually a 3 minute limit on how fast your entire notebook can run. If your solutions do not all run within this limit, there is a real danger of losing.

Duration: 30 hours

This module contains materials for the final exam.ÌýIt will involve formulating a solution/algorithm for some problem and then implementing it in Python to pass test cases. If you've upgraded to the for-credit version of this course, please make sure you review the additional for-credit materials in the introductory module and anywhere else they may be found.

The final exam is aÌý 30 hour exam that involves solving two algorithmic problems with multiple parts to each. These problems will involve the material you have learned in this class: linear programming, integer programming, approximation algorithms and travelling salesperson problem. It will involve formulating a solution/algorithm for some problem and then implementing it in Python to pass test cases.

Final is open book/notes. This means that you can consult any of our notes from this class and the reference CLRS (though the CLRS book is not needed). You can also consult documentation online for python and the PuLP package which we have been using to solve LPs. You can consult previous assignments.

However, it is forbidden to seek any other source of help. Do not ask on online forums or anyone else either in the class or outside for help to solve your problems. Also, do not try to search for the problem or solutions on the internet. Doing any of these forbidden activities constitutes cheating.

The 30 hour time limit is very strict. Please submit before this limit expires. We will not accept late submissions or modifications to submissions after the time limit has passed.

Also, some of the questions need efficient solutions. If your notebook as a whole takes more than 2 minutes to run, then it is clear that you are not efficient. Points will be lost if this happens.