CSCI 4470/6470 -- Algorithms -- Fall 2009
SYLLABUS
Instructor : Robert W. Robinson
Email : rwr at cs dot uga dot edu
Office : 423 Boyd GSRC
Office hours : Updated list for end of semester;
& by appointment
- Lectures : Mondays 12:20--1:10 in 101 Dawson ; Tuesdays &
Thursdays in room 304 Forest Resources
- Required Text :
Introduction to Algorithms, 2nd edn., by Cormen, Leiserson, Rivest,
and Stein,
MIT Press/McGraw-Hill, © 2001.
- Prerequisites : Intro. to Theory of Computing (CSCI 2670)
and Data Structures (CSCI 2720).
- Course Description : Algorithms, covering basic analysis
techniques, basic design techniques (divide-and-conquer, dynamic
programming, and greedy), basic graph algorithms, and NP-completeness.
- Course Homepage : The URL for the course homepage is
http://www.cs.uga.edu/~rwr/csx470.html.
The readings, homework, announcements, corrections, hints,
and other basic course information can be found there.
- Teaching Assistant : Shahab Razavi
Email: srazavi at uga dot edu
Office hours : 2:00--3:30 Tuesdays in room 301 Boyd.
- Grading :
- Homework : 40% (assignments due most Tuesdays by 5:30 PM in
room 423 Boyd)
- Midterm Exam : 20% (10-15)
- Final Exam : 40% (12-15, 12:00--3:00 PM, room 304
Forestry)
Course assessment will be based on the following scale: if your final
average is at least 85, you're guaranteed an A, if 81 an A-,
if 76.5 a B+, if 72.5 a B, if 68.5 a B-, if 64 a C+, if 60 a C,
if 57 a C-, and if 50 a D.
Graduate students must include at least one graduate/optional exercise
in each homework set.
- Topics and their location in the text:
- Chapter 1 ---- Algorithms in Computing (skim; should be review)
- Chapter 2 ---- Getting Started (skim; should be review)
- Chapter 3 ---- Growth of Functions (study for mastery)
- Chapter 4 ---- Recurrences (Sections 1 and 2)
- Chapter 5 ---- Probabalistic Analysis (Sections 1, 2, and 3)
- Chapter 7 ---- Quicksort
- Chapter 8 ---- Linear Time Sorting
- Chapter 9 ---- Medians and Order Statistics
- Chapter 15 --- Dynamic Programming
- Chapter 16 --- Greedy Algorithms (Sections 1 and 2)
- Chapter 22 --- Elementary Graph Algorithms
- Chapter 23 --- Minimum Spanning Trees
- Chapter 24 --- Single-Source Shortest Paths
- Chapter 25 --- All-pairs Shortest Paths
- Chapter 26 --- Network Flow
- Chapter 34 --- NP-Completeness
- Chapter 35 --- Approximation Algorithms
- Policies: Attendance will not be taken but the class sessions are
an integral part of the course. If you are absent it is your responsibility
to find out what was covered in class and to catch up.
Late homework may not be accepted, and if accepted will
be subject to a 30% penalty. If you can't be in class to turn in a homework,
notify the instructor before that homework is due to arrange an alternate time
for you to turn in the homework.
If you are going to be absent on the day of an examination, you must
provide a University-approved excuse for your absence before the day of the
examination.
Deviations: The course syllabus is a general plan for the course;
deviations announced to the class by the instructor may be necessary.
- Academic Honesty : The overall UGA policy applies. All academic
work must meet
the standards contained in "A Culture of Honesty". Students are responsible
for informing themselves about those standards before performing any
academic work. The link to more detailed information about academic honesty
can be found at
http://www.uga.edu/honesty/ahpd/procedures.html
The Computer Science Department Honesty Policy also applies (see below).
Students are encouraged to consult with the instructor whenever
help is needed. In addition to the instructor's scheduled office
hours, students can make appointments for other times.
E-mail is often a convenient way to ask short questions or to make
an appointment.
Computer Science
Departmental Policy Statement
Academic Honesty
The Computer Science Department recognizes honesty and
integrity as necessary to the academic function of the University. Therefore
all students are reminded that the CS faculty requires compliance with the
conduct regulations found in the University of Georgia Student Handbook.
Academic honesty means that any work you submit is your own work.
Common forms of academic dishonesty which students should guard
against are :
- copying from another student's test paper or laboratory report, or
allowing another student to copy from you;
- fabricating data (computer, statistical) for an assignment;
- helping another student to write a laboratory report or computer
software code that the student will present as his own work, or accepting
such help and presenting the work as your own;
- turning in material from a public source such as a book or the Internet
as your own work.
Three steps to help prevent academic dishonesty are :
- Familiarize yourself with the regulations.
- If you have any doubt about what constitutes academic dishonesty, ask
your instructor or a staff member at the Office of Judicial Programs.
- Refuse to assist students who want to cheat.
All faculty, staff and students are encouraged to report all suspected
cases of academic dishonesty. All cases of suspected academic dishonesty
(cheating) will be referred to the Office of Judicial Programs. Penalties
imposed by the Office of Judicial Programs may include a failing grade in
the course and a notation on the student's transcript. Repeated violations
are punishable by expulsion from the University. For further information
please refer to the UGA Code of Conduct, available at the URL below.
http://www.uga.edu/judicialprograms/2006-07%20Code%20of%20Conduct.pdf