Readings

The assigned reading prior to Tuesday, January 15th is an overview of data structures and a review of complexity analysis. Please refer to:

  1. Data Structures and Other Objects Using C++:

    • Chapter 1

Alternative

If you do not have the primary textbook, you can use the following free alternative texts instead:

  1. Data Structures & Algorithm Analysis

    • Chapter 1, Chapter 3

  2. Open Data Structures

    • Chapter 1

The readings prior to Tuesday, January 22nd focus on C++ templates and memory management, and an exploration of basic sequence containers such as dynamic arrays, linked lists.

This should be a review, and as such feel free to (re)skim Dr. Plank's notes. If you would like to use our textbook, this material can be found in the early part of the book. The new material for templates can be found below:

  1. C++ Templates Tutorial

Alternative review material

If you do not have the primary textbook, you can use the following free alternative texts instead:

  1. Data Structures & Algorithm Analysis

    • Chapter 4

  2. Open Data Structures

    • Chapter 2, 3

Questions (due 1/22, 10:30am)

Once you have completed the readings, answer the following questions:

  1. In the context of data structures, why would using a language with templates be advantageous?

  2. What is the difference between a vector's size and capacity? How do these properties influence the insert operation?

  3. Suppose I wanted to implement a sequence container by using an linked list. What would be the complexity in terms of Big-O for the following operations:

    • Locate an element based on index
    • Insert an element in the front
    • Insert an element in the back

  4. Describe one operation where a doubly linked list would affect the complexity of that operations as compared to a more "generic" singly linked list?

Submission

To submit your reading assignment, you must upload a text/PDF file onto Canvas prior to class