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

Call Numbers 20667 (undergraduate) and 17455 (graduate).

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.

- 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

**Exams**:

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

All exams will be closed book, closed notes, closed neighbor, no calculators, just a writing implement and your mind.

Homeworks |
35% |

Midterm Exam |
30% |

Final Exam |
35% |

(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.)

You can submit your homeworks in many ways:
· Hand it in class
· Give it to the TA or the instructor in person
· Email a picture or a scan of it to the TA or the instructor
· Leave it in the TA's mailbox (905 SEO) or the instructor's mailbox (1120 SEO)
· Slide it under the instructor's office door (1136 SEO)
Whatever you do, make sure to submit your homework **verifiably** before the due time.

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

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.

**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 Conduct Process 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 http://www.uic.edu/depts/dos/studentconduct.html for more details.

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

• Any lecture notes not posted on the class website.

Statement about disability services

List of registration and records policies

UIC Undergraduate Catalog

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

Topic revision: r26 - 2015-01-04 - 16:32:27 - 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 |