This page was last updated Friday September 6, 2024 at 11:42:45 EDT.
Syllabus for CSCE 750
Analysis of Algorithms
Fall 2024
Time and Place
MW 2:20pm - 3:35pm, Swearingen 2A05
The lectures will be in person and will be recorded and made available
on Blackboard. The University lists two sections for this course:
001 and J60. There will be no meaningful difference in course content
or grading between these sections.
Instructor
Name: Stephen Fenner
Email: fenner at cse dot sc dot edu
Web: https://cse.sc.edu/~fenner
Office: Storey Innovation Center 2249
Office Hours: MW 1:00pm - 2:00pm, Innov. Ctr. Rm. 2249
Teaching Assistant
Name: Canyu Zhang
Email: canyu at email dot sc dot edu
Office Hours: WF 10:00am - 11:30am, Innovation Center 2242
CRNs
11521 (Section 001), 17268 (Section J60)
Description
Official Description
Algorithm design techniques; algorithms and data structures for sets
and graphs; time and space complexity; sorting and searching;
NP-complete problems.
Content
The course emphasizes methods for analyzing algorithms. It includes a
selection of specific algorithms that solve important problems,
illustrate recurring algorithm design techniques, or both, along with
an introduction to a set of tools, including the theory of
NP-completeness, for establishing the hardness of algorithmic
problems.
Prerequisites
CSCE 350 (Data Structures and Algorithms) or an equivalent
undergraduate-level course on algorithms and data structures. I will
refer to and build upon this background material throughout the
semester.
Textbooks
Required
T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction
to Algorithms, fourth edition, MIT Press/McGraw-Hill, 2009. (We will
cover a substantial fraction the material in this book, which is
considered to be a standard reference for algorithms. Homework
problems will be assigned from it. You can limp along with most of
the course if you only have the 3rd edition, but I don't recommend it.)
Recommended
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide
to the Theory of NP-Completeness, Freeman, 1979. (This is the
definitive book on NP-completeness, which we will cover in the final
part of the semester. The book has remained remarkably relevant and
accessible since its original publication.)
Homework and Quiz Submission, Evaluation, and Grading
The following is based on the as-yet unconfirmed
assumption that I will have a TA/grader for the course. Should this
not be the case, some significant adjustments will be made.
Your learning in this course will be evaluated based on the following
measurements.
- Seven graded homework assignments, worth 10 points each.
Homework grading
will be based on a significant good-faith attempt to solve the
assignment problems correctly. Earning full credit
for the homework requires making such a good-faith attempt to
solve each problem. To submit homework, you must upload
your scanned or typeset answers to the appropriate Blackboard portal
before 23:30 (11:30pm) on the due date. This is a strict deadline.
Late submissions cannot be accepted.
- Seven quizzes, worth 40 points each (see the table on
the homepage for dates and times). Each quiz
will last 20-30 minutes. Quizzes are open book, open
notes, but no electronic devices allowed except for necessary
downloading if a quiz is taken remotely. (I strongly suggest that you
not rely on using the textbook or notes during the quiz.)
- Rules for Section 1: Students in
Section 1 will take the quiz in person in the usual classroom at or
very near the start of class. A Section 1 student taking the quiz remotely or
taking a make-up quiz will not be allowed except under certain extreme
circumstances: a recent positive COVID-19 test, quarantining required
by the University, a pre-arranged alternative testing agreement with
the Student Disabilities Office, or a dire household
emergency. In any case, prior notice and documentation are
required. Examples of insufficient reasons not to take the quiz in
person include, but are not limited to: car trouble; an event (such as
a wedding or travel) that is known in advance; illness or death of a
friend or extended (i.e., non-immediate) family member.
- Rules for Section J60: Students in Section J60 will take the
quizzes remotely at the same time, receiving the quiz handout via
Blackboard and uploading their answers to the appropriate Blackboard
portal before the deadline mentioned in the email message. (NOTE: If
for any technical reason the Blackboard portal is inaccessible, you
should instead attach your submission to an email directly to the TA
(email address above) before the deadline.) You are given extra time
(over those in Section 1)
to upload and submit your quiz answers electronically: 5 minutes for a
quiz, 10 minutes for the final exam. You are expected to stop writing
your answer when the extra time period starts. If you continue to
write your answers during the extra time period, you run the serious
risk of not being able to upload (or email, if necessary) your quiz
answers by the deadline, thus getting a 0 for the quiz or final exam.
The deadline is strict.
Communicating during the quiz-taking window with anyone except me
regarding the content of the quiz is strictly forbidden and is
considered a violation of the Carolina Honor Code with all its severe
consequences (see the Cheating section of Class Policies, below).
- A final exam worth
200 points (see the table on the homepage for
date and time). The rules for both sections of the course are the
same as for the quizzes. The final exam will be open book, open
notes, but no electronic devices are allowed.
Thus, a total of 550 points will be available through the
semester.
Your letter grade corresponds to your total point value x as follows:
| A |
if 495 ≤ x ≤ 550 |
| B+ |
if 473 ≤ x < 495 |
| B |
if 440 ≤ x < 473 |
| C+ |
if 418 ≤ x < 440 |
| C |
if 385 ≤ x < 418 |
| D+ |
if 363 ≤ x < 385 |
| D |
if 330 ≤ x < 363 |
| F |
if x < 330 |
Gradebook access
Grades will be posted on Blackboard. It is your responsibility to
verify that grades are correctly recorded on this site.
Showing your work
Merely giving a correct final answer on a homework problem, test, or
quiz is not enough to show that you understand the crucial principles and
methods used to solve a problem beyond simply guessing. Therefore, unless I
explicitly say otherwise, you must show reasonable and relevant work
on every problem. Not showing your work will carry a point penalty,
even if your final answer is correct. Conversely, showing reasonable
work may earn you partial credit if your final answer is incorrect.
Corrections and regrades
Our goal is to ensure that all of the grading for this course is fair
and correct. If you believe there's been a mistake in grading, please
bring it to the instructor's or the TA's attention in office hours
within one week after the scores are posted. Regrade requests after
one week will be politely declined. Please note that we do not
negotiate point values; we will change grades only if a mistake was
made in grading.
Deviations from the grading policy
We assume that every student takes the class intending to succeed, and
we share that goal. However, in the interest of fairness and
consistency, requests for grade increases that are inconsistent with
the stated grading scale will be politely declined. Here is an
incomplete list of hypothetical requests from students that are not
sufficient reasons to deviate from the stated grading scale:
- I need a GPA of at least ____ to get the internship I want.
- My parents will be disappointed in me.
- If my grade is less than ____, I won't be able to graduate.
- I've never gotten a grade as low as ____ before.
- Getting a grade lower than ____ makes me feel sad.
- I have too many other responsibilities.
- The course is too hard for me.
- I worked really hard in this course.
- I am about to graduate.
- I have a good GPA so far.
- I have never failed a class before.
- I am willing to do extra work.
- I am really close to getting a ____.
- I want to stay in the graduate program.
Class Policies
Attendance
The instructor will not keep detailed records of class attendance.
However, your instructor will make every effort to ensure that class
attendance is worth your time. Missed quizzes due to unexcused
absences will result in a score of zero.
Cheating
Academic dishonesty undermines the educational mission of the course
and the University
and reflects disrespect to your classmates and to your
instructor. Therefore, you are expected to practice the highest
possible standards of academic integrity. The academic penalty for
cheating is a failing grade for the course. This policy includes all
forms of academic misrepresentation. Details on the university's academic
integrity policies are available at
http://sc.edu/academicintegrity
Collaboration
For the homework assignments, it is permissible (even encouraged) to discuss the
problems at a high level with your classmates, but you should work out
the details and compose the complete answers independently. Submission
of identical or substantially identical work will be considered strong
evidence that cheating has occurred. The quizzes and final exams must
be completed fully independently.
Late assignments
Homework assignments cannot be accepted late, because solutions will
be posted shortly after the deadline.
Mobile devices
Please silence any mobile devices before coming to class. If your
phone rings in class, I reserve the right to answer it for you and
take a message. Likewise, if my phone rings during class time, I will
allow a student to do the same.
Accommodations for disabilities
The instructor is happy to ensure that the class is fully accessible
to students with disabilities. Any student with a documented
disability should contact the Student Disability Resource Center to
make arrangements for appropriate accommodations.
Policy changes
As with previous semesters, this Fall presents a degree of
uncertainty due to the course of COVID-19. As a result,
changes to the syllabus at the instructor's reasonable discretion,
including changes to course schedule or to the evaluation and grading
mechanisms, are possible. (See the next item.)
Policies related to COVID-19
The last thing I want is for someone in my class to fall ill due to
contracting COVID-19 from someone else in my class. Therefore, I
strongly encourage being vaccinated. The University also strongly
recommends all
students, faculty, and staff to wear masks in UofSC buildings and on
campus busses. Doing this will protect both yourself and those around
you. Other common-sense measures, such as frequent testing (if
unvaccinated) and physical distancing should also be practiced both
in and out of class. The University provides several online
covid-related links: