Data Structures, Fall 2024

Unit 1: Java Prerequisites and ADTs

• polymorphism
• equals and hashCode
• the Comparable and Comparator interfaces
• anonymous classes
• default and static methods in interfaces
• static factory methods
• vararg parameters
• List and ArrayList

• Meeting 1: Wed 8/28, repeated Thu 8/29 morning and afternoon
• Meeting 2: Tue 9/3 morning and afternoon, repeated Wed 9/4 (we missed about 45 minutes of class; please watch the last 45 minutes of either of the 9/3 recordings)

• Code
• Documentation:
  • the Object and Objects classes
  • the Comparable and Comparator interfaces
  • the List interface and the ArrayList class
• Optional reading:
  • Building Java Programs chapters 1-10
  • Reading 15 from MIT 6.031
  • Comparable and Comparator by Baeldung
  • Effective Java, items 1, 10, 11, 14, 53, and 64
• optional video on varargs

• HW 1 (not graded)
• HW 2 (on CodeLab; see Blackboard for more information)

• Meeting 3: Thu 9/5 morning and afternoon, repeated Mon 9/9
  • (mostly completing the previous topic, only beginning ADTs)

• Code
• Optional reading: Readings 10, 11, 12, and 15 from MIT 6.031

• generic classes and interfaces
• generic static methods
• bounded type parameters
• wildcards
• restrictions on generics

• Meeting 4: Tue 9/10 morning and afternoon, repeated Wed 9/11
  • (mostly completing ADTs, only beginning generics)
• Meeting 5: Thu 9/12 morning and afternoon, repeated Mon 9/16

• Code
• Two introductory videos: video 1, video 2
• Optional reading:
  • Generics on dev.java
  • Java Generics FAQ by Angelika Langer

• primary interfaces
• iterators
• unmodifiable collections
• views
• abstract collection classes (no time)

• Meeting 6: Tue 9/17 morning and afternoon, repeated Wed 9/18
• Meeting 7: Thu 9/19 morning and afternoon, repeated Mon 9/23

• Diagram
• Some documentation slides
• Code
• Documentation:
  • collections framework overview and outline
  • primary interfaces: Collection, SequencedCollection (Java 21+), List, Set, Queue, and Map
  • the Collections class
  • iteration-related interfaces: Iterable, Iterator, and ListIterator
  • an abstract class: AbstractList (there are others)
• Optional reading:
  • Building Java Programs chapter 11
  • The Collections Framework on dev.java
  • the adapter, decorator, iterator, and template method design patterns on refactoring.guru
  • Nested Classes on dev.java
• Optional videos:
  • Young Pups: New Collections APIs for Java 9 by Stuart Marks
  • Beneath the Planet of the Collections by Stuart Marks and Maurice Naftalin
    • Updated: Escape from the Planet of the Collections
  • Sequenced Collections by Stuart Marks
  • Collections Corner Cases by Stuart Marks
  • Java Collections Puzzlers by Maurice Naftalin and José Paumard

Unit 2: Algorithms

• Meeting 8a: Tue 9/24 morning and afternoon, repeated Wed 9/25
  • (recordings include meeting 8b)

• Code
• Optional reading:
  • Building Java Programs chapter 12
  • Recursion by David Eck
  • Reading 14 from MIT 6.031

• Meeting 8b: Tue 9/24 morning and afternoon, repeated Wed 9/25
  • (recordings include meeting 8a)
• Meeting 9: Thu 9/26 morning and afternoon, repeated Mon 9/30

• Code
• Documentation: the Arrays class
• Optional videos:
  • binary search
  • selection sort
  • bubble sort
  • insertion sort
  • mergesort
  • quicksort
• Optional reading:
  • Building Java Programs chapter 13
  • Searching and Sorting by David Eck
  • blog post by Josh Bloch about a common bug in binary search

• Meeting 10: Tue 10/1 morning and afternoon, repeated Mon 10/7
• Meeting 11a: Tue 10/8 morning and afternoon, repeated Wed 10/9

• Code
• Documentation: StringBuilder
• Optional reading:
  • Building Java Programs chapter 13
  • Analysis of Algorithms by David Eck

Unit 3: Data Structures

• Meeting 11b: Tue 10/8 (morning and afternoon), repeated Wed 10/9

• Code
• Documentation: the ArrayList class
• Handout: time complexity of ArrayList operations
• Optional reading: Building Java Programs chapter 15

• Q&A meetings on Zoom:
  • Mon 10/14 at 3pm (recording)
  • Sunday 10/20 at 9am (recording)
• Section MY9 exam date: Mon 10/21
• Sections TY9 and TY2 exam date: Tue 10/22

• Exam information
• MY9 exam, solutions
• TY9 and TY2 exam, solutions

• Meeting 12: Thu 10/10 morning and afternoon, repeated Tue 10/15 (Monday schedule) (diagrams)
• Meeting 13: Wed 10/16 (diagrams); class cancelled Thu 10/17 (watch 10/16 recording instead)

• Code
• Documentation: the LinkedList class (but see)
• Handout: time complexity of ArrayList and LinkedList operations
• Optional reading:
  • Building Java Programs chapter 16
  • Linked Data Structures by David Eck

