CS 5110 Design and Analysis of Algorithms
Syllabus
-
Instructor: Alice McRae
-
- Office: 312L Anne Belk Hall
- Email: [email protected]
- Phone: 828-262-2385
- Office hours: TR: 10-11:30, MW: 2-4, and by appointment or walk-in.
- Class Times: MWF 11:00-11:50, Belk 318
- Textbook
- Introduction to Algorithms, by Cormen, Leiserson, and Rivest, 3rd edition (McGraw Hill)
- Course Objectives
-
- Become familiar with algorithm techniques that are applicable
to a wide variety of problems.
- Analyze an algorithm
- Learn some well-known algorithms
- Be able to read and follow textbooks and journal papers related to
algorithms.
- Be able to write algorithms and analysis of algorithms using
appropriate notation
- See (and perhaps become a part of) the development of new research
- Topics Covered
- We will skip around quite a bit in the textbook. I hope to cover the
following: divide and conquer, greedy algorithms, branch and bound algorithms,
backtracking, probabilistic algorithms, approximation algorithms, dynamic
programming, and NP-completenss.
- Grading Policy
- A standard 10-point scale is used for assigning final grades.
Your grade will be computed from the following:
- Midterm Exam, 20%
- Final Exam, 25%
- Class Participation, Assignments, 35%
- Research Assignment, 20%
- Reading
-
Try to read the appropriate sections of the book as we cover the
topic in class. Many times we will skip over details in class,
and you can find more preciseness in the text. If you are not sure
which sections in the book correspond to the material we are covering,
feel free to ask in class.
- Assignments
- Assignments will be given regularly. For most assignments,
you are encouraged to discuss your work
with others and to bring up questions and ideas in class.
- Research Project
-
Students will choose an intractable problem for their project. The
student will pick a problem that is original (it may be
related to a familiar algorithmic problem). The instructor can help
you hone in on an original problem. The student will design a
research paper and programming project that includes the
following:
- A discussion of the problem and related work
- An original NP-completeness proof
- An implementation of an original algorithm for a special case
of the problem
- An implementation of a heuristic algorithm
- Exams
- Exams are worked on individually without collaboration.
The final exam is scheduled for Monday, December 7th, from 9:00 to 11:30am.
- Academic Integrity Code
(quoted from Vice Provost)
-
As a community of learners at Appalachian State University, we must create
an atmosphere of honesty, fairness, and responsibility, without which we
cannot earn the trust and respect of each other. Furthermore, we recognize
that academic dishonesty detracts from the value of an Appalachian degree.
Therefore, we shall not tolerate lying, cheating, or stealing in any form
and will oppose any instance of academic dishonesty. This course will
follow the provisions of the Academic Integrity Code, which can be found
on the
Office of Student Conduct Web Site at www.studentconduct.appstate.edu.
- Accomodations for Students with Disabilities (quoted from Vice Provost)
-
Appalachian State University is committed to making reasonable
accommodations for individuals with documented qualifying disabilities
in accordance with the Americans with Disabilities Act of 1990,
and Section 504 of the Rehabilitation Act of 1973. Those seeking
accommodations based on a substantially limiting disability
must contact and register with The
Office of Disability Services (ODS)
at http://www.ods.appstate.edu/ or 828-262-3056. Once registration
is complete, individuals will meet with ODS staff to discuss eligibility
and appropriate accommodations.