**Course Number:** CS 401 (3 or 4 credits)**Lectures: **Tuesday and Thursday 12:30 pm – 1:45 pm in SES 138.

Call Numbers 35218 (undergraduate) and 35219 (graduate) (and the course is cross listed with MCS: 35220, 35221)

Deadlines for Registration/Add/Drop/Credit Change

**Book:** Kleinberg and Tardos, *Algorithm Design* , Addison Wesley, 2006, ISBN 0-321-29535-8. The publisher's website has student support site.

The design of computer algorithms is a rich and heavily studied area in computer science, whose impact has been great in both the practical and theoretical aspects of the field. At a high level, this course's aim is to introduce you to various standard methods for designing algorithms, including the greedy method, divide-and-conquer, and dynamic programming. We then venture on to the theory of NP-completeness, which is a theory developed by the computer science community in an attempt to prove that some computational problems simply do not have efficient algorithms, but rather only extremely inefficient ones.

'C' or better in: CS 251 or MCS 360

(Discrete math, Data structures, simple algoirthms such as search, sort, tree and graph traversals, run time analysys)

- Some representative problems
- The stable matching problem
- Five representative problems

- Basics of Algorithm Analysis (mostly review material)
- Comptutational tractability
- Asymptotic order of growth
- Common running times

- Graphs (again, much review material)
- Basic definitions and applications
- Graph traversal
- Testing bipartiteness
- Connectivity in directed graphs
- DAGs and Topological ordering

- Greedy Algorithms
- Interval scheduling
- Scheduling to minimize lateness
- Single-source shortest paths (Dijkstra's algorithm)
- Minimum spanning tree (Prim's algorithm, Kruskal's algorithm, UnionFind data structure)
- Clustering

- Divide and Conquer
- Mergesort
- Solving recurrence relations using the following methods: Unrolling the recurrence, substitution (guess and check), and annihilators.
- Detour: Lower bound for comparison-based sorting algorithms.
- Counting inversions
- Closest pair of points
- Integer multiplication

- Dynamic Programming
- Weighted interval scheduling
- Coin changing
- Segmented least squares
- Subset sum problem
- Sequence alignment
- Shortest paths

- Network Flows
- The Maximum-Flow problem and Ford-Fulkerson algorithm
- Maximum flows and minimum cuts
- Improving Ford-Fulkerson by choosing good augmenting paths
- Bipartite matching
- Disjoint paths
- Extensions to Max Flow
- Project selection

- Computational Intractability
- The complexity classes P, NP, EXP, and the importance of the P vs NP question
- Polynomial-time reductions (Hamiltonian Path, Vertex Cover, Independent Set, Clique, Subset Sum)
- A review of Turing Machines and the Church-Turing Thesis
- The Cook-Levin Theorem (SAT is NP-complete) and its proof
- An introduction to the PCP theorem

- Independent learning via course project: Tractable special cases of NP-hard problems
- Solving NP-hard problems on trees
- Solving NP-hard problems on graphs with bounded tree-width

**The following evaluation policy is TENTATIVE, and subject to change at any time for any reason.**

**Exams**:

- Midterm exam: In class sometime in the middle of the semester.
- Final exam: The final exam will be
**comprehensive**.

**Tentative **weighting scheme (the instructor reserves the right to make adjustments to these weights based on her a posteriori evaluation of the relative difficulty and fairness of the exams and homeworks).

Homeworks | 35% |

Midterm Exam | 30% |

Final Exam | 35% |

**The final grade is computed as follows:**

(average of the homeworks)*.35 + midterm*.3 + final*.35 + raw extra credit

Grades will be posted online on the UIC Blackboad system.

If you have a question or complaint about the way a homework or exam problem was graded, then, **within one week** of the date the assignment is returned, you should either explain what it is on a separate piece of paper and give it to the TA along with the assignment or, better yet, come into office hours and get it straightened out then. We want everyone happy and satisfied, but we can't do much in the couple of minutes before and after class.

*If you do not work on all the problem sets, then do not expect to pass the course. *(Not only are the problem sets weighted heavily, but students who don't do the problem sets flunk the midterm and the final.)

There will be problem sets roughly every 2-3 weeks, due in class. **In general,** **no late assignments will be accepted. **Requests for an extension will almost always be denied, except for extenuating circumstances, which must be requested **at least a day before the due date of the assignment**.

**Your homeworks must be submitted on Blackboard, each question as a separate submission.** You can submit a PDF, MSWord or a JPEG file. You can generate it electronically (from LaTeX, for example) or scan or take a *legible* picture of your handwritten homework.

**Extra Credit:**

Some homeworks will have extra credit questions. You can only get extra credit if you solve the homework questions first. To receive the extra credit you need to solve the extra credit question almost perfectly (it is an all or nothing system).

**Each extra credit question's points will be added unmodified to the total final grade.**

Please read the Guidelines for Written Homeworks before doing the first assignment.

**Attendance:** I do not plan to associate grades with whether or not you attend class, unless a serious problem with attendance develops.

The *UIC Undergraduate Catalog* states that in addition to needing excellent justification for an incomplete, a student must also have been “making satisfactory progress in the course.”

Therefore, no matter how good your excuse, I will not grant you an incomplete if you have less than a C average at the time you ask for an incomplete.

You may discuss the homework problems with other students—in fact, I encourage you to do so—but you are expected to write up your solutions by yourself. *If you do work on the problem sets with other students, please put the names of your group at the top of your problem set. If you consult any web page while working on an assignment, put the URL for the page on the homework.* If your homework is highly similar to another students’ homework (e.g., more than 50% as detemined by the similarity checking software) then we will consider you to be guilty of cheating.

**Cheating will not be tolerated.**

Not only is cheating a violation of the campus code of integrity, which might incur a reduced grade, expulsion from the class or university, it is also a slight against the other students in the class who will give you dirty looks. Refer to the UIC Student Disciplinary Policy for guidlines and policy on student integrity and possible repercussions. Cheating is plagiarism, taking credit for somebody else's work and I take it very seriously.

The minimum penalty for any cheating will be a grade of zero for the homework, project, or exam in question, along with a warning. The minimum penalty for cheating after a warning has been given will be an F for the course. In both cases, the maximum penalty is expulsion from the University.

See https://dos.uic.edu/studentconductprocess.shtml for more details.

You must keep private and not email, post on the web, or share in any way:

• Any solutions to homework problem sets of tests that we give you,

• Any lecture notes not posted on the class website.

Information about how to interpret midterm grades

Statement about disability services

List of registration and records policies

http://www.uic.edu/ucat/catalog/CA.shtml#f

*Credits: this webpage has been adapted from Dr. Sevag Gharibian, who taught this course in fall 2012.*

Topic revision: r30 - 2017-08-26 - 19:54:22 - Main.tanyabw

Copyright 2016 The Board of Trustees of the University of Illinois.webmaster@cs.uic.edu |
WISEST Helping Women Faculty Advance Funded by NSF |