Design & Analysis of Algorithms - CS 4/56101
SPRING 2009

MW 12:30 pm - 01:45 pm

MSB 115

Instructor Office Hours Email  Telephone

Dr. Feodor Dragan  Room 254 MSB MW 1:45 – 2:15 pm, M 3:30 – 5:00 pm and by appointment  dragan at cs dot kent dot edu (330) 672-9058

Teaching Assistant Office Hours Email  Telephone

Yang Xiang Room 352 MSB T 11:00 am-12:30pm, W 2:00-3:30pm and by appointment  yxiang@cs.kent.edu (330) 672-9106

• WWW:  http://www.cs.kent.edu/~dragan/CS4-56101-D&AofAlg.html
• Prerequisites:  Data Structures - CS 33001
• Course Description:  This course is an introductory undergraduate/graduate course on the design and analysis of algorithms. The course builds on the study of the analysis and implementation of data structures and algorithms from CS 33001. The goal is to introduce a number of important algorithm design techniques as well as basic algorithms that are interesting both from a theoretical and also practical point of view. We will cover basic algorithm design techniques such as divide-and-conquer, dynamic programming, and greedy techniques for optimization. We will cover techniques for proof of the correctness of algorithms and also asymptotic analysis of algorithm time bounds by the solution of recurrence equations. We will apply these design and analysis techniques to derive algorithms for a variety of tasks such as sorting, searching, and graph problems. Some specific algorithm topics include: deterministic and randomized sorting and searching  algorithms, depth and breadth first search graph algorithms for finding paths and matchings, and algebraic algorithms for fast multiplication and linear system solving.
• Goals:  This course has several goals.
• Study important data structures and algorithmic techniques not normally covered in CS 33001.
• Develop ability to design efficient algorithms.
• Develop ability to prove correctness and evaluate efficiency of algorithms.

The main goal of the course is to learn to think algorithmically like a ``real'' computer scientist.

• Textbook

Algorithm Design: Foundations, Analysis, and Internet Examples, Wiley, 2002, ISBN 0-471-38365-1
(by   Michael T. Goodrich and Roberto Tamassia)   Book's web site

• 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).
• Algorithm Analysis
• Data Structures (Elementary Data Structures, Vectors,  Stacks, Queues,  Sequences, Trees, Heaps, Priority Queues, Hash Tables, Dictionaries)
• Searching ( Binary Search Trees,  AVL Trees, Red-Black Trees, Skip Lists, Locators)
• Sorting (Merge Sort, Quick Sort, Sorting Lower Bound, Sets, Radix Sort, Selection)
• Fundamental Techniques (Greedy Method, Divide-and-Conquer, Dynamic Programming)
• Graphs Algorithms (Graphs, Depth-First Search, Breadth-First Search, Biconnectivity, Directed Graphs)
• Weighted Graphs (Shortest Paths, Minimum Spanning Tree)
• Network Flow and Matching
• Text Processing (Pattern Matching)
• Course Requirements

Homework	-	-	-	40%
Midterm Exam	???????	March ??, 2009	12:30 pm - 01:45 pm	30%
Final Exam	Wednesday	May 13, 2009	10:15 am - 12:30 pm.	30%

Homework is very important. It is expected that most of your learning will come from the process of solving the homework problems. Exams will in large part be based on the homework.

• 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.
• Cheating and 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 violate 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 and on sanctions are 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 Feb. 1, 2009. 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. F. Dragan
dragan at cs dot kent dot edu
Spring 2009