Fall 2016

Syllabus for CSC 8301 (Design and Analysis of Algorithms)

Fall 2016

 

Instructor

Dr. Mirela Damian, Mendel Science Center 167A

mirela.damian@villanova.edu (preferred contact method)
Phone: (610)519-7414

Office Hours

M   3:00 pm – 4:30 pm, R 2:00 pm – 3:30 pm, and by appointment

Course Meets

M 6:15 pm 9:00 pm in Mendel G86

Prerequisites

General requirements (calculus, discrete math, data structures)

Textbook

Introduction to the Design and Analysis of Algorithms

3rd ed., by Anany Levitin, ISBN-10: 0-13-231681-1

 

Course Description

 

Major algorithm design techniques; theoretical and empirical analysis of nonrecursive and recursive algorithms; applications to sorting, searching, string matching, graphs; P and NP complexity classes, approximation algorithms.

 

Course Objectives

 

1.     Establish an understanding of fundamental techniques for algorithm design

2.     Establish an understanding of efficiency classifications

3.     Develop and ability to mathematically analyze recursive and nonrecursive algorithms

4.     Apply algorithmic techniques to important problems from various areas of computing

 

 

Resources

 

Website:

http://www.csc.villanova.edu/~mdamian/csc8301/

Notes, assignments, announcements and other course-related materials will be posted on this class website. Please make sure you check the class page regularly.

Texts:

1.     (Required) Introduction to the Design and Analysis of Algorithms, 3rd ed., by Anany Levitin, ISBN-10: 0-13-231681-1

2.     (Recommended as supplement) Introduction to Algorithms, Cormen et. al, 3rd edition, ISBN 0262033844

Course Requirements

1.     Homework: Homework will be assigned after each lecture and will include reading and exercises (with hints and solutions provided).  Although homework assignments will not be collected for grading, doing them timely and diligently is crucial for mastering the subject.

 

2.     Quizzes: 10-minute quizzes will be given every class. They will be administered at the beginning of the class, so make sure to show up on time to class. A missed quiz will just result in a zero (no make-up quizzes).

 

3.     Tests: one midterm and one comprehensive final exam. Tests will be open books, closed notes, closed electronic devices.

 

Tentative Grading Procedure

 

Your grade will be computed based on home readings and activities, quizzes, lab projects and exams, each contributing equally to your final score as follows:

                                   

Quizzes:

30%

Midterm:

30%

Final exam:

40%

 

The average of the two exams must be ≥ 50 to pass the course. On a 100-point scale, you can expect the following letter grades:

 

 

≥ 80: B+

≥ 57: C+

≥ 94: A

≥ 72: B

≥ 50: C

≥ 87: A-

≥ 64: B-

 

Policies

 

1.     Class Attendance Policy. Mandatory. Each student is responsible for all material, announcements, and assignments covered during any class missed.

 

2.     Makeup Policy. There will be no makeup quizzes (regardless of whether you had an excused or unexcused absence). If you need to miss an exam due to an emergency, try to notify me in advance so we can make arrangements to make it up. Makeup tests will not be easier than regularly scheduled tests.

 

3.     Academic Integrity. All students are expected to uphold Villanova’s Academic Integrity Policy and Code.  Any incident of academic dishonesty will be reported to the Dean of the College of Liberal Arts and Sciences for disciplinary action.  For the College’s statement on Academic Integrity, you should consult the Enchiridion.  You may view the university’s Academic Integrity Policy and Code, as well as other useful information related to writing papers, at the Academic Integrity Gateway site

 

http://library.villanova.edu/Help/AcademicIntegrity

           

4.     Special Arrangements. Students with disabilities who require reasonable academic accommodations should schedule an appointment to discuss specifics with me. It is the policy of Villanova to make reasonable academic accommodations for qualified individuals with disabilities. You must present verification and register with the Learning Support Office by contacting 610-519-5176 or at learning.support.services@villanova.edu, or for physical access or temporary disabling conditions, please contact the Office of Disability Services at 610-519-4095 or email Stephen.mcwilliams@villanova.edu. Registration is needed in order to receive accommodations.


Tentative Course Schedule

 

The course schedule below is approximate and subject to change as the semester progresses. It is the responsibility of the student to learn and adjust to changes.

 

Date

Topic

References

Week 1: Aug. 29

Introduction. Efficiency Analysis Framework

Chapter 1, 2

Sep. 5

Labor Day – ENJOY!

Week 2: Sep. 12

Mathematical Analysis of Non-Recursive Algorithms

Chapter 2

Week 3: Sep. 19

Mathematical Analysis of Recursive Algorithms

Chapter 2

Week 4: Sep. 26

Brute Force, Exhaustive Search, DFS, BFS

Chapter 3

Week 5: Oct. 3

Decrease and Conquer

Chapter 4

Oct. 10 – 16

Fall Break – ENJOY !

Week 6: Oct. 17

Divide and Conquer

Chapter 5

Week 7: Oct. 24

Midterm

Week 8:  Oct. 31

Transform and Conquer

Chapter 6

Week 9: Nov. 7

Space and Time Tradeoffs

Chapter 7

Week 10: Nov. 14

Dynamic Programming

Chapter 8

Week 11: Nov. 21

Greedy Approach

Chapter 9

Week 12: Nov. 28

Linear Programming and the Simplex Method

Chapter 10

Week 13: Dec. 5

P; NP; NPC; Backtracking and Branch-and-Bound

Chapters 11, 12

Week 14: Dec. 12

Approximation Algorithms

Chapter 12

Final Exam

Monday, Dec. 19, 6:00 pm – 8:30 pm