Andrew’s Instant Math Club

In previous blogs, I described conversations with Andrew Bauman, an up-and-coming mathematician who is an undergrad at UALR and who spends spare time tinkering with problems in linear algebra and quantum mechanics. Today, in one of our gym-facilitated meetings, Andrew brought three distinguished and enjoyable intellects besides himself. This led to a wide-ranging conversation that I will attempt to recap here for posterity. We will start with a sidebar since the evening was full of them, some recursive, some eight layers deep.

Before tonight’s impromptu, mostly math and quantum computing discussion, I checked in with our pool lifeguard, a pole vaulter (not the back flipping fellow above, but certainly capable). A review of video footage of his record pole vault revealed excellent form, with one specific moment that could benefit from an improvement that consisted of pressing to a handstand and walking on one’s hands. This body position is attained for less than a second during the pole vault but is critical to obtaining greater heights. He showed me footage of his hand standing and walking, which was quite good. It gave me ideas for a follow-up exercise involving an inverted shoulder shrug, an inverted pole grip change/grip walk, and an inverted kip-up that could benefit him further. I’m writing this here as part of a stream-of-consciousness recap so I don’t forget it in the twists and turns of what follows.

Weight, there's more:

I strapped a 5 lb weight on each hip for my nightly mile walk/run tonight. However, due to the chance encounter with Andrew (and company), I did not make it to my walk, but I sported the weights like a pair of revolvers from the Wild West. Anyone seeing our extended conversation would have to wonder, “Why a weight belt for talking about math?”. Answer, “Heavy Topic”!

Andrew paused his ping-pong game to introduce me to his ping-pong partner, Dr. Sudan Xing, a mathematician and professor at UALR who specializes in geometric projection and embedding problems.

A peek at Google Scholar introduces us to the central theme of Dr. Xing's work, which is focused on the Orlicz-Brunn-Minkowski theory and related Minkowski problems in convex geometry. This theory is an extension of the classical Brunn-Minkowski theory, which deals with the relationship between the volumes of convex bodies and their Minkowski sums.

Now I’m a dolt, so I wanted to know what a simple Minkowski sum looked like, so I asked ChatGPT-4 to write me some code and produced the figure below. It was almost a 1-shot job; more recent work I have done has taken nearly 40 shots/redos to get right. The code is here.

The mathematics involved in her work primarily comes from convex geometry, functional analysis, and measure theory. Key concepts include:

• Convex bodies and functions
• Minkowski addition and Orlicz addition
• L_p norms and Orlicz norms
• Surface area measures and the Minkowski problem
• Brunn-Minkowski and isoperimetric inequalities
• Log-concave functions and measures

Dr. Xing's work contributes to developing a more general theory of convex bodies and related geometric inequalities, with potential applications in mathematics and beyond.

Next, we met her bioinformatics colleague, Ju Ni. We discussed how exciting it was to live in the time of AI/ML and the OMIM database, where we can know the genes involved in almost any affliction of human beings. We discussed the importance of visualizing gene and biochemical pathways for specific conditions. We discussed the particular example of Thyroid Cancer, one of the only truly “curable” cancers, since it can be treated with Iodine-131, which is preferentially taken up by the thyroid, thus neutralizing the cancer, but alas, the thyroid as well, necessitating lifelong medication afterward.

We briefly referenced a certain Calculus book, a Facebook math site, and my AddSubMulDivia five-book series “that nobody reads.” We had a good laugh about how pathetic it is to care so much about things no one else does.

Dr. Xing and I found out we shared appreciation for 2010 Fields medal laureate Cedric Villani, a mathematician and politician who is friends with the president of France. Quoting from my favorite LLM:

Villani revolutionized mathematical physics with contributions to optimal transport theory, kinetic theory, partial differential equations, and the study of Ricci curvature in metric spaces. His work, notable for bridging pure mathematics with applied physics, includes groundbreaking analyses of the Boltzmann equation and its convergence to the Landau equation, shedding light on gas behaviors in varied regimes. Villani's innovative use of optimal transport for exploring metric spaces with Ricci curvature bounds has influenced areas ranging from plasma physics to network analysis.

