A printable PDF is also available.
CSC 454/654 – Spring 2021 – Syllabus
Instructor: Stephen R. Tate (Steve)
Lectures: Tues/Thurs 9:30-10:45 (via Zoom)
Office Hours: Tues/Thurs 11:00-12:15, or by appointment (via Zoom)
E-mail:
Notes for Spring 2021: Due to the ongoing COVID-19 pandemic, classes and office hours are online using the Zoom teleconferencing software – links to the classroom and office hours room are provided in Canvas. Note that this class is synchronous, which means you are expected to be present and interacting with the class during the scheduled time period. You must be logged in to your UNCG account to attend the Zoom class, which will be the basis for taking attendance for each class. While the lecture portion of each class will be recorded, the recordings are for review and for rare instances when you are not able to attend “live.” Classes will have regular in-class activities that require active participation by everyone, and will utilize Zoom breakout rooms to divide the class into small workgroups. Your participation and work during these sessions will be part of your grade. To take this class, you must have a computer that is capable of running Zoom and online collaboration apps (like Google Jamboard), and you must have and use camera/audio capabilities for collaboration during class.
Class Web Page: https://www.uncg.edu/cmp/faculty/srtate/454.s21/
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
understand how recursion works;
know how to design divide-and-conquer algorithms using three steps and apply to merge sort, quick sort, Strassen’s matrix multiplication;
understand asymptotic notations, and analyze common algorithms using them;
use a greedy strategy to solve some problems such as minimum spanning tree and shortest path;
apply dynamic programming to problems such as matrix chain product, longest common subsequence, and graph algorithms;
understand NP-completeness and why it is important;
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 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.
- Preliminaries (asymptotic notations, data structures)
- Randomized algorithms
- Divide and conquer
- Greedy algorithms
- Dynamic programming
- Graph algorithms
- NP-completeness and approximation algorithms
Teaching Methods and Assignments: This class will meet online for two 75-minute periods per week, and class meetings will consist of a combination of lecture/presentation, discussion, and in-class exercises. Students must be prepared for each class, having done all required readings, and are expected to participate in in-class activities.
In-class participation: Students are expected to participate in class sessions, and problems will be assigned to be solved in small groups. A random participant will be selected for each problem to describe the work and solution of their group, with each student required to present at least one solution during the semester. Attendance is taken using the Zoom participant list, and the in-class participation grade will depend on attendance, work done and submitted for in-class problems, and solution presentation. Each student gets two free “skip days” before attendance penalties are taken, but use of skip days is strongly discouraged!
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. 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 one mid-term exam and one final exam. The midterm exam will be March 9 during the regular class time, and the final exam is scheduled according to the university final exam schedule (May 4, 12:00-3:00). Exams are online, but must be done at the scheduled time.
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 | |
|---|---|
| In-class/participation | 8% |
| Assignments | 48% |
| Mid-term Exam | 20% |
| Final Exam | 24% |
| 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 | |
|---|---|
| In-class/participation | 7% |
| Assignments | 42% |
| Mid-term Exam | 17.5% |
| Final Exam | 21% |
| Research Project | 12.5% |
| 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- |
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. Any cheating in an online exam, no matter how minor, will result in an automatic F in the class. 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 is required, and students are expected to attend class sessions. Attendance is part of the final grade calculation, as described above. 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.
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: During class time, you should be focused on the class. As so much work has moved online in the past few months, there has been a lot of attention to having a professional online presence, which is expected of your participation in this class. This includes everything from backgrounds to dress to other activities going on in your home or workspace. While we can’t control every detail in a work-from-home situation – life happens, after all – you should treat this as a professional setting and act accordingly. You should keep your microphone muted when you are not actively engaged in a class discussion. To promote a sense of community, you are asked to turn on your camera when participating in in-class work groups or when asking or answering a question in the full class setting.
Health and Wellness: 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
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.
Zoom Classes and Recordings: The lecture parts of this course (main room only – no breakout rooms) will be recorded for students to use for review and study, and for rare instances when you are not able to attend “live.” Recordings will include student presentations and interaction in the main lecture room. Access to recordings in Canvas and Panopto will be restricted to class attendees, and students may not attempt to make copies of these recordings or distribute them in any way.
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.