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
- Mondays and Wednesdays 9:35am-10:50am, Sycamore Hall (SY) Room 137.
Labs
Expect at least one quiz per month during lab time.
- 15 minutes, at the end of a lab session
- The scope of each quiz is everything turned in prior to the quiz, including homework and lab assignments
Instructors
- Jeremy Siek (jsiek), office hours Tuesdays 4-5pm, Wednesdays 11am-noon, in Luddy Room 3014.
Teaching Assistants
- Cloteaux, Matei (mcloteau)
- Josenhans, Calvin (cjosenha)
Office Hours
Office hours with TAs are in Luddy Hall Room 0121.
| Time |
Monday |
Tuesday |
Wednesday |
Thursday |
Friday |
| 10am |
|
|
|
|
|
| 11am |
|
|
Jeremy |
|
|
| 12pm |
|
|
|
|
|
| 1pm |
|
|
|
|
|
| 2pm |
Matei |
Calvin |
Matei |
|
|
| 3pm |
|
|
|
|
Calvin |
| 4pm |
|
Jeremy |
|
|
|
| 5pm |
|
|
|
|
|
Textbook
Data Structures and Algorithm Analysis in Java, 3rd Ed. by Mark A. Weiss
Slack (communicating with instructors and other students)
Signup
Assignments, Collaboration, AI, and Office Hours
You may work together with other students on the assignments.
You may use Artificial Intelligence.
You may come to office hours to get help from Real Intelligence.
You are responsible for learning all of the material. The midterm and
final exam questions are designed to test whether you learned
everything from the assignments.
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 |
code, test |
| Sep. 1 |
Labor Day (no class) |
|
|
|
| Sep. 3 |
Algorithm Analysis |
Ch.2 |
|
|
| Sep. 5 |
— |
|
Project: FloodIt! |
code |
| Sep. 8 |
Algorithm Analysis, Merge Sort |
Ch.7 Sec.6 |
|
|
| Sep. 10 |
Linked Lists and Abstract Data Types |
Ch. 3 sec. 1-5 |
Homework 1 |
|
| Sep. 12 |
— |
|
Lab: Merge Sort |
submit |
| Sep. 15 |
Programming in Deduce with Linked Lists |
Programming in Deduce |
|
|
| Sep. 17 |
Sorting: Insertion, Quick |
Ch.7 Sec.2,7 |
|
|
| Sep. 19 |
— |
|
Lab: Linked Lists in Deduce |
submit |
| 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 |
submit |
| Sep. 26 |
— |
|
Project: Segment Intersection (BST) |
code, test |
| Sep. 29 |
More Proofs and Induction |
|
|
|
| Oct. 1 |
Balanced Search Trees (AVL) |
Ch. 4 Sec. 4 |
|
|
| Oct. 3 |
— |
|
Project: Segment Intersection (AVL) |
code, test |
| Oct. 6 |
Review for Midterm Exam |
|
|
|
| Oct. 8 |
Midterm Exam |
|
|
|
| Oct. 9 |
|
|
Homework: Quick Reverse Correct
|
code |
| 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 |
code |
| Oct. 17 |
— |
|
Lab: Hash Table |
code, test |
| 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 |
code |
| Oct. 24 |
— |
|
Lab: Heap |
|
| Oct. 27 |
|
|
|
|
| Oct. 27 |
Review Solutions: Quick Rev, Proof Ex. 2 |
|
|
|
| Oct. 29 |
Graphs and Breadth-first Search |
Ch. 9 sec. 1,3 |
|
|
| Oct. 31 |
— |
|
Lab: Binomial Heaps |
code, test |
| Nov. 3 |
Depth-first Search |
Ch. 9 sec. 6 |
|
|
| Nov. 5 |
Shortest Paths |
Ch. 9 sec. 3 |
|
|
| Nov. 7 |
— |
|
Lab: Connected Components, Homework: Search is O(n) in Deduce |
Connected Components Submit Code, Connected Components Submit Test, Search is O(n) Submit |
| Nov. 10 |
Union Find |
Ch. 8 |
|
|
| Nov. 12 |
Minimum Spanning Tree |
Ch. 9 sec. 5 |
|
|
| Nov. 14 |
— |
|
Project: Routing Wires, Homework: Insertion Sort Correct |
Insertion Sort Correct Submit, Routing Wires Submit |
| Nov. 17 |
Backtracking |
Ch. 10 sec. 5 |
|
|
| Nov. 19 |
Dynamic Programming |
Ch. 10, sec. 3 |
|
|
| Nov. 21 |
— |
|
Lab: work on Routing Wires, |
|
| Nov. 24-28 |
Thanksgiving |
|
|
|
| Dec. 1 |
DNA Alignment |
|
|
|
| Dec. 3 |
More Dynamic Programming |
|
|
|
| Dec. 5 |
— |
|
Lab: DNA Sequence Alignment,
Quiz 3 (take home) on Hash Tables, Heaps, and Connected Components,
Homework: BST Correct |
BST Correct Submit, DNA Code Submit, DNA Test Submit |
| Dec. 8 |
Code Review |
|
|
|
| Dec. 10 |
Review for Final Exam |
|
|
|
| Dec. 12 |
— |
|
Lab: Review for Final Exam |
|
| Dec. 15 |
Final Exam: Monday, 8am-10am, in SY 137 |
|
|
|
Resources
-
Algorithm Analysis Recipes
- Practice Midterm Exams
- Practice Final Exams
-
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.
- Deduce Proof Checker
- Installing Deduce video
- Introduction to Deduce video.
- Programming in Deduce video.
- Writing Proofs in Deduce (Part 1) video.
- Writing Proofs in Deduce (Part 2) video.
- Writing Proofs in Deduce (Part 3) video.
- Writing Proofs in Deduce (Part 4) video.
- Proof by induction on linked lists in Deduce video.
Grade Weighting
- Assignments (30%)
- Quizzes (10%)
- Midterm Exam (25%)
- Final Exam (35%)
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 |