CPSC 225

Data Structures and Algorithms

Spring 2025

CPSC 225 Course Information

On this page:

Course Description and Objectives
Prerequisites
Assignments and Evaluation
Time Expectations
Course Materials


Course Description and Objectives	Catalogue description: This course builds on CPSC 124, covering some of the more advanced fundamentals of programming including basic data structures (such as lists, stacks and queues, binary trees, and hash tables), recursion, common algorithms (such as searching and sorting), and generic programming. This course also looks more deeply at object-oriented programming, including the use of class hierarchies. Currently, the course is taught using the Java programming language. Computer science revolves around programs ‐ creating programs, analyzing programs, making programs more efficient and easier to understand, making it easier to create and maintain programs, considering what programs can and cannot do...the list goes on. The first semester of programming (CPSC 124) is intended to introduce basic programming skills ‐ the syntax and semantics of a particular programming language, and some of the basics of program design. This second semester of programming (CPSC 225) is intended to build a more sophisticated and confident programmer by focusing on skills necessary for the construction of larger, more complex programs. The emphasis on data structures and data organization reflects the importance of managing data in programs ‐ choosing an appropriate data structure for a particular application is important for the program's efficiency and simplicity. This course covers basic data structures (arrays, linked lists, and binary trees) and abstract data types (lists, stacks and queues, priority queues, maps, and sets) as well as some common algorithms (searching and sorting), fundamental algorithmic techniques (recursion), and writing correct and efficient programs. It also takes a deeper look at object-oriented programming. Some additional topics such as GUI programming, client-server programming, streams and files, and threads may be covered as time permits. The course is taught in Java. By the end of the course, the successful student should be able to: describe the tradeoffs in efficiency and memory usage for arrays and linked lists (all variations) correctly implement basic algorithms involving arrays, linked lists, and binary trees (e.g. traversal, insertion, removal) and to work out algorithms for new tasks involving these data structures describe and implement the typical operations for lists, stacks, queues, priority queues, maps, and sets given a particular implementation use the major classes of the Java Collections framework explain what an abstract data type is describe, implement, and discuss the efficiency of common algorithms for searching and sorting understand and implement recursive methods design and implement algorithms involving recursive data structures habitually comment code, including writing pre- and postconditions for every method use assertions and exceptions appropriately habitually include error-detection mechanisms habitually define test cases to thoroughly test components of the program do a close reading of the program's specifications to create a reasonable design for a program (organizing the code into appropriate classes and methods) choose appropriate ADTs and implementations for particular applications, and defend the choices made in terms of suitability and efficiency

Prerequisites	C- or better in CPSC 124, or instructor permission

Assignments and Evaluation	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. Labs: Lab sessions will be held on Thursdays in the Rosenberg 009 computer lab. Labs are an opportunity to explore, practice, and reinforce ideas from class. Some labs may also introduce new material. While it is intended that the majority of each lab assignment will be completed during the lab period, anything not completed during lab must be finished outside of class. Projects: Projects constitute the bulk of the out-of-class work for this course. These assignments provide an opportunity to work on larger, more complex programs and to apply the course material. Exams and Project Interviews: Exams and interviews assess what you, individually, have mastered. There will be two midterm exams and a final exam, and an interview following each project. The midterms will be written exams held during a regular lab period. The dates of these exams are given on the schedule page. The final will be during the assigned final exam timeslot. More details about each exam will be announced prior to the exam. 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%), in-class exercises (10%), class prep assignments (10%), labs (30%), and projects (40%). Mastery reflects your mastery of competency areas based on the course learning objectives as demonstrated by exams and project interviews. Grading: Attendance: Missing three or fewer classes and at most one lab is needed for full credit. Missing more than six classes or more than two labs will result in a lower than passing grade for attendance. In-class exercises: Graded on a 0/-/✔/✔+ scale based on making reasonable progress during class. A few low scores will be dropped. An average of ✔ is needed for full credit. Class prep: Graded based on completion. A few 0s will be dropped. Labs and projects: Graded on a 10-point scale based on effort and achievement: 11-12 points — exceeds specifications (includes extra credit features) 10 points — meets or largely meets the specifications 7 points — falls short of meeting specifications (bugs and/or incomplete) 3 points — some effort but well short of meeting specifications 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. If you are concerned about your grade or are struggling with the material, come to office hours and/or Teaching Fellows to get help! Staying on top of things and seeking help as soon as possible when you need it is the best route to success; the course material is cumulative so falling behind on one topic makes it that much more difficult to catch up.

Time Expectations	You are expected to attend all scheduled class and lab meetings (4.5 hours per week) and project interviews (approx 1-2 hours total over the course of the semester). Interviews will be scheduled at mutually convenient times. You will also need to spend additional time outside of class and lab 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 and/or the Teaching Fellows for help.

Course Materials	Textbook Introduction to Programming Using Java, JavaFX Edition (version 9.0) David Eck The book is freely available online at http://math.hws.edu/javanotes/. You can also download a PDF copy or an ebook if you prefer an electronic version that you can read offline, or order a printed copy if you'd like something you can refer to away from the computer. See the "Downloading And Other Links" section at the bottom of the http://math.hws.edu/javanotes/ page for more information. We will primarily use the second half of the book, so you can order just Part II and access any necessary material from Part I online. Or, if you don't have a copy of Part I from CPSC 124 and would like the whole thing, you can save a few dollars by ordering the whole book instead of the separate parts. Please do not print out chunks of the text on the Math/CS department printers. Laptop If you have a laptop that you are able to bring to class on lecture days, please do so as there will sometimes be in-class activities. (It's OK if you don't have a laptop; in-class activities will be done in small groups so you can team up with someone else.) Software Programming will be done in Java, using the Eclipse IDE. Java, JavaFX, and Eclipse are available on the Linux computers in the Rosenberg 009 and Lansing 310 computer labs 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 accessing Linux, using Eclipse, and setting up your own computer is contained in lab 1 (on the schedule page).