CPSC 212-002 Computer Science IV
(Data Structures and Algorithms)

Syllabus

Instructor: Dr. Andrew Duchowski
Office: McAdams 309, 656-7677, andrewd@cs.clemson.edu
Office hours: M 13:00—15:00 (or by appointment)
Email: Communication with the instructor via email is preferred.
Required texts:
  1. Weiss, Mark Allen, Data Structures and Algorithm Analysis in C++, 3rd ed., 2006.
    ISBN: 0-321-44146-X
Recommended texts:
  1. Dale, Nell, Weems, Chip, and Headington, Mark, Programming in C++, Jones and Bartlett, 1997.
Supplemental texts:
  1. Jensen, Henrik Wann, Realistic Image Synthesis Using Photon Mapping, A K Peters, Ltd., 2001.
Grading scheme: Based on programming assignments, final project, midterms, and the final exam.
Grade distribution:
Assignments40%
Midterm20%
Lab10%
Final Exam30%
Bonus2-5%
%Grade
90-100A
80-89B
70-79C
60-69D
< 60F
Programming assignments: Problem specification and due date will be given in class.
Assignment grading: Source code and demonstrations will be required.
Assignment format: Hardcopy of the assignment must include the following:
  • Description of the problem.
  • Design of the solution (e.g., algorithm) and its implementation (e.g., classes, data structures, etc.).
  • Documentation of the program solution (e.g., usage).
Electronic submission of the code must include the following:
  • Modules (files) must begin with a comment giving the author's name, course, and section number (e.g., John Doe, CPSC XXX-YYY). The assignment number must also be included, except for general-purpose modules. A brief description of the purpose of the module should follow (e.g., problem solved by the main program, facilities provided by the class, etc.). A brief description of the approach to solving the problem or facility by the module should also be included.
  • Comments must be included in declarations to state what each constant or variable represents.
  • Each function must be documented (with comments) stating what the function does, and if appropriate, how the function is performed. Comments should also indicate the role of each parameter.
  • Indentation levels (2 spaces per indent; avoid tabs) should be used to indicate nesting levels in code.
Assignment late policy: Late assignments will be accepted but points will be deducted according to the formula (3n)3 where n is the number of days late. Example: assuming assignments are due on Monday, the point deduction is as follows:
Max points possible Day received Days late
100Monday0 (due date)
73Tuesday1 day late
0Wednesday2 days late
Late assignments will receive lowest priority for grading and returning.
Attendance: Roll will be taken for the first one or two weeks while the class roll fluctuates. However, attendance is not required. Absence, excused or not, does not change the responsibility for assigned work. No unexcused absences are allowed from labs. Tests missed due to excused absences will normally result in the test not being counted in the average grade (i.e., there will normally be no makeup tests). An unexcused absence from a test will normally result in a grade of zero for that test. Students are expected to give at least one week advance notice for excused absences.
Independent work: Unless otherwise stated explicitly (e.g., in the case of the final project), each student must do his or her work independently.
Academic dishonesty: The University policies on academic dishonesty apply. Publicly-available code or other material may be freely used if appropriately attributed. Each student is responsible for protecting his or her files from access by others. Work that is essentially the same and submitted without proper attribution is considered to be a violation of academic dishonesty policy by all those submitting the work, regardless of who actually did the work.
Class cancelation: Students are expected to wait for 15 minutes after the class beginning time before leaving if the instructor is late.
Course description: The course will cover C++, data structures, analysis of algorithms, and selected application/implementation examples, generally following the organization of the text:
  • Part I: Objects and C++
    • Pointers, Arrays, and Structures
    • Objects and Classes
    • Templates
    • Inheritance
  • Part II: Algorithms and Building Blocks
    • Algorithm Analysis
    • Data Structures
    • Recursion
    • Sorting Algorithms
    • Randomization
  • Part IV: Implementations
    • Stacks and Queues
    • Linked Lists
    • Trees
    • Binary Search Trees
    • Hash Tables
    • A Priority Queue: The Binary Heap
  • Part III: Applications
Topics for Part III will be selected as time permits.