<?xml version="1.0"?>
<feed xmlns="http://www.w3.org/2005/Atom" xml:lang="de">
	<id>https://staging.moocwiki.org/index.php?action=history&amp;feed=atom&amp;title=English%3AData_Structures_and_Algorithms</id>
	<title>English:Data Structures and Algorithms - Versionsgeschichte</title>
	<link rel="self" type="application/atom+xml" href="https://staging.moocwiki.org/index.php?action=history&amp;feed=atom&amp;title=English%3AData_Structures_and_Algorithms"/>
	<link rel="alternate" type="text/html" href="https://staging.moocwiki.org/index.php?title=English:Data_Structures_and_Algorithms&amp;action=history"/>
	<updated>2026-09-04T04:16:01Z</updated>
	<subtitle>Versionsgeschichte dieser Seite in MOOCsWiki Staging</subtitle>
	<generator>MediaWiki 1.46.0</generator>
	<entry>
		<id>https://staging.moocwiki.org/index.php?title=English:Data_Structures_and_Algorithms&amp;diff=48973&amp;oldid=prev</id>
		<title>Glanz: aiMOOC über GPT aiMOOC Action erstellt</title>
		<link rel="alternate" type="text/html" href="https://staging.moocwiki.org/index.php?title=English:Data_Structures_and_Algorithms&amp;diff=48973&amp;oldid=prev"/>
		<updated>2026-08-31T20:46:29Z</updated>

		<summary type="html">&lt;p&gt;aiMOOC über GPT aiMOOC Action erstellt&lt;/p&gt;
