COSC 211: Data Structures
course materials for Fall 2021
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.
Meetings
 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)
For writing scribe notes and assignment submissions in the markdown format, please use this template. You can see the output of the template file here.
Interfaces and Implementations
SimpleDS: interfaces requiring only basic functionality
SimpleList
SimpleDeque
SimpleStack
SimpleQueue
SimpleUSet
SimpleSSet
(note:SimpleSSet
extendsSimpleUSet
, so you need both files to implementSimpleSSet
)SimplePriorityQueue
(forthcoming)SimpleMap
(forthcoming)
Resources by Week
Week 01 (08/30 – 09/03)
Relevant readings:
Code:
SimpleList.java
: an interface for the List ADTArraySimpleListOne.java
: an implementation ofSimpleList
using an arraySimpleListTester.java
: a simple program demonstrating ourSimpleList
implementation
Week 02 (09/06 – 09/10)
Relevant readings:
 ODS, Chapter 3: Linked Lists (For Tuesday, Assignment 01)
 Listlike 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)
Code:
SimpleLists.zip
TestingSimpleList
implementations (Lecture 03)CountTimer.zip
An example demonstrating the use ofCSVWriter
andRunTimer
to record the running times of methods.
Slides:
Week 03 (09/13 – 09/17)
Relevant Readings:
 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:

Code from lecture 05. This program compares two arraybased implementations of the
SimpleStack
interface that differ only in theirincreaseCapacity
method. In both implementations, thepush
method (which callsincreaseCapacity
has worstcase running time \(O(n)\). However, in the second implementationArraySimpleStackTwo
, we showed that the amortized running time ofpush
is \(O(1)\). The empirical running times of the two implementations are displayed in Lecture 05 Slides. 
Code from lecture 06. This program
PrimeTimes.java
compares arraybased implementations of theSimpleUSet
andSimpleSSet
interfaces. In first implementation implements thefind
operation 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.
Slides:
Week 04 (09/20 – 09/24)
Relevant Readings:
 Recursion, Stacks, and Induction (for Tuesday)
 The Logarithm Function (for Tuesday)
 ODS Chapter 6: Binary Trees (for Thursday)
Scribe Notes
Lectures
 Lecture 02, (pdf notes)
 Lecture 03 (pdf)
 Lecture 04 (pdf)
 Lecture 05
 Lecture 06
Assignments
 Assignment 1 (Due 09/14)
 Assignment 2 (Due 09/23)
 Assignment 3 (Due 09/30)
 Assignment 4 (Due 10/07)
 Assignment 5 (Due 10/14)
 Assignment 6 (Due 10/21)
 Assignment 7 (Due 10/28)
 Assignment 8 (Due 11/4)
 Assignment 9 (Due 11/11)
 Assignment 10 (Due 11/18)
 Assignment 11 (Due 12/02)