CPSC 327 Course Information

At the heart of computer science is the development of efficient algorithms for solving problems. This course focuses on the design and analysis of data structures and algorithms, continuing the study of data structures begun in CPSC 225 with a focus on more advanced structures (hashtables, heaps, balanced binary trees, graphs, and building your own data structure for a particular application), common algorithmic approaches (iterative, recursive, divide-and-conquer, greedy, backtracking, branch-and-bound, dynamic programming), and covering topics such as correctness, efficiency, complexity, and NP-completeness.

The course has three main goals (and several subgoals):

• developing the skill of analyzing a problem and creating an efficient and provably correct solution to that problem, which includes:
  • gaining a working knowledge of algorithmic efficiency, to inform the algorithm- and program-design process by providing a basis for comparing solutions and defining good solutions
  • developing a toolbox of known data structures and algorithmic strategies which can be used to solve many common problems
  • developing the knowledge of how to think about algorithms and data structures, for when a "canned" data structure or algorithm might not be sufficient
• fostering an appreciation for the practical value of studying algorithms and data structures
• developing other skills useful in computer science: abstract thinking, comfort with the idea of tradeoffs, and a habit of critical reflection

By the end of the course, the successful student should be able to:

• describe and discuss different ways in which the efficiency of an algorithm can be determined
• define big-Oh notation
• discuss the pros and cons of asymptotic measures (big-Oh) and experimental measures of algorithm efficiency
• define the difference between best case, worst case, and average case running time/space
• determine the (best, worst, average) running time/space of an iterative or recursive algorithm
• arrange algorithms from fast to slow based on their asymptotic running times

• define: iterative algorithm, recursive algorithm, divide-and-conquer, greedy, recursive backtracking, branch-and-bound, dynamic programming
• give examples of algorithms utilizing each approach
• for each approach, identify the problem characteristics that make that approach suitable (or not suitable)
• identify the steps for developing algorithms of each type
• develop algorithms for a new problem using suitable approach(es)
• convincingly justify the correctness of the resulting algorithm

• identify the key properties and typical operations of common ADTs for collections, sorting, and lookup
• give examples of applications of each ADT
• match the needs of the problem to an appropriate ADT
• compare and contrast the time- and space-efficiency of different implementations of ADTs and discuss situations in which each implementation is most appropriate
• define and implement basic graph algorithms (e.g. depth-first search, breadth-first search, topological sort, shortest path), determine their running times, and discuss their applications

• define P, NP, NP-hard, and NP-complete and give examples of relevant problems
• describe several important NP-complete problems (e.g. 3SAT, vertex cover, clique, knapsack, TSP)
• discuss and apply algorithmic strategies (e.g. backtracking, branch-and-bound) for dealing with NP-complete problems

CPSC 225 is required.
This course builds directly on the material in CPSC 225 (and 124): programming in Java, fundamental program constructs such as loops and conditionals, basic abstract data types (lists, stacks, queues, and binary trees), how those data types are implemented (using arrays, linked lists, and other linked structures), and recursion.

CPSC 229 is helpful, but not essential.
The most relevant topics from 229 are the idea of a formal mathematical proof, and specific proof techniques such as induction and proof by contradiction. The topics of Turing machines and computability will also make an appearance. While prior exposure to this material is helpful, no knowledge is assumed and all of these topics will be introduced as needed.

Readings and Class Prep: Readings are the first introduction for most material — it often takes more than one encounter to fully absorb something, and class time is more effective if it can be used to fill in the gaps and answer questions about things you have already started to think about. Class prep assignments have a few questions or contain a short exercise to help you self-assess what concepts you understand from the reading and identify what needs further attention.

Homework and Programming Assignments: Hands-on practice is essential for learning and mastery, and homework problems provide an opportunity to tackle problems for yourself. Most homework will involve written solutions, but there will also be a few programming assignments.

Exams and Interviews: Exams and interviews assess what you, individually, have mastered. There will be three midterm exams in the first half of the semester covering core skills and "toolbox elements" — analysis of algorithms, ADTs and data structures, and graphs and graph algorithms — and a final exam covering the design and development of data structures and algorithms. There will also be interviews following each of the programming assignments and for one "design problem" homework. The dates of the exams and the approximate dates of the programming assignments and design problem are on the schedule page. More details about each exam and the format of interviews will be announced prior to the exam/first interview.

