Advanced Algorithms - CS 6/76101 
Fall 2008

TR 3:45 - 5:00 PM
MSB   276

Instructor
Office Hours
 

Email 
Telephone

Dr. Feodor Dragan 
Room 254 MSB
TR  2:30 - 3:30 PM 
and by appointment 
dragan at cs.kent.edu
(330) 672-9058

Teaching Assistant
Office Hours
 

Email 
Telephone

???????????
Room ???  MSB 
??  ??????

and by appointment 
????? (at) cs.kent.edu
(330) 672-9???
  • WWW http://www.cs.kent.edu/~dragan/CS6-76101-AdvAlg.html
  • Prerequisites
    A firm prerequisite is a senior level algorithms course at approximately the same level as  CS 4/56101 (Intro. to Design & Analysis  of  Algorithms). A combined Data Structures and Algorithms course like  CS 33001 is not an adequate preparation for this course. This course assumes both  CS 33001 and CS 4/56101 as background.
  • Goals:  This course has several goals.
    • Study important algorithm areas and techniques not normally covered in the first course.
    • Develop ability to design efficient algorithms.
    • Develop ability to prove correctness and evaluate efficiency of algorithms.
    • To cover a number of additional topics not covered in CS 4/56101 (first algorithms course).
  • Text   (CLRS)
    Thomas Cormen,  Charles Leiserson,  Ronald Rivest, and  Cliff Stein,  Introduction to Algorithms, McGraw  Hill Publishing Company and MIT Press, 2001 (2nd Edition).
    (The MIT Press web site for the textbook is http://mitpress.mit.edu/algorithms, and it contains a link to the list of known bugs and errata.)
  • Additional Book & Web References
    •  Ellis Horowitz, Sartaj Sahni, and Sangurthevar Rajasekaran, Computer Algorithms, Computer Science Press, 1998. (HSR)
    •  Gilles Brassard and Paul Bratley, Fundamental of Algorithmics, Prentice Hall, 1996. (BB)   (used in Prel.Exams)
    •  Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
    •  J. O'Rourke, Computational Geometry in C, Cambridge  University Press, 1998 (Second Edition).
    •  Michel Goemans, Advanced Algorithms Course Notes are available from this website.
  • Some assumed topics from first algorithms course
    • Reasonable knowledge of basic topics in CLRS textbook.
    • Some maturity in designing, evaluating running time, and proving correctness of algorithms.
    • Asymptotic notation and complexity (Ch. 2-3 of  CLRS).
    • Recurrences and summations (Ch.  4 and Appendix A in CLRS).
    • Major Sorts (including quicksort and heapsort), linear time sorts, lower bound for sorting (Ch. 6-9 of CLRS).
    • Hash tables (Ch. 11 of CLRS).
    • Binary search trees, red-black trees (Ch. 12-13 of CLRS).
    • Graph algorithms including traversals, minimum spanning trees, shortest path (Ch. 22-25 of CLRS).
    • Basic numeric routines, including matrix operations (Ch. 29,31 of CLRS).
  • Topics will include: We will cover the following topics (the topics and order listed are tentative and subject to change; some topics may only be quickly surveyed to add breadth, while others will be covered in reasonable depth).
    • Dynamic Programming
    • Optimal greedy algorithms
    • Amortized analysis
    • Parallel and circuit algorithms
    • Network flow algorithms
    • Randomized algorithms
    • Number theoretic & cryptographic algorithms
    • String matching algorithms
    • Computational geometry algorithms
    • Algorithms for NP-hard and NP-complete problems
    • Approximation algorithms
    • Online algorithms
    • Linear programming algorithms
  • Course Requirements

Homework 

- 

- 

- 

40% 

Midterm Exam

 ???????

October ??, 2008

3:45 - 5:00 pm 

30% 

Final Exam

Thursday 

December 11, 2008 

7:45 - 10:00 a.m.

30%
  • Milestone for successful completion of the course
    • Attend the classes regularly,
    • Perform the homework thoroughly and independently,
    • Read the book carefully and several times.
  • Make-up and Late policy:  Attendance at times exams are given is a course requirement. Missed tests are only excused if absence was essential and can be fully documented. Unexcused late homework is normally not accepted after 11:59:99 pm of due date. Class extensions on homework will be announced in class. They may also be announced by email and at the course website.
  • Homework and Collaboration: You will need to devote a considerable amount of time to homework. You may discuss the homework with other students, but you must write your solutions independently.  Study groups should limit their size to 2-3 so that each collaborator can participate in solution. If you obtain a solution to a homework problem through research (e.g., from books or journals), you are expected to acknowledge your sources in your writeup and  also to write up your solution independently.
  • Plagiarism: Copying the solution from another student or jointly writing up the solution of a problem constitutes plagiarism. You are not permitted to use solutions to assigned problems from earlier terms.  Such activities and other unapproved or anti-intellectual behavior violates the University's plagiarism rules and can result in severe penalties. Behavior of this type is unfair to both yourself (in missed learning opportunities) and to the other students. University rules on plagiarism are given here.
  • Student Accessibility: University Policy 3342-3-01.3 requires that students with disabilities be provided reasonable accommodations to ensure their equal access to course content.  If you have a documented disability and require accommodations, please contact the instructor at the beginning of the semester to make arrangements for necessary classroom adjustments.  Please note, you must first verify your eligibility for these through Student Accessibility Services (contact 330-672-3391 or visit www.kent.edu/sas for more information on registration procedures).
  • Registration Requirement:  The official registration deadline for this course is September 7, 2008.  University policy requires all students to be officially registered in each class they are attending.  Students who are not officially registered for a course by published deadlines should not be attending classes and will not receive credit or a grade for the course.  Each student must confirm enrollment by checking his/her class schedule (using Student Tools in FlashFast) prior to the deadline indicated.  Registration errors must be corrected prior to the deadline.


F. Dragan
dragan at cs.kent.edu
Fall 2008