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


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:


Scribe Notes

Lectures


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)