Comp 220: Data Structures, Fall 2018

This syllabus is subject to change based on specific class needs, especially the schedule. Significant deviations will be discussed in class.

Logistics

Content

Data structures continues the study of abstraction and programming through a focused study of data structures, algorithms, and abstract data types. The primary focus of this course is the design and development of algorithms and programs using data abstraction and information hiding via abstract data types ADTs. Data abstraction is absolutely fundamental to good programming practice and the management of large scale problems and data sets. This course is designed to round out a student’s understanding of basic computer science concepts while strengthening the program design and development skills through continued use of a test-driven design methodology.

It is imperative that programmers and program designers be able to determine which of the many solutions available is the best for their specific task. Throughout the course, students will focus on to making solid quantitative and qualitative judgments about program efficiency and overall program design choices. Gone are the days when “it works” is a good enough assessment for the quality of a program.

Students will explore the ideas and concepts brought up in class and homework assignments during the weekly lab session. In addition to hands on exercises, lab sessions will be used to explore current, relevant research in computer science.

Topics

We will focus on chapter 5 and beyond from the text. This includes, but is not limited to:

Sources

The course textbook will be:

Other sources will be posted on this webpage as needed.

Programming Environment

This course utilizes the Code::Blocks IDE and the GNU compiler for C++ development.

All programs written in this course are required to compile and run on a server running Ubuntu 18.04.1. All students will have access to the departmental server and thereby the above development tools. While development is not required in this environment, failure to properly port a program to the required environment could result in your program not compiling correctly at the time of grading. Further, I may not be able to provide support for installing and using other development environments. All software for this course is available free of charge and can be found on the web if students wish to install it on their personal machines.

Policies

Assessment

Assignments

The course workload is as follows:

Category Number Of Assignments
Labs 10
Homework 8–10
Projects 2
Exams 6–7

Homework assignments will always either precede a lab to prepare for it or follow a lab to complete it. Students are also encouraged to look at the textbook’s review questions, since the solutions are available online. There will be no dedicated midterm or final exam, but 7 exams spaced throughout the semester. Each exam will focus primarily, but not necessarily exclusively, on the material covered since the previous exam. The final exam will include a small number of cumulative questions, and I reserve the right to include at most one cumulative question on each of the other exams. Your lowest non-final exam score will be dropped.

Workload

The weekly workload for this course will vary by student but on average should be about 13 hours per week. The follow tables provides a rough estimate of the distribution of this time over different course components for a 16 week semester.

Category Total Time Time/Week (Hours)
Lectures+Labs   4
Homework 48 3
Exam Study 16 1
Projects 48 3
Reading+Unstructured Study   2
    13

Grading

Lab and homework assignments are graded on a simple 3 point scale. Grades are marked with, in decreasing order, a check-plus, check, or check-minus. Your final grade for these two assignment categories is then based off the respective averages and determined by the following chart. Notice this chart lists the minimum average needed to achieve a particular letter grade.

Assignment Avg. (min) Letter Grade
2.8 A
2.75 A-
2.5 B+
2.25 B
2 B-
1.75 C+
1.5 C
1 C-
0.75 D
0.5 F

Your final grade is based on a weighted average of particular assignment categories. You can estimate your current grade based on your scores and these weights. You may always visit the instructor outside of class to discuss your current standing.

Category Weight
Exams 40%
Projects 25%
Homework 12.5%
Labs 12.5%
Participation 10%

Your participation grade is based on a variety of activities. During class I will often make sure of the Socrative app, so you’ll need to install this on your phones. Participating in Socrative questions and with in-class group activities is required for a decent participation grade; a full grade also includes asking questions either in class or in office hours.

This courses uses a standard grading scale. Assignments and final grades will not be curved except in rare cases when its deemed necessary by the instructor. Percentage grades translate to letter grades as follows:

Score Grade
94–100 A
90–93 A-
88–89 B+
82–87 B
80–81 B-
78–79 C+
72–77 C
70–71 C-
68–69 D+
62–67 D
60–61 D-
0–59 F

You are always welcome to challenge a grade that you feel is unfair or calculated incorrectly. Mistakes made in your favor will never be corrected to lower your grade. Mistakes made not in your favor will be corrected. Basically, after the initial grading your score can only go up as the result of a challenge.

