This page was last updated Friday November 26, 2021 at 15:23:11 EST.

Syllabus for CSCE 750
Analysis of Algorithms
Fall 2021

Time and Place

TTh 11:40am - 12:55pm, Storey Innovation Center 1400.

The lectures will be in person and will be recorded and made available electronically. The University lists two sections for this course: 001 and J60. There will be no meaningful difference between these sections.

Course Homepage

Instructor

Name: Stephen Fenner
Telephone: 803-777-2596 (email preferred)
Email: fenner at cse dot sc dot edu
Web: https://cse.sc.edu/~fenner
Office: Storey Innovation Center 2249
Office Hours: TTh 10:30am - 11:30am virtually via Blackboard Collaborate (link provided on CSE Dropbox)

Teaching Assistant

Name: Theppatorn Rhujittawiwat
Email: rhujittt at email dot sc dot edu
Office Hours: MW 11:30am - 1:00pm virtually via Zoom (link provided on CSE Dropbox)
Office Hours:

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, third 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.)

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 in the 42 years since its original publication.)

Evaluation and Grading

Your learning in this course will be evaluated based on the following measurements.

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 the CSE Moodle server: https://dropbox.cse.sc.edu 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 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.

Class Policies

Attendance

The instructor will not keep detailed recores of class attendance. However, your in- structor 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 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 university’s academic integrity policies are available at http://sc.edu/academicintegrity

Collaboration

For the homework assignments, it is permissible 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 that 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 requires 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: