# CSCA 5424: Approximation Algorithms and Linear Programming

* ***Preview this course in the non-credit experience today! **

Start working toward program admission and requirements right away. Work you complete in the non-credit experience will transfer to the for-credit experience when you upgrade and pay tuition. See How It Works for details.

**Course Type: **Pathway | Breadth

**Specialization:** Foundations of Data Structures and Algorithms

**Instructor:** Dr. Sriram Sankaranarayanan, Professor of Computer Science

**Prior knowledge needed: **You must understand all concepts covered in Dr. Sankaranarayanan's *non-credit* Algorithms for Searching, Sorting, and Indexing and Trees and Graphs: Basics courses to succeed in this course. We highly recommend successfully completing those two courses in the non-credit experience before starting this course; they are a great option to refresh your skills and ensure you're ready. Note that you *cannot *apply credit from either of these courses toward MS-CS graduation requirements.

- Programming language: Intermediate experience with Python, Jupyter Notebook
- Math: Intermediate Linear Algebra, Sets and Functions: Properties of sets, definition and properties of functions. Logarithms and Exponentials: and their properties. Basic series summations: arithmetic and geometric series summations. Probability theory: basic definition of probability, independence of events, probability distributions and expectations.
- Technical requirments: Windows or Mac, Chrome, VS Code

**Course Description**

This course continues our data structures and algorithms specialization by focussing on the use of linear and integer programming formulations for solving algorithmic problems that seek optimal solutions to problems arising from domains such as resource allocation, scheduling, task assignment, and variants of the traveling salesperson problem. Next, we will study algorithms for NP-hard problems whose solutions are guaranteed to be within some approximation factor of the best possible solutions. Such algorithms are often quite efficient and provide useful bounds on the optimal solutions. The learning will be supported by instructor provided notes, readings from textbooks and assignments. Assignments will include conceptual multiple-choice questions as well as problem solving assignments that will involve programming and testing algorithms.

**Learning Outcomes**

- Formulate linear and integer programming problems for solving commonly encountered optimization problems.
- Understand how approximation algorithms compute solutions that are guaranteed to be within some constant factor of the optimal solution.
- Develop a basic understanding of how linear and integer programming problems are solved.

**Course Grading Policy**

Assignment | Percentage of Grade |
---|---|

Quizzes (19 quizzes) | 2% each (total 38%) |

Programming Assignments (4 assignments) | 11.75% each (total 47%) |

Final Exam | 15% |

**Course Content**

**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.

## Notes

**Cross-listed Courses:**Courses that are offered under two or more programs. Considered equivalent when evaluating progress toward degree requirements. You may not earn credit for more than one version of a cross-listed course.**Page Updates:**This page is periodically updated. Course information on the Coursera platform supersedes the information on this page. Click the*View on Coursera*button above for the most up-to-date information.