CSCI 104 - Fall 2019 Data Structures and Design

Midterm Review

Quick review from last week

Introduction

This lab goes over important concepts that you will need to know for the midterm.

DISCLAIMER: The material presented is recommended by the CPs, not the professor. You should also go over lecture material and your homework in order to fully prepare.

Some topics not covered in this lab (that could be covered in midterm):

  1. const
  2. exceptions
  3. streams

Lab Survey

Please take our lab survey! We want to make sure the labs in the second half of the semester are the best possible for you. This is all you have to do for checkoff, so you're free to fill this out and leave if you want.

Recursion

Recursion is a problem solving technique in which the solution to the main problem depends on solutions to smaller instances of the same problem (as opposed to iteration). Take the example of a fibonacci number that we looked at last week. Its value is equal to the sum of the previous 2 numbers, and so on. So the sequence looks like this: 1, 1, 2, 3, 5, 8, 13... We can solve this same problem using recursion.

What is the k fibonacci number?

int fib(int i) {
    if(i == 0) return 1;
    if(i == 1) return 1;
    return fib(i - 1) + fib (i - 2);
}

Remember that for successful recursion you need: - The right base case(s) - A problem that gets smaller (closer to the base case) every time

With respect to data structures, recursion is mostly used by linked lists and trees (you will learn later). However, many problems may require you to use recursion in conjunction with an ADT or other data structure.

The big drawback to recursion is that it is limited by the stack of the program/computer. Every time a function call happens, a return address is pushed onto the stack and another instantiation of the current function is also added. This leads to A LOT of memory being used for just a function calls, so imagine if you had hundreds, thousands, or even millions of functions calls. This is what stack overflow is! In practice, recursion isn't widely used because of this limitation. Instead, iterative approaches are used because anything recursive can be done iteratively.

Data Structures (So far)

A data structure is a data organization, management and storage format that enables efficient access and modification. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

Data structures can implement one or more particular Abstract Data Types, which specify the operations that can be performed on a data structure and the computational complexity of those operations. In comparison, a data structure is a concrete implementation of an ADT.

You don't need to know these runtimes for the exam, so feel free to tune out, but it's good background knowledge for why you would choose one data structure over another.

1. Array

An array is a collection of items stored at contiguous memory locations. The idea is to store multiple items of the same type together. This makes it easier to calculate the position of each element by simply adding an offset to a base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array). Adding and removing from an array is generally very costly as in order for the data to remain contiguous, all data needs to be shifted to accommodate an addition or deletion.

O(1) means constant — you can go directly to element 5, no matter how big your array is.

O(n) means linear — if you want to find the minimum element (in an unsorted array), you have to look at every single element, so finding the minimum of an array of size 2000 will take twice as long as finding the minimum of an array of 1000.

  1. Access: O(1)
  2. Search: O(n)
  3. Insertion: O(n)
  4. Deletion: O(n)

2. Linked List

A linked list is a data structure in which elements are linked using pointers. A node represents an element in linked list which has some data and a pointer pointing to next node. By arranging data in this way, we have a new way to store data other than an array. Insertion and deletion of nodes are really easy. Unlike an array, we don’t have to shift elements after insertion or deletion of an element. In a linked list we just have to update the address present in next pointer of a node.

  1. Access: O(n)
  2. Search: O(n)
  3. Insertion: O(n)
  4. Deletion: O(n)

ADTs (so far)

Abstract Data type (ADT) is a type (or class) whose behavior is defined by a set of operations.

The definition of ADT only mentions what operations are to be performed but not how these operations will be implemented. It does not specify how data will be organized in memory and what algorithms will be used for implementing the operations. It is called “abstract” because it gives an implementation independent view. The process of providing only the essentials and hiding the details is known as abstraction.

There are 5 main Abstract Data Types that you will need to know (for now): List, Stack, Queue, Map, Set.

1. List

A list contains elements of the same type arranged in sequential order. The following are the generic operations that can be used on the list, and their commonly associated runtimes:

  1. insert(position, value) | O(n): inserts the value right before the given position, shifting the rest. the later elements one position to the right.
  2. remove(position) | O(n): removes the value at the given position, moving all later elements one position to the left.
  3. set(position, value) | O(1): overwrites the given position with the given value.
  4. get(position) | O(1): returns the value at the given position.

2. Stack

A Stack performs operations based off of a Last In First Out (LIFO) approach. It contains elements of same type arranged in sequential order and all operations takes place at a single end (the top of the stack). Think of a stack of pancakes — you put a new pancake on top, and you could take off a pancake from the top. The following are the generic operations that can be used on the stack, and their commonly associated runtimes:

  1. push() | O(1): inserts an element at the top of the stack.
  2. pop() | O(1): removes the top of element from the stack.
  3. top() | O(1): return the element at the top of the stack without popping it.

You often want to use top() and pop() together (in that order!). Why?

3. Queue

A Queue performs operations based off of a First In First Out (FIFO) approach. It contains elements of same type arranged in sequential order and operations takes place at both ends, insertion is done at end and deletion is done at front. The following are the generic operations that can be used on the queue, and their commonly associated runtimes:

  1. enqueue() | O(1): inserts an element at the end of the queue.
  2. dequeue() | O(1): removes the first element of queue.
  3. peek() | O(1): return the element at the beginning of the queue without removing it.

What's a real world example of a queue?

4. Map

