TAOCP - The Art Of Computer Programming Reading Group Meetup

https://www.meetup.com/theartofcomputerprogramming

Next TAOCP Meetup

TAOCP #37 - Binary Merge
Saturday, 5 Jun 2021, 2-4pm America/New_York

Next Papers Meetup

Papers #1 - Binomial Heaps, Jean Vuillemin, 1978
Wednesday, 26 May 2021, 7-9pm America/New_York

Description

We are devoted to reading, understanding and working through The Art Of Computer Programming by Donald Knuth (TAOCP). We go through a portion of TAOCP at each meetup. Text is read out and discussed. We work on some simple and medium exercises.

The world is fortunate that over 50 years ago a person like Donald Knuth undertook an epic quest of bringing "readers to the frontiers of knowledge in every [computer science] subject that was treated". Later realizing that "the rapid rise of computer science made such a dream impossible", he decided to "concentrate on classic techniques that are likely to remain important for many more decades, and to describe them as well as [he could]".

We strongly believe Knuth has gathered timeless concepts and explained them with great flair. The material is detailed and rigorous and leavened with humor.

If you feel the same way or would like to know why the ACM Turing Award cited Knuth's TAOCP as having "served as a focal point for developing curricula and as an organizing influence on computer science", please join us in our endeavor to study and learn from TAOCP in a systematic and regular manner.

Anyone may join from anywhere. No programming knowledge is required.

Note on MMIX and MIX

The MMIX is a hypothetical computer designed by Knuth. It is a successor to MIX which is still referred to in all printings of Vols. 1-3 of TAOCP. MMIX is significantly different from MIX. In order to use MMIX instead of MIX now means having to supplement TAOCP with two primary sources.

