Welcome to the Fall 2021 edition of COSC 211: Data Structures! Here, you will find links to course materials and assignments. Please start by reading the course syllabus.
- Lecture 01: T/Th 10:00–11:20, SCCE A131
- Lecture 02: T/Th 1:00–2:20, SCCE A131
- Professor’s Office Hours, SCCE C109
- Tuesday 2:30–3:30
- Wednesday 11:00–12:00
- TA Office Hours: M/W 7:00–9:00pm, SCCE A131
Notes and Resources
Notes and resources updated throughout the week.
- Suggested readings are primarily from Open Data Structures (ODS)
Interfaces and Implementations
SimpleDS: interfaces requiring only basic functionality
Resources by Week
Week 01 (08/30 – 09/03)
Week 02 (09/06 – 09/10)
- ODS, Chapter 3: Linked Lists (For Tuesday, Assignment 01)
- List-like ADTs (For Tuesday, Quiz 01)
- ODS, Sections 1.3.3, 1.4, and 1.5 (For Thursday)
- Asymptotic Analysis and Big O Notation (For Thursday)
SimpleListimplementations (Lecture 03)
CountTimer.zipAn example demonstrating the use of
RunTimerto record the running times of methods.
Week 03 (09/13 – 09/17)
- ODS Section 1.3: Mathematical Background (ignore the section on probability for now)
- ODS Section 1.5: Correctness, Time Complexity, and Space Complexity
- Comparable Interface Java documentation
- Amortized Analysis (for Thursday)
- Simple Set ADTs (for Thursday)
Code from lecture 05. This program compares two array-based implementations of the
SimpleStackinterface that differ only in their
increaseCapacitymethod. In both implementations, the
pushmethod (which calls
increaseCapacityhas worst-case running time \(O(n)\). However, in the second implementation
ArraySimpleStackTwo, we showed that the amortized running time of
pushis \(O(1)\). The empirical running times of the two implementations are displayed in Lecture 05 Slides.
Code from lecture 06. This program
PrimeTimes.javacompares array-based implementations of the
SimpleSSetinterfaces. In first implementation implements the
findoperation using linear search, without the assumption that the underlying data can be sorted. The second implementation applies binary search to find elements in a sorted set. The empirical comparison between the two methods are shown in the Lecture 06 Slides.
Week 04 (09/20 – 09/24)