Final Grades: There are two components to the final course grade: engagement (30%) and mastery (70%). Engagement covers your active participation in the learning activities of the course: attendance (10%), class prep assignments (10%), homeworks (50%), and programming assignments (30%). Mastery reflects your mastery of competency areas based on the course learning objectives as demonstrated by exams and interviews.

Grading:

• Attendance: Missing three or fewer classes is needed for full credit. Missing more than six classes will result in a lower than passing grade for attendance.

• Class prep: Graded based on completion. A few 0s will be dropped.

• Homeworks and programming assignments: Graded on a 10-point scale based on effort and achievement:

  • 11-12 points — goes above and beyond (includes optional elements or extra credit)
  • 10 points — solution is complete and correct, or largely so; program meets or largely meets the specifications
  • 7 points — solution/program is generally on the right track but falls a bit short (incomplete and/or some flaws/bugs)
  • 3 points — some effort but solution/program falls well short (very incomplete and/or major flaws/bugs)
  • 0-1 point — generative AI and/or other resources used as a learning cheat

  Most assignments that earn 3 or more points on the initial handin can be revised and resubmitted once. The grade for the revised version will replace the original grade and, because understanding and correcting mistakes is a valuable part of learning, an additional point will be earned for a substantive revision effort.

• Exams and interviews: Mastery is graded on the following scale:

  • Outstanding (100): surpasses the learning objective; demonstrates a thorough, deep, and nuanced understanding of the concepts; few to no errors
  • Proficient (90): fully meets the learning objective; demonstrates a solid and consistent understanding; few errors
  • Satisfactory (70): adequately meets the learning objective; demonstrates a basic understanding, though gaps may exist; work is functional but may lack depth or attention to detail
  • Unsatisfactory (45): partially meets the learning objective; demonstrates limited understanding with noticeable gaps or errors; requires significant revision to meet expectations
  • Insufficient (20): fails to meet the learning objective; demonstrates little to no understanding of the material; work is incomplete and/or contains major errors
  • Not applicable (0): no evidence (work not handed in or no answer)

  For a particular competency/skill, the top half (rounded up) of the scores will be averaged. "Satisfactory" (70) or higher is required for a passing grade on a particular competency. In addition, a passing grade for mastery as a whole is required to pass the course regardless of the engagement grade.

You are expected to attend all scheduled class meetings (3 hours per week) and interviews (approx 1-2 hours total over the course of the semester), as well as some office hours and/or help sessions (minimum of 3-4 hours over the course of the semester). Interviews will be scheduled at mutually convenient times. If you cannot attend scheduled office hours or help sessions, you can make an appointment to meet at another time.

You will also need to spend additional time outside of class completing assignments and studying. This additional out-of-class time is intended to be approximately 8 hours per week on average, though your experience may vary. However, if you routinely spend much less time, you may not be successfully mastering the material — or you should challenge yourself by tackling some of the extra credit! — and if you routinely spend substantially more time, especially if you feel like you are spinning your wheels and not making progress, you should visit office hours for help.

Textbook

The Algorithm Design Manual (3rd ed)
Steven S Skiena
Springer, 2020
ISBN 978-3030542559 (hardcover), 978-3030542580 (softcover), 978-3030542566 (ebook)

This is both a textbook for learning how to design algorithms and data structures, and a useful reference with an extensive catalog of algorithmic problems that arise in practice. I hope that you will enjoy reading the book during the course and that you will want to hang on to the book afterwards to use in your future algorithmic endeavors.

If you are buying the book on Amazon or elsewhere, note that the third edition has a very similar-looking cover to the second edition. Look for "Third Edition" on the cover and/or check the ISBN to make sure you are getting the right version.

Additional material will be handed out or posted on the course webpage.

Software

There will be several programming assignments which involve programming in Java. The tools that you need (Java, JavaFX, Eclipse) are available on the lab computers in Rosenberg 009 (reboot them to Linux) and Lansing 310 and via the Linux virtual desktop.

Using the Linux virtual desktop for remote access to Linux is recommended, but if you want to set up your own computer as an alternative to using the Linux VDI, you will need Java, JavaFX, Eclipse, and a file transfer program (FileZilla) to copy files between your computer and the Linux filesystem.

Information on how to set up your own computer will be provided in advance of the first programming assignment.

last updated: --Thu Jan 30 07:50:52 EST 2025--
page owned by: bridgeman@hws.edu