TWiki> CS401 Web>Syllabus (revision 26)EditAttach

## Syllabus: CS 401, Computer Algorithms I, Spring 2015

Course Number: CS 401 (3 or 4 credits)

Lectures:
Tuesday and Thursday 12:30 pm – 1:45 pm in BH 305.

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

## Overview: Key learning objectives

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.

## Prerequisites

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

## Course Topics (subject to change without notice)

• 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

## Evaluation

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.

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

### Weight of course components for grades

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

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

### Homework:

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.

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.

### Incompletes

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 or to a web page and you have not put that name or URL on your paper, 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 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.

### Keeping documents private

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.