commit 3c1685fcb3f4ce9dbcbce26134596bb2add86062 parent efadfbb8fff4678dc4092369f9a9cd2b1df8f996 Author: Alex Balgavy <alex@balgavy.eu> Date: Wed, 9 Jun 2021 18:57:20 +0200 Computational thinking notes Diffstat:
36 files changed, 443 insertions(+), 1 deletion(-)
diff --git a/content/_index.md b/content/_index.md @@ -39,7 +39,7 @@ title = "Alex's university course notes" ## Subject notes: Year 1 -* [Computational thinking](https://thezeroalpha.github.io/compthink-notes) +* [Computational thinking](compthink-notes) * [Systems architecture](https://thezeroalpha.github.io/sysarch-notes) * [Physical Computing](https://thezeroalpha.github.io/physcomp-notes) * [Logic & sets](logicsets-notes/) diff --git a/content/compthink-notes/Algorithms/12aad5b5a9912ccca9e0190e5cc2f911.png b/content/compthink-notes/Algorithms/12aad5b5a9912ccca9e0190e5cc2f911.png Binary files differ. diff --git a/content/compthink-notes/Algorithms/index.md b/content/compthink-notes/Algorithms/index.md @@ -0,0 +1,40 @@ ++++ +title = 'Algorithms' ++++ +# Algorithms +## What is an algorithm? + +An effective method, finite n of steps or instructions, to solve a problem or accomplish a task + +always works + + + +## Solution strategies + +- Guess and check + - “try something" +- Try all possibilities + - suitable with small possibilities +- Divide the problem into steps + - reduces complexity + - simplifies the problem +- Use formulas/equations + - better overview +- Discover a structure or pattern + - sometimes it’s necessary to extend the problem +- Make a model + - simpler problem or situation + - e.g. diagram or picture +- Brute force + - relies on computing power, uses computer + - example: bubble sort, linear search +- Divide and conquer + - three steps: + + 1. Divide problem of size *n* into number of subproblems of same type and about same size + + 2. Conquer: recursively solve sub-problems + 3. Combine: appropriately combine solutions + + - examples: binary search, merge sort, quick sort diff --git a/content/compthink-notes/Big O Notation.md b/content/compthink-notes/Big O Notation.md @@ -0,0 +1,47 @@ ++++ +title = 'Big O Notation' +template = 'page-math.html' ++++ +# Big O Notation +used to classify algorithms +function characterisation according to rates of growth +useful for analysing efficiency +always uses approximate worst case +read “order of" + +Example: +- $T(n)=4n^2-2n+2$ +- $n=500$ => $4n^2$ is 1000 times larger than 2n +- $T(n) = O(n^2)$ + +## Time complexity +expressed in Big O notation +performance: how much time, memory, disk, etc. + +time complexity: amount of time taken by an algorithm to run, as a function of the length of the string representing the input + +typically interested in worst-case time complexity T(*n*) + +Determining complexities: + +- sequence of statements: + - T=t(statement 1)+t(statement 2)+…+t(statement k) + - if simple, time for each statement is constant, so total time is constant + - therefore T(*n*) = O(1) +- if-then-else + - worst case is the slower of two possibilities + - max(time(block1), time(block2)) + - if block1 takes O(1) and block2 takes O(N), it will be O(N) +- loops + - loop executes N times, so sequence of statements also executes N times + - if assume statements are O(1), total time is N\*O(1) + - so O(N) +- nested loops + - if N is times for outer loop, and M is times for inner loop + - executes total of N\*M times + - so complexity is O(N\*M) +- function/procedure calls + - f(k) has O(1) + - g(k) has O(k) + - if a loop goes 1 .. N and calls g(J) every time + - complexity of O(N)² diff --git a/content/compthink-notes/Binary search.md b/content/compthink-notes/Binary search.md @@ -0,0 +1,37 @@ ++++ +title = 'Binary search' +template = 'page-math.html' ++++ +# Binary search +an efficient algorithm to search position of element in a *sorted list* + +belongs to the “Divide and Conquer” strategy (divide into subproblems into smallest is solved, solve subproblems recursively, combine all solutions) + +average faster than linear search + +How it works: +works by comparing the search key K with the middle element A[m] of the list + +middle element found by: +subtract array.length-1, divide by 2, round up + +then: + +- if $K>A[m]$, first half is eliminated + - search goes on in the second half of the array + - continues recursively +- if $K<A[m]$, second half is eliminated + - search goes on in the first half of the array + - continues recursively + +Performance: + +- Best case: 1 comparison +- Worst case: log₂(n+1) comparisons +- Average: ~log₂(n) comparisons + +Time complexity: + +- Best case: O(1) +- Worst case: O(log(n)) +- Average: O(log(n)) diff --git a/content/compthink-notes/Bubble sort.md b/content/compthink-notes/Bubble sort.md @@ -0,0 +1,20 @@ ++++ +title = 'Bubble sort' ++++ +# Bubble sort +"brute force" +1. compare adjacent elements: if current is bigger than next, swap +2. compare next adjacent elements +3. repeat until go through all and no swaps have been made + +## performance + +a list with n elements: need n-1 comparisons for first pass, n-2 for second pass, etc. + +number of key comparisons = (n-1) + (n-1) + (n-3) … + 1 = n(n-1)/2 + +## complexity + +- Best case: O(n) +- Worst case: O(n²) +- Average: O(n²) diff --git a/content/compthink-notes/Dijkstra_s algorithm/10c18b7eda75d354a80a0da5cba48ee6.png b/content/compthink-notes/Dijkstra_s algorithm/10c18b7eda75d354a80a0da5cba48ee6.png Binary files differ. diff --git a/content/compthink-notes/Dijkstra_s algorithm/54fc0ba4872f66721aa476105989c3a4.png b/content/compthink-notes/Dijkstra_s algorithm/54fc0ba4872f66721aa476105989c3a4.png Binary files differ. diff --git a/content/compthink-notes/Dijkstra_s algorithm/bbadc5fc82170d9966cb2e1052d45b3a.png b/content/compthink-notes/Dijkstra_s algorithm/bbadc5fc82170d9966cb2e1052d45b3a.png Binary files differ. diff --git a/content/compthink-notes/Dijkstra_s algorithm/index.md b/content/compthink-notes/Dijkstra_s algorithm/index.md @@ -0,0 +1,23 @@ ++++ +title = "Dijkstra's algorithm" ++++ +# Dijkstra's algorithm +What is it? + +Solves the single-source shortest path problem — find shortest path from one designated node to every other node. + +Only works with non-negative edge weights. + +Steps: +1. Take the starting node +2. Compute the distances to every other connected node (just follow the edges from the starting node) +3. Take the smallest edge, and follow it to a new node +4. Use the edges from the new node to update the table, and possibly create new/smaller paths to other nodes +5. Take the new smallest edge to a node that was not visited yet +6. Repeat from step 4 + +**Methods:** + +| **Graphical** | **Tabular** | +| --- | --- | +|  |  | diff --git a/content/compthink-notes/Graphs/20ea83217532edc5fd09f38ca92efee7.png b/content/compthink-notes/Graphs/20ea83217532edc5fd09f38ca92efee7.png Binary files differ. diff --git a/content/compthink-notes/Graphs/index.md b/content/compthink-notes/Graphs/index.md @@ -0,0 +1,41 @@ ++++ +title = 'Graphs' ++++ +# Graphs +## What is a graph? + +a set of vertices (nodes) and a set of edges (arc/arrows) connecting pairs of vertices + +consists of a collection *V* of vertices and collection *E* of edges, for which we write *G = (V, E)* + +each edge e ∈ E is said to join two vertices (end points) +if *e* joins *u*, v ∈ *V*, we write *e = (u, v)* + +*V* — finite set of vertices +*E* — set of edges (pairs of vertices) + +*V = {a, b, c, d, e, f}* + +*E = {(a,c), (a,d), (b,c), (b,f), (c,e), (d,e), (e,f)}* + +[Types of graphs](./types-of-graphs) + +## Completeness + +A graph is complete if you have *n* vertices and *n-1 *edges on each vertex. Must be simple and undirected. + +## Edges properties + +- connects two vertices +- an edge connecting vertices *i *and *j* is written as *ij* +- sometimes has a direction (*i —> j*) +- weights assigned by means of numbers (e.g. distance between two vertices) + +## Adjacency Matrix representation +Notation: A[i,j] + +Symmetric: A[i,j] = A[j,i] + +when a graph is undirected, the adjacency matrix is always symmetric + + diff --git a/content/compthink-notes/Greedy technique.md b/content/compthink-notes/Greedy technique.md @@ -0,0 +1,25 @@ ++++ +title = '"Greedy" technique' ++++ +# "Greedy" technique +**What is it?** + +a simple algorithm, looking for the best (“greedy”) choice from the available alternatives + +hoping that series of local optimal choices leads to a global optimal solution to big problem + +used to solve optimisation problems + +choice on each step should be: + +- feasible +- local optimal +- irrevocable + +disadvantage: does not operate exhaustively on all data, thus often fails to find globally optimal solution + +**Algorithms** + +- [Dijkstra's algorithm](./dijkstra-s-algorithm) +- [Prim's algorithm](./prim-s-algorithm) +- [Kruskal's Algorithm](./kruskal-s-algorithm) diff --git a/content/compthink-notes/Kruskal_s Algorithm.md b/content/compthink-notes/Kruskal_s Algorithm.md @@ -0,0 +1,15 @@ ++++ +title = "Kruskal's Algorithm" ++++ +# Kruskal's Algorithm +Used to find minimum spanning tree +Faster in sparse graphs, does not need the graph to be connected. + +Steps: +1. Removes all loops and parallel edges except one with least weight. +2. Create edge table. +3. Sort all the edges in increasing order of their weight. + +4. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it. + +5. Repeat step #4 until there are (V-1) edges in the spanning tree. diff --git a/content/compthink-notes/Linear Search.md b/content/compthink-notes/Linear Search.md @@ -0,0 +1,23 @@ ++++ +title = 'Linear Search' ++++ +# Linear Search (sequential search) +- simplest search algorithm for finding particular element in a list +- efficient for small lists +- belongs to the “Brute force” strategy + +How it works: + +each element in list is checked one by one based on a condition until desired element is found + +element found => location returned, algorithm stops + +Performance: + +- Best case: 1 comparison +- Worst case: n comparisons +- Average: (n+1)/2 comparisons + +Time complexity: + +- Worst case n comparisons: O(n) diff --git a/content/compthink-notes/Merge sort.md b/content/compthink-notes/Merge sort.md @@ -0,0 +1,14 @@ ++++ +title = 'Merge sort' ++++ +# Merge sort +belongs to “divide and conquer” + +1. if only one element remaining in list, it is sorted — return +2. divide list recursively into two halves until no longer divided +3. merge smaller list into new list in sorted order + +Time complexity: + +- Best case: O(nlogn) +- Worst case: O(nlogn) diff --git a/content/compthink-notes/Paths/d3b66b27d68752421b0281c6ab69fcff.png b/content/compthink-notes/Paths/d3b66b27d68752421b0281c6ab69fcff.png Binary files differ. diff --git a/content/compthink-notes/Paths/index.md b/content/compthink-notes/Paths/index.md @@ -0,0 +1,17 @@ ++++ +title = 'Paths' ++++ +# Paths +**Trees** + +Simple, undirected, connected, acyclic graphs. Any two vertices are connected by exactly one path. Must have *n-1* edges if *n *vertices. + + + +**Eulerian path** + +A path that visits *every edge* exactly once. It is a cycle if it starts and ends on the same vertex. + +**Hamiltonian graph** + +A path in a graph that visits *each vertex* exactly once. It is a cycle if it starts and ends on the same vertex. diff --git a/content/compthink-notes/Prim_s algorithm/7d5925bbe23e06f7e258c970f3c7c0e8.gif b/content/compthink-notes/Prim_s algorithm/7d5925bbe23e06f7e258c970f3c7c0e8.gif Binary files differ. diff --git a/content/compthink-notes/Prim_s algorithm/index.md b/content/compthink-notes/Prim_s algorithm/index.md @@ -0,0 +1,21 @@ ++++ +title = "Prim's algorithm" ++++ +# Prim's algorithm +## What is it? + +Finds *minimum spanning tree* for a connected weighted undirected graph. Faster in dense graphs with more edges than vertices. + +Spanning tree: connected acyclic subgraph that contains all vertices of the graph + +weight of tree: sum of weights on all the tree’s edges +minimum spanning tree: spanning tree of smallest weight + +**Steps:** +1. Select any vertex to be first of T + +2. Consider which edge connects vertices in T to vertices outside T. Pick any one with min weight. Add edge and vertex to T. + +3. Repeat step 2 until T has every vertex of graph. + + diff --git a/content/compthink-notes/Quicksort.md b/content/compthink-notes/Quicksort.md @@ -0,0 +1,27 @@ ++++ +title = 'Quicksort' ++++ +# Quicksort +Divide and conquer. + +Algorithm: +1. Make right-most index value pivot +2. partition array using pivot value +3. quicksort left partition recursively +4. quicksort right partition recursively + +Find the pivot value: +1. Choose highest index value as pivot +2. Two variables point left and right of list (except pivot) +3. Left points to low index +4. Right points to high index +5. While value at left < pivot; move right +6. While value at right > pivot; move left +7. If *both* step 5 and step 6 fail — swap +8. If left ≥ right, point where they met is new pivot + +Time complexity: + +- Best case: O(nlogn) +- Worst case: O(n^2) +- Average case: O(nlogn) diff --git a/content/compthink-notes/Search algorithms.md b/content/compthink-notes/Search algorithms.md @@ -0,0 +1,10 @@ ++++ +title = 'Search algorithms' ++++ +# Search algorithms +What is it? +An algorithm for finding an item with certain properties + +Algorithms: +- [Linear Search](./linear-search) +- [Binary search](./binary-search) diff --git a/content/compthink-notes/Sorting algorithms.md b/content/compthink-notes/Sorting algorithms.md @@ -0,0 +1,28 @@ ++++ +title = 'Sorting algorithms' ++++ +# Sorting algorithms +Sorting: arranging the elements in a list/collection in increasing/decreasing order of some property; elements are homogeneous + +important to: + +- optimise the use of other algorithms +- make searching easier (you can use binary search) +- normalise and standardise data +- produce a readable output + +Classification based on: + +- computational complexity (big O) +- memory usage +- recursion +- stability + - a sorting algorithm is stable if: relative order of elements with equal values in input is maintained in the output + - example: sorting list of words by first letter, if two words “straw” and “spoon” stay in the same order, it is stable (we only care about the first letter) + - stability is not an issue with array of integers + +Types: + +- [Bubble sort](./bubble-sort) +- [Quicksort](./quicksort) +- [Merge sort](./merge-sort) diff --git a/content/compthink-notes/Symbols of a flowchart/51c7ed7e4c652e7d4fe14e86a03c77f7.png b/content/compthink-notes/Symbols of a flowchart/51c7ed7e4c652e7d4fe14e86a03c77f7.png Binary files differ. diff --git a/content/compthink-notes/Symbols of a flowchart/index.md b/content/compthink-notes/Symbols of a flowchart/index.md @@ -0,0 +1,5 @@ ++++ +title = 'Symbols of a flowchart' ++++ +# Symbols of a flowchart + diff --git a/content/compthink-notes/Types of graphs/01e7a5b2f0ddddef838882b31e14bb0c.png b/content/compthink-notes/Types of graphs/01e7a5b2f0ddddef838882b31e14bb0c.png Binary files differ. diff --git a/content/compthink-notes/Types of graphs/1d51452f58935b1fa6c2b9c02f2c2a14.png b/content/compthink-notes/Types of graphs/1d51452f58935b1fa6c2b9c02f2c2a14.png Binary files differ. diff --git a/content/compthink-notes/Types of graphs/46f1af0e00eb8d6d76b8a68fa5789360.png b/content/compthink-notes/Types of graphs/46f1af0e00eb8d6d76b8a68fa5789360.png Binary files differ. diff --git a/content/compthink-notes/Types of graphs/5599e893bd5d381f3346ebe72a7070cb.png b/content/compthink-notes/Types of graphs/5599e893bd5d381f3346ebe72a7070cb.png Binary files differ. diff --git a/content/compthink-notes/Types of graphs/73f28abacce4a7c95766a5908690328e.png b/content/compthink-notes/Types of graphs/73f28abacce4a7c95766a5908690328e.png Binary files differ. diff --git a/content/compthink-notes/Types of graphs/955ccf90835ef4f55efc5af6d3a0cdc1.png b/content/compthink-notes/Types of graphs/955ccf90835ef4f55efc5af6d3a0cdc1.png Binary files differ. diff --git a/content/compthink-notes/Types of graphs/aecb0a5cf2b4d7b44991d715d6f8fe77.png b/content/compthink-notes/Types of graphs/aecb0a5cf2b4d7b44991d715d6f8fe77.png Binary files differ. diff --git a/content/compthink-notes/Types of graphs/c39fbee31a32652e49b69479cccda233.png b/content/compthink-notes/Types of graphs/c39fbee31a32652e49b69479cccda233.png Binary files differ. diff --git a/content/compthink-notes/Types of graphs/f9222403d65bcae110253413dc91d4d6.png b/content/compthink-notes/Types of graphs/f9222403d65bcae110253413dc91d4d6.png Binary files differ. diff --git a/content/compthink-notes/Types of graphs/index.md b/content/compthink-notes/Types of graphs/index.md @@ -0,0 +1,27 @@ ++++ +title = 'Types of graphs' ++++ +# Types of graphs +## Symmetricity + +| **Undirected (symmetric)** | **Directed/digraph (asymmetric)** | **Mixed** | +| --- | --- | --- | +|  |  |  | + +## Weighted graph + + + +## Simplicity + +| **Simple** | **Multigraph** | +| --- | --- | +| Undirected, unweighted graph that has no loops and no more than one edge between any two different vertices<br> | Multiple edges connecting the same two vertices within a simple graph<br> | + +## Connectedness + +A graph may also have a connected component + +| **Connected** | **Disconnected** | +| --- | --- | +| If there is for any two given vertices a path between them<br> | If not all pairs of vertices have a path between them<br> | diff --git a/content/compthink-notes/_index.md b/content/compthink-notes/_index.md @@ -0,0 +1,22 @@ ++++ +title = 'Computational Thinking' ++++ +# Computational Thinking +1. [Flowchart symbols](symbols-of-a-flowchart) +2. [Solution strategies](algorithms) +3. Algorithms + 1. [Big O](big-o-notation) + 2. [Search](search-algorithms) + - [Linear (sequential)](linear-search) + - [Binary](binary-search) + 3. [Sort](sorting-algorithms) + - [Bubble](bubble-sort) + - [Quick](quicksort) + - [Merge](merge-sort) +4. [Graph theory](graphs) + 1. [Types of graphs](types-of-graphs) + 2. [Paths](paths) + 3. [Greedy algorithms](greedy-technique) + - [Dijkstra’s](dijkstra-s-algorithm) + - [Prim’s](prim-s-algorithm) + - [Kruskal's](kruskal-s-algorithm)
