A printable PDF is also available.

CSC 454/654 – Spring 2022 – Syllabus

Instructor: Stephen R. Tate (Steve)
Lectures: Tues/Thurs 11:00-12:15, in Petty 219
Office: Petty 157
Office Hours: Tues/Thurs 1:45-3:15 (or by appointment), in-person or virtual – see below
E-mail:

Note regarding Spring 2022: While the COVID-19 pandemic is ongoing, the wide availability of safe and effective vaccines provide hope that we will be able to hold a somewhat normal, in-person semester. In particular, this class is planned as a fully in-person class, and you are expected to attend lectures in the assigned classroom. If the COVID situation worsens and in-person meetings cannot be held safely, then we will revert to online meetings. However, this is not a hybrid class, and all students will have the same experience – either all in-person or all online.

Office hours are available both in-person (in my office, Petty room 157) or online via Zoom teleconferencing software – a link to the Zoom office hours room is in Canvas. Please be aware that my office is a small enclosed space, and if you are uncomfortable with that you can connect via Zoom. Also, due to my small office space, down a short but narrow side-corridor, you are asked to wait in the more open main hallway if I am meeting with someone else (in person or virtually). If I’m talking to someone online when you arrive, make sure I see you and then I will come out to the main hallway to let you know when I’m available after the online session. I can only meet with one person at a time during office hours.

For us to be able to get back to normal, everyone must do their part to protect both their own health and the health of others. More information COVID-specific class protections and policies is in the university COVID statement at the end of the syllabus.

Class Web Page: https://www.uncg.edu/cmp/faculty/srtate/454.s22/

Catalog Description: Sequential algorithm design and complexity analysis. Dynamic programming. Greedy algorithms. Graph algorithms. Selected advanced topics from NP-completeness; approximation, randomized, parallel, number-theoretic algorithms; Fast Fourier Transform; computational geometry; string matching.

Prerequisites: Grade of C or better in CSC 330, or permission of instructor.

Longer Description: This class is all about the study of algorithms, covering how to model real-world problems with precise mathematical models, how to apply different algorithmic problem solving techniques, how to analyze efficiency and reason about correctness of algorithms, and how to communicate clearly about algorithms. Student work will include theoretical analysis and proofs, on-paper design, and programming solutions. Expected background includes a solid mathematical background in discrete mathematics and proof-writing (CSC 250) and knowledge of data structures (CSC 330). While you aren’t expected to be an expert, you should have working knowledge of asymptotic notation, recurrence relations, hash tables, tree structures, graphs, and basic graph algorithms such as search and path-finding algorithms.

Student Learning Outcomes: Upon successful completion of this course students should be able to

  1. understand how recursion works;

  2. know how to design divide-and-conquer algorithms using three steps and apply to merge sort, quick sort, Strassen’s matrix multiplication;

  3. understand asymptotic notations, and analyze common algorithms using them;

  4. use a greedy strategy to solve some problems such as minimum spanning tree and shortest path;

  5. apply dynamic programming to problems such as matrix chain product, longest common subsequence, and graph algorithms;

  6. understand NP-completeness and why it is important;

  7. prove some problems (such as CLIQUE, VC, and subset sum) are NP-complete.

Textbook and Readings: The required textbook is

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition, MIT Press, 2009. ISBN: 9780262033848

This book is available to UNCG students for free at https://ebookcentral.proquest.com/lib/uncg/detail.action?docID=3339142 (requires login with your UNCG account).

Topics: The following are the major topics that will be covered in this class. A detailed schedule, including references to textbook sections/chapters covered, is on the class website.

Teaching Methods and Assignments: This class will meet for two 75-minute periods per week, and class meetings will consist of a combination of lecture/presentation and discussion, with a heavy emphasis on working through problems as a class and potentially in small student groups. Students are expected to be prepared and actively participate in class, having done all required readings in advance. Students should take notes of any parts of the readings that are not clear, so that these can be discussed during the class meetings. Grades are based on student work done in assignments and exams.

