Fichas
CE204
Fichas del conjunto (26)
- 1Quicksort• Recursive
• The pivot is in the correct position when left items are smaller and right items are bigger
• make middle item pivot
• left pointer takes first smaller item
• right pivot takes first larger item
• swap larger and smaller items
• when pointer meet swap pivot with middle item
• sort sublists same way - 2Mergesort• Divide and conquer
• Recursive
• Easy-split hard-merge
• O(nlogn)
• Break array down into single variables
• Compare the individual values in pairs
• Create new temparrays to store the sorted values
• Continue to compare temp arrays until a sorted array is created - 3Insertion sort• Easy-split hard-merge
• Linear
• O(n^2)
• Work from left to right
• Examine each item and compare it to items on its left
• Insert item into the correct position
• Mark first item as sorted
• Compare next item to item before
• If smaller swap items
• Keep comparing to items before until there are no lower values before
• Move to next item - 4Selection sort• Hard-split easy-merge
• Iterative
• O(n^2)
• Select the smallest item from the unsorted partition
• Move it to the sorted partition
• Start at first value
• Progress through array until the smallest value is found
• If a smaller value is found, swap that with the current value
• Move to net value - 5Primm's Algorithm• Greedy
• Cannot add vertices that are already in MCST
• Create empty list "visited"
• Pick a node to start from
• Add that node to visited list
• Choose next cheapest path to unvisited node and add to list
• Continue to add cheapest paths stemming from visited nodes
• Add edge weights to get MCST's total weight
• {A}, {B, E}, {C}, {D} Add BE to MCST
• {A, D}, {B, E}, {C} Add AD to MCST
• Final MCST: BE, AD, DE, AC - 6Kruskal's algorithm• Acyclical
Pick smallest edge to start
• Add edges that don't create a cycle
• Continue to add smallest edges
• Don't connect 2 nodes that are in the same tree - 7Loop, for, if etc. time complexity• O(n)
• n being number of times occuring - 8Non-computable function• A function that can be specified precisely but cannot be implemented using a programming language
• An example is the halting problem - 9Halting Problem• Non-computable
• Whether a program will terminate when run with specific data
• Supplied string 'p' containing program source and data 'd'
• Can the 'p' terminate when run with 'd'
• Function 'h' can tell us if a program halts with given input
• Program 'h+' should run 'p' with 'd' using 'h'.
• 'h+' should halt the problem if 'h' says it will run indefinitely
• 'h+' should run indefinitely if 'h' says the problem should halt
• Uses proof by contradiction
• The program cannot return the correct results in all cases
• Proves that there cannot be a general algorithm that states if every program will halt or not - 10Adjacency MatrixA two-dimensional array a[u][v] will have the value of true if edge a[u][v] exists
- 11Adjacency List• A list of the adjacencies in a graph
• A: (C,3) (D,2) (B,5) - 12Big O statement
- 13Balancedfor every non-leaf node the size of its left and right children differs by at most one
- 14AVL-balancedfor every non-leaf node the depth of its left and right children differs by at most one
- 15Binary Tree (Return post order)
- 16Stack Class
- 17Stack isempty
- 18Stack Top
- 19Stack pop
- 20Stack push
- 21Queue Class
- 22Queue isempty
- 23Queue add
- 24Queue Front
- 25Queue Remove front
- 26King Jouis
Información
- Descripción
- Fichas sobre CE204, creado por B O U Y B O Y el 14/05/2019.
- Creado por
- B O U Y B O Y
- Visitas
- 12
- Valoración