We talked about:

the advent of AI/ML is enabling the revisiting of unsolved math problems

symbolic algebra (now called CAS)

symbolic geometry, invented by my friend Phil Todd and his program Geometry Expressions™

Andrew mentioned he was working on a problem that starts with drawing a bisecting line on a piece of paper, and proving that the halfspaces generated by the line are distinct.

Dr. Xing responded with H+/H- halfspaces, then visualized the problem in 3D with her 'ping-pong paddle' analogy. She discussed the 'floating problem' – a sphere trimmed into equal-volume sections by tangent planes. This process seems to give the sphere unique properties, but we switched topics too quickly.

We touched on projective geometry and how representation (explicit, implicit, parametric, iterated, chaotic) influences what we can understand about a problem. I mentioned the challenges of intersecting closed tensor product surfaces made with B-splines and wondered if Dr. Xing's dualized projection approach could help.

I mentioned my curiosity about a set of planar ray tracing problems as a family of reachability problems that are quite interesting. These live under the heading “Visibility Polygon” and the Art Gallery Problem.

We talked a lot about how people conceptualize various kinds of mathematical concepts.

At this time, Greg, a friend of Andrew’s, had arrived. He has a Master’s degree and was focusing on math education.  Dr. Xing and Ju Ni had to go, so Greg, Andrew, and I started drilling down on several topics.

The topic space exploded before we settled down and had a heart-to-heart on quantum computing and Bell’s Inequality.

Topic Explosion (Free Association Gone Wild)

• inner products and their connection to standard deviation and variance
• Hilbert spaces, norms
• distance metrics: Euclidean, Manhattan, Minkowski
• closure loss on the inclusion of zero
• maintaining state on chained binary operations of AddSubMulDiv-ia to enable reversibility and prevent the loss of structure of the path of a calculation that would otherwise be non-unique if results were discarded at intermediate states. Undoability.
• skew and kurtosis being higher moments in statistics
• discrete and continuous distributions
• moments in structural mechanics and moments of inertia.I demonstrated how a phone tossed in space will land without a change in rotation in two of its three axes but not the third. The Veritasium link below explains it better.
• Spaghetti Sort as an analogy to quantum computing simultaneous equation solving using entangled particles.
• The mystery of entanglement is the same as having tossed a coin that landed heads and automatically knowing that the other particle’s spin is “tails”.
• The Bloch sphere
• Bell’s inequality
• Alice and Bob’s experiment: A stream of entangled particles
• Quantum and Classical Interpretations of the experiment
• The interchangeability of streaming and fixed interval experiments
• Interval arithmetic
• The register operation of comparing A and B’s results,
• XNOR was the decision operator correctly identified by Greg
• Marvin Minsky’s XOR catastrophe started the AI winter, requiring two neurons.

Links

• Veritasium: Pilot wave theory
• Veritasium: Two-way vs. one-way speed of light
• Veritasium: The strange physics of rotating bodies
• Van TSP Blog Entry
• Van Sorting Blog Entry
• Van Animating Arc Length Integration Blog Entry

Sorting out Sorting in 16 Shots with an LLM

In an homage to the seminal computer animation, "Sorting out Sorting" by Ronald M. Baecker and David Sherman at  University of Toronto, presented at SIGGRAPH 1981, this present day retrospective embarked on a man-machine collaboration to revisit the concept with modern LLM technology. To complete this "quick-hack" nod to the original, ChatGPT-4, was employed to illuminate the intricacies of sorting algorithms through a Python demonstration that was built and run for multiple cases in an evening - a much shorter period of time that coding this from scratch, for this author anyway.

In the end, this collaboration focused on four sorting algorithms: quicksort, bubblesort, insertion sort, and selection sort. Each algorithm was animated to showcase its operational nuances and performance implications, dependent on the array size.

The exploration spanned various case studies, from sorting four items to the challenge of a forty-item array. These cases illustrated the performance scalability of each algorithm, reinforcing the importance of algorithm choice based on data size and structure.

