CSCI 570: Advanced Algorithms

Time: Tuesday 6:10pm - 8:30pm
Room: LKD 2113
Instructor: Chunmei Liu
Office: LKD 2038
Email: chunmei AT scs.howard.edu
URL: hucs.dynu.net/liu, or www.networks.howard.edu/liu
Office Hrs: 2pm-3:30pm Tuesday and Thursday
Textbook: Introduction to Algorithms, T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, 3rd Edition, McGraw-Hill.

Course Content:

This course provides an advanced 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 optimization algorithms, approximation algorithms, and algorithms applicable to some computational problems in molecular biology.

Prerequisites:

The prerequisite for this course is CSCI 354: Computer Science 3. Students in the course should have significant programming experience. Students who do not have this background come to see the instructor first.

Assignments:

There will be about five 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.

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.

Grading Policy:

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

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

 

Policy on submission, late assignments, projects, and make-up exams:

        a. No late submissions are accepted.

        b. Students may submit assignments late if an emergency occurs. The instructor must be notified of the emergency at least 12 hours before the deadline if possible. An approval from the instructor before the late submission must be obtained, and the submission must be done within a week from the deadline. In addition, a proof of the emergency must be provided.
Academic Integrity:
Although discussions are encouraged, all homework and programming projects must be completed independently. Suspected plagiarism will incur interviews. The first verified plagiarism will result in zero point of the involved submission and cancel all extra credits. The second will result in a failure in the course.

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 (14 weeks):      

Part 0. Mathematics Foundation (1 week)
Part I. Introduction: Chapters 1-5 (2.5 weeks)
Part II. Sorting and order statistics: Chapters 6-9 (2.5 weeks)
Part IV. Advanced design and analysis techniques: Chapters 15-16 (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.

Syllabus Addendum:

The following understandings, expectations, and requirements shall apply to all classes that are offered by the College of Engineering and Architecture, effective fall 2016. These are the expectations that the students can have from their professors, and the expectations that the professors will have from each student taking her/his class. These are intended promote the success of our students here at Howard, and after graduation.

Students expect that their professors will:

1.      Care about the success of each student, and promote mutual respect.

2.      Come to every class, and on time.

3.      Keep abreast of the technical field she/he is teaching.

4.      Explain how the subject being taught is broadly connected to the field and possibly to other courses.

5.      Keep abreast of, and adapt to, evolving teaching approaches.

6.      Have office hours for each class, and be present at these times.

7.      Coordinate any travel with his/her Department Chairs.

Students who feel that a professor fails in the above expectations may confidentially express his concerns in the Comments box in the Office of Student Services in the L. K. Downing Building, Room 1114, or email Dr. Rhoulac Smith, Director of Student Services, at trhoulac@howard.edu. Your communication must be respectful, professional, and truthful.

 

Professors expect that their Students will:

(Failing to comply will result in appropriate penalties. In certain cases these penalties are expressly defined below.)

   Take a professional approach to all class activities and interactions. Show that your take the class seriously and come to class prepared.

2.      Absenteeism: Come to every class.

·         2% penalty from total class grade for every unexcused absence

3.      Lateness: Not come to class after it begins.

·         1% penalty from total class grade for every instance of infraction

4.      Leaving Early: Not leave class before it ends.

·         1% penalty from total class grade for every instance of infraction

5.      Disruption: Avoid entering and leaving the classroom during instruction.

6.      Eating: No eating in class.

·         1% penalty from total class grade for every instance of infraction.

7.      Electronics: No use of laptop, cell phone, iPad, headphones or other electronic equipment that are not explicitly requested to be used by the Professor.

·         1% penalty from total class grade for every unexcused absence

8.      Cheating: Any form of cheating, including plagiarism, in an exam or assignment shall automatically result in a zero-grade for all involved, for that exam or assignment.

9.      Communication: Communication, oral or written, with the Professor, including email, in all matters concerning the course, shall be done professionally; that is, as it would be done with a potential employer. (e.g., respectful, include your full name, clearly articulate the objective of the communication concisely)