Computer Science III: Data Structures and Algorithms
Fall 2024
Administrivia
- Instructor: Nate Phillips
- Office hours: Tues/Thurs 3:15-4:15 PM & Wed 1-3 PM.
Also available by appointment and over Slack or Zoom. - Canvas page: Use for grades, online assignment submissions, and assignment solutions.
- Syllabus and additional policies.
Resources
- Java in the browser: Repl.it, CodeHS
- Official Java documentation
Calendar
- Thu, Aug 29
- Introduction and Java Review
- Tue, Sep 3
- Java Review, cont.
Project 1 due Sep. 11 - Thu, Sep 5
- List ADT
Homework 1 due Sep. 17 - Tue, Sep 10
- ArrayLists and Big O
- RList The RList interface
- RArrayList The RArrayList implementation
- Reading Ch. 2.1: Big O running time
- RList The RList interface
- Thu, Sep 12
- Recursive Big O and Linked Lists
- Node The Node class
- RLinkedList The RLinkedList implementation
- Demo A demo with examples of how to use singly linked lists
- Reading Ch. 2.6: Singly-linked lists
- Node The Node class
- Tue, Sep 17
- Singly-linked and doubly-linked lists
- Project 2 due Sep. 26
- Thu, Sep 19
- Stacks and Queues
- RStack The RStack implementation
- RIntQueue The RIntQueue implementation
- Reading Ch. 2.7: Doubly-linked lists
- Homework 2 due Oct 1
- RStack The RStack implementation
- Tue, Sep 24
- Quadratic sorting
- Exam Review Some example problems to help you study
- Reading Ch. 8.3-8.4: Quadratic sorting
- Exam Review Some example problems to help you study
- Thu, Sep 26
- Finish quadratic sorting
- Project 3 due Oct 14
- Tue, Oct 1
- Exam Review
- Exam Review Solutions Solutions to the example problems
- Thu, Oct 3
- Exam I
- Tue, Oct 8
- Trees and traversals
- Reading Ch. 6.1-6.2: General trees
- Thu, Oct 10
- Set/Map ADTs
- Reading Ch. 7.1-7.2: Set/Map ADTs
- Project 4 due Oct 25
- Reading Ch. 7.1-7.2: Set/Map ADTs
- Tue, Oct 15
- Binary Search Trees
- Visual Example
- RBinarySearchTree The RBinarySearchTree implementation
- TreeNode The TreeNode implementation
- Reading Ch. 6.5: Binary search trees
- Visual Example
- Thu, Oct 17
- Hashing
- Reading Ch. 7.3: Hashing
- Tue, Oct 22
- No class, Fall break
- Thu, Oct 24
- Hashing
- Homework 3 due Oct 31
- Tue, Oct 29
- Mergesort
- Reading Ch. 8.6: Mergesort
- Project 5 due Nov 14
- Reading Ch. 8.6: Mergesort
- Thu, Oct 31
- Quicksort
- Reading Ch. 8.9: Quicksort
- Exam Review Some example problems to help you study
- Happy Halloween!
- Reading Ch. 8.9: Quicksort
- Tue, Nov 5
- Review/catchup
- Quicksort
- Mergesort
- Demo Code
- Exam II Review Solutions Solutions to the example problems
- Quicksort
- Thu, Nov 7
- Exam II
- Tue, Nov 12
- Graphs
Reading Ch. 10.1: Graphs - Thu, Nov 14
- Graph Implementations
- Breadth-First Search Code
- Tue, Nov 19
- Dijkstra’s Algorithm
- Reading Ch. 10.6: Dijkstra’s algorithm
- Project 6 due Dec 4
- Reading Ch. 10.6: Dijkstra’s algorithm
- Thu, Nov 21
- Graphs and Graph Search, Continued
- Tue, Nov 26
- Priority queues and heaps
- Priority Queue
- Heap Info Sheet and Pseudocode
- Priority Queue
- Thu, Nov 28
- No class, Thanksgiving break
- Tue, Dec 3
- Heap sort and Exception Handling in Java:
- Exceptions in Java
- Thu, Dec 5
- Bellman-Ford Algorithm and negative cycles
- Bellman-Ford Algorithm Pseudocode
- The Bellman-Ford Algorithm in Java
- Bellman-Ford Algorithm Pseudocode
- Tue, Dec 10
- Wrapup and review for final
- Final Exam Review
- Final Exam Solutions
- Final Exam Review
- Thu, Dec 12
- Reading Day