The effort culminated in a Python-based animation, refined across 16 shots to aid clarity, accuracy, and pedagogical value. This man-machine collaboration with ChatGPT-4 underscores the synergy between human expertise and artificial intelligence in computer science education.

For those intrigued by the nuances of algorithm efficiency and the visual pedagogy of sorting, this quick project serves as a testament to the enduring relevance of the original "Sorting out Sorting" and the evolutionary journey of computational teaching tools and the technology that drives them.

Results:

Note the number of steps that each sort took for each of the size-item cases:

1) The four-item case:

2) The five-item case:

3) The ten-item case:

4) The twenty item case:

5) The forty item case:

Observations
Notice the relatively poor performance of quicksort relative to the other sorts for small numbers of items and the relatively good performance of selection sort.


TLDR;

Parallel attempts were made using ChatGPT-3.5 and Claude3-Opus, but these fell short of expectations, so the author used ChatGPT-4 to execute a brief exploration of sorting algorithms. The conversation that led to acceptable code required16 iterative chat laps outlined for those who are coding with Large Language Models (LLMs) as follows:

1. Initial Request: Asked for a Python demo to animate sorting with a comparison of quicksort and bubblesort in Jupyter Notebook using Google Colab.
2. Clarification and Correction: Adjustments were made to increase the array size, which caused an IndexError.
3. Fix for IndexError: Provided a solution to fix the IndexError related to the array size increase.
4. Background Color Adjustment: You requested changing the graph background to your trademark color and further adjustments.
5. Sorting Algorithm and Layout Update: Requested adding mergesort to the comparison and faced an execution error.
6. Alternative Sorting Algorithm: Suggested using insertion sort as an easier alternative for visualization.
7. Visualization Enhancement: Added detailed visualization for tracking the sorting process with colors.
8. Error Handling: Addressed an IndexError related to indexing issues in the updated visualization code.
9. Additional Sorting Algorithm and Grid Layout: Included a fourth sorting algorithm and updated the layout to a 2x2 grid.
10. Visual Tracking Features: Requested marking special elements (pivot, etc.) with specific colors for clarity, this was successful, though quite complex to track.
11. Step Annotations Missing: Noted that step annotations were dropped from the visualization.
12. Reintroduction of Step Annotations: Added step annotations back into the visualization for clarity.
13. Title Color Adjustment: You wanted the titles of the sorting algorithms colored blue.
14. Legend Addition: Asked to add a legend explaining the color coding of the elements.
15. Legend Visibility Issue: Addressed the issue where the video progress bar covered the legend.
16. Conclusion: Expressed satisfaction with the assistance provided.

Python 3 Source: (Run in a Google Colab Jupyter Notebook)

import numpy as np

import matplotlib.pyplot as plt

from matplotlib.animation import FuncAnimation

import matplotlib.patches as mpatches

from IPython.display import HTML

# Initialize data and steps for each sorting algorithm

np.random.seed(0)

data = np.random.randint(0, 100, 40)

steps_qs, markers_qs = [], []

steps_bs, markers_bs = [], []

steps_is, markers_is = [], []

steps_ss, markers_ss = [], []

# Quicksort with detailed tracking

def quicksort(arr, lo, hi, steps, markers):

if lo < hi:

p = partition(arr, lo, hi, steps, markers)

quicksort(arr, lo, p - 1, steps, markers)

quicksort(arr, p + 1, hi, steps, markers)

def partition(arr, lo, hi, steps, markers):

pivot = arr[hi]

i = lo

for j in range(lo, hi):

if arr[j] < pivot:

arr[i], arr[j] = arr[j], arr[i]

i += 1

# Markers: pivot (hi), current item (j), and swap position (i)

markers.append([hi, j, i])

steps.append(arr.copy())

arr[i], arr[hi] = arr[hi], arr[i]

markers.append([hi, i, -1]) # Final swap to place pivot

steps.append(arr.copy())

return i

# Bubblesort with detailed tracking

def bubblesort(arr, steps, markers):

n = len(arr)

for i in range(n):

