CPTR 318
Data Structures and Algorithms Winter 2017

Home Code Final Exam Study Guide Assignments WebGrades


Instructor

Rick Halterman

School of Computing
1117E 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


Course Venue

HSC 1307   MWF 11:00 am


Textbook

Shaffer, Clifford. Data Structures and Alorithm Analysis in C++, Third Edition. Dover Publications. ISBN 048648582x. 2011. (http://store.doverpublications.com/048648582x.html)

The printed version of the textbook is available for purchase from the publisher. As an alternative to the print edition, the author has a free-for-educational-use electronic version last dated March 28, 2013 (Update 3.2.0.10) available at his website: http://people.cs.vt.edu/~shaffer/Book/.


Prerequisites

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


Purpose

Catalog description:

CPTR 318. Data Structures and Algorithms 3 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.

Successful students in this course will

  1. be able use and implement the most common data structures
  2. be able to analyze algorithms mathematically
  3. be able to select appropriate algorithms to solve a variety of problems subject to time and space constraints
  4. understand a wide variety of classic algorithms
  5. become more proficient using the C++ programming language


Class Requirements and Grading

Class Work. The following class activities, weighted as indicated, determine the student's overall average for the course.

Activity Weight
Assignments 20%
Worksheets 20%
Quizzes 20%
Midterm Examination 20%
Final Examination 20%

Grade Distribution. The overall average determines the course grade according to the following table:

Overall Average
(avg)
Letter
Grade
92 ≤ avg A
90 ≤ avg < 92   A–
88 ≤ avg < 90   B+
82 ≤ avg < 88 B
80 ≤ avg < 82   B–
78 ≤ avg < 80   C+
70 ≤ avg < 78 C
60 ≤ avg < 70   C–
58 ≤ avg < 60   D+
52 ≤ avg < 58 D
50 ≤ avg < 52  D–
avg < 50 F

Remarks

Programming Experience. CPTR 318 assumes students have at least a basic knowledge of the C++ programming language. Many students will not have had a course involving C++ in almost a year. Please review the material at The C++ Language Tutorial website to brush up on your C++ skills. This site also has a downloadable PDF version of its C++ tutorial. A working knowledge of the content of this tutorial website is sufficient preparation for any of the programming assignments in this course.

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.

Unless directed otherwise, all assignments must represent individual effort. Working with others, whether they be classmates or not, is not acceptable. See the note below on ethics. Your code will be compiled and checked for correctness and completeness. You may elect to work in any environment and upon any platform (for example, Linux, Microsoft Windows, Mac OS X), but your submitted code must compile and run correctly under the Visual C++ compiler on the Microsoft Visual Studio 2015 Community Edition platform.

Quizzes. Daily quizzes encourage students to remain current in their class preparation. Usually quizzes will be distributed at the beginning of the class period and take about five minutes to complete. Missed quizzes may not be made up; however, your lowest quiz score 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 25% 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. 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.

The programming assignments are meant to be learning experiences. It is OK to get legitimate help from others. As long as each student develops his or her own logic and code, it is permissible to help each other over occasional rough spots. Legitimate help includes pointing out simple corrections or providing hints about how to structure a solution. Explaining to a classmate how a particular C++ language feature works independent of its use within their program is always permissible and welcome. Helping to extinguish a particularly puzzling compiler error also is acceptable behavior.

INAPPROPRIATE help includes I do not know what you are doing, but here, look at my function, this is how I did it. Or, even worse, Ill send you my code so you can see how I did it. Providing clues or hints to nudge in the right direction is much more beneficial to learning.

It obviously is bad if you submit someone elses work as your own, but, as is common in academic settings, knowingly enabling the opportunity for someone else to copy your work also is bad.

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 score of 0 on the assignment and a grade of F in the course.

All incidents of academic dishonesty will be reported to the Associate Vice-president of Academic Affairs.

Please take care as you are providing help to others. It IS OK to help others, and you SHOULD help others as you can, but giving others your code or doing their work for them is not really the help they need.

If you have any questions or concerns about this matter, please do not hesitate to ask the instructor for clarification.

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, and 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 students who prefer to pursue on their computers activities that are unrelated to the current class should 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.

It is important that you check your southern.edu email account frequently (at least daily, if possible) so you you do not miss potentially important information about this course. Please use use your southern.edu email account when contacting the instructor; if you use a non-Southern account, your message may not make it through the University's spam filter. Additionally, messages sent from a non-Southern email account introduce uncertainty about the actual identity of the sender.

Disability Suport Services. In keeping with university policy, any student with a disability who needs academic accommodations should call Disability Support Services at 423-236-2574 or visit Lynn Wood Hall, room 137, 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 might not complete the process in time to receive accommodations for that semester.) Legally, no retroactive accommodations can be provided. For more details, visit the Disability Support Services website at http://www.southern.edu/disabilitysupport. Accommodations for disabilities are available only as recommended by Disability Support Services. Students whose accommodations are approved will be provided confidential letters which students should review and discuss with their professors in relation to particular course requirements.


Topics

Topic Textbook Section
Introduction to data structures/C++ review 1.1-1.2
Mathematical preliminaries: sets, relations, logarithms, summations 2.1-2.4
Recurrences and recursion 2.4-2.5
Proof techniques: direct, contradiction, induction 2.6
Introduction to algorithm analysis 3.1-3.3
Asymptotic analysis 3.4-3.10
Empirical analysis 3.11
Linked lists 4.1
Stacks, queues, and deques 4.2-4.3
Binary trees 5.1-3
Binary search trees 5.4
Heaps and priority queues 5.5
Huffman trees 5.6
n-ary trees 6.1-6.3
Θ(n2) sorts: insertion sort, bubble sort, selection sort 7.1-7.3
Θ(n log(n)) sorts: mergesort, quicksort, heapsort 7.3-7.6
Set representations 9.3
Hashing 9.4
Graphs: representations, implementations, traversals (DFS, BFS) 11.1-11.3
Graphs algorithms: shortest path, minimal spanning trees 11.4-11.5
AVL trees, red-black trees 13.1-13.2
Analysis techniques: summations, recurrences 14.1-14.2
Amortized analysis 14.3
Dynamic programming 16.1
Randomized algorithms: skip lists 16.2
NP-completeness 17.1-17.2
Undecidability 17.3


Important Dates

  • Monday, January 9: first day of class for CPTR 318
  • Monday, January 16: no class (MLK Jr./Community Service Day)
  • Wednesday, February 22: Midterm exam
  • Friday, March 3–Friday, March 10: no classes (midterm break)
  • Thursday, March 23: Last day to drop a class
  • Monday, May 1 at noon: final exam (note day and time)


Class Code

Code we develop in class is available at https://github.com/halterman/318_W17