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

  • A function template is not a function

  • The instance of a function template is a function

  • A class template is not a class

  • The instance of a class template is 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

  • Single header module for templates

Linked-List

Implementations

  • singly-linked

    • head pointer

    • tail pointer (optional)

    • node with next pointer

    • Cannot access previous node easily

  • 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

    • partially filled array

  • Behaviors

    • push

    • pop

    • peek/top

    • check empty

Queue

  • FIFO or LILO

  • Implementation

    • Mostly as a linear data structure

    • 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

Hashing

  • Applications: hash table, cryptography, fingerprinting, checksum, etc.

  • Hash function

    • mapping data to data

    • collision - different keys mapped to the same hash value

Hash table

  • Hash table

    • Requirements

      • Unique keys

    • Characteristics

      • fast lookup \(\Theta(1)\)

      • redundant storage space

      • performance degradation when overfilled

        • load factor

    • buckets

    • hash function

      • key -> index

      • modulo operator

    • collision

      • different keys mapped to the same index

      • something we always need to handle

    • collision resolution methods

      • chaining: let each bucket hold more than one element

      • open addressing: find another empty bucket

        • Probing methods

          • linear \([h(key) + c*i]\%n\)

          • quadratic \([h(key) + c_1*i + c_2*i^2]\%n\)

          • double hashing \([h1(key) + c*i*h2(key)]\%n\)

  • ADTs that are implemented using hash tables

    • hash map (key-value pairs)

    • hash set (only keys)

      • when we do not care about values

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

  • Write sorting algorithms as functions (take C array as parameter)

  • Master how quick partition works on paper

  • Master how sorted merge works on paper

  • Write insertion sort on linked-list

  • Master open addressing collision resolution methods on paper

    • Calculate

      • hash value

      • probing sequence

    • Simulate how probing works on paper