{ "cells": [ { "cell_type": "markdown", "id": "ch15-title", "metadata": {}, "source": [ "# Algorithms" ] }, { "cell_type": "markdown", "id": "ch15-overview", "metadata": {}, "source": [ "This chapter introduces algorithm foundations using a simple input-process-output model.\n", "\n", "- Algorithm steps as input, process, and output\n", "- Sequence, decision, and repetition as control patterns\n", "- Runtime measurement and Big O growth\n", "- Search algorithms and tradeoffs\n", "- Sorting algorithms and benchmark patterns\n" ] }, { "cell_type": "markdown", "id": "1500-video", "metadata": {}, "source": [ "

Chapter Video

\n", "\n", "This overview introduces algorithmic thinking, searching, sorting, and Big O reasoning.\n", "\n", "```{raw} html\n", "\n", "```\n", "\n", "> *[Algorithms and Data Structures Tutorial - Full Course for Beginners (5:22:08)](https://youtube.com/watch?v=8hly31xKli0) by freeCodeCamp.org*\n", ">\n", "> Hosted on YouTube; property of its original creator, embedded here for educational reference only." ] }, { "cell_type": "markdown", "id": "ch15-goals", "metadata": {}, "source": [ "

Learning Objectives

\n", "\n", "By the end of this chapter, you will be able to:\n", "\n", "1. Describe an algorithm as input, process, and output, and check it against the properties of finiteness, definiteness, and effectiveness\n", "2. Analyze the time complexity of simple functions and classify their growth with Big O notation, from $O(1)$ to $O(n^2)$\n", "3. Implement and trace linear search and binary search, and explain why binary search requires sorted input\n", "4. Choose a search strategy (linear search, binary search, `bisect`, or hash-based lookup) from data order, lookup count, and memory constraints\n", "5. Implement insertion sort and merge sort, compare them with quicksort, and sort real data with `sorted()` and `list.sort()` using key functions\n", "6. Measure algorithm performance with `time.perf_counter()` and `timeit`, and compare the measured results with Big O predictions\n" ] }, { "cell_type": "markdown", "id": "ch15-flow", "metadata": {}, "source": [ "

Chapter Flow

\n", "\n", "```{container} chapter-flow\n", "1. {doc}`1401-algorithms`\n", "2. {doc}`1402-searching`\n", "3. {doc}`1403-sorting`\n", "```" ] }, { "cell_type": "markdown", "id": "ch14-glossary", "metadata": {}, "source": [ "

Glossary

\n", "\n", "| # | Term | Explanation |\n", "|---:|---|---|\n", "| 1 | Algorithm | A step-by-step procedure for solving a problem or completing a task. |\n", "| 2 | Input | The data an algorithm receives before it runs. |\n", "| 3 | Output | The result an algorithm produces. |\n", "| 4 | Correctness | Whether an algorithm produces the right output for valid inputs. |\n", "| 5 | Complexity | A description of how an algorithm's resource use grows with input size. |\n", "| 6 | Time complexity | How running time grows as input size grows. |\n", "| 7 | Space complexity | How memory use grows as input size grows. |\n", "| 8 | Big O notation | A notation for describing an algorithm's growth rate at a high level. |\n", "| 9 | Constant time | A growth pattern where work does not depend on input size. |\n", "| 10 | Linear time | A growth pattern where work grows in direct proportion to input size. |\n", "| 11 | Logarithmic time | A growth pattern where each step greatly reduces the remaining search space. |\n", "| 12 | Benchmarking | Measuring code performance by running timed experiments. |\n", "| 13 | Linear search | A search algorithm that checks items one at a time. |\n", "| 14 | Binary search | A search algorithm that repeatedly halves a sorted search space. |\n", "| 15 | `bisect` | A standard-library module for searching and inserting in sorted sequences. |\n", "| 16 | Hash-based lookup | Finding values through a hash table, commonly using a `set` or `dict`. |\n", "| 17 | Sorting | Rearranging values into an order. |\n", "| 18 | Stability | A sorting property that preserves the relative order of equal-key items. |\n", "| 19 | In-place sort | A sort that rearranges the original list instead of returning a full separate copy. |\n", "| 20 | Divide and conquer | A design strategy that solves a problem by splitting it into smaller subproblems. |\n", "| 21 | Quadratic time | A growth pattern, O(n^2), where work grows with the square of the input size, typical of nested loops. |\n", "| 22 | Linearithmic time | A growth pattern, O(n log n), typical of efficient comparison sorts such as merge sort. |\n", "| 23 | Insertion sort | A sorting algorithm that builds a sorted section one item at a time by sliding each new item left into place. |\n", "| 24 | Bubble sort | A sorting algorithm that repeatedly swaps adjacent out-of-order pairs until a full pass makes no swaps. |\n", "| 25 | Merge sort | A divide-and-conquer sort that splits a list in half, sorts each half, and merges the sorted halves. |\n", "| 26 | Quicksort | A divide-and-conquer sort that partitions items around a pivot and recursively sorts the smaller and larger groups. |\n", "| 27 | Pivot | The element quicksort uses to partition the other items into smaller, equal, and larger groups. |\n", "| 28 | Timsort | The stable hybrid of merge sort and insertion sort that Python's `sorted()` and `list.sort()` use. |\n", "| 29 | Key function | A function passed as `key=` to a sort that computes the value used to compare each item. |\n", "| 30 | Counting sort | A non-comparison sort that tallies how often each integer value occurs and rebuilds the list from the counts in O(n + k) time. |\n" ] }, { "cell_type": "markdown", "id": "1500-slides", "metadata": {}, "source": [ "

Chapter Overview Slides

" ] } ], "metadata": { "kernelspec": { "display_name": ".venv (3.13.7)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.13.7" } }, "nbformat": 4, "nbformat_minor": 5 }