Algorithm Study

Knapsack problems are classic dynamic programming challenges where the goal is to maximize the total value of items placed in a limited-capacity bag, given item attributes like weight, value, and quantity. Common variants include:

• 0/1 Knapsack: Each item is unique; you either take it or leave it (quantity = 1).
• Complete Knapsack: Each item has an infinite supply; items can be selected multiple times.
• Multiple Knapsack: Each item has a limited quantity (between 1 and many).
• Grouped Knapsack: Items are divided into groups, and only one item per group can be selected.
• Multi-dimensional Knapsack: The bag has multiple constraints (e.g., weight and volume).
• Mixed Knapsack: A combination of the above types.

The VuePress theme-hope layout consists of global elements and page-specific components that can be customized via theme options and page frontmatter.

Global Layout Elements:

• Navbar
• Sidebar
• Footer

Page-Specific Elements:

• Breadcrumbs
• Page Title and information
• Table of Contents (TOC)
• Meta information (update time and contributors)
• Comments section

Interface Elements:

• Dark Mode toggle button
• Back to top button
• Print button

A Spanning Tree (or Generating Tree) of an undirected connected weighted graph G with n vertices is a connected subgraph consisting of all n vertices and n-1 edges. The Spanning Tree with the minimum total edge weight is called the Minimum Spanning Tree (MST).

Key concept: A 'cross-set edge' is an edge (u, v) where u is in a non-empty subset S of vertices and v is in the remaining set V-S. The minimum cross-set edge is guaranteed to be part of some MST.

A Heap is a special type of complete binary tree. It comes in two primary forms:

• Max Heap: The value of any node is greater than or equal to the values of its children. The root (top) contains the maximum value.
• Min Heap: The value of any node is less than or equal to the values of its children. The root (top) contains the minimum value.

Key terminology:

• Heap Top: The root of the heap.
• Heap Bottom: The rightmost node in the lowest level.

An expression binary tree is constructed by breaking down a mathematical expression where operators serve as internal nodes and operands serve as leaf nodes. The tree's traversal sequences correspond to different expression notations:

• In-order traversal (中根序列) produces the Infix expression.
• Post-order traversal (后根序列) produces the Postfix expression.

A Binary Search Tree (BST) is defined by the following properties:

1. All node keys must be unique.
2. For any given node P, all keys in its left subtree must be less than the key of P, and all keys in its right subtree must be greater than the key of P.

Key derived operations include:

• Sorting: An in-order traversal of a BST produces a sorted sequence of keys.
• Finding Min/Max: The minimum element is the first element of the in-order sequence (leftmost node), and the maximum is the last element (rightmost node).

An AVL tree (Height-Balanced Tree) is a binary search tree where the heights of the left and right subtrees of any node differ by at most 1.

• Balance Factor (BF): Calculated as Height(Left Subtree) - Height(Right Subtree).
• Valid BF: For a node to be balanced in an AVL tree, its balance factor must be 1, 0, or -1.
• Goal: By maintaining this balance, the tree prevents degradation into a linked list, ensuring search time complexity remains O(log n).

Huffman trees are used to minimize the Weighted Path Length (WPL) for text compression. Key concepts include:

• Extended Binary Tree: A tree where all empty pointer positions are filled with specific empty leaf nodes. These are called 'external nodes', while others are 'internal nodes'.
• Weighted Path Length (WPL): The sum of the products of each external node's weight (e.g., character frequency) and its path length to the root. In text compression, WPL represents the total size of the compressed data.
• Prefix-free Coding: Because no external node is an ancestor of another, Huffman encoding ensures that no code is a prefix of another, preventing ambiguity during decoding.