The first supplement is Fascicle 1, MMIX, a booklet written by Knuth describing the computer and its assembly programming language. It replaces Sections 1.3 and 1.4 of Chapter 1, Basic Concepts. The section numbers in the fascicle have a prime (') suffix to distinguish them from the originals, e.g. fascicle section 1.3.1' replaces TAOCP section 1.3.1.

The second supplement is The MMIX Supplement by Martin Ruckert that has MMIX versions of all programs and content in TAOCP that currently refer to the older MIX computer. It uses the same section numbers as in TAOCP with page references and text snippets from TAOCP to help sync the MMIX version of the content with its location in TAOCP.

Scheduled and Past Meetups

All scheduled meetups in reverse chronological order

TAOCP #37 - Binary Merge (Chapter 5, Sorting: Section 5.3.2)

Caution Short Merge Ahead!

We're looking at optimum sorting. After analyzing what it means to minimize comparisons for sorting, Knuth turns to the related question of how to most efficiently merge two sorted sets in 5.3.2 Minimum-Comparison Merging. This is an optional starred section so expect a bit more math than usual.

We go over couple theorems on the minimum number of comparisons needed for merging from Graham/Karp, Hwang/Lim and Stockmeyer/Yao

We learn the proof technique of an adversary to establish these results

The constrained adversaries approach leads to Algorithm H (Binary merge) also from Hwang and Lim that takes its name from an application of binary search

We'll do some exercises

This event will be recorded and posted to YouTube as a public video at https://www.youtube.com/channel/UCHOHy9Rjl3MlEfZ2HI0AD3g

Keep the conversation going!

Facebook: https://www.facebook.com/groups/678335496099220<br> IRC ##taocp: https://webchat.freenode.net/##taocp

Date: Saturday, 5 Jun 2021
Time: 2-4pm America/New_York

Agenda

2:00 - 2:10 Meet and greet
2:10 - 3:00 Read and discuss couple pages at a time from Chapter 5, Sorting (along with MMIX Supplement)

• 5.3.2 Minimum-Comparison Merging (197-204)
  • What is the best way to merge two ordered sets? (197)
  • Theorem M (198)
  • Constructing lower bounds, constrained adversaries (198-199)
  • An adversary for merging, Strategy A (199)
  • All strategies (199)
  • Constraints on the strategies (200)
  • Lower bounds on merging from the adversary, Table 1 (200-202)
  • Theorem K (202)
  • Upper bounds on merging (202-203)
  • Algorithm H (Binary merging), Table 2 (203)
  • Analysis of Algorithm H (204)

3:00 - 3:10 Break
3:10 - 4:00

• Exercises
  • Volume 3 (205-207)
• Shoot the breeze

TAOCP #36 - Merge Insertion Sort (Chapter 5, Sorting: Section 5.3.1)

It's The Best Sort, Don - The Best!

Knuth - "Of course there is no best possible way to sort"

What Knuth offers instead are three sections on minimizing the number of comparisons while sorting, merging or selecting

We look at the first section under 5.3 Optimum Sorting in this meetup - 5.3.1 Minimum-Comparison Sorting

We introduce comparison trees to establish a theoretical framework for analyzing comparison-based sorting techniques

Then we consider two problems - finding comparison trees that minimize the maximum number of comparisons made - similarly those that minimize the average number of comparisons

More concretely we learn merge insertion sort that came about as a generalization of a solution to the question - "What is the best way to sort five elements? Can five elements be sorted using only seven comparisons?"

We'll do some exercises

This event will be recorded and posted to YouTube as a public video at https://www.youtube.com/channel/UCHOHy9Rjl3MlEfZ2HI0AD3g

Keep the conversation going!

Facebook: https://www.facebook.com/groups/678335496099220<br> IRC ##taocp: https://webchat.freenode.net/##taocp

Date: Saturday, 29 May 2021
Time: 2-4pm America/New_York

Agenda

2:00 - 2:10 Meet and greet
2:10 - 3:00 Read and discuss couple pages at a time from Chapter 5, Sorting (along with MMIX Supplement)

• 5.3. Optimum Sorting/5.3.1 Minimum-Comparison Sorting (pp.180-187, 192-193)
  • Binary comparison tree (pp.180-182)
  • The best worst case (pp.182-184)
  • Merge insertion (pp.184-185)
  • Analysis of merge insertion sort (pp.185-187)
  • The average number of comparisons (pp.192-193)

3:00 - 3:10 Break
3:10 - 4:00

• Exercises
  • Volume 3 (pp.193-197)
  • MMIX Supplement (p.94)
• Shoot the breeze

Papers #1 - Binomial Heaps, Jean Vuillemin, 1978

Title: A Data Structure for Manipulating Priority Queues
Authors: Jean Vuillemin
Year: 1978
Length: 6 pages
Citation: Communications of the ACM, April 1978, 309-315
Paper: https://dl.acm.org/doi/abs/10.1145/359460.359478

Welcome to our first TAOCP Papers meetup!

TAOCP Papers is an irregular series of meetups on papers on algorithms and data structures related to TAOCP

These could be papers mentioned in TAOCP - like today's selection - or papers that expand on a topic Knuth has covered in TAOCP

The Papers meetup will typically be scheduled on weekdays at 7p New York time - the format is much the same as the main TAOCP meetup - we'll read a bit and discuss - and repeat

It's expected the portions we discuss at a time will be much smaller than couple pages since papers tend to be more dense than a text like TAOCP - it's quite possible some papers may need more than one session

Our regular Saturday afternoon TAOCP meetup continues with no change

Today's paper on binomial heaps - called binomial queues in the paper - is one of the "new ways to represent priority queues" that Knuth mentions in 5.2.3 Sorting by Selection

Along with Fibonacci heaps they are implemented in Knuth's Stanford GraphBase library for graph algorithms development

Supplementary Resources:

• Binomial heaps are based on binomial trees which are covered in 7.2.1.3 Generating all combinations, TAOCP Volume 4A, Combinatorial Algorithms, Part 1

• Binomial heaps are the subject of a lecture on 15 Apr 2021 in CS166, Data Structures, Spring 2021 at Stanford - accompanied by an excellent set of slides at https://web.stanford.edu/class/cs166

This event will be recorded and posted to YouTube as a public video at https://www.youtube.com/channel/UCHOHy9Rjl3MlEfZ2HI0AD3g

Keep the conversation going!

Facebook: https://www.facebook.com/groups/678335496099220<br> IRC ##taocp: https://webchat.freenode.net/##taocp

Date: Wednesday, 26 May 2021
Time: 7-9pm America/New_York

Agenda

7:00 - 7:10 Meet and greet
7:10 - 8:00 Read and discuss a bit at a time

• A Data Structure for Manipulating Priority Queues (pp.309-314)
  • 1 Introduction (p.309)
  • INSERT, DELETE, MIN, UPDATE, UNION operations (pp.309-310)
  • 2 Binomial Trees and Forests, Fig 1, 2, 3 (pp.310-311)
  • 3 Binomial Queues (p.311)
  • UNION algorithm, Fig 4, 5 (p.311)
  • INSERT algorithm (pp.311-312)
  • DELETE algorithm, Fig 6, 7 (p.312)

8:00 - 8:10 Break
8:10 - 9:00 Continue reading and discussing

• UPDATE algorithm (pp.312-313)
• 4 Implementation of Binomial Forests as Binary Trees, Fig 8 (p.313)
• UNION pseudocode (pp.313-314)
• DELETE/EXTRACTMIN pseudocode (p.314)

TAOCP #35 - Priority Queues (Chapter 5, Sorting: Section 5.2.3)

Top Of The Heap!

We saw in TAOCP #34 how a heap - a tree with of keys K_1, ..., K_N with the heap condition

--------------------- K_⌊j/2⌋ >= K_j for 1 <= ⌊j/2⌋ < j <= N -------------------

may be used to sort the keys in a guaranteed worst case time of O(N * log(N))

This time we look at priority queues - another application where heaps shine

Priority queues are convenient data structures for whenever data arrives in an unpredictable way but has to be processed in a known priority order. Priority may be time or distance or some measure of the importance of the