SYCS 570: Advanced Algorithms

Course Content:

This course provides an introduction to the modern study of computer algorithms. Topics include: asymptotic notations and basic algorithm analysis techniques, analysis of sorting algorithms, algorithm design techniques such as divide-and-conquer, greedy, and dynamic programming, fundamental graph algorithms, and a glance at the theory of NP-completeness. In addition, students will be exposed to some advanced subjects such as randomized algorithms, approximation algorithms, and algorithms applicable to some computational problems in molecular biology.

Prerequisites:

The prerequisite for this course is SYCS 354: Advanced Data Structures. Students in the course should have significant programming experience in C++/Java and UNIX. Students who do not have this background come to see the instructor first.

Assignments:

There will be about seven written assignments. Generally, they will be assigned on Tuesday in class, due one week later on the following Tuesday in class. Your written assignments must be TYPED and PRINTED.

One programming project will also be assigned. It will be a team project with two students each team. It will be handed out around mid-term, and will be due two weeks before final exam. Your submission should include the following:

• An electronic version of the source code of your program. The source codes should contain detailed comments.
• A detailed README file explaining where and how you compile and run your program (compiler, machine, commands, etc).
• A document containing the test cases and results of your running your program.

NOTE: If your programming projects cannot be compiled at all, your grade for the project will be ZERO.

Exams:

There will be a midterm exam which will cover all material up to and including the previous lecture. The final exam will cover all materials talked in the course.

Oral and Written Communications:

Every student may be required to submit written reports (not including exams, tests, quizzes, or commented programs) of typically 2-3 pages and to make an oral presentation accordingly of typically 5 minutes.

Grading Policy:

The programming assignments and exams all contribute significantly to your grade. Specifically, your final course grade will be calculated as follows:

• Assignments and projects: 40%

• Presentation: 5%

• Midterm exam: 20%

• Final Exam: 35%

A: 90-100, B: 80-89, C: 70-79, D: 60-69, F: 0-59

         NOTE: Assignments submitted late will not be accepted unless under exceptional circumstances. You will have one uncounted assignment (will not count the lowest score of your assignment into the grading). Grades cannot be argued except there are computing mistakes from the instructor.

There will no extensions due to scheduling conflicts, computer downtime, or other such factors, except under truly extraordinary circumstances. Extensions will be granted only for university-sanctioned excuses such as illness, and then only with the proper documentation. You are responsible for planning ahead and managing your time so that you can complete the assignments on time. You must either finish on time or accept the consequences of doing otherwise.

Academic Dishonesty:

It is expected that the work you submit is your own. Plagiarism and other forms of academic dishonesty will be handled within the guidelines of the Student Handbook. Do not, under any circumstances, copy another person's assignments. Any dishonest forms will violate the University's academic regulations and will be dealt with harshly.

Attendance policy:

You are expected to and should attend classes regularly and complete all assignments on time. Class attendance may be a factor in determining the course grade. If you must miss a class, it's a good idea to let your instructor know in advance or as soon thereafter as possible. If you don't explain your absence, your instructor may assume you don't care about the class or your grade. Coming to class late three times will be counted as one class absence. And later than 10 minutes will also be counted as one class absence. Students are required to attend class during the regularly scheduled tests and the final exam unless prior arrangements have been made.

Tentative Schedule (13 weeks):      

Part 0.	Mathematics Foundation (1 week)
Part I.	Introduction: Chapters 1-5 (1.5 weeks)
Part II.	Sorting and order statistics: Chapters 6-9 (2.5 weeks)
Part IV.	Advanced design and analysis techniques: Chapters 15-17 (4 weeks)
Part VI.	Graph algorithms: Chapters 22-24 (4 weeks)

NOTE: The instructor reserves the right to change the course content, omit parts of the topics listed above or introduce new material midstream to supplement the  course text.

University ADA Policy:

Howard University is committed to providing an educational environment that is accessible to all students. In accordance with this commitment, students in need of accommodations due to a disability should contact the Office of the Dean for Special Student Services for verification and determination of reasonable accommodations as soon as possible after admission to the University, or at the beginning of each academic semester. The Dean of the Office for Special Student Services, Dr. Barbara Williams, may be reached at 202.238.2420.