Schedule

The following tentative calendar should give you a feel for how work is distributed throughout the semester. Assignments and events are listed in the week they are due or when they occur. This calendar is subject to change based on the circumstances of the course.

Date Topic Resources and Assignments
Wed 08/22 Intro, Using VNC and CodeBlocks Review 161 Shell Notes 1 and 2
Thu 08/23 Logarithms and Big O Lab/HW 1 assigned, COMP161 Big O Notes
Fri 08/24 Review C++ Libraries and Google Test COMP161 C++ Notes I, COMP161 C++ Notes II
Mon 08/27 Analyzing Simple Recursion Read Ch. 7
Wed 08/29 Palindromes and Binary Search  
Thu 08/30 Recursion to Iteration HW 1 due, Lab/HW 2 AND HW 3
Fri 08/31 Review  
Mon 09/03 Exam 1 (Solutions)  
Wed 09/05 Structural Recursion and Iteration  
Thu 09/06 Recursion for intToStr HW 2 AND 3 due, Lab 3
Fri 09/07 Analyzing Sorting Read Ch. 10.1-10.2
Mon 09/10 Divide and Conquer Sorting (Mergesort) Read 10.3-10.4, Sorting Visualizations
Wed 09/12 Quicksort Read 10.5-10.6
Thu 09/13 Tracing Sorting and Searching Lab/HW 4 (Solutions)
Fri 09/14 Continuing Tracing Lab  
Mon 09/17 Collections: Stacks and Queues Read 5.1-5.3
Wed 09/19 Collections: Maps and Sets  
Thu 09/20 Using Stacks and Queues Lab 5
Fri 09/21 Exam 2 (Solutions) Read 5.4-5.5
Mon 09/24 Traversing Collections Read 5.6
Wed 09/26 Designing Classes Read 6.1
Thu 09/27 Map Inversion Lab 6/HW 5
Fri 09/28 Operator Overloading Read 6.2
Mon 10/01 Rational Class Read 6.3
Wed 10/03 Exam 3 (Solutions)  
Thu 10/04 Stacks Using Vectors Lab/HW 7
Fri 10/05 Handling Input: Tokenizing Read 6.4
Mon 10/08 Debugging Programs Exam 4 (take-home)
Wed 10/10 Exceptions  
(10/11–10/15) (Fall Break) (Fall Break)
Wed 10/17 Memory and Pointers Read 11.1-11.2
Thu 10/18 Reverse Polish Notation Calculator Exam 4 due, Project 1 out
Fri 10/19 Arrays and Pointer Arithmetic Read 11.3-11.4
Mon 10/22 C-style strings  
Wed 10/24 Dynamic Memory and Linked Lists Read 12.1-12.3
Thu 10/25 Free Lab for Project 1  
Fri 10/26 Arrays vs. Linked Lists  
Mon 10/29 (Class Cancelled)  
Wed 10/31 (Class Cancelled) Read 12.4-12.5
Thu 11/01 Linked List Stack (Lab) Lab 8
Fri 11/02 DoubleStack  
Mon 11/05 (Class Cancelled) Exam 5 (take-home)
Wed 11/07 Object Copying Read 12.7
Thu 11/08 Implementing IntVector Lab 9
Fri 11/09 Dynamic Array Analysis Read 12.8
Mon 11/12 Templates Read 14.1-14.2
Wed 11/14 Implementing Queues Read 14.3
Thu 11/15 Big Integers Project 2 out
Fri 11/16 Implementing Vectors Labp2 due, Read 14.4-14.5
Mon 11/19 Exam 6  
(11/21–11/25) (Thanksgiving Break) (Thanksgiving Break)
Mon 11/26 (Class Cancelled) Read 15.1
Wed 11/28 Implementing Maps Read 15.2-15.4
Thu 11/29 Free lab for Project 2  
Fri 11/30   Project 2 Due
Mon 12/03 Binary Search Trees Read 16.1-16.3
Wed 12/05 Balanced Trees, Review  
Fri 12/07 8:00 AM   (Final) Exam 7 (Solutions)

Monmouth College Services