A printable PDF is also available.

CSC 656 – Fall 2019 – Syllabus

Instructor: Stephen R. Tate (Steve)
Lectures: Mon/Wed 3:30-4:45, Petty 007
Office: Petty 157
Office Hours: Mon/Wed 2:00-3:20, or by appointment
E-mail:

Class Web Page: http://www.uncg.edu/cmp/faculty/srtate/656/

Catalog Description: Introduces the mathematical foundations that support advanced studies in computer science including computer programming and the analysis of algorithms.

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

Note that I expect you to have a solid undergraduate-level mathematics background, with knowledge of discrete mathematics topics that are typically covered in an undergraduate computer science curriculum. This includes a basic ability to write proofs and an understanding of simple combinatorics and mathematical structures (sets, relations, graphs, etc.).

Longer Course Description: This course is all about developing your reasoning, analytical, and communication skills in computer science. This includes reasoning about the correctness of algorithms, writing clear and rigorous proofs, analyzing properties of algorithms such as running time or other resource requirements, mapping computer science problems to more general/abstract mathematical structures, and working with these mathematical structures. Throughout the course you will be exposed to some core computer science topics which you may see again in other courses, but our focus in this class will be on the analysis and reasoning skills around these topics rather than a full exploration of the topic itself. I understand that students in this class come from a variety of backgrounds, and some are not native English speakers, but clear communication skills in English are vital to anyone working in the field of computer science. We will work on this, and you will be held to high standards!

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

1. Perform mathematical analysis of algorithm resource requirements at an advanced level;

2. Work with graphs and other important discrete structures;

3. Write proofs to establish basic mathematical and computational properties;

4. Analyze events in a system using probability theory.

Textbook and Readings: The required textbook is

Eric Lehman, F. Thomas Leighton, and Albert R. Meyer. Mathematics for Computer Science, June 6, 2018.

This book is available as a free PDF download from https://courses.csail.mit.edu/6.042/spring18/mcs.pdf or a local download (authorized with a Creative Commons license). Note that there are several versions online, as the book has been updated, so please make sure you have the correct version for this class which is the “2018/6/6” version. For those that prefer a print copy, you can order one through Amazon – however, read the reviews first, because some people are unhappy with the print and Kindle versions.

Throughout the semester, additional readings will be provided covering additional topics. These will be made available through the class web site and/or Canvas, as appropriate.

Topics/Schedule: This class is undergoing a redesign from the way that it has been taught in the past, so the schedule and precise topic list is flexible. The class is divided roughly into thirds, as follows:

• One third on mathematical background, basic analysis, and proof techniques;

• One third on graph theory; and

• One third on probabilistic analysis.

A detailed schedule showing a couple of weeks beyond the current date is on the class web site, and will be updated throughout the semester.

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 to come to class prepared, having done all required readings, and are expected to participate in in-class activities. Since technical communication is an important part of this class, all students will be expected to present solutions to the class during the semester.

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). Assignment solutions should be prepared using LaTeX, as it is the standard for preparing technical/mathematical documents. A template will be provided and a small amount of in-class time will be spent giving an overview, but students will be expected to learn this primarily on their own. LaTeX can be used either as a locally-installed program (the traditional way) or through an online service such as Overleaf. Neatness, professionalism, and aesthetics are an important part of technical communication, and will be part of your grade. Do not use Microsoft Word or some other word processor for your assignments!

Exams: There will be two mid-term exams and one final exam, following the basic course structure with content divided into thirds (see “Topics/Schedule” above). The final exam will be comprehensive, but the majority of the exam (at least 66%) will cover topics from probabilistic analysis (the final third of the course).

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 http://academicintegrity.uncg.edu/

Assignments in this class are for individual work, unless explicitly stated otherwise, and when you are asked to solve a problem you are to come up with a solution to the problem through your own mental problem solving — note that this is quite different from just “finding a solution,” which you will never be asked to do in this class. 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. The “general concepts” rule applies to online materials as well: if you use online materials to help you learn general concepts, that’s fine, but nothing you use should be specific to a problem you are assigned to solve. Even doing a Google search looking for an assigned problem is a violation of academic integrity.

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. 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, and incidents will be reported to the UNCG Office of Student Rights and Responsibilities.

Attendance Policy: Since this is a very interactive class, with students giving presentations, regular attendance is vital. While perfect attendance isn’t required, points will be deducted from your participation grade if attendance becomes an issue (if you miss more than two classes). If you regularly miss classes (more than 5 classes in the semester), then more severe penalties will be given, exceeding the small number of points in the participation part of your 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 the beginning of class 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!

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. The final exam will be at the university-scheduled time: Friday, December 6, 3:30–6:30.

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 http://oars.uncg.edu).

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.