&lt;p&gt;&lt;b&gt;Neue Seite&lt;/b&gt;&lt;/p&gt;&lt;div&gt;{{T}}&lt;br /&gt;
[[Category:English]]&lt;br /&gt;
[[Category:Data Structures and Algorithms]]&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
= Introduction =&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Data Structures and Algorithms&amp;#039;&amp;#039;&amp;#039; studies how you organize information and how you design procedures that transform, search, rank, connect, and optimize that information. At university level, the central question is not only whether a program works, but whether its underlying method is correct, efficient, scalable, and appropriate for the constraints of the problem.&lt;br /&gt;
&lt;br /&gt;
A [[English:Data structure|data structure]] specifies how data and relationships are represented so that operations can be carried out efficiently. An [[English:Algorithm|algorithm]] is a finite procedure for producing an output from an input. The two ideas are inseparable: a strong algorithm often depends on choosing a representation that makes its critical operations inexpensive.&lt;br /&gt;
&lt;br /&gt;
MIT&amp;#039;s undergraduate algorithms curriculum similarly emphasizes mathematical modeling, common data structures and algorithmic paradigms, the relationship between algorithms and programming, and performance analysis. In this aiMOOC you will move between abstract models, concrete implementations, proofs, experiments, and design decisions.&lt;br /&gt;
&lt;br /&gt;
{{#ev:youtube|https://www.youtube.com/watch?v=ZA-tUyM_y7s|500|center}}&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
= Learning Objectives =&lt;br /&gt;
&lt;br /&gt;
After working through this course, you should be able to explain and compare common data structures, analyze asymptotic running time and space, justify algorithmic correctness, select suitable structures for a stated workload, implement representative algorithms, and evaluate empirical performance against theoretical expectations.&lt;br /&gt;
&lt;br /&gt;
You should also be able to recognize recurring design paradigms such as [[English:Divide-and-conquer algorithm|divide and conquer]], [[English:Greedy algorithm|greedy methods]], [[English:Dynamic programming|dynamic programming]], and graph traversal, and explain when their assumptions do or do not fit a problem.&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
= Foundations: Problems, Algorithms, and Representations =&lt;br /&gt;
&lt;br /&gt;
A computational problem describes acceptable outputs for possible inputs. An algorithm solves the problem when it produces a correct output for every valid input covered by the specification. A program is an implementation of an algorithm in a concrete language and runtime environment.&lt;br /&gt;
&lt;br /&gt;
A data structure is more than a container. It combines stored values, relationships among those values, and supported operations. The same abstract data type can have several representations. For example, a sequence may be represented by a contiguous dynamic array or by linked nodes. Both support ordered elements, but they distribute costs differently across indexing, insertion, deletion, memory allocation, and locality.&lt;br /&gt;
&lt;br /&gt;
This distinction between &amp;#039;&amp;#039;&amp;#039;interface&amp;#039;&amp;#039;&amp;#039; and &amp;#039;&amp;#039;&amp;#039;representation&amp;#039;&amp;#039;&amp;#039; is essential. An [[English:Abstract data type|abstract data type]] tells you what operations mean; a representation determines how those operations are implemented and therefore influences their cost.&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
== Correctness Before Speed ==&lt;br /&gt;
&lt;br /&gt;
Efficiency matters only after correctness. A rigorous algorithmic argument usually states the precondition, the desired postcondition, and why each step preserves the properties required to reach that postcondition.&lt;br /&gt;
&lt;br /&gt;
For iterative algorithms, a [[English:Loop invariant|loop invariant]] can capture what remains true before and after each iteration. For recursive algorithms, correctness is often established by induction on the input size or on the recursion structure. For greedy algorithms, you usually need an exchange argument or another proof that a locally optimal choice can be part of some globally optimal solution. For dynamic programming, you must justify optimal substructure and a recurrence over overlapping subproblems.&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
= Complexity Analysis =&lt;br /&gt;
&lt;br /&gt;
Algorithm analysis predicts how resource consumption grows with input size. The most common resource is running time, but memory use, I/O operations, communication, cache behavior, and parallel work may also matter.&lt;br /&gt;
&lt;br /&gt;
[[English:Big O notation|Big O]] gives an asymptotic upper bound. [[English:Big Omega notation|Big Omega]] gives a lower bound, and [[English:Big Theta notation|Big Theta]] gives a tight asymptotic bound when both upper and lower bounds match. These notations suppress constant factors and lower-order terms so that growth trends become visible.&lt;br /&gt;
&lt;br /&gt;
For example, scanning every element of an array is typically linear in its length. Binary search on a sorted random-access sequence repeatedly halves the candidate range, giving logarithmic search time. Merge sort divides the input into subproblems and performs linear merging at each logarithmic level, giving a typical bound of Theta n log n.&lt;br /&gt;
&lt;br /&gt;
The relevant complexity model depends on the operations counted. A comparison-based sorting lower bound differs from a word-RAM analysis of integer sorting. Likewise, a hash-table operation is often discussed in expected amortized time rather than as a deterministic worst-case guarantee.&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
== Worst Case, Average Case, and Amortized Analysis ==&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Worst-case analysis&amp;#039;&amp;#039;&amp;#039; bounds the cost of the most expensive valid input of a given size. &amp;#039;&amp;#039;&amp;#039;Average-case analysis&amp;#039;&amp;#039;&amp;#039; requires an explicit probability distribution over inputs or operations. &amp;#039;&amp;#039;&amp;#039;Expected analysis&amp;#039;&amp;#039;&amp;#039; may instead average over internal random choices made by the algorithm or data structure.&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Amortized analysis&amp;#039;&amp;#039;&amp;#039; studies a sequence of operations and shows that occasional expensive operations can be spread over many cheap ones. Dynamic-array resizing is a classic example: a single resize can cost linear time, but geometrically increasing capacity allows repeated append operations to have constant amortized cost under standard assumptions.&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
= Linear Data Structures =&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
== Arrays and Dynamic Arrays ==&lt;br /&gt;
&lt;br /&gt;
An [[English:Array data structure|array]] stores elements in contiguous positions, which supports constant-time indexed access in the standard random-access model. This locality often interacts well with caches. However, inserting near the front or middle of a packed array may require shifting many later elements.&lt;br /&gt;
&lt;br /&gt;
A dynamic array keeps extra capacity and periodically allocates a larger block when it fills. This trades unused space and occasional copying for efficient indexing and amortized appends. When you analyze such a structure, distinguish logical length from allocated capacity.&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
== Linked Lists ==&lt;br /&gt;
&lt;br /&gt;
A [[English:Linked list|linked list]] stores elements in nodes connected by references. A singly linked list lets each node point to its successor. With a pointer to the correct position, local insertion or deletion can avoid shifting the rest of the sequence. In contrast, finding the element at an arbitrary index generally requires traversal from a known node.&lt;br /&gt;
&lt;br /&gt;
[[File:Singly-linked-list.svg|500px|frameless|center]]&lt;br /&gt;
&lt;br /&gt;
Linked structures can be useful when stable node identities or frequent local updates matter, but their pointer overhead and weak locality can make them less attractive than arrays in practice. Complexity notation does not automatically capture these machine-level effects, so theory and measurement should inform each other.&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
== Stacks and Queues ==&lt;br /&gt;
&lt;br /&gt;
A [[English:Stack data structure|stack]] uses last-in, first-out behavior. Typical operations are push, pop, and access to the top. Stacks appear in function-call management, expression evaluation, undo mechanisms, and depth-first exploration.&lt;br /&gt;
&lt;br /&gt;
[[File:Data stack.svg|500px|frameless|center]]&lt;br /&gt;
&lt;br /&gt;
A [[English:Queue data structure|queue]] uses first-in, first-out behavior. Typical operations are enqueue and dequeue. Queues support scheduling, buffering, breadth-first search, and event processing.&lt;br /&gt;
&lt;br /&gt;
[[File:Data Queue.svg|500px|frameless|center]]&lt;br /&gt;
&lt;br /&gt;
A deque generalizes both ideas by allowing insertion and removal at both ends. Choosing an implementation such as a circular buffer or linked structure changes the practical and theoretical cost profile.&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
= Associative Structures and Hashing =&lt;br /&gt;
&lt;br /&gt;
A [[English:Associative array|map]] or dictionary associates keys with values. The goal is usually to support search, insertion, and deletion by key. Two major implementation families are hash tables and search trees.&lt;br /&gt;
&lt;br /&gt;
A [[English:Hash table|hash table]] applies a hash function to map a key into a table position. Because several keys can map to the same position, collisions must be handled. Common strategies include separate chaining and open addressing.&lt;br /&gt;
&lt;br /&gt;
[[File:Hash table 5 0 1 1 1 1 1 LL.svg|500px|frameless|center]]&lt;br /&gt;
&lt;br /&gt;
With a suitable hash function and controlled load factor, hash tables offer expected constant-time operations in many standard models. That claim is not the same as a universal worst-case guarantee. Poor hashing, adversarial inputs, or excessive loading can degrade performance. Resizing policies also introduce amortized costs.&lt;br /&gt;
&lt;br /&gt;
Hashing is especially suitable when you need key-based lookup but do not require ordered traversal. If you need predecessor queries, sorted iteration, or range queries, a balanced search tree may be more appropriate.&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
= Trees, Search Trees, and Heaps =&lt;br /&gt;
&lt;br /&gt;
A [[English:Tree data structure|tree]] represents hierarchical relationships. In a rooted tree, every node except the root has a parent, and nodes may have children. Trees model file systems, syntax, spatial partitions, search spaces, indexes, and many other structures.&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
== Binary Search Trees ==&lt;br /&gt;
&lt;br /&gt;
A [[English:Binary search tree|binary search tree]] maintains an ordering property: keys in the left subtree precede the node&amp;#039;s key and keys in the right subtree follow it, according to the chosen ordering relation.&lt;br /&gt;
&lt;br /&gt;
[[File:Bin-search-tree.svg|500px|frameless|center]]&lt;br /&gt;
&lt;br /&gt;
Search, insertion, and deletion take time proportional to the tree height. If the tree becomes a long chain, that height can be linear. Balanced variants such as [[English:AVL tree|AVL trees]] and [[English:Red–black tree|red-black trees]] control height so that fundamental ordered-set operations remain logarithmic.&lt;br /&gt;
&lt;br /&gt;
Binary search trees support operations that hash tables do not naturally provide, including ordered traversal, predecessor and successor queries, and range reporting.&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
== Heaps and Priority Queues ==&lt;br /&gt;
&lt;br /&gt;
A [[English:Heap data structure|heap]] is commonly used to implement a [[English:Priority queue|priority queue]]. In a binary min-heap, every node&amp;#039;s key is no greater than the keys of its children. The minimum is therefore stored at the root.&lt;br /&gt;
&lt;br /&gt;
A binary heap is usually stored compactly in an array. Parent and child relationships can be computed from indices, avoiding explicit pointers. In a standard binary heap, finding the minimum is constant time, while insertion and extracting the minimum take logarithmic time.&lt;br /&gt;
&lt;br /&gt;
Priority queues are important in scheduling, event simulation, graph algorithms such as Dijkstra&amp;#039;s algorithm, and best-first search.&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
= Searching and Sorting =&lt;br /&gt;
&lt;br /&gt;
Searching and sorting expose the connection between problem assumptions and algorithm choice. A linear search works on an unsorted sequence but may inspect every element. [[English:Binary search algorithm|binary search]] is much faster asymptotically, but it requires an ordered random-access structure and careful maintenance of search boundaries.&lt;br /&gt;
&lt;br /&gt;
{{#ev:youtube|https://www.youtube.com/watch?v=6Svu_ae5ebk|500|center}}&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
== Merge Sort and Divide and Conquer ==&lt;br /&gt;
&lt;br /&gt;
[[English:Merge sort|merge sort]] divides the input into smaller sequences, recursively sorts them, and merges the sorted results. The merge step is linear in the combined size, and the recursion has logarithmic depth for balanced splits. The resulting running time is Theta n log n in the standard comparison model.&lt;br /&gt;
&lt;br /&gt;
[[File:Merge sort animation.gif|500px|frameless|center]]&lt;br /&gt;
&lt;br /&gt;
Divide and conquer is broader than sorting. The paradigm separates a problem into subproblems, solves them, and combines their solutions. The design challenge is to choose subproblems and combination work that improve total complexity.&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
== Quicksort and Input Sensitivity ==&lt;br /&gt;
&lt;br /&gt;
[[English:Quicksort|quicksort]] partitions elements around a pivot and recursively sorts the resulting parts. Its performance depends on partition quality. Balanced partitions give logarithmic recursion depth and Theta n log n work, while highly unbalanced partitions can lead to quadratic worst-case time.&lt;br /&gt;
&lt;br /&gt;
[[File:Sorting quicksort anim.gif|500px|frameless|center]]&lt;br /&gt;
&lt;br /&gt;
Randomized pivot selection or carefully designed pivot rules reduce the likelihood of systematically poor partitions. Quicksort also illustrates why asymptotic analysis and implementation details both matter: memory locality and in-place partitioning can make it attractive in practice.&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
= Graphs and Graph Algorithms =&lt;br /&gt;
&lt;br /&gt;
A [[English:Graph data structure|graph]] consists of vertices and edges. Edges may be directed or undirected, and they may carry weights. Graphs represent transportation networks, dependencies, communication links, social relations, state spaces, and many other systems.&lt;br /&gt;
&lt;br /&gt;
Common representations include adjacency lists and adjacency matrices. An adjacency list is space-efficient for sparse graphs, while an adjacency matrix offers constant-time edge-existence tests at the cost of quadratic storage in the number of vertices.&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
== Breadth-First Search ==&lt;br /&gt;
&lt;br /&gt;
[[English:Breadth-first search|breadth-first search]] explores vertices by increasing number of edges from a source in an unweighted graph. A queue stores the frontier. With adjacency lists, BFS runs in linear time in the number of vertices plus edges.&lt;br /&gt;
&lt;br /&gt;
[[File:Animated BFS.gif|500px|frameless|center]]&lt;br /&gt;
&lt;br /&gt;
BFS can construct a shortest-path tree in an unweighted graph because the first discovery of a vertex occurs through a path with the minimum number of edges.&lt;br /&gt;
&lt;br /&gt;
{{#ev:youtube|https://www.youtube.com/watch?v=oFVYVzlvk9c|500|center}}&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
== Depth-First Search ==&lt;br /&gt;
&lt;br /&gt;
[[English:Depth-first search|depth-first search]] follows one branch as far as possible before backtracking. It can be implemented recursively or with an explicit stack. DFS supports connected-component analysis, cycle detection, topological sorting in directed acyclic graphs, and structural exploration.&lt;br /&gt;
&lt;br /&gt;
[[File:Depth-First-Search.gif|500px|frameless|center]]&lt;br /&gt;
&lt;br /&gt;
Both BFS and DFS run in linear time in vertices plus edges when adjacency lists are used, but they reveal different structural information because their frontier disciplines differ.&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
== Shortest Paths and Dijkstra&amp;#039;s Algorithm ==&lt;br /&gt;
&lt;br /&gt;
For graphs with nonnegative edge weights, [[English:Dijkstra&amp;#039;s algorithm|Dijkstra&amp;#039;s algorithm]] repeatedly settles the unsettled vertex with minimum tentative distance and relaxes its outgoing edges. A priority queue can make this selection efficient.&lt;br /&gt;
&lt;br /&gt;
[[File:Dijkstra Animation.gif|500px|frameless|center]]&lt;br /&gt;
&lt;br /&gt;
Dijkstra&amp;#039;s algorithm depends critically on nonnegative edge weights. If negative edges are allowed, the greedy settling argument fails and another algorithm such as Bellman-Ford may be required. This is a good example of an assumption that belongs in both the problem specification and the correctness proof.&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
= Algorithmic Design Paradigms =&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
== Greedy Algorithms ==&lt;br /&gt;
&lt;br /&gt;
A greedy algorithm builds a solution through locally preferred choices. Greedy methods can be elegant and fast, but a plausible local rule is not enough. You need a proof that the rule preserves the possibility of an optimal global solution.&lt;br /&gt;
&lt;br /&gt;
Examples include Kruskal&amp;#039;s and Prim&amp;#039;s minimum-spanning-tree algorithms and Dijkstra&amp;#039;s algorithm under nonnegative weights. Greedy reasoning often uses exchange arguments, cut properties, or structural invariants.&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
== Dynamic Programming ==&lt;br /&gt;
&lt;br /&gt;
[[English:Dynamic programming|dynamic programming]] is useful when a problem has overlapping subproblems and an exploitable recurrence. A top-down method stores results through memoization, while a bottom-up method fills a table in an order that guarantees dependencies are already available.&lt;br /&gt;
&lt;br /&gt;
A good dynamic-programming design identifies the state, recurrence, base cases, evaluation order, and reconstruction information. Complexity then follows from the number of distinct states multiplied by the work per state.&lt;br /&gt;
&lt;br /&gt;
Dynamic programming is not simply recursion with caching. The state must capture enough information to make subproblems independent of the earlier path used to reach them.&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
== Recursion and Recurrence Relations ==&lt;br /&gt;
&lt;br /&gt;
Recursive algorithms solve instances in terms of smaller instances. Their running time is often described by a [[English:Recurrence relation|recurrence relation]]. For example, a balanced divide-and-conquer recurrence may combine two half-size subproblems with linear merge work.&lt;br /&gt;
&lt;br /&gt;
Recursion also consumes call-stack space unless optimized or transformed. An iterative formulation may preserve the same asymptotic time while changing memory behavior and practical constants.&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
= Choosing the Right Structure =&lt;br /&gt;
&lt;br /&gt;
Algorithm design is a workload-matching problem. Ask which operations dominate, what order properties are required, whether the input is static or dynamic, how large the data may become, whether worst-case guarantees matter, and what the machine environment makes expensive.&lt;br /&gt;
&lt;br /&gt;
A dynamic array is often strong for indexed traversal and append-heavy workloads. A linked list can favor local structural updates when a node is already known. A hash table favors expected key lookup without ordering. A balanced tree favors ordered dictionaries and range operations. A heap favors repeated access to an extreme-priority element. A graph representation should reflect density and the algorithms you intend to run.&lt;br /&gt;
&lt;br /&gt;
There is no universally best data structure. The right choice follows from the required operations and guarantees.&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
= From Theory to Implementation =&lt;br /&gt;
&lt;br /&gt;
Real implementations introduce concerns beyond asymptotic notation: memory allocation, cache locality, branch prediction, object overhead, integer width, recursion limits, language runtime behavior, and constant factors. These effects do not invalidate asymptotic analysis; they answer a different level of the performance question.&lt;br /&gt;
&lt;br /&gt;
A useful university-level workflow is to state the model, prove correctness, derive an asymptotic bound, implement the method, construct informative tests, measure performance, and explain any mismatch between measured behavior and the simplified model.&lt;br /&gt;
&lt;br /&gt;
{{#ev:youtube|https://www.youtube.com/watch?v=PmAI76OGE_E|500|center}}&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
= Interactive Tasks =&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
== Quiz: Test Your Knowledge ==&lt;br /&gt;
&lt;br /&gt;
{{MC}}&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Which statement best describes an abstract data type?&amp;#039;&amp;#039;&amp;#039;&lt;br /&gt;
(It specifies operations and their meaning independently of representation)&lt;br /&gt;
(!It specifies a single mandatory memory layout)&lt;br /&gt;
(!It is any algorithm that uses recursion)&lt;br /&gt;
(!It is a table containing only numeric keys)&lt;br /&gt;
&lt;br /&gt;
{{E}}&lt;br /&gt;
&amp;lt;br&amp;gt;&lt;br /&gt;
&lt;br /&gt;
{{MC}}&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Which growth rate matches binary search on a sorted random access sequence?&amp;#039;&amp;#039;&amp;#039;&lt;br /&gt;
(Logarithmic)&lt;br /&gt;
(!Linear)&lt;br /&gt;
(!Quadratic)&lt;br /&gt;
(!Exponential)&lt;br /&gt;
&lt;br /&gt;
{{E}}&lt;br /&gt;
&amp;lt;br&amp;gt;&lt;br /&gt;
&lt;br /&gt;
{{MC}}&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Which data structure naturally implements first in first out processing?&amp;#039;&amp;#039;&amp;#039;&lt;br /&gt;
(Queue)&lt;br /&gt;
(!Stack)&lt;br /&gt;
(!Heap)&lt;br /&gt;
(!Binary search tree)&lt;br /&gt;
&lt;br /&gt;
{{E}}&lt;br /&gt;
&amp;lt;br&amp;gt;&lt;br /&gt;
&lt;br /&gt;
{{MC}}&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;What is the usual expected search time of a well managed hash table?&amp;#039;&amp;#039;&amp;#039;&lt;br /&gt;
(Constant)&lt;br /&gt;
(!Logarithmic)&lt;br /&gt;
(!Linearithmic)&lt;br /&gt;
(!Quadratic)&lt;br /&gt;
&lt;br /&gt;
{{E}}&lt;br /&gt;
&amp;lt;br&amp;gt;&lt;br /&gt;
&lt;br /&gt;
{{MC}}&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;What determines the running time of basic binary search tree operations most directly?&amp;#039;&amp;#039;&amp;#039;&lt;br /&gt;
(Tree height)&lt;br /&gt;
(!Number of hash collisions)&lt;br /&gt;
(!Queue capacity)&lt;br /&gt;
(!Array element width)&lt;br /&gt;
&lt;br /&gt;
{{E}}&lt;br /&gt;
&amp;lt;br&amp;gt;&lt;br /&gt;
&lt;br /&gt;
{{MC}}&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Which algorithm finds shortest paths by edge count from one source in an unweighted graph?&amp;#039;&amp;#039;&amp;#039;&lt;br /&gt;
(Breadth first search)&lt;br /&gt;
(!Depth first search)&lt;br /&gt;
(!Merge sort)&lt;br /&gt;
(!Heap sort)&lt;br /&gt;
&lt;br /&gt;
{{E}}&lt;br /&gt;
&amp;lt;br&amp;gt;&lt;br /&gt;
&lt;br /&gt;
{{MC}}&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Which condition is required for the standard correctness of Dijkstra algorithm?&amp;#039;&amp;#039;&amp;#039;&lt;br /&gt;
(Nonnegative edge weights)&lt;br /&gt;
(!Every vertex has equal degree)&lt;br /&gt;
(!The graph is complete)&lt;br /&gt;
(!All paths have one edge)&lt;br /&gt;
&lt;br /&gt;
{{E}}&lt;br /&gt;
&amp;lt;br&amp;gt;&lt;br /&gt;
&lt;br /&gt;
{{MC}}&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Which sorting algorithm guarantees Theta n log n time in its standard comparison based form?&amp;#039;&amp;#039;&amp;#039;&lt;br /&gt;
(Merge sort)&lt;br /&gt;
(!Insertion sort)&lt;br /&gt;
(!Selection sort)&lt;br /&gt;
(!Bubble sort)&lt;br /&gt;
&lt;br /&gt;
{{E}}&lt;br /&gt;
&amp;lt;br&amp;gt;&lt;br /&gt;
&lt;br /&gt;
{{MC}}&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;What does amortized analysis study?&amp;#039;&amp;#039;&amp;#039;&lt;br /&gt;
(Cost averaged over a sequence of operations)&lt;br /&gt;
(!Cost of only the final operation)&lt;br /&gt;
(!Probability of a syntax error)&lt;br /&gt;
(!Memory use of one variable)&lt;br /&gt;
&lt;br /&gt;
{{E}}&lt;br /&gt;
&amp;lt;br&amp;gt;&lt;br /&gt;
&lt;br /&gt;
{{MC}}&lt;br /&gt;
&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;Which design approach stores solutions to overlapping subproblems?&amp;#039;&amp;#039;&amp;#039;&lt;br /&gt;
(Dynamic programming)&lt;br /&gt;
(!Linear probing)&lt;br /&gt;
(!Breadth first search)&lt;br /&gt;
(!Selection sort)&lt;br /&gt;
&lt;br /&gt;
{{E}}&lt;br /&gt;
&amp;lt;br&amp;gt;&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
== Memory Game ==&lt;br /&gt;
&lt;br /&gt;
&amp;lt;div class=&amp;quot;memo-quiz&amp;quot;&amp;gt;&lt;br /&gt;
{|&lt;br /&gt;
|-&lt;br /&gt;
| Dynamic array || Resizable contiguous sequence with efficient indexing&lt;br /&gt;
|-&lt;br /&gt;
| Linked list || Node sequence connected by references&lt;br /&gt;
|-&lt;br /&gt;
| Hash table || Key value structure using a hash function and collision handling&lt;br /&gt;
|-&lt;br /&gt;
| Binary heap || Complete tree representation supporting priority operations&lt;br /&gt;
|-&lt;br /&gt;
| Breadth first search || Traversal that explores by increasing edge distance&lt;br /&gt;
|-&lt;br /&gt;
| Depth first search || Traversal that explores one branch before backtracking&lt;br /&gt;
|-&lt;br /&gt;
| Merge sort || Divide and conquer sorting through recursive splitting and merging&lt;br /&gt;
|-&lt;br /&gt;
| Memoization || Caching of previously solved subproblems&lt;br /&gt;
|}&lt;br /&gt;
{{E}}&lt;br /&gt;
&amp;lt;br&amp;gt;&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
== Drag and Drop ==&lt;br /&gt;
&lt;br /&gt;
&amp;lt;div class=&amp;quot;lueckentext-quiz&amp;quot;&amp;gt;&lt;br /&gt;
&lt;br /&gt;
{| class=&amp;quot;wikitable&amp;quot;&lt;br /&gt;
! Match the correct terms.&lt;br /&gt;
! Topic&lt;br /&gt;
|-&lt;br /&gt;
| &amp;#039;&amp;#039;&amp;#039;Stack&amp;#039;&amp;#039;&amp;#039;&lt;br /&gt;
| Last in first out access&lt;br /&gt;
|-&lt;br /&gt;
| &amp;#039;&amp;#039;&amp;#039;Queue&amp;#039;&amp;#039;&amp;#039;&lt;br /&gt;
| First in first out access&lt;br /&gt;
|-&lt;br /&gt;
| &amp;#039;&amp;#039;&amp;#039;Balanced tree&amp;#039;&amp;#039;&amp;#039;&lt;br /&gt;
| Ordered dictionary with logarithmic height&lt;br /&gt;
|-&lt;br /&gt;
| &amp;#039;&amp;#039;&amp;#039;Hash table&amp;#039;&amp;#039;&amp;#039;&lt;br /&gt;
| Expected constant time key lookup&lt;br /&gt;
|-&lt;br /&gt;
| &amp;#039;&amp;#039;&amp;#039;Priority queue&amp;#039;&amp;#039;&amp;#039;&lt;br /&gt;
| Repeated access to the most urgent element&lt;br /&gt;
|}&lt;br /&gt;
{{E}}&lt;br /&gt;
&lt;br /&gt;
&amp;lt;br&amp;gt;&lt;br /&gt;
...&lt;br /&gt;
&amp;lt;br /&amp;gt;&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
== Crossword Puzzle ==&lt;br /&gt;
&lt;br /&gt;
&amp;lt;div class=&amp;quot;kreuzwort-quiz&amp;quot;&amp;gt;&lt;br /&gt;
{|&lt;br /&gt;
|-&lt;br /&gt;
| Heap || Which structure supports repeated access to an extreme priority key?&lt;br /&gt;
|-&lt;br /&gt;
| Queue || Which structure is used as the frontier in breadth first search?&lt;br /&gt;
|-&lt;br /&gt;
| Hashing || Which technique maps keys to table positions through a function?&lt;br /&gt;
|-&lt;br /&gt;
| Recursion || Which technique defines a solution in terms of smaller instances?&lt;br /&gt;
|-&lt;br /&gt;
| Topological || Which kind of ordering places every directed acyclic dependency before its dependent vertex?&lt;br /&gt;
|-&lt;br /&gt;
| Memoization || Which dynamic programming technique caches results of solved subproblems?&lt;br /&gt;
|}&lt;br /&gt;
{{E}}&lt;br /&gt;
&amp;lt;br&amp;gt;&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
== LearningApps ==&lt;br /&gt;
&lt;br /&gt;
&amp;lt;iframe&amp;gt; https://learningapps.org/index.php?s=Data+Structures+and+Algorithms &amp;lt;/iframe&amp;gt;&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
== Cloze Text ==&lt;br /&gt;
&lt;br /&gt;
&amp;lt;quiz display=simple&amp;gt;&lt;br /&gt;
{&amp;#039;&amp;#039;&amp;#039;Complete the text.&amp;#039;&amp;#039;&amp;#039;&amp;lt;br&amp;gt;&lt;br /&gt;
|type=&amp;quot;{}&amp;quot;}&lt;br /&gt;
An algorithm must be both correct and { efficient } for its intended scale. An abstract data type separates an interface from its { representation }. Binary search reduces the candidate range and therefore has { logarithmic } search time on a suitable sorted sequence. A dynamic array achieves efficient repeated appends through { amortized } analysis. A hash table must handle { collisions } when different keys map to the same position. Breadth first search uses a { queue } to explore an unweighted graph layer by layer. Dijkstra&amp;#039;s algorithm requires { nonnegative } edge weights in its standard form. Dynamic programming exploits overlapping subproblems by storing { solutions }. A balanced binary search tree keeps its { height } logarithmic. Empirical benchmarking should complement rather than replace { asymptotic } analysis.&lt;br /&gt;
&amp;lt;/quiz&amp;gt;&lt;br /&gt;
&lt;br /&gt;
&amp;lt;br&amp;gt;&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
= Open-Ended Tasks =&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
=== Easy ===&lt;br /&gt;
# [[English:Complexity diary|Complexity diary]]: Choose five everyday programming operations and predict whether their cost is constant, logarithmic, linear, or worse; explain the assumptions behind each prediction.&lt;br /&gt;
# [[English:Data structure sketch|Data structure sketch]]: Draw a dynamic array, linked list, stack, queue, hash table, and binary search tree for a small shared data set, then annotate one operation on each.&lt;br /&gt;
# [[English:Search experiment|Search experiment]]: Implement linear search and binary search, generate sorted inputs of increasing size, and compare measured operation counts with your theoretical expectations.&lt;br /&gt;
# [[English:Traversal video|Traversal video]]: Create a two-minute screen recording that manually traces breadth-first search on a graph and explains the role of the queue.&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
=== Standard ===&lt;br /&gt;
# [[English:Hash table laboratory|Hash table laboratory]]: Implement a hash table with separate chaining, vary the load factor, record collision statistics, and interpret the resulting lookup behavior.&lt;br /&gt;
# [[English:Sorting benchmark|Sorting benchmark]]: Implement or use transparent implementations of insertion sort, merge sort, and quicksort, then compare them on random, sorted, reverse-sorted, and duplicate-heavy inputs.&lt;br /&gt;
# [[English:Tree investigation|Tree investigation]]: Insert the same keys into a plain binary search tree in several orders, measure the resulting heights, and explain how insertion order changes performance.&lt;br /&gt;
# [[English:Algorithm interview|Algorithm interview]]: Interview a software developer or computer-science instructor about a real situation where data-structure choice changed system performance, then evaluate the reasoning using concepts from this course.&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
=== Advanced ===&lt;br /&gt;
# [[English:Priority queue engineering|Priority queue engineering]]: Implement Dijkstra&amp;#039;s algorithm with two different priority-queue strategies, benchmark both on graphs with different densities, and relate results to theoretical operation counts.&lt;br /&gt;
# [[English:Correctness proof project|Correctness proof project]]: Select a nontrivial algorithm, state preconditions and postconditions, formulate a loop invariant or inductive hypothesis, and write a rigorous proof of correctness.&lt;br /&gt;
# [[English:Dynamic programming design|Dynamic programming design]]: Model a new optimization problem, define its state and recurrence, implement both memoized and bottom-up versions, and analyze time and space complexity.&lt;br /&gt;
# [[English:Algorithm visualization project|Algorithm visualization project]]: Build an interactive visualization of a graph, tree, or sorting algorithm that exposes internal state transitions and includes a written explanation of correctness and complexity.&lt;br /&gt;
&lt;br /&gt;
{{:Open Task - Create a MOOC}}&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
= Learning Assessment =&lt;br /&gt;
&lt;br /&gt;
# [[English:Structure selection case|Structure selection case]]: Given a workload with frequent key lookup, ordered range queries, and periodic bulk updates, compare at least three candidate data structures and justify a final design.&lt;br /&gt;
# [[English:Asymptotic argument|Asymptotic argument]]: Derive a tight asymptotic bound for a multi-stage algorithm, identify the dominant term, and explain which assumptions make the derivation valid.&lt;br /&gt;
# [[English:Correctness and counterexample|Correctness and counterexample]]: Evaluate a proposed greedy algorithm, prove it correct or construct a minimal counterexample, and explain what property succeeds or fails.&lt;br /&gt;
# [[English:Graph algorithm transfer|Graph algorithm transfer]]: Model a real routing, dependency, or scheduling problem as a graph and select an algorithm whose assumptions match the model.&lt;br /&gt;
# [[English:Performance discrepancy analysis|Performance discrepancy analysis]]: Compare predicted asymptotic behavior with benchmark data and explain at least three plausible implementation-level causes of divergence.&lt;br /&gt;
# [[English:Dynamic programming reconstruction|Dynamic programming reconstruction]]: Extend a dynamic-programming solution so that it reconstructs an optimal solution, not only its objective value, and justify the added state.&lt;br /&gt;
# [[English:Adversarial test design|Adversarial test design]]: Construct inputs that expose worst-case or edge-case behavior in two algorithms and explain why those inputs are informative.&lt;br /&gt;
&lt;br /&gt;
&amp;lt;br&amp;gt;&lt;br /&gt;
&amp;lt;br&amp;gt;&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
= Evidence of Learning =&lt;br /&gt;
&lt;br /&gt;
Evidence of learning should show more than successful execution. Strong work demonstrates that you can connect representations, invariants, complexity models, implementation choices, and empirical results.&lt;br /&gt;
&lt;br /&gt;
# &amp;#039;&amp;#039;&amp;#039;Knowledge&amp;#039;&amp;#039;&amp;#039;: You can explain arrays, linked structures, stacks, queues, hash tables, balanced trees, heaps, graph representations, searching, sorting, shortest paths, greedy methods, and dynamic programming.&lt;br /&gt;
# &amp;#039;&amp;#039;&amp;#039;Analysis skills&amp;#039;&amp;#039;&amp;#039;: You can derive asymptotic time and space bounds, distinguish worst-case, expected, and amortized claims, and state the assumptions behind each result.&lt;br /&gt;
# &amp;#039;&amp;#039;&amp;#039;Proof skills&amp;#039;&amp;#039;&amp;#039;: You can use invariants, induction, exchange arguments, or recurrence reasoning to justify why an algorithm is correct.&lt;br /&gt;
# &amp;#039;&amp;#039;&amp;#039;Implementation products&amp;#039;&amp;#039;&amp;#039;: You can produce tested code, benchmark reports, visualizations, and documented experiments that expose the behavior of algorithms and data structures.&lt;br /&gt;
# &amp;#039;&amp;#039;&amp;#039;Design transfer&amp;#039;&amp;#039;&amp;#039;: You can translate a new real-world problem into a computational model and select a data structure or algorithm that matches its operations and constraints.&lt;br /&gt;
# &amp;#039;&amp;#039;&amp;#039;Evaluation&amp;#039;&amp;#039;&amp;#039;: You can identify when a theoretically attractive method performs poorly in practice and investigate memory, locality, input distribution, and constant-factor effects.&lt;br /&gt;
&lt;br /&gt;
&amp;lt;br&amp;gt;&lt;br /&gt;
&amp;lt;br&amp;gt;&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
= OERs on the Topic =&lt;br /&gt;
&lt;br /&gt;
The following open resources provide useful extensions. MIT OpenCourseWare offers complete university-level materials for Introduction to Algorithms, including lectures, notes, assignments, and practice resources: [https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/ MIT OpenCourseWare 6.006 Introduction to Algorithms].&lt;br /&gt;
&lt;br /&gt;
&amp;lt;iframe&amp;gt; https://en.m.wikipedia.org/wiki/Data_structure &amp;lt;/iframe&amp;gt;&lt;br /&gt;
&lt;br /&gt;
&amp;lt;iframe&amp;gt; https://en.m.wikipedia.org/wiki/Algorithm &amp;lt;/iframe&amp;gt;&lt;br /&gt;
&lt;br /&gt;
&amp;lt;br&amp;gt;&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
= Linked Learning Areas =&lt;br /&gt;
&lt;br /&gt;
{| align=center&lt;br /&gt;
{{:D-Tab}}&lt;br /&gt;
&amp;#039;&amp;#039;&amp;#039;[[English:Data Structures and Algorithms|Data Structures and Algorithms]]&amp;#039;&amp;#039;&amp;#039;&lt;br /&gt;
# [[English:Algorithm analysis|Algorithm analysis]]&lt;br /&gt;
# [[English:Abstract data type|Abstract data type]]&lt;br /&gt;
# [[English:Computational complexity|Computational complexity]]&lt;br /&gt;
# [[English:Sorting algorithm|Sorting algorithm]]&lt;br /&gt;
# [[English:Search algorithm|Search algorithm]]&lt;br /&gt;
# [[English:Tree data structure|Tree data structure]]&lt;br /&gt;
# [[English:Graph theory|Graph theory]]&lt;br /&gt;
# [[English:Hash table|Hash table]]&lt;br /&gt;
# [[English:Dynamic programming|Dynamic programming]]&lt;br /&gt;
# [[English:Software engineering|Software engineering]]&lt;br /&gt;
|}&lt;br /&gt;
&lt;br /&gt;
[[Category:English]]&lt;br /&gt;
[[Category:Higher Education]]&lt;br /&gt;
[[Category:Computer Science]]&lt;br /&gt;
[[Category:Algorithms]]&lt;br /&gt;
[[Category:Data Structures]]&lt;br /&gt;
[[Category:Programming]]&lt;br /&gt;
[[Category:Algorithm Analysis]]&lt;br /&gt;
[[Category:Data Structures and Algorithms]]&lt;br /&gt;
&lt;br /&gt;
{{BR}}&lt;br /&gt;
= aiMOOC Projects =&lt;br /&gt;
[[Category:English]]&lt;br /&gt;
[[Category:Data Structures and Algorithms]]&lt;br /&gt;
[[Category:Computer Science]]&lt;br /&gt;
[[Category:Algorithms]]&lt;br /&gt;
[[Category:Data Structures]]&lt;br /&gt;
[[Category:Programming]]&lt;br /&gt;
[[Category:Algorithm Analysis]]&lt;br /&gt;
[[Category:Higher Education]]&lt;br /&gt;
[[Category:AI_MOOC]]&lt;br /&gt;
[[Category:GPT aiMOOC]]&lt;br /&gt;
{{MT}}&lt;/div&gt;</summary>
		<author><name>Glanz</name></author>
	</entry>
</feed>