Course Information
- Instructor: Dr. Aaron Garrett (garrettal@wofford.edu)
- Class Meeting (Olin 218): MWF 2:00p-2:50p
- Office Hours (Olin 111A): MWF 3:00p-5:00p; TR 12:30p-2:30p; or by appointment
- Textbook: None
- Final Exam: See the Registrar’s page
Catalog Description
A study of the design and analysis of algorithms for solving problems, including dynamic programming, divide-and-conquer algorithms, greedy algorithms, graph algorithms, and search algorithms. Evaluation of time-space trade-offs.
Prerequisite: (COSC 240 with a minimum grade of D or MATH 260 with a minimum grade of D) and COSC 350 with a minimum grade of C.
Goals
- Understand algorithm strategies, including brute-force, greedy, divide and conquer, dynamic programming, randomized, branch-and-bound, and recursive backtracking.
- Solve problems by applying suitable strategies.
- Know standard graph algorithms, including those to find the shortest path and a spanning tree.
- Write programs in C++.
- Use components of the C++ Standard Template Library (STL) based on reading API documentation.
- Understand the concepts of encapsulation, inheritance, and polymorphism in the context of C++.
- Understand the concepts of template and operator overloading in the context of C++.
Grades
Your grade in the course will be based on a combination of assignments and exams.
- Assignments
- Assignments are short exercises that reinforce the core concepts.
- Exams
- Exams are timed assessments of conceptual understanding.
| Artifact | Points |
|---|---|
| Assignments (~4) | 200 |
| Exam 1 | 250 |
| Exam 2 | 250 |
| Final Exam | 300 |
| Total | 1000 |
The usual grading scale will be applied to the accumulated points: 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.
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.
Generative AI Policy
Generative AI is NOT allowed in this course. This course is foundational, emphasizing the development of essential skills such as writing and understanding code, as well as enhancing analytical and critical thinking abilities. To achieve the learning outcomes, all assignments must be completed individually by the student. Generative AI is a powerful tool, but it should be used by individuals with a solid understanding of the domain it is applied to. This course is designed to build that foundational knowledge, ensuring you have the skills needed to effectively use such tools in your future career. Therefore, the use of generative AI for any part of your work in this course is strictly prohibited. Any AI-generated content submitted as part of your assignments will be treated as plagiarism and a violation of the Honor Code.
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
| Week | Topics | Deadline |
|---|---|---|
| 1 | C++ review, functions, pass-by, recursion, structs, classes | |
| 2 | memory, arrays, linked structures, lists, stacks, queues, trees, BSTs | |
| 3 | priority queues, heaps, maps, graphs | |
| 4 | balanced search trees | A1 |
| 5 | Exam 1 | |
| 6 | algorithm analysis, recursive algorithm analysis | |
| 7 | problem types, brute force | A2 |
| 8 | decrease and conquer | |
| 9 | divide and conquer | |
| 10 | transform and conquer | A3 |
| 11 | Exam 2 | |
| 12 | space-time tradeoff | |
| 13 | dynamic programming | |
| 14 | greedy technique | A4 |
Note: This syllabus is subject to change with notice.