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
nSimpleDeque
SimpleStack
SimpleQueue
SimpleUSet
SimpleSSet
(note:SimpleSSet
extendsSimpleUSet
, so you need both files to implementSimpleSSet
)SimplePriorityQueue
SimpleMap
(forthcoming)
Trees: implementations of tree data structures
BinarySearchTree
SpliceException
(required forBinarySearchTree
)SimpleSSet
andSimpleUSet
interfaces are also required
AVLTree
(extendsBinarySearchTree
)
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)
Week 05 (09/27 – 10/01)
 Midterm 01 (posted to Moodle)
Week 07 (10/13 – 10/15)
Relevant Readings:
 ODS Section 10.1: Binary Heaps (for Thursday)
Code:
 Code for Lecture 13. A program that compares a basic BST implementation to an AVL tree implementation. The
main
method is inTreeComparison.java
. Be sure to view/compare the BST implementations provided inBinarySearchTree.java
andAVLTree.java
.
Slides:
Week 08 (10/18 – 10/22)
Relevant Readings:
 Lecture 14 Notes (for Tuesday)
 ODS Sections 4.1 and 4.2: Skiplists (for Thursday)
 Introduction to Probability (for Thursday)
 The Geometric Distribution (for Thursday)
Coding Challenge (in case you need one):
 Last week, we saw an implementation of an a
SimpleSSet
that employed an AVL tree to performfind
,add
, andremove
in \(O(\log n)\) time. Modify theAVLSimpleSet
so that it implements theSimpleList
interface in such a way that all operations (in particular,get
,add
, andremove
) all run in time \(O(\log n)\). Note that in order to do this, it may be helpful to have the nodes in the tree store additional information.
Week 09 (10/25 – 10/29)
Relevant Readings:
 ODS Section 4.4: Analysis of Skiplists (for Tuesday)
 ODS Section 5.1:
ChainedHashTable
: Hashing with Chaining (for Thursday)
Code:
 Code for Lecture 17 Contains a skiplist impelementation of the
SimpleSSet
class,SkipSSet.java
. The programSimpleSSetComparison.java
gives an empirical comparison between threeSimpleSSet
implementations: unbalanced binary trees, AVL trees, and skiplists.
Slides:
Scribe Notes
Lectures
 Lecture 02, (pdf notes) (09/02)
 Lecture 03 (pdf) (09/07)
 Lecture 04 (pdf) (09/09)
 Lecture 05 (09/14)
 Lecture 06 (09/16)
 Lecture 07 (09/21)
 Lecture 08 (09/23)
 Lecture 09 (09/28)
 Lecture 10 (09/30)
 Lecture 11 (10/05)
 Lecture 12 (10/07)
 Lecture 13 (10/14)
 Lecture 14 (10/19)
 Lecture 15 (10/21)
 Lecture 16 (10/26)
 Lecture 17 (pdf) (10/28)
 Lecture 18 (pdf) (11/02)
 Lecture 19 (11/04)
 Lecture 20 (11/09)
 Lecture 21 (11/11)
 Lecture 22 (11/16)
 Lecture 23 (11/18)
 Lecture 24 (11/30)
 Lecture 25 (12/02)
 Lecture 26 (12/07)
Assignments
 Assignment 1 (Due 09/14)
 Assignment 2 (Due 09/23)
 Assignment 3 (Due 10/07)
 Assignment 4 (Due 10/21)
 Assignment 5 (Due 10/28)
 Assignment 6 (Due
11/411/08)  Assignment 7 (Due 11/18)
 Assignment 8 (Due
12/0212/08)  Assignment 9 (optional)