**Algorithms & Data Structures** **Reed College MATH/CSCI 382 Fall 2025**   [Jim Fix][] • [Harper Knittel][]   ![](images/algorithms.gif width="200) ......................... . . . . . . . . . . . . .
# Overview This course is an in-depth study of the design and analysis of algorithms and data structures. We will look at ways of solving combinatorial problems (e.g. sorting, network optimization, string search), and study classic data structures that support their solution. Following the text, we'll emphasize an abstract approach: We give algorithms in pseudocode, we carefully prove their correctness, and we analyze their performance. We'll also be implementing several of our ideas as real executable code. There is an accompanying lab section that will be a mix of problem solving sessions and implementation sessions. There you will often work with a partner or in groups. Prerequisites: : **MATH 112 and 113.** You must be familiar with making mathematical arguments and giving mathematical proofs. **MATH 121 or the equivalent.** You should have basic programming proficiency in a language like Java or Python; you should be familiar with linked data structures and recursion; you should have some familiarity with a few basic sorting algorithms; you may have seen some use of asymptotic ("big Oh") notation. Meeting Times: : **Lecture:** MW 2:40-4:00 in Library 389
**Instructor:** Jim Fix `` **Lab:** F 2:40-4:00 in Library 389
**Instructor:** Harper Knittel `` Office Hours: *until September 19th* : **Jim**: M 11:30-12:30, 4-5; Tu 1-2; W 10-11; Zoom on F 12-1, 4-5
**Harper**: being devised and to be posted soon **Required Text:**
: *Introduction to Algorithms* by Cormen, Leiserson, Rivest, Stein. This is often just called "CLRS" or "The Bible." # Schedule The course consists of two lecture meetings and one lab meeting each week. You will be doing pair and group work during lab, and so your attendance is required. Below we will detail out each meeting's topics week by week as the semester unfolds. Here we will give links to lecture materials and other resources. Under that weekly schedule is our current sense of the semester's schedule of topics. It includes our plan for the three exams. **Week 1**: overview and warm-ups
• **Lecture**: [**line intersection**](lectures/AD-Lec01-1.pdf) • *Reading: CLRS3e 33.2*
• **Lab**: [**bubble sort and inversions**](lab01.html)
**Week 2**: sorting case studies; notation
• **Lecture 1**: [**insertion and merge sort**](lectures/AD-Lec02-1.pdf) • *Reading: CLRS3e 1 & 2*
• **Lecture 2**: [**asymptotic notation**](lectures/AD-Lec02-2.pdf) • *Reading: CLRS3e 3*
• **Lab**: [**funky sort and some cloudy computing**](lab02.html)
• **Homework 01**: [**sorting and asymptotic notation**](homework01.html)
**Week 3**: binary heaps and heapsort
• **Lecture 1**: priority queue ADT; binary heaps *Reading: CLRS3e 6*
• **Lecture 2**: Floyd's method and heapsort
**Remaining topics:**
* **Week 3:** binary heaps; priority queue ADT * **Week 4:** quicksort; sorting lower bound * **Week 5:** count and radix sort; hash tables * **Week 6:** ordered dictionaries; binary search trees * **Week 7:** MIDTERM EXAM; AVL trees * **Week 8:** *FALL BREAK* * **Week 9:** splay trees; graphs * **Week 10:** breadth- and depth-first search * **Week 11:** minimum spanning trees and matroids * **Week 12:** shortest paths * **Week 13:** MIDTERM EXAM; dynamic programming * **Week 14:** string algorithms * **Week 15:** network flow * **FINAL EXAM** # Assignments *Labs, homework, and exam materials will be posted here.* # Responsibilities and Evaluation **Lectures and Labs:** Lectures are held Mondays and Wednesdays and lab is held on Fridays. You are required to come to lab sessions. At that lab meeting you will often be paired with a partner or work in a group on exercises directly related to the lecture material. You'll hand in the work done in lab at the end of that lab session. **Homework:** In addition there will be written homework assigned roughly every week or two. These will be a mix of written answers to problems and the occasional coding problem. I will post links to these homework and lab assignments in the section just above and also within the weekly schedule. **Exams:** There will be two "half-term" exams (one mid-semester, one near the end of semester) and a final exam. The first half-term covers material from the beginning of the course up until hash tables. The second half-term, covers material from search trees up until spanning trees. There will also be a comprehensive final exam during finals week. It will re-examine material from the first two half-terms and also (in essence) contain a "third half-term" on the last weeks of material, covering shortest paths and beyond. **Grade Calculation:** Your final grade will be determined, roughly speaking, with a weighted breakdown of about 45% for labs and homework assignments, 15% each for the comprehensive half-term exams, and 25% for the final exam. # Outcomes Students will be able to: * Devise algorithms, give justification of their correctness, and analyze their performance. * Express algorithms using machine-independent code (“pseudo-code”) towards their analysis and towards communicating them to other algorithm designers. * Write proofs of formal statements about algorithms’ correctness and efficiency, including arguing upper and lower bounds on an algorithmic problems solution. * Solve recurrences and use asymptotic notation that express an algorithm’s performance. * Devise and analyze the running time efficiency of standard data structures that support algorithms, including stacks, queues, priority queues, unordered and ordered dictionaries, and also their standard implementations in code. * Identify and implement several sorting algorithms, including bubble-sort, insertion-sort, quick-sort, merge-sort, heap-sort, and radix sort. * Identify and apply algorithms on graphs including the graph traversals of depth- and breadth-first search. Formulate and solve optimization problems like finding a shortest path, a minimum spanning tree, or a maximum network flow of a graph. * Appropriately deploy standard approaches to devising algorithms, including recursion, “divide and conquer,” and dynamic programming. **Distribution Requirements**
This course can be used towards your **Group III: Natural, Mathematical, and Psychological Science** requirement. It accomplishes the following learning goals for the group: ✓ Use and evaluate quantitative data or modeling, or use logical/mathematical reasoning to evaluate, test or prove statements ✓ Given a problem or question, formulate a hypothesis or conjecture, and design an experiment, collect data or use mathematical reasoning to test or validate it. × Collect, interpret, and analyze data. This course *does not* satisfy the “primary data collection and analysis” requirement. # Other Policies **Have Integrity**
All individual work you turn in for this class should be yours and yours alone. We take this very seriously and will not hesitate to report violations of this principle. Working on exercises together can be great, and we encourage you to do it. Talking through ideas and approaches to solve a problem or to devise a proof is a useful way of learning the material. (We even will set up many lab assignments in a way that they require collaboration.) However, you should avoid dictating to someone, or being dictated, a solution. So much of this course involves seeking the germ of a solution to a puzzle of some sort. Getting the trick from someone else, or some source, stops you from developing the (possible discomfortably) process of finding solutions on your own. If you happen to get an idea from someone, or some source, please acknowledge them or cite the source. If you work closely and collaboratively with someone or with a group, include the names of your collaborators. (An exception is Harper and Jim, who you are welcome to talk to at any time about ideas and to ask for hints.) For some work you will be specifically asked to collaborate with another student, or students, in the class. The same rules above apply to you as a team in completing the work. If you have questions about what constitutes a reasonable level of collaboration, ask us. You are allowed to look up general background on the internet. But be aware: there are many sites and sources (including ChatGPT) that in essence give you an answer. The things we study might best be learned by solely working with (us and) the textbook. Oftentimes our goal is for you to figure out a problem by just working from the info we provide. You cannot use the internet to find information that is intended to directly solve the problem you are trying to solve, or to copy such code. As a rule of thumb, ask yourself “If this exercise was completely different but still on the same topic, would this resource still be just as useful to me?” If the answer is no, it is not an acceptable resource to use. Forbidden internet use includes use of artificial intelligence programs like ChatGPT, VSCode co-pilot, or Github co-pilot. While these tools can be useful to an expert in the material of the course, at this stage in your education using these will very likely prevent you from learning important problem-solving skills and mastering the content. You are also not allowed to consult materials from prior offerings of this course. On exams, and the final, of course no communication at all is allowed with the internet or any person other than the instructor. **Be Clear**
When you write code, solve problems, and develop proofs, you are writing these solutions in ways that need to be understood by others (including us and any graders), oftentimes with you working to justify that they are correct. A significant component of this course seeks you developing the ability to communicate these (mathematical, algorithmic, logical) ideas clearly and carefully, oftentimes with precision as well as accuracy. We value code, solutions, and arguments that are clear, careful, and appropriately concise, but with enough explanation to justify the result and to convince someone that it is correct. If something you write is not clear to us and you are not sure why, talk with us about our expectations. In many cases we will accept revisions and rewrites of work and we'll offer some credit for you making and submitting them. **Have Fun!**
Congratulations on having gained enough programming experience and having enough mathematical preparation to tackle the ideas of this course. Both Harper and Jim *love* this material and have experienced the joy of solving similar puzzles in a similar class (or classes), and in their research. One of the fun things about the course is that we work at a level of detail that allows us to cover a wide variety of problems and techniques, in a substantive way, but without always having to detail things out by implementing them in running code. With experience here, you'll be able to learn about lots of people's work, and quickly so. And of course, you might now and then be compelled to implement some of these things. Your practice with this course helps you translate people's ideas, communicated similarly and briefly, into detailed, working code. [Jim Fix]:https://jimfix.github.io [Harper Knittel]:https://mknittel.github.io ......................... . . . . . . . . . . . . . . . .