Course Information
- Instructor: Dr. Aaron Garrett (garrettal@wofford.edu)
- Class Meeting (Olin 218): MWF 10:30a-11:20p
- Office Hours (Olin 204E): MW 2:00p-4:30p; TR 1:00p-3:30p; or by appointment
- Textbook: C++ Programming by D. S. Malik
- Required Software Mimir Classroom (available in bookstore)
- Final Exam: 13 May 2019 from 2:00p-5:00p
Catalog Description
An introduction to the formal study of data structures, such as arrays, stacks, queues, lists, and trees, along with algorithm design and analysis of efficiency.
Prerequisite: COSC 235 with a minimum grade of C.
Goals
- Understand abstraction and how it helps to control complexity
- Understand the concept of an abstract data type (ADT) and how to implement custom ADTs
- Understand how to use and implement common CS data structures
- Understand how memory is managed within a C++ program
- Understand how to use arrays, structures, and pointers to implement ADTs
- Understand tradeoffs among various implementations for a given interface
- Understand recursion and be able to use it to solve problems
- Understand the concepts of algorithmic complexity and “Big O” notation
- Be able to determine the time complexity of an algorithm
- Be familiar with commonly used algorithms for interacting with data structures
- Be able to implement ADTs in C++
- Be proficient with the C++ programming language
Grades
Your grade in the course will be based on a combination of assignments, projects, and exams.
- Assignments
- Assignments are short exercises that reinforce the core concepts.
- Projects
- Projects are more complex problems that require a combination of concepts.
- Exams
- Exams are timed assessments of conceptual understanding.
- Labs
- Labs are ungraded (but recommended) practice with the course material.
| Artifact | Points |
|---|---|
| Assignments (~10) | 200 |
| Projects (~4) | 400 |
| Midterm Exam | 200 |
| Final Exam | 200 |
| Total | 1000 |
The usual grading scale will be applied to the accumulated percentage: 93–100: A, 90–92: A-, 87–89: B+, 83–86: B, 80–82: B-, 77–79: C+, 73–76: C, 70–72: C-, 60–69: D, 0–59: F.
Policies
Attendance
You are expected to attend class meetings and come to class prepared. That includes having completed assigned readings, problem sets, and tutorials.
You are expected to dedicate your attention to what is going on in class and to participate fully in classroom activities, including discussions. No laptops or tablets are to be used in class unless being used for a classroom exercise. (Notes may be taken using a device if needed as an approved accommodation.)
Refer to the General Policy Regarding Attendance in the Wofford College Student Handbook. The policy makes you responsible for catching up on missed classes. If you must be absent for class, please email me in advance to let me know.
Make-up exams are not available. If you have a legitimate, excused absence during the midterm exam, then you must make it up during the final exam period.
Assignment Deadlines
Late assignments will not be accepted without a legitimate excuse. All assignments are expected to be submitted by 11:55p ET on the posted deadline.
Academic Integrity
The Honor Code requires faculty, staff, and students to maintain a high standard of individual honor and integrity. While I may specify some assignments as collaborative, work represented as your own must be your own. If you have any doubt about what is appropriate for a given assignment, you should contact me for clarification.
Accommodations
If you have a disability that requires assistance or accommodation, or if you have questions related to any accommodations for testing, note takers, readers, etc., please contact Dean Beth Wallace by telephone at (864) 597-4371 or in person by visiting the Hugh R. Black Infirmary. You must arrange accommodations during the first week of classes.
Tentative Schedule
Generally, assignments are due on Wednesdays and projects are due on Fridays.
| Meeting | Topics | Textbook | Deadline |
|---|---|---|---|
| 04 Feb | preprocessor, compiler | pp. 9–20 | |
| 06 Feb | data types, main function | pp. 27–43, 80–92 | A00 |
| 08 Feb | I/O | pp. 123–136, 160–164 | |
| 11 Feb | control structures | pp. 187–205, 269–283, 297–305 | |
| 13 Feb | functions | pp. 347–384 | A01 |
| 15 Feb | functions (parameter passing) | pp. 384–403, 415–420 | |
| 18 Feb | enumerations, strings | pp. 468–478 | |
| 20 Feb | arrays | pp. 523–544 | A02 |
| 22 Feb | searching | pp. 544–547 | P01 |
| 25 Feb | sorting | pp. 547–551 | |
| 27 Feb | structs | pp. 611–628 | A03 |
| 01 Mar | SIGCSE - NO CLASS MEETING | pp. 651–671 | |
| 04 Mar | classes | pp. 671–691 | |
| 06 Mar | memory management | pp. 817–826 | A04 |
| 08 Mar | pointers | pp. 829–837 | |
| 11 Mar | pointers | pp. 837–847 | |
| 13 Mar | classes with dynamic memory | pp. 847–858 | A05 |
| 15 Mar | Midterm Exam review | P02 | |
| 18 Mar | Midterm Exam | Midterm | |
| 20 Mar | Midterm Exam | Midterm | |
| 22 Mar | algorithm analysis | ||
| 25 Mar | recursion | pp. 1035–1051 | |
| 27 Mar | sorting revisited | pp. 1069–1083 | |
| 29 Mar | linked lists | pp. 1115–1129 | |
| 08 Apr | linked lists | ||
| 10 Apr | ADTs | A06 | |
| 12 Apr | ADTs | ||
| 15 Apr | List ADT (unordered) | pp. 1129–1150 | |
| 17 Apr | List ADT (ordered) | pp. 1150–1161 | A07 |
| 19 Apr | Stack ADT | pp. 1210–1245 | P03 |
| 22 Apr | Queue ADT | pp. 1259–1277 | |
| 24 Apr | tree terminology | A08 | |
| 26 Apr | Binary Search Tree ADT | ||
| 29 Apr | Heap ADT | ||
| 01 May | Map ADT | A09 | |
| 03 May | Graph ADT | P04 | |
| 06 May | |||
| 08 May | A10 | ||
| 10 May | Final Exam review |
Note: This syllabus is subject to change with notice.