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.

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
Trees: implementations of tree data structures


Resources by Week
Week 01 (08/30 – 09/03)

Relevant readings:

Code:

Week 02 (09/06 – 09/10)

Relevant readings:

Code:

  • SimpleLists.zip Testing SimpleList implementations (Lecture 03)
  • CountTimer.zip An example demonstrating the use of CSVWriter and RunTimer to record the running times of methods.

Slides:

Week 03 (09/13 – 09/17)

Relevant Readings:

Code:

  • Code from lecture 05. This program compares two array-based implementations of the SimpleStack interface that differ only in their increaseCapacity method. In both implementations, the push method (which calls increaseCapacity has worst-case running time \(O(n)\). However, in the second implementation ArraySimpleStackTwo, we showed that the amortized running time of push 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 array-based implementations of the SimpleUSet and SimpleSSet interfaces. In first implementation implements the find 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:

Week 05 (09/27 – 10/01)
  • Midterm 01 (posted to Moodle)
Week 07 (10/13 – 10/15)

Relevant Readings:

Code:

  • Code for Lecture 13. A program that compares a basic BST implementation to an AVL tree implementation. The main method is in TreeComparison.java. Be sure to view/compare the BST implementations provided in BinarySearchTree.java and AVLTree.java.

Slides:

Week 08 (10/18 – 10/22)

Relevant Readings:

Coding Challenge (in case you need one):

  • Last week, we saw an implementation of an a SimpleSSet that employed an AVL tree to perform find, add, and remove in \(O(\log n)\) time. Modify the AVLSimpleSet so that it implements the SimpleList interface in such a way that all operations (in particular, get, add, and remove) 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:

Code:

  • Code for Lecture 17 Contains a skiplist impelementation of the SimpleSSet class, SkipSSet.java. The program SimpleSSetComparison.java gives an empirical comparison between three SimpleSSet implementations: unbalanced binary trees, AVL trees, and skiplists.

Slides:

Week 10 (11/01 – 11/05)

Relevant Readings:

Week 11 (11/08 – 11/12)

Slides:

Week 12 (11/15 – 11/19)

Slides:

Week 13 (11/29 – 12/07)

Relevant Readings:

Code:

Slides:


Scribe Notes

Lectures


Assignments