• HW 5u (ungraded)
• HW 5g (graded, on CodeLab)

• Meeting 15: Wed 10/23 (diagrams); class cancelled Thu 10/24 (watch 10/23 recording instead)
• Meeting 16: Mon 10/28, repeated Tue 10/29 morning and afternoon
• Meeting 17: Wed 10/30, repeated Thu 10/31 morning and afternoon

• Code
• Diagram
• Documentation:
  • the Queue and Deque interfaces
  • the LinkedList, ArrayDeque, and (legacy) Stack classes
• Optional reading:
  • Building Java Programs chapter 14
  • Stacks, Queues, and ADTs by David Eck

• HW 6u (ungraded)
• HW 6g (graded) on CodeLab

• Meeting 18: Mon 11/4, repeated Tue 11/5 morning and afternoon
• Meeting 19: Wed 11/6 (diagrams), repeated Thu 11/7 morning and afternoon (diagrams)

• Code
• Slides
• Documentation:
  • the Set, SequencedSet, Map and SequencedMap interfaces
  • the HashSet, LinkedHashSet, HashMap, and LinkedHashMap classes
• Optional reading:
  • Building Java Programs sections 11.2, 11.3, and 18.1
  • Maps by David Eck
• Optional introductory video

• HW 7u (ungraded)

• Meeting 20: Mon 11/11, repeated Tue 11/12 morning and afternoon

• Code
• Slides
• Optional reading:
  • Building Java Programs sections 17.1-17.3
  • Binary Trees by David Eck

• Q&A meeting on Zoom:
  • Thu 11/21 at 8pm
  • Sun 12/1 at 11am
• Section MY9 exam date: Mon 11/25
• Sections TY9 and TY2 exam date: Tue 11/26

• Exam information
• Running time table
• Section MY9 exam
• Section TY9 exam
• Section TY2 exam

• Meeting 21: Wed 11/13 (diagrams), repeated Thu 11/14 morning and afternoon
• Meeting 22: Mon 11/18, repeated Tue 11/19 morning and afternoon

• Code
• Handout: Set and Map running times
• Documentation:
  • the SortedSet, NavigableSet, SortedMap and NavigableMap interfaces
  • the TreeSet and TreeMap classes
• Optional reading: Building Java Programs sections 11.2-11.3 and 17.4-17.5
• Optional: Record Classes, Local Variable Type Inference

• Meeting 23: Wed 11/20, repeated 11/21 morning and afternoon

• Code
• Slides
• Documentation: the PriorityQueue class
• Optional reading:
  • Building Java Programs section 18.2
  • section 10.1 of Open Data Structures
  • lecture notes from Dartmouth CS 10

Unit 4: Functional-style Programming

• functional interfaces
• Comparator creation methods
• using lambdas with the JCF

• Meeting 25: Mon 12/2, repeated Tue 12/3 morning and afternoon
• Meeting 26: Wed 12/4, repeated Thu 12/5 morning and afternoon

• Code
• Documentation:
  • functional interfaces:
    • Comparator
    • the entire java.util.function package, especially Function, Predicate, BinaryOperator, UnaryOperator, Consumer, BiConsumer, and Supplier
  • using lambdas with the JCF: Iterable, Collection, List, Map
• Optional reading:
  • Building Java Programs sections 19.1 and 19.2 (not in 3rd ed.)
  • Lambda Expressions on dev.java
• Optional videos:
  • Lambdas and Streams Master Class Part 1 by José Paumard and Stuart Marks
  • Collections Refueled by Stuart Marks
  • Comparison Method Violates Its General Contract! (Part 1) by Stuart Marks
  • Comparison Method Violates Its General Contract! (Part 2) by Stuart Marks

• Meeting 27: Mon 12/9, repeated Tue 12/10 morning and afternoon
• Meeting 28: Wed 12/11, repeated Thu 12/12 morning and afternoon

• Code
• Documentation:
  • the Stream, IntStream, and DoubleStream interfaces of the java.util.stream package
  • the Optional, OptionalInt, and OptionalDouble classes
• Optional reading:
  • Building Java Programs sections 19.3-19.6 (not in 3rd ed.)
  • Introduction to the Stream API by David Eck
  • The Stream API and Refactoring from the Imperative to the Functional Style on dev.java
  • Reading 26 from MIT 6.031
• Lambda Hands-on Lab by Stuart Marks
• Optional videos:
  • Lambdas and Streams Master Class Part 2 by José Paumard and Stuart Marks
  • Collectors in the wild! by José Paumard
  • Optional - The Mother of All Bikesheds by Stuart Marks

• Q&A meetings on Zoom: Thursday 12/12 at 8 pm and Sunday 12/15 at 11 am
• Section MY9 exam: Mon 12/16 8-10 am in Ingersoll 2127
• Section TY9 exam: Thu 12/19 8-10 am in Ingersoll Extension 329
• Section TY2 exam: Thu 12/19 1-3 pm in Ingersoll Extension 329

• Exam information
• More practice
• Exam: section MY9, sections TY9 and TY2