CPTR 314
Data Structures, Algorithms,
and Knowledge Systems Winter 2010

Rick Halterman

School of Computing
126 Hickman Hall
Southern Adventist University
Collegedale, TN 37315-0370
423-236-2871

halterman@southern.edu
http://computing.southern.edu/halterman

Office Hours: http://computing.southern.edu/halterman/General/OfficeHours

HSC 332   MWF 11:00 am
HSC 115   T 11:00 am

Weiss, Mark Allen. Data Structures and Algorithm Analysis in C++, 3/E. 2007.

Admission to the School of Computing, CPTR 215, and MATH 120 or equivalent; MATH 181 is recommended.

Catalog description:

CPTR 314. Data Structures, Algorithms, and Knowledge Systems 4 hours
Prerequisite: Admission to the School of Computing, CPTR 215; MATH 120 or equivalent. Recommended: MATH 181.
Advanced data structures including heaps, hash tables, height-balanced trees, and graphs. Techniques for data abstraction. Algorithms that have application in many areas of computer science including searching, sorting, and graph algorithms. Recursive algorithms. Analysis of algorithms including time and space complexity analysis. Criteria for choosing data structures and algorithms. Fundamental issues in intelligent systems, search and constraint satisfaction, knowledge representation, and reasoning.

This course has seven objectives:

1. to be able to use and implement the most common data structures
2. to develop the ability to analyze algorithms mathematically
3. to understand a wide variety of classic algorithms
4. to understand the basic techniques used in knowledge representation and searching
5. to become more proficient in the C++ language
6. to complete successfully a software team project
7. to complete successfully individual tasks within the team project

Grade Distribution. Final grades are determined according to the following table:

Average	Letter Grade
100-93	A
92-82	B
81-71	C
60-70	D
0-59	F

The letter grades indicate guaranteed minimums; a plus (+) or minus (-) may be attached to further qualify a letter grade.

Class Work. The average used to determine the final grade is computed from the following class activities and is weighted as indicated.

Activity	Weight
Assignments	20%
Quizzes	20%
Test 1	20%
Test 2	20%
Final Examination	20%

Assignments. Assignments consist of written homework and programming problems. Written assignments must be turned in at the beginning of the class period on the day they are due. Solutions to programming problems may be submitted electronically, as described in class.

Quizzes. Periodic quizzes encourage students to remain current in their class preparation. Usually quizzes will be distributed at the beginning of the class period. Missed quizzes may not be made up; however, your lowest two quiz scores will be dropped.

Examinations.  Each test contributes significantly to the overall grade. In certain situations, due to unavoidable circumstances, a missed test may be made up. Arrangements for the retake should be made before the time of the originally scheduled test. The make-up test may vary greatly in form from the original test, but its content (topics addressed) will be the same. Because of this difference, any points added (the so called "curve") to tests taken during the regularly scheduled time may not apply to retakes.

The final examination is worth 20% of your total course grade. Please note the date and time for our final exam on the tentative class schedule. You need to plan to take your final exam at the scheduled time. Please make your work and vacation plans accordingly. Academic Administration will grant approval for variance from the published exam schedule only in cases of verified, serious, illness or a death in the immediate family. Academic Administration may, in case of exceptional and unavoidable circumstances, approve a variance, in consultation with the professor of this course. A $65 processing fee may be assessed.

Ethics. It is expected that each student work individually on individual programming assignments.  For team assignments, collaboration is limited to teammates.  Some exam questions will be based on experience gained by doing the assignments, so it is important that each student develop his own programs for adequate preparation for the examinations. As long as each student develops her own logic and code, it is permissible to help each other over occasional rough spots. In a team programming environment, each team member is expected to understand the workings of the complete program regardless of the division of responsibilities during development.  Except among teammates, portions of programs should never be shared. Those involved in allowing their programs, or parts of their programs, to be copied, or copying from other students' programs risk receiving a grade of F in the course.

Class study. Appropriate study for the course includes reading the textbook (at least as far as last class's lecture material), experimenting with the programs from the book and programs we develop in class, working through the exercises at the end of each chapter.

Class decorum. Please comply with the standards of classroom attire as specified in the Student Handbook.  Notebook computers are welcome, and the classroom and lab (generally) have an excellent wireless signal.  Those with computers should mute the volume and sit in the rear of the class so as not to distract students behind them.  Electronic devices must be turned off during quizzes and tests.  You are expected to remain in the classroom during quizzes and tests, so be sure to take care of affairs (such as bathroom visits and tissue acquisition) before you sit for the quiz or test.

Extra credit. Since the assigned material and activities are sufficient for most students, no extra credit will be available for additional work. However, well-prepared students wishing to enhance their learning experience beyond the class activities will be directed, upon request, to additional resources. Any such additional work will not influence the grade for this class.  

SAU account.  All students must have an active Southern Adventist University email account. This account is necessary to receive class messages and to be able to use the computers in the programming lab. If you normally use a different email address, please set up your SAU account to forward your email to your preferred address; instructions about how to do this are available upon request.

Disability Suport Services. In keeping with University policy, any student with a disability who needs academic accommodations must call Disability Support Services at 236-2574 or stop by Lynn Wood Hall, room 308, to arrange a confidential appointment with the Disability Services Coordinator (DSC) before or during the first week of classes. (Students who request accommodations after the third week of the semester should not depend on receiving accommodations for that semester. Legally, no retroactive accommodations can be provided. For more details, visit the Disability Support Services Web site at http://dss.southern.edu/ .)

Accommodations for disabilities are available only as recommended by Disability Support Services.

• Mathematics review
• C++ review: classes, pointers, templates, STL
• Matrices
• Algorithm analysis
• Abstract data types
• Lists
• Stacks
• Queues
• Binary trees
• Binary search trees
• AVL trees
• B-trees
• Hashing
• Priority queues
• Sorting
• Graphs and their implementation
• Topological sort
• Shortest-path algorithms
• Introduction to NP-completeness
• Greedy algorithms
• Divide and conquer algorithms
• Dynamic programming algorithms
• Fundamental issues of intelligent systems
• Problem spaces/searching
• Best-first search
• Backtracking algorithms
• Games: minimax strategy
• Games: alpha-beta pruning
• Red-black trees
• Neural networks

Note: Items in blue are not covered in the textbook.

• Tuesday, January 6: first day of class
• Monday, January 18: no class (MLK Day)
• Wednesday, February 10: Test 1
• Friday, February 26–Friday, March 5: no class (spring break)
• Wednesday, March 24: Test 2
• Monday, April 26 at 10:00am (note time): final exam

Code we develop in class is available at here.