example-en.typ

// example-en.typ — English-language demo (mirror of example.typ with lang: "en").
// Compile: typst compile example-en.typ
#import "lib.typ": *

#show: textbook.with(
  title: "Algorithms and Data Structures",
  subtitle: "From Mathematical Foundations to Engineering Practice",
  author: "Wei Zhang",
  series: "Foundations of Computer Science",
  publisher: "Example University Press",
  lang: "en", // switches every label: Theorem / Chapter 1 / Contents / IEEE refs…
)

#front-matter[
  #preface[
    This book demonstrates every feature of the template: chapter openers, a
    color-coded theorem system, code blocks with a filename tab and line
    numbers, console output, auto-collected exercise answers, an index, and
    IEEE-style references. The first line of each paragraph is indented.

    Quotations and emphasis use an italic face, for example:
    #emph[Programs must be written for people to read, and only incidentally
    for machines to execute.]
  ]
  #table-of-contents()
]

#main-matter[

#part("Mathematical Foundations")

#chapter("Sets and Logic", label: "ch:sets")

#overview[
  Sets are the language every later chapter speaks. We fix notation for the
  basic operations, prove one law completely, and record the mistake readers
  most often make when negating a quantifier.
]

Sets#index("set")#gls("set", def: [a collection of distinct objects]) are the common language of modern mathematics. This chapter is
a minimal example covering the definition, theorem, proposition, lemma, proof,
note, and exercise environments.

== Set Operations

#definition(title: "Union")[
  Let $A, B$ be sets. Define $A union B = {x mid(|) x in A or x in B}$.
] <def:union>

#intuition[
  Complementing a union should leave only the elements that escaped *both*
  sets — so the union turns into an intersection.
]

#theorem(title: "De Morgan's Law")[
  For any sets $A, B$ and universe $U$,
  $ (A union B)^c = A^c inter B^c. $ <eq:demorgan>
] <thm:demorgan>

#proof[
  Take any $x in (A union B)^c$; then $x in.not A$ and $x in.not B$, so
  $x in A^c inter B^c$. The reverse inclusion is analogous.
]

#lemma[If $A subset B$, then $B^c subset A^c$.] <lem:contra>

#proposition[
  Union distributes over intersection:
  $A union (B inter C) = (A union B) inter (A union C)$.
] <prop:distrib>

#note[@eq:demorgan also holds for the union of arbitrarily many sets.]

#pitfall[
  "The complement of a union is the union of the complements." It is the
  _intersection_ — see @thm:demorgan. Swapping the two is the most common slip
  in a first proof course.
]

A display used purely for layout should not consume an equation number, so wrap
it in `unnumbered`:
#unnumbered[
  $ A union B = B union A. $
]

#exercises-heading()

#exercise(solution: [Verify pointwise from the definition of complement.])[
  Prove that $(A inter B)^c = A^c union B^c$.
]

#part("Programming")

#chapter("Sorting Algorithms", label: "ch:sorting")

Sorting#index("sorting", see-also: "algorithm")#gls("sorting", def: [rearranging elements into a given order]) is fundamental to data processing. Quicksort#index("sorting!quicksort")
was proposed by Hoare @clrs and runs in expected time
$O(n log n)$#gls($O(n log n)$, def: [the expected running time of quicksort], group: "notation", sort: "O"). Inline code
style: call `quicksort(a)` to sort in place.

Cross-chapter references resolve against the target, not the citing page: the
set-theory material is @ch:sets, its central result is @thm:demorgan with
@eq:demorgan, and the supporting facts are @lem:contra, @prop:distrib, and
@def:union. Notation lives in @app:notation, tabulated in @tab:notation.

== Quicksort

#code(filename: "quicksort.py", caption: [A Python implementation of quicksort])[
```python
def quicksort(a, lo=0, hi=None):
    """In-place quicksort."""
    if hi is None:
        hi = len(a) - 1
    if lo >= hi:
        return
    p = partition(a, lo, hi)  # partition around the pivot
    quicksort(a, lo, p - 1)
    quicksort(a, p + 1, hi)
```
]

#console[```
$ python quicksort.py
input:  [9, 3, 7, 4, 1, 8]
output: [1, 3, 4, 7, 8, 9]
```]

#algorithm(title: "Quicksort", input: [array $a$, range $[l, h]$], output: [$a$ in ascending order])[
  + #alg-if($h - l <= 0$)[
      + #alg-return[]
    ]
  + choose a random pivot and partition in place, obtaining pivot position $p$
  + #alg-for([each subrange $[l, p-1]$, $[p+1, h]$])[
      + sort that range recursively
    ]
] <alg:quicksort>

#example(title: "Lower bound for 8 elements")[
  When $n = 8$, $ceil(log_2 8!) = 16$, so any comparison sort needs at least 16
  comparisons in the worst case.
] <ex:lower-bound>

The steps above are @alg:quicksort and the counting argument is @ex:lower-bound;
both are numbered within this chapter and referenced by label.

#warning[
  The worst case (already-sorted input with a fixed pivot) degrades to $O(n^2)$;
  always randomize the pivot.
]

#exercises-heading()

#exercise(solution: [Partition around 9 first, then recurse; 15 comparisons in total.])[
  Trace quicksort by hand on the array $[9, 3, 7, 4, 1, 8]$ and count the
  comparisons.
]
#exercise[Prove that 7 comparisons are both necessary and sufficient to sort
  5 distinct elements.]

]

#appendix[
  #chapter("Notation", label: "app:notation")

  #figure(
    table(
      columns: (auto, 1fr),
      [$O(f)$], [asymptotic upper bound],
      [$Omega(f)$], [asymptotic lower bound],
      [$Theta(f)$], [asymptotic tight bound],
    ),
    caption: [Common notation],
  ) <tab:notation>
]

#answers()
// The bibliography path must be resolved here, in your own file — pass bytes.
#references(read("refs.bib", encoding: none), full: true)
#make-glossary()
#make-glossary(group: "notation")
#make-index()