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

1. C++ Templates Tutorial

2. C++ Made Easier: The Rule of Three

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

   • Skim Chapter 2 - 8 (Most of this should be review; we will not test you on this directly below or later, but we will build upon this material through the semester)

Alternative

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. In C++ Templates Tutorial, the author provides the following class template:

   //stack.h
   #pragma once
   template <class T>
   class Stack
   {
   public:
     Stack(int = 10) ;
     ~Stack() { delete [] stackPtr ; }
     int push(const T&);
     int pop(T&) ;  // pop an element off the stack
     int isEmpty()const { return top == -1 ; }
     int isFull() const { return top == size - 1 ; }
   private:
     int size ;  // Number of elements on Stack
     int top ;
     T* stackPtr ;
   } ;
   

   Unfortunately, this class violates the Rule of Three. Explain what this violation is, why it is problematic, and what you would do to fix it.

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

4. 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
   
   
5. 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