Flashcards

CE204

B O U Y B O Y Inglês 26 flashcards

Flashcards do 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