for j in range(0, n-i-1):

if arr[j] > arr[j+1]:

arr[j], arr[j+1] = arr[j+1], arr[j]

# Markers: current item (j) and comparison item (j+1)

markers.append([j, j+1])

steps.append(arr.copy())

# Insertionsort with detailed tracking

def insertionsort(arr, steps, markers):

for i in range(1, len(arr)):

key = arr[i]

j = i-1

while j >= 0 and key < arr[j]:

arr[j + 1] = arr[j]

j -= 1

# Markers: current item (i) and shift position (j)

markers.append([i, j])

steps.append(arr.copy())

arr[j + 1] = key

markers.append([i, j+1]) # Placement of key

steps.append(arr.copy())

# Selectionsort with detailed tracking

def selectionsort(arr, steps, markers):

for i in range(len(arr)):

min_idx = i

for j in range(i+1, len(arr)):

if arr[j] < arr[min_idx]:

min_idx = j

arr[i], arr[min_idx] = arr[min_idx], arr[i]

# Markers: minimum item (min_idx) and current position (i)

markers.append([min_idx, i])

steps.append(arr.copy())

# Sort and track steps

quicksort(data.copy(), 0, len(data)-1, steps_qs, markers_qs)

bubblesort(data.copy(), steps_bs, markers_bs)

insertionsort(data.copy(), steps_is, markers_is)

selectionsort(data.copy(), steps_ss, markers_ss)

# Visualization setup

# Define legend handles

legend_handles = [

mpatches.Patch(color='red', label='Unchanged Item'),

mpatches.Patch(color='blue', label='Pivot / Insertion Point'),

mpatches.Patch(color='orange', label='Current Item')

]

# Initialize the figure and axes again if needed

fig, ax = plt.subplots(2, 2, figsize=(8, 8), facecolor='#99CC99')

for axs in ax.flat:

axs.set_facecolor('#99CC99')

# Adjust subplots to make room for the legend below

fig.subplots_adjust(bottom=0.2)

# Animation update function with step annotations

def update(frame):

# Maps for color coding

color_map = {0: 'red', 1: 'blue', 2: 'orange', 3: 'green'}

plots = [steps_qs, steps_bs, steps_is, steps_ss]

titles = ['Quicksort', 'Bubblesort', 'Insertion Sort', 'Selection Sort']

markers = [markers_qs, markers_bs, markers_is, markers_ss]

for axs, plot, title, marker in zip(ax.flat, plots, titles, markers):

axs.clear()

axs.set_title(title, color='blue', fontsize=12)

current_step = plot[min(frame, len(plot)-1)]

if frame < len(marker):

current_marker = marker[frame]

else:

current_marker = [-1] # Default no marker

for i, val in enumerate(current_step):

color = 'red' # Default color

if i in current_marker:

color = color_map[current_marker.index(i)]

axs.bar(i, val, color=color)

# Annotate current step number on each subplot

step_text = f'Step: {min(frame+1, len(plot))}/{len(plot)}'

axs.text(0.35, 0.95, step_text, transform=axs.transAxes, ha='right', va='top', fontsize=12, color='blue', bbox=dict(facecolor='#99CC99', alpha=0.5, edgecolor='none'))

# Adding credit in the last subplot

fig.legend(handles=legend_handles, loc='lower center', bbox_to_anchor=(0.5, 0.1), fancybox=True, shadow=True, ncol=3)

fig.text(1, 0.0, 'Van2024/ChatGPT-4', fontsize=12, color='yellow', horizontalalignment='right', verticalalignment='bottom')

# Creating the animation

ani = FuncAnimation(fig, update, frames=max(len(steps_qs), len(steps_bs), len(steps_is), len(steps_ss)), interval=100, repeat=False)

# Display the animation

HTML(ani.to_html5_video())

Blazing Fast TSP: Comparing Brute Force and 2-Opt Algorithms

