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) |
|
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 |
|