A printable PDF is also available.

CSC 454/654 – Spring 2020 – Syllabus

Instructor: Stephen R. Tate (Steve)
Lectures: Mon/Wed 5:30-6:45, Petty 227
Office: Petty 157
Office Hours: Mon/Wed 1:30-3:00, or by appointment
E-mail:

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

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 CSC 350) 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 notation, 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 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 web site.

• 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 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 come to class prepared, having done all required readings, and are expected to participate in in-class activities. 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 solutions may be prepared electronically using LaTeX or may be neatly handwritten, and are to be turned in on paper at the beginning of class on the due date. Do not use a standard word processor such as Word or LibreOffice unless you properly write mathematics using the equation editor capabilities. Programming problems 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 chosing. 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:

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 web sites, 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.). Many topics covered in this class are challenging, and it is highly unlikely that a student who regularly misses classes will be successful in the course. If attendance becomes a problem, the instructor reserves the right to give pop-quizes or graded in-class exercises.

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. 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 the beginning of class on the due date, and no credit will be given for late assignments. 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.

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 (including the final) may not be taken early or late due to personal travel plans.

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.

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 a separate testing environment you must make arrangements more than one week before any exam.

University Closings: If university facilities are closed due to flu outbreak or other emergencies, it does not mean that classes are canceled. In such an event, please check the class web page and Canvas site for information about if and how the class will proceed.

Commercial note-taking services: Selling class notes for commercial gain or purchasing such class notes in this or any other course at UNCG is a violation of the University’s Copyright Policy and of the Student Code of Conduct. Sharing notes for studying purposes, or borrowing notes to make up for absences, without commercial gain, are not violations.