Assignments: For practice and to demonstrate abilities, students will be given 5-6 assignments over the course of the semester (approximately every two weeks, adjusted to exclude exam weeks). Assignments will include some written problems and some programming problems. Written problem solutions will be submitted in Canvas as PDF files. Written solutions may be neatly handwritten and scanned or prepared electronically if written using appropriate mathematics typesetting techniques. More information on how to properly and professionally write mathematical documents is provided on the Assignments page of the class website. If you write your solutions up by hand and want to use your phone to produce the PDF, you should use a “scan to PDF” app to produce a proper and readable PDF document (do not just submit pictures or pictures converted to PDF format). If you are planning to do this, practice well in advance to make sure you can create a PDF — deadlines will be enforced, and “I waited until 11:55 to test my scan-to-pdf software” is not an acceptable excuse for late submission. Programming problems will be submitted using a system set up specifically to accept and test solutions (more details later), and solutions can be completed in Java, C++, or Python; other languages may be used if pre-approved by the instructor.

Exams: There will be two mid-term exams and one final exam. Tentative dates for each exam are provided on the class web site schedule.

Graduate Students: Students taking this class for graduate credit (as CSC 654) or as a contract honors course will complete a research project on an algorithms topic of their choosing. More information, including a list of potential topics, will be given approximately halfway through the semester.

Evaluation and Grading: Each student work product will be graded, and the student’s final grade will be determined by assigning each category of work a weighted score according to the following distribution:

Undergraduates
Assignments 50%
Mid-term Exam 1 15%
Mid-term Exam 2 15%
Final Exam 20%

 

Letter Grade Assignment
[87.5 , 89.5) = B+ [77.5 , 79.5) = C+ [67.5 , 69.5) = D+ [0 , 59.5) = F
[91.5 , ∞) = A [81.5 , 87.5) = B [71.5 , 77.5) = C [61.5 , 67.5) = D
[89.5 , 91.5) = A- [79.5 , 81.5) = B- [69.5 , 71.5) = C- [59.5 , 61.5) = D-
Graduate Students
Assignments 45%
Mid-term Exam 1 13.5%
Mid-term Exam 2 13.5%
Final Exam 18%
Research Project 10%

 

Letter Grade Assignment
[87.5 , 89.5) = B+ [77.5 , 79.5) = C+ [0 , 71.5) = F
[91.5 , ∞) = A [81.5 , 87.5) = B [71.5 , 77.5) = C
[89.5 , 91.5) = A- [79.5 , 81.5) = B-

 

Note that Canvas uses the same letter grade assignment for undergraduate and graduate students, even though there are no passing grades below a C for graduate students. Any graduate student with a C- or below in Canvas will receive an F in the class.

Academic Integrity: Students are expected to be familiar with and abide by the UNCG Academic Integrity Policy, which is online at https://academicintegrity.uncg.edu/.

Assignments in this class are for individual work, unless explicitly stated otherwise. General concepts and material covered in the class may be discussed with other students or in study groups, but specific assigned problems should not be discussed and all submitted work should be entirely your own. If you use external references (including websites, books, etc.) in preparing your solutions, you should clearly mark the part(s) of your solution influenced by these references and provide clear citations to the source of information you are using. Just doing a Google search for solutions to assigned problems is a violation of academic integrity, whether or not you use what you find in your answer. Sharing your own work is a serious violation of academic integrity, and if homework is copied then both the person who actually did the work and the person who copied it will be punished. Any incidents of academic dishonesty will be handled strictly, resulting in either a zero on the assignment or an F in the class, depending on the severity of the incident. Significant incidents will be reported to the UNCG Office of Student Rights and Responsibilities. Note that the Department of Computer Science maintains records of all academic integrity incidents, and multiple violations, even in different classes or semesters, will always result in reporting to the university and serious penalties.

Attendance Policy: Attendance will not be taken in class, and is voluntary; however, all students are responsible for everything done or said in class (this can include changes in assignments, due dates, etc.). Note that class meetings will not be simply information delivery – that’s what the textbook is for – but will focus largely on working through and solving problems similar to those on assignments and exams. It is highly unlikely that a student who regularly misses classes will be successful in the course. If attendance becomes a problem, then in-class exercises may be used as part of the assignment portion of the grade.