I recently encountered a solicitation on LinkedIn that said, "You have been selected to explain the Traveling Salesman Problem". (TSP). The solicitation turned out to be a way of getting multiple computer science people to solve the same problem, which would then be Darwinized and used by LinkedIn for further promotion. I provided a complete solution, but they would not accept a link, presumably because it takes the user off-site, which is anathema to social media profits. Beware the Machine.

Nonetheless, I thought this would be a good opportunity to demonstrate automatic code generation with a Large Language Model (LLM). So I set about with the following request:

Dear ChatGPT - I appreciate you so much! You have been an honest and faithful helper in coding up demonstrations of various principles in computer science, numerical analysis, computer graphics, and anything I'm interested in. Tonight, I need your help coding up a simple but beautiful demonstration of approaches to solving the Traveling Salesman Problem (TSP). As you know, this famous problem in computer science and operations research is well known for its pathological growth characteristics in time complexity. Nonetheless, we have to solve such problems, even if we cannot be guaranteed the optimal solution. I want you to build a Python demonstration compatible with Google Colab that uses matplotlib to generate approaches to solving TSP. It should run as an interactive demo that I can record off my screen.

While in previous blogs this approach yielded a straightforward generation processes, the more typical route to a working demo with satisfactory appearance is MUCH more circuitous.  One shot solutions are the exception to the rule, this effort required 29 iterations in ChatGPT 3.5 and 10 more in ChatGPT 4! Pressing on:
In the world of computer science and operations research, few problems are as iconic and challenging as the Traveling Salesman Problem (TSP). The TSP asks a simple question with profound implications: given a list of cities and the distances between them, what is the shortest possible route that visits each city exactly once and returns to the original city? Despite its seemingly straightforward nature, the TSP is notorious for its time complexity, which is exponential in the number of cities, making it a fascinating subject for exploration. This kind of complexity is informally called "hockey-stick growth". As each additional city case is processed in a brute force approach, all previous cases are relegated to be of low complexity in comparison.

In this blog post, we embark on a journey through the world of TSP-solving algorithms, focusing on two primary approaches: brute force and 2-opt. We'll delve into the inner workings of these algorithms, explore their strengths and weaknesses, and compare their performance in solving increasingly complex instances of the TSP.

Brute Force: The Traditional Approach

We kick off our exploration with the brute force algorithm, the most straightforward method for solving the TSP. Brute force systematically evaluates every possible permutation of city visitation order, calculating the total distance traveled for each permutation and selecting the shortest route. While conceptually simple, brute force quickly becomes impractical for large numbers of cities due to its exponential time complexity.

import numpy as np

import matplotlib.pyplot as plt

import time

from itertools import permutations

# Function to solve TSP using brute force

def brute_force_tsp(points):

min_dist = float('inf')

max_dist = 0

best_path = None

all_paths = []

start_time = time.time()

for perm in permutations(points):

dist = sum(np.linalg.norm(np.diff(perm, axis=0), axis=1))

all_paths.append(np.array(perm)) # Convert the tuple to a NumPy array

if dist < min_dist:

min_dist = dist

best_path = perm

if dist > max_dist:

max_dist = dist

end_time = time.time()

return best_path, min_dist, max_dist, all_paths, end_time - start_time

2-Opt: A Smarter Solution

Next, we introduce the 2-opt algorithm, a more sophisticated approach that seeks to improve upon the limitations of brute force. 2-opt operates by iteratively swapping pairs of edges in the current solution, aiming to reduce the total distance traveled. Unlike brute force, 2-opt exhibits polynomial time complexity, making it more scalable for larger problem instances. However, 2-opt does not guarantee optimal solutions and may occasionally converge to suboptimal routes.

# Function to solve TSP using 2-opt heuristic

def tsp_2opt(points):

n = len(points)

path = np.arange(n)

improvement = True

best_dist = sum(np.linalg.norm(np.diff(points, axis=0), axis=1))

while improvement:

improvement = False

for i in range(1, n - 1):

for j in range(i + 1, n):

new_path = path.copy()

new_path[i:j] = path[j - 1:i - 1:-1]

new_dist = sum(np.linalg.norm(np.diff(points[new_path], axis=0), axis=1))

if new_dist < best_dist:

