Indiana University, Fall 2025
This course studies the fundamental ideas for correctly and efficiently analyzing large amounts of data, such as DNA sequence databases and geographic information. These fundamental ideas come in two kinds: algorithms and data structures. Algorithms are instructions for solving problems and data structures are strategies for organizing information on computers. To implement algorithms and data structures correctly relies on software engineering skills such as testing, debugging, and reasoning logically about the code, which we practice in this course. Efficient algorithms require appropriate data structures, and vice versa, so the study of algorithms and data structures is tightly linked. In this course we learn about the algorithms and data structures that form the building blocks for many of Today’s large-scale computer systems. We apply these ideas to solve challenging problems in bioinformatics and geographic information systems. Warning: a possible side-effect of taking this course is doing better on job interview questions.
Lecture
Labs
Friday 10:20am-12:15pm, Ballantine Hall (BH) Room 229
Expect at least one quiz per month during lab time.
Instructors
Teaching Assistants
Office Hours
Office hours with TAs are in Luddy Hall Room 0121.
| Time | Monday | Tuesday | Wednesday | Thursday | Friday |
|---|---|---|---|---|---|
| 10am | |||||
| 11am | |||||
| 12pm | |||||
| 1pm | |||||
| 2pm | |||||
| 3pm | |||||
| 4pm | |||||
| 5pm |
Textbook
Data Structures and Algorithm Analysis in Java, 3rd Ed. by Mark A. Weiss
Slack (communicating with instructors and other students)
Schedule
| Day | Lecture Topic | Reading Due | Assignments and Due Dates | Link |
|---|---|---|---|---|
| Aug. 25 | Introduction | |||
| Aug. 27 | Arrays, Rotation, Testing | Ch.1 | ||
| Aug. 29 | — | Lab: Array Search and Testing | ||
| Sep. 1 | Labor Day (no class) | |||
| Sep. 3 | Algorithm Analysis | Ch.2 | ||
| Sep. 5 | — | Project: FloodIt! | ||
| Sep. 8 | Algorithm Analysis, Merge Sort | Ch.7 Sec.6 | ||
| Sep. 10 | Linked Lists and Abstract Data Types | Ch. 3 sec. 1-5 | Homework: about big-O | |
| Sep. 12 | — | Lab: Merge Sort | ||
| Sep. 15 | Programming in Deduce with Linked Lists | Programming in Deduce | ||
| Sep. 17 | Sorting: Insertion, Quick | Ch.7 Sec.2,7 | Homework: about algo. analysis | |
| Sep. 19 | — | Lab: Linked Lists in Deduce | ||
| Sep. 22 | Writing Proofs in Deduce | Proofs in Deduce | ||
| Sep. 24 | Binary Trees and Binary Search Trees (BST) | Ch.4 Sec.1,2,3 | Homework: Deduce Proof Exercise 1 | |
| Sep. 26 | — | Project: Segment Intersection (BST) | ||
| Sep. 29 | More Proofs and Induction | |||
| Oct. 1 | Balanced Search Trees (AVL) | Ch. 4 Sec. 4 | Homework: Quick Reverse Correct |
|
| Oct. 3 | — | Project: Segment Intersection (AVL) | ||
| Oct. 6 | Review for Midterm Exam | |||
| Oct. 8 | Midterm Exam | |||
| Oct. 10 | Fall Break | |||
| Oct. 13 | Discovering and Generalizing Lemmas | |||
| Oct. 15 | Hash Tables | Ch. 5 sec. 1,2,3,5,6 | Homework: Deduce Proof Exercise 2 | |
| Oct. 17 | — | Lab: Hash Table | ||
| Oct. 20 | Heaps and Priority Queues | Ch. 6 sec. 1-4,9 | ||
| Oct. 22 | Binomial Heaps and Queues | Ch.6 Sec.8 | Homework: List Search Correct | |
| Oct. 24 | — | Lab: Heap | ||
| Oct. 27 | ||||
| Oct. 29 | Graphs and Breadth-first Search | Ch. 9 sec. 1,3 | Homework: Search is O(n) in Deduce | |
| Oct. 31 | — | Lab: Binomial Heaps | ||
| Nov. 3 | Depth-first Search | Ch. 9 sec. 6 | ||
| Nov. 5 | Shortest Paths | Ch. 9 sec. 3 | Homework: Insertion Sort Correct | |
| Nov. 7 | — | Lab: Connected Components | ||
| Nov. 10 | Union Find | Ch. 8 | ||
| Nov. 12 | Minimum Spanning Tree | Ch. 9 sec. 5 | Homework: Insertion Sort is O(n^2) in Deduce | |
| Nov. 14 | — | Project: Routing Wires | ||
| Nov. 17 | Backtracking | Ch. 10 sec. 5 | ||
| Nov. 19 | Dynamic Programming | Ch. 10, sec. 3 | Homework: BST Correct | |
| Nov. 21 | — | Lab: work on Routing Wires | ||
| Nov. 24-28 | Thanksgiving | |||
| Dec. 1 | DNA Alignment | |||
| Dec. 3 | More Dynamic Programming | Homework: TBD | ||
| Dec. 5 | — | Lab: DNA Sequence Alignment | ||
| Dec. 8 | Code Review | |||
| Dec. 10 | Review for Final Exam | |||
| Dec. 12 | — | Lab: Review for Final Exam | ||
| Dec. 15-19 | Final Exam Week |
Resources
Autograder for submitting coding assignments.
Code Editor and Debugger: IntelliJ IDEA (Community Edition)
Note: Autograder uses JUnit5.7.0, so please stick to this version for JUnit.
Grade Weighting
Late Policy
This policy applies to labs, projects, textbook exercises, and quizzes. For quizzes, you can do a make-up quiz during office hours. This policy does not apply to the midterm and final exam. When you complete something up to one week late, there is a 10% deduction to its grade.
| 100% | up to the due date |
| 90% | up to one week after due date |
| 0% | after one week past the due date |