Midterm 2 Topic Review

How to use this document

• All contents covered in Midterm I will not be specifically tested but will likely to be used in the questions.
• Self-test using this document to see what concepts are challenging to you
• Course notes document is the main resource for tips, pitfalls. High priority in midterm preparation.
• Review all participation activities and challenge activities in zyBook
• Practice your ability to finish the patterns listed here from scratch without the help from any editor/ IDE

Templates

Concepts

• Declares a variable to match any data type
• A function template is not a function
• A class template is not a class

Syntax

• The template clause must be used right above all entities using the typename

  • function declarations and definitions
  • class declarations
  • out-of-line method definitions

  template <typename T>
  T add(T a, T b) {
    return a + b;
  }
  

• Single header module for templates

Linked-List

Implementations

• singly-linked
  • head pointer
  • tail pointer (optional)
  • node with next pointer
  • Cannot access previous node easily
  • Slow to remove the last node!
• doubly-linked
  • head pointer
  • tail pointer (optional)
  • node with next and prev pointers
• Implementation details
  • recursive vs iterative
  • empty linked list is handled as a special case
  • first, last and middle nodes are handled differently
  • big three
  • search
  • insert before
  • insert after
  • remove
• Compared to Array
  • dynamic size
  • insertion and removal are efficient
  • access by index is inefficient

Linear ADTs

List

• Sequential
• Behaviors
  • add and remove at any position
  • search
  • access by index
  • check size

Stack

• LIFO or FILO
• Implementation
  • Mostly as a linear data structure
  • linked-list (avoid deleting from the tail for singly-linked list)
  • partially filled array
• Behaviors
  • push
  • pop
  • peek/top
  • check empty

Queue

• FIFO or LILO
• Implementation
  • Mostly as a linear data structure
  • linked-list (avoid deleting from the tail for singly-linked list)
  • circular partially filled array (FYI)
• Behaviors
  • enqueue
  • dequeue
  • peek
  • check empty

Deque

• Double-ended queue
• Implementation
  • Mostly as a linear data structure
  • linked-list
  • circular partially filled array (FYI)
• Behaviors
  • enqueue at both ends
  • dequeue at both ends
  • peek at both ends
  • check size

Wrapper class

• One ADT can cover the usage of another ADT
• Wrapper class
• E.g. wrap the std::vector class to implement a Stack
• E.g. wrap Deque to implement Stack and Queue

Sorting

• Sorting algorithms concepts
  • in-place (only swap) vs out-of-place (move data to another array)
  • general purpose (comparison based) sorting algorithms vs non-comparison based sorting algorithms
  • stable vs unstable (whether the original order of duplicate elements is preserved, FYI)
  • best complexity for comparison based sorting algorithms $\Theta(n \log n)$
• Quick sort
  • Quick partition as a sub-algorithm
    • Our variation of Hoare’s scheme (different from the zybook algorithm, refer to the lab)
  • in-place algorithm
  • time complexity: $\Theta(n \log n)$ or $\Theta(n^2)$ in the worst case
• Merge sort
  • top-down merge sort
  • out-of-place algorithm
  • sorted merge as a sub-algorithm
  • time complexity $\Theta(n \log n)$
  • space complexity $\Theta(n)$
• Radix sort
  • not a general algorithm
  • out-of-place algorithm
  • time complexity $\Theta(nk)$ where $k$ is the number of digits
  • space complexity $\Theta(n)$
• Linked-list based sorting
  • recursive vs iterative
  • not all sorting algorithms are suitable
  • insertion sort
    • sorted insert
  • merge sort
    • sorted merge

Patterns

• Write a function template
• Write a class template
• Write C++ class declarations to describe ADTs (only need to write the declarations of public methods)
• Write methods of common operations of linked-lists, understand the code example totally! deque
• Write sorting algorithms as functions (take C array as parameter)
• Master how quick partition works on paper
• Master how sorted merge works on paper