best_dist = new_dist

path = new_path

improvement = True

break

if improvement:

break

return path, best_dist, improvement

Comparative Analysis: Brute Force vs. 2-Opt

With both algorithms in hand, we conduct a comparative analysis to evaluate their performance across various TSP instances. We examine factors such as execution time, solution quality, and scalability, shedding light on the trade-offs between computational efficiency and solution optimality. 

Conclusion: Navigating the TSP Landscape

In conclusion, our exploration of the Traveling Salesman Problem has provided valuable insights into the world of combinatorial optimization. While brute force offers a straightforward and reliable method for finding optimal solutions, its computational demands prove prohibitive for larger problem sizes. In contrast, 2-opt presents a more scalable alternative, leveraging heuristic techniques to efficiently explore solution space. By understanding the nuances of each approach, practitioners can navigate the TSP landscape with confidence, selecting the most appropriate algorithm for their specific requirements.

Join us on this journey as we unravel the complexities of the Traveling Salesman Problem, uncovering the algorithms and strategies that drive computational optimization in the digital age.

The remaining source code is below, it can be run in Google Colab for free!
But beware, it slows down significantly for more than about 8 cities!

# Test cases (number of cities)

test_cases = range(2, 8)

brute_force_runtimes = []

brute_force_shortest_distances = []

brute_force_longest_distances = []

num_paths = []

# Combined demonstration

plt.figure(figsize=(14, 12), facecolor='#99CC99')

for idx, num_points in enumerate(test_cases, start=1):

points = np.random.rand(num_points, 2)

# Solve TSP using brute force approach

best_path_brute_force, min_dist_brute_force, max_dist_brute_force, all_paths_brute_force, brute_force_runtime = brute_force_tsp(points)

brute_force_runtimes.append(brute_force_runtime)

brute_force_shortest_distances.append(min_dist_brute_force)

brute_force_longest_distances.append(max_dist_brute_force)

num_paths.append(len(all_paths_brute_force))

# Plot all attempted paths for brute force

plt.subplot(4, len(test_cases), idx)

for path in all_paths_brute_force:

path_list = path.tolist()

plt.plot(np.append([point[0] for point in path_list], path_list[0][0]),

np.append([point[1] for point in path_list], path_list[0][1]),

color='black', linestyle='-', linewidth=0.5, alpha=0.5)

plt.scatter(points[:,0], points[:,1], color='red', zorder=2)

plt.title(f'Brute Force\nCities: {num_points}\nShortest: {min_dist_brute_force:.2f}\nLongest: {max_dist_brute_force:.2f}', backgroundcolor='#99CC99')

# Solve TSP using 2-opt approach

best_path_2opt, min_dist_2opt, _ = tsp_2opt(points)

# Plot 2-opt path

plt.subplot(4, len(test_cases), len(test_cases) + idx)

plt.plot(np.append(points[best_path_2opt, 0], points[best_path_2opt[0], 0]),

np.append(points[best_path_2opt, 1], points[best_path_2opt[0], 1]),

color='red', linestyle='-', linewidth=1, zorder=3)

plt.scatter(points[:,0], points[:,1], color='red', zorder=2)

plt.title(f'2-Opt\nDistance: {min_dist_2opt:.2f}', backgroundcolor='#99CC99')

plt.tight_layout()

plt.show()

plt.figure(figsize=(7,6), facecolor='#99CC99')

# Plot number of paths as a function of the number of cities

plt.subplot(2, 1, 1)

plt.plot(test_cases, num_paths, marker='o', color='green')

plt.xlabel('Number of Cities')

plt.ylabel('Number of Paths')

plt.title('Number of Paths vs. Number of Cities', backgroundcolor='#99CC99')

# Plot summary graphs

plt.subplot(2, 1, 2)

plt.plot(test_cases, brute_force_runtimes, label='Brute Force', marker='o')

plt.xlabel('Number of Cities')

plt.ylabel('Time (seconds)')

plt.title('Execution Time Comparison', backgroundcolor='#99CC99')

plt.legend()

plt.tight_layout()

plt.show()