Course Overview

CS 315 is an introduction to Data Structures. The topics include the study of Abstract Data Types, Binary-Search Trees, Balanced Trees, Heaps, Skip Lists, and Hash Tables. The following is a list of more specific data structures that are covered in this course.

  1. Vector- and linked-list-based (singly and doubly linked-lists) implementation of Dictionary operations.

  2. Binary trees and Binary-Search trees.

  3. AVL and 2-3 balanced trees and an overview of splay trees.

  4. Heap-ordered trees and Binomial Queues.

  5. Skip Lists.

  6. Hash Tables, with Linear and Double Probing and Chaining.

You are expected to be familiar with the vector- and linear linked-list-based data structures from either CS 215 or its equivalent. In this course, we will overview those topics.

In addition to the data structures, we will discuss abstract data types and the use of C++ classes to implement them; recursion; time complexity of different algorithms and how the choice of data structures could influence that.

Programming will be done in C++; important language features such as inheritance and polymorphism will be discussed.

Textbook

Required: Data Abstraction & Problem Solving with C++: Walls and Mirrors, 7th Edition, Frank M. Carrano and Timothy Henry, Pearson Publishing, ISBN-13: 9780134478401.

Optional: A Tour of C++, Bjarne Stroustrup, ISBN 978-0321958310, 2013, Addison-Wesley

Optional: Programming: Principles and Practice using C++, Bjarne Stroustrup, ISBN: 978-0-321-99278-9, 2nd Edition, Addison-Wesley 2014

Prerequisites

Programming II (CS 215) and Discrete Structures for CS (CS 242), with a grade of C- or better in each course.

Students who have not acquired a strong foundation in the fundamentals of programming are encouraged to retake CS 215 or its equivalent before taking this class.

Important Dates
Midterm Exam 1 Wednesday, March 1
Midterm Exam 2 Wednesday, April 12
Final Exam Monday, May 15, 11:00 AM -- 12:50 PM
Lecture

The proposed outline of what is to be covered appears in the course schedule. This page will be updated regularly. So, please check it often. You are required to attend all lectures and labs, and to read the relevant sections of the text prior to lecture, and the relevant online documentation prior to lab. Attending lectures and labs is extremely important to your success in this course. You may not use any electronic devices during the lectures or the exams.

Labs

Labs are designed to have you implement programs that are either based on the topics of lectures or complement what you learn in the lectures. They are extremely important to your understanding of the course material and to your ability to write solutions to projects. You might not always be able to finish your lab during the lab hours. In that case, you should make sure to learn the concepts in the lab so that you can complete the lab on your own. Read the labs very carefully and answer the questions that are posed before moving on. Please follow the instructions that are provided to you under Programming Projects when submitting your solutions to lab assignments.

Programming Projects

There will be four or five programming projects in C++. You may work at home with any C++ environment, but your completed work must be submitted ready to run on our blue.cs server. Do not submit any lab or project solutions unless you have made sure that it compiles and runs on blue.cs first.

Your submitted work must consist of a single directory which contains a makefile and all source files that are needed to build an executable, any data files needed to run the program, and any documentation that resides in a separate file.

Every project (or lab) that you submit for grading should include a README.txt file that contains the following contents.

The makefile must have a default target which compiles any (all) executable(s) that is (are) required for the assignment (i.e. if you type just "make"), a target which runs the executable (i.e. assuming there is only one executable, typing "make run" should run it), and a target which removes any files that were created by the compilation (i.e. typing "make clean" should remove any object files and executable leaving only the files you need to rebuild the final executable). In other words, we want to be able to type "make" and then "make run" and run your solution.

You should tar the directory that contains your solution and submit it. For example, here is how you should prepare your solution to project 1 for submission.

tar cf project1.tar project1

or 

tar czf project1.tgz project1

You will then submit either project1.tar or project1.tgz. The assumption is that all files that are required to build your project 1 on blue.cs are in project1 directory. We should be able to run the following commands to test your program.

tar xf project1.tar  # or tar xzf project1.tgz
cd project1          # the tar file creates directory, project1
make                 # make the executable
make run             # run the (single) executable. 

On the projects page, there will be a link to a form that will allow you to submit your file(s). This form will ask you for a user-name and password and the tag-name of the assignment. We will provide the user-names and passwords to you during the lab. They will be different than your MySSU or blue.cs user-names and passwords. In general, your user-name will be your last-name followed by your first-name. Your submission will be logged under your name with a complete time-stamps of the time that it was submitted. The due date and time are based on the blue.cs's local time when you submit your solution. If you resubmit a file it will not overwrite any previous submissions. However, unless you tell us otherwise, we will grade the last submission that is before the due date of the assignment.

No work will be accepted late without a compelling explanation. If you have not completed your assignment by the time it is due, you may turn in what you have completed for partial credit. In order to give you partial credit, we will follow the instruction that you provide in your README.txt. Please note that a partially working submission will get a small percentage of the points that is assigned to the project or the lab. For example, a submission that implements about 75 percentage of the assignment and can be tested to demonstrate that, will get at most 30 percent of the maximum points for the assignment. A program that doesn't compile will get zero points regardless of whether it perfectly compiles on a system other than blue.cs or it has syntax errors.

Slip days: In order to account for the unexpected, you can use two slip days for your projects. That is, you can turn in one project late by two days (exactly 48 hours after the due date) or two projects late by one day each (exactly 24 hours after the due date). Do not use your slip days early on. As you might expect, the projects get more complex as the semester progresses.

Quizzes

Approximately 6-8 pop quizzes will be given during the semester. Note: pop quizzes will be given at the beginning of the class. You will forfeit the entire 10% of your semester grade for this category if you were to miss more than one of them. If you come to class late and a quiz is in progress, you will be given one only if no quizzes have been turned in yet. After the first quiz has been turned in, you will not be given the opportunity to take that quiz.

Midterms and Final Exam

There will be two midterm exams and a final exam. All exams are closed book. Exams cover the material from the textbook, lectures, projects, and labs. Specifically, you are responsible for all the material covered in the lecture and labs regardless of whether they appear in the textbook or not. Only with a compelling reason that can be documented you may make up a missed exam.

The final exam will be comprehensive.

Grading
Projects 35%
Labs 20%
Quizzes 10%
Midterms 20%
Final Exam 15%

You must separately pass the exams (2 midterms and the final, combined and normalized), the labs, and the programming projects with a grade of C- or better to make a grade of C- or better in the course.

A- 90 A 93
B- 80 B 83 B+ 87
C- 70 C 73 C+ 77
D- 60 D 63 D+ 67
Policy on Collaboration
You are encouraged to discuss course material with other students. Don't be shy about consulting with anyone, but please understand that you, and only you, bear the responsibility for solving the problems associated with producing a successful project or solving a homework assignment. Please keep the following in mind.

For the details of University policies regarding add and drop, cheating and plagiarism, grade appeal, access to programs for students with disability, and diversity statement, refer to Important Policies and Procedures for Students web-site.

CS majors must take this course for a letter grade. University and Computer Science Department guidelines regarding the grade of Incomplete will be strictly adhered to. Incomplete grades will only be given for circumstances beyond a student's control; inability to keep up with the work due to an excessive course load, for example, is insufficient to warrant an Incomplete.