A Map contains touples of keys to values or key-value pairs. Given a certain key, the associated value can be accessed. No order can be inferred. The following are the generic operations that can be used on the map, and their commonly associated runtimes:

  1. get(key) | O(logn): returns the associated value.
  2. put(key, value) | O(logn): inserts the key value pair into the map.
  3. remove(key) | O(logn): removes key value pair from the map.

5. Set

A set stores unique values, without any particular order. This is typically used to check if something is within the set. The following are the generic operations that can be used on the set, and their commonly associated runtimes:

  1. add(value) | O(logn): adds value to the set.
  2. remove(value) | O(logn): removes value from the set.
  3. contains(value) | O(logn): returns a boolean if the value is within the set.

Rule of 3

The rule of 3 is used when we have an object that uses dynamically allocated memory. This rule is a good way to maintain good memory management and ensures that objects are correctly using their own memory and not sharing. This rule consists of 3 functions: Copy Constructor, Destructor, Assignment Operator.

1. Copy Constructor

Shallow copies duplicate as little as possible. A shallow copy of a collection is a copy of the collection structure, not the elements. With a shallow copy, two collections now share the individual elements.

Deep copies duplicate everything. A deep copy of a collection is two collections with all of the elements in the original collection duplicated.

By default, C++ generates a default copy constructor that is a shallow copy. We need to define our own copy constructor only if an object has pointers or any runtime allocation of resources. This will be a deep copy, allowing two objects to use completely separate memory spaces.

2. Destructor

By default, C++ generates an empty destructor and all member variables are deallocated at the end of the destructor. However, that means if you have a pointer to an object, the pointer will be deallocated, but the object it points to will not. If this happens to be the last pointer to the object, this causes memory leak.

Thus, if you may be holding on to resources that you need to free, you need to define your own destructor.

3. Assignment Operator Overload

Like copy constructors, assignment operators are created by default following the same principles (member-wise assignment). However, because it is not a constructor, an object must be returned. This is the same reasoning behind a copy constructor. We need a deep copy in order to correctly use objects and manage memory.

// By default, C++ will do this without you ever specifying an assignment operator
Example& Example::operator=(const Example& e)
{
    this->e1 = e.e1;
    this->e2 = e.e2;
    ...
    this->eN = e.eN;
    return *this;
}

Inheritance (public, private, protected)

Inheritance is a key aspect of Object Oriented programming and will be very important in your careers as Software Engineers (if that's what you want to do).

Given a class A, inheritance allows you to define a new class B that ‘inherits’ (automatically copies) all data and functions from A. Further, it allows you to modify and add functions as necessary, and overwrite existing functions. We can see that inheritance is the capability of a class to derive properties and characteristics from another class, and can be done in three ways: publicly, privately, and protectedly.

These different types just determine the scope of functions and variables from the base class to the derived class.

inheritance

Inheritance can also be broken up into three types: Is-A, As-A, and Has-A.

1. Is-A

When you write code, Is-A relationships are typically implemented by using public inheritance: you want all the functionality of A to remain available, while possibly adding more functions or data to B.

Implementation

class Backpack : public std::vector<std::string> {
public:
    Backpack();
};

Usage

Backpack bp;
bp.push_back("170 notes?");

Backpack is publicly inheriting a vector. This means that in order to add to the backpack we can still call the push_back function of the vector because it is publicly available.

2. As-A

When you write code, As-A relationships are typically implemented by using protected or private inheritance: you do not want other classes to see the underlying functionality, only the new stuff you implement using it.

Implementation

class Backpack : private std::vector<std::string> {
public:
    Backpack();
    void addToBackpack(std::string item) {
        push_back(item)
    };
};

Usage

Backpack bp;
bp.addToBackpack("my toaster of a laptop");

Backpack is privately inheriting a vector. This means that in order to add to the backpack we have to call the addToBackpack function. Unlike Is-A inheritance, push_back is now a private function in Backpack. From the outside, we have abstracted away the vector.

3. Has-A

Has-A relationships require no inheritance; they simply involve creating a member variable of type A in B.

Implementation

class Backpack {
public:
    Backpack();
    void addToBackpack(std::string item){
        items.push_back(item);
    };
private:
    std::vector<std::string> items;
};

Usage

Backpack bp;
bp.addToBackpack("stacks of class notes");

Backpack now has a vector in its private variables. The implementation of pushBackItem is now just using the items vector and inserting into that.

Virtual

Virtual functions allow for function overriding and the use of the runtime function. See the previous lab for more details: Lab 04

Any questions about the practice midterm?

Test Your Knowledge

ADT Questions

Which ADT or combination of ADTs should be used here?

  1. Every time you go grocery shopping (every day), you buy an apple. Whenever you're at home and want an apple (every other day), you grab the apple you bought most recently. Which data structure does this resemble? Which data structure should you be inspired by instead, to prevent your apples from going bad?

Coding Question

Given a list of prime factors generate all the products that can be made from any subset of the factors and return those products in a vector For example, given the prime factors:

2 3 7

there are 2n subsets of these factors:

{ {}, {2}, {3}, {7}, {2,3}, {2,7}, {3,7}, {2,3,7} }

Which would yield the products:

{ 1, 2, 3, 7, 6, 14, 21, 42 }

Use recursion to help generate these products. Each recursive call should be responsible for 1 factor and choose to either:

Guidelines

To test your code run make AllProductsTest.

Any general questions?

The exercises are a great way to get some extra practice. To be super prepared for the exam, you could also try writing them out on a piece of paper before coding them up.

Recommended:

recursion: llmax_head assignment operators: intarray_assign inheritance & polymorphism: shapes, virfunc1 and virfunc2