Welcome to CS7200 - Algorithm Design and Analysis

Instructor:	Dr. Thomas Wischgoll  thomas.wischgoll@wright.edu 485 Joshi Research Center 937-775-5057
Office Hours:	Mon/Wed 04:30pm - 05:30pm (or by appointment)
Textbook:	Algorithm Design J. Klienberg and Eva Tardos Addison Wesley, 2005. ISBN 0-321-29535-8
Webpage:	http://avida.cs.wright.edu/courses/CS7200/
Lecture:	Mon/Wed/Fri 03:35 pm - 04:30 pm (Russ Engineering Center 146)
Exams:	Midterm: Mon, Oct 19th, 03:35 pm (in class) Final exam: Wed, Dec 16th, 2:45 pm
Grading Policy:	50% (midterm) + 50% (final exam)= 100%
	Each class is different. Therefore, no absolute grading scheme can be defined in advance. However, the following guarantees will always be made: 90% 80% 70% 60% 50% A B C D F

Course Goals/Objectives

This course introduces concepts related to the design and analysis of algorithms. Specifically, it discusses recurrence relations, and illustrates their role in asymptotic and probabilistic analysis of algorithms. It covers in detail greedy strategies, divide and conquer techniques, dynamic programming and max flow - min cut theory for designing algorithms, and illustrates them using a number of well-known problems and applications. It also covers popular graph and matching algorithms, and basics of randomized algorithms and computational complexity. However, the depth of coverage of complexity classes and intractability, approximation algorithms, and randomized algorithms, will be as time permits. The programming assignments can be coded in Python or Java.

To provide a solid foundation in algorithm design and analysis. Specifically, the student learning outcomes include:

• Basic knowledge of graph and matching algorithms.
• Ability to understand and design algorithms using greedy strategy, divide and conquer approach, dynamic programming, and max flow - min cut theory.
• Ability to analyze asymptotic runtime complexity of algorithms including formulating recurrence relations.
• Basic knowledge of computational complexity, approximation and randomized algorithms.

Prerequisites

• CS 3100/5100 Data Structures and Algorithms

Course Format

The course consists of three lectures a week. Attendance of the lectures is not strictly mandatory. However, you are responsible for all materials, announcements, assignments, etc. covered in either the lecture or assignments. If you miss a class, consult a classmate for any missed materials.

The purpose of the class is for everyone to understand the issues involved with computer graphics. To this end, if you don't understand something during class, please ask. If you are confused, it is likely that a few of your classmates are as well. Also, listen to others' questions. Many times you'll think you understand a concept until you hear someone else's question about it. Dialogue is the best way to learn things, so don't be afraid to speak up.

There will be two assignments to be returned on the specified date, one in class midterm, and one final project. The grade will be determined as stated earlier.

Assignments

There may be assignments given during the course of the semester. These assignments may not be graded and do not directly influence your grade. However, it is strongly recommended to do these assignments as they will help you learn the material of the course. Do not expect to get a good/passing grade without working on the assignments.

Office Hours

Other Resources

The class web page is maintained at http://avida.cs.wright.edu/courses/CS7200/. It will keep information, assignments, announcements, etc. There is also a class mailing list. Make sure your email address is registered with the registration system. Please check the web page and read your email. I will try to make any announcements in both places as well as in class, but you don't want to miss anything.
 

Class Policy

Fine Print

Exams Exams will emphasize insight and problem solving ability rather than memorization. Exams will be closed notes, closed book, and no laptops or calculators.

Missed Exams Makeup exams will only be given for the gravest of reasons. If you must miss an exam due to extreme illness, etc., contact the instructor (email is fine) or leave a message with the Department of Computer Science and Engineering office (937-775-5131) before the exam. Be sure to leave both the reasons for missing the exam and how to reach you.

Add/drop Policy A copy of the add/drop policy is available at the main office or online.

Cheating Please do not. I am not obsessed with looking for cheating, but if I see something suspicious, I will refer it to the Office of Judicial Affairs. This is more work for me, and is embarrassing for everyone.  Again, please don't; this has been a problem in the past. If the rules are unclear or you are unsure of how they apply, ask the instructor beforehand. The acacemic integrity policiy as available online.

Feedback If you like, dislike, or don't understand something I'm doing with the course, please stop by my office hours, send me email, or paste together a note from newspaper clippings and drop it in my mailbox. I won't always change things, but I will always explain why I'm doing them the way I am.

Copyright All federal and state copyrights reserved for all original material presented in this course through any medium, including lecture or print. Individuals are prohibited from being paid for taking, selling, or otherwise transferring for value, personal class notes made during this course to any entity without the express written permission of the lecturer.