Home CPSC 340

CPSC 340: Data Structures and Algorithms

Meeting Times:Section 1: Monday and Wednesday, 9:00 – 10:50, Trinkle B52
Section 2: Monday and Wednesday, 1:00 – 2:50, Trinkle B52.
Prerequisite:CPSC 125A, CPSC 225, and a grade of C or better in CPSC 240.
Instructor:Ian Finlayson
Office:Trinkle B18
Office Phone:540-654-1714
Office Hours:Tuesday & Thursday 9 – 12, or by appointment.

Course Description

Continued study of data modeling and incorporation of abstract data types including linked lists, stacks, queues, heaps, trees, and graphs. Study of advanced sorting and searching techniques. Provides experience in the use of algorithm analysis. Continued study of program design, coding, debugging, testing, and documentation in an object-oriented higher level language.

Course Goals & Objectives

Grading Policy

Your grade will be determined as follows: The grading scale used for this course is as follows:

There is a 10% per day late penalty on assignments that are not turned in on time. Final grades will not be rounded up, and no extra credit opportunities will be given on an individual basis.

Lab assignments are always due by midnight of the day following the lab. So Monday lab assignments are due by midnight on Tuesday, and Wednesday labs are due by midnight on Thursday.

This course is focused on building data structures and writing algorithms ourselves. As such, use of any data structures libraries in C++, such as the STL, is not allowed. Including any of the files in your program will result in points being deducted: string, sstream, algorithm, vector, deque, list, stack, queue, priority_queue, set, map.

The University provides the opportunity to provide grading feedback midway through the semester. This will take into account your score on the mid-term exam and the programming projects and lab exercises submitted up to that point. Any student receiving less than a 65% on either of these will receive a "U" for their mid-semester grade. If this happens to you, please don't hesitate to talk with me about how we can improve your performance in this class.

Student Conduct

Honor Policy

Students are expected to conduct themselves in a manner consistent with the letter and spirit of the UMW Honor Constitution, as well as the CPSC department honor policy. For this class in particular:

For labs, collaboration is OK. The goal of the labs is to ensure you understand the concepts we are going over.

For projects, you may discuss the ideas with other students, but all of your work must be your own. You must yourself write and understand everything in each assignment you submit. It is an honor code violation to copy directly from another student either by copy and paste or by transcription, or to copy from the web.

For exams, you can not talk to anyone during the exam, or use any kind of notes.

If you have any questions or need clarification, please don't hesitate to contact me!

Disability Statement

The Office of Disability Services has been designated by the University as the primary office to guide, counsel, and assist students with disabilities. If you already receive services through the Office of Disability Services and require accommodations for this class, make an appointment with me as soon as possible to discuss your approved accommodations needs. Please bring your accommodation letter with you to the appointment. I will hold any information you share with me in the strictest confidence unless you give me permission to do otherwise. If you have not contacted the Office of Disability Services and need accommodations, I will be happy to refer you. The office will require appropriate documentation of disability. Their phone number is 540-654-1266. The office is located in Lee Hall, Room 401.

Tentative Schedule

Date Class Topic Lab Topic Assignment Due
January 18 Course Overview, Introduction to C++ Compiling C++ Programs  
January 23 More C++ Programming No Lab  
January 25 Files, Strings and Pointers Palindrome Checker  
January 30 Dynamic Memory Dynamic Memory Exercise  
February 1 Operator Overloading Operator Overloading Exercise  
February 6 Building a string class No Lab Grayscale Converter
February 8 Dynamic Memory ContinuedDebugging  
February 13 Linked Lists Linked List Exercise  
February 15 Linked Lists Continued No Lab  
February 20 Doubly Linked Lists Valgrind  
February 22 Using Multiple Files Makefiles Big Ints
February 27 Stacks, Midterm Review Stack Exercise  
March 1 Midterm Exam  
March 3 (Friday)Play List
March 6 Spring Break
March 8 Spring Break
March 13 Templates Template Exercise  
March 15 Algorithm Analysis Analysis Exercise  
March 20 Queues No Lab Calculator
March 22 Recursion Recursion Exercise  
March 27 Recursion Continued Recursive Powers Exercise  
March 29 Searching & Sorting No Lab  
April 3 Class Cancelled  
April 5 Binary Search Trees No Lab Bank Simulation
April 10 Binary Search Trees Continued Binary Tree Exercise  
April 12 Hash Tables Hash Table Exercise  
April 17 Graphs Graph Exercise  
April 19 Graphs Continued No Lab Spell checker
April 24 Heaps No Lab  
April 26 Huffman Coding, Final Review No Lab  
April 28 (Friday)Scheduler
May 1 Section 1 Final Exam, 8:30 - 11:00
May 3 Section 2 Final Exam, 12:00 - 2:30

Copyright © 2018 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.