The university allows for a limited number of excused absences for religious observances. Students who plan to take such an absence should notify the instructor at least two weeks in advance so that accommodations can be made (see the late work policy below). It is the student’s responsibility to obtain notes from another student if they miss class.

Late Policy and Makeup Exams: Assignments are due at 11:59PM on the due date, and may be turned in up to 7 calendar days late with a 25% late penalty. Students with planned absences, whether for university events, religious observance, or other reason, are expected to make arrangements with the instructor to turn in assignments or take exams before the scheduled date of the assignment or test. No assignment will be accepted more than 7 calendar days after the original due date! For graduate/honors students completing the research project, it may not be submitted late.

Exam/test dates will be announced at least two weeks in advance, and may be made up only if it was missed due to an extreme emergency and arrangements are made before the exam date. Exams may not be taken early or late due to personal travel plans.

Given the COVID-19 situation, I will be flexible and accommodating within reason, but students must inform me of any complications in advance of due dates.

In-class Behavior: When you are in class you should be focused on the class, and you should act in a professional and mature manner. During class there should be no eating, drinking, e-cigarettes, cellphone use, non-class related laptop use, or anything else that does not pertain to the class activities. Any distracting items may be confiscated at the discretion of the instructor. Students are required to abide by UNCG COVID policies (see below), and will be asked to leave if there is an issue.

ADA Statement: UNCG seeks to comply fully with the Americans with Disabilities Act (ADA). Students requesting accommodations based on a disability must be registered with the Office of Accessibility Resources and Services located in 215 Elliott University Center: (336) 334-5440 (or on the web at https://oars.uncg.edu). Note that if you require testing accommodations you must make arrangements more than one week before any exam.

University COVID-19 Policy: As we return for Spring 2022, all students, faculty, and staff are required to uphold UNCG’s culture of care by actively engaging in behaviors that limit the spread of COVID-19. These actions include, but are not limited to:

Instructors will have seating charts for their classes. These are important for facilitating contact tracing should there be a confirmed case of COVID-19. Students must sit in their assigned seats at every class meeting. Students may move their chairs in class to facilitate group work, as long as instructors keep seating chart records. Students should not eat or drink during class time.

A limited number of disposable masks will be available in classrooms for students who have forgotten theirs. Face coverings are also available for purchase in the UNCG Campus Bookstore. Students who do not follow masking requirements will be asked to put on a face covering or leave the classroom to retrieve one and only return when they follow the basic standards of safety and care for the UNCG community. Once students have a face covering, they are permitted to re-enter a class already in progress. Repeated issues may result in conduct action. The course policies regarding attendance and academics remain in effect for partial or full absence from class due to lack of adherence with face covering and other requirements.

For instances where the Office of Accessibility Resources and Services (OARS) has granted accommodations regarding wearing face coverings, students should contact their instructors to develop appropriate alternatives to class participation and/or activities as needed.

Health and well-Being: Health and well-being impact learning and academic success. Throughout your time in the university, you may experience a range of concerns that can cause barriers to your academic success. These might include illnesses, strained relationships, anxiety, high levels of stress, alcohol or drug problems, feeling down, or loss of motivation. Student Health Services and the Counseling Center can help with these or other issues you may experience. You can learn about the free, confidential mental health services available on campus by calling 336-334-5874​, visiting the website at https://shs.uncg.edu/ or visiting the Anna M. Gove Student Health Center at 107 Gray Drive. For undergraduate or graduate students in recovery from alcohol and other drug addiction, the Spartan Recovery Program (SRP) offers recovery support services. You can learn more about recovery and recovery support services by visiting https://shs.uncg.edu/srp or reaching out to recovery@uncg.edu

Elasticity Statement: It is the intention of the instructor that this syllabus and course calendar will be followed as outlined, however, as the need arises there may be adjustments to the syllabus and calendar. In such cases, the instructor will notify the students in class and via e-mail with an updated syllabus and calendar within a reasonable timeframe to allow students to adjust as needed.