COSC262 Flashcards Quizlet PDF

Preview

Summary

Some key definition (Not my work). From quizlet....

Description

08/06/2021

COSC262 Flashcards | Quizlet

COSC262 Terms in this set (62) A well defined computational procedure that solves a class of problems. What is an algorithm?

Input : An instance of a computational problem. output: A solution to the instance of the problem. The procedure needs to work for all instances of the problem.

• Correctness • Scalability - How the algorithm behaves as the Key Properties of Algorithms

problem size increases. Efficient in time, space and anything else. • Clarity - How understandable is the algorithm?

Since usually the best case is extremely unlikely, so Why do we focus on the worst case?

it meaningless when comparing algorithms. And the average case is really hard to establish since its really complex, and contains too many factors to accurately measure the "average-case".

COSC262 https://quizlet.com/nz/511328706/cosc262-flash-cards/

1/15

08/06/2021

COSC262 Flashcards | Quizlet

• This is because knowing how an algorithm deals with small amounts if data ins't really that interesting. • To know if an algorithm is optimal we need to Why do we focus on the

know how it performs with large amounts of data.

asymptotic analysis?

• So seeing how it performs, as it tends to an infinite amount of data. We get a clearer picture of how optimal the algorithm is when comparing to another.

Types of recursion splitings

(1, n-1), (n/2, n/2), (n-1, 1)

• 2^d nodes at depth d, each cost c*(n/(2^d)). • Total cost at depth d = c*n. Analysis of Merge-sort

• Base case is reached when n/(2^d) = 1, i.e. when d = log(n). Therefore total cost = T(n) = c nd = cnlog(n) = BigTheta(n*log(n)).

• Base case = Big-Theta(1) • Total cost at depth d = c * 2^d Analysis of Tower of Hanoi

• Base case is reached when d = n-1. • Therefore total cost: T(n) = c sum(c(2^d). between d = 0, and d = n-1).

• Nodes at depth d = 1 • Cost of each node at depth d=c. Analysis of Binary Search

• Base case reached when n / (2^d) = 1 i.e. when d = log(n) • Total Cost: T(n) = c*log(n) = Big-Theta(log(n))

COSC262 https://quizlet.com/nz/511328706/cosc262-flash-cards/

2/15

08/06/2021

COSC262 Flashcards | Quizlet

• Tail recursion means - When are return value of a function is just a recursive call to the function. • For functional languages they sneakly jump back

Tail Recusion

to the start of the function and adjust the values. This means no extra computation is allowed.

• A simple intuitive method A Greedy Method Definition

• Choose whatever option looks best at the time. • No backtracking allowed.

• The greedy solution is to order them by increasing finishing times.

Activity Selection Problem

• Then grab the next time slot that's has a initial time larger then the last finishing time (which fits).

• Greedy solution is to order them by value/weight. fractional knapsack problem

Then go through the list and grab the highest values first, until you can't fit anything else.

Upgrade to remove adverts

Only NZ$5/month

• Uses a "bottom-up" greedy approach. • Maintains a list of partial coding trees, sorted in order of total frequency of all characters in the tree Huffman Coding Algorithm

(a min-heap can work too instead of a tree). • Repeatedly combine the two trees of lowest frequency. If they are equal the lower letter (lower one of the two trees goes to the left).

COSC262 https://quizlet.com/nz/511328706/cosc262-flash-cards/

3/15

08/06/2021

COSC262 Flashcards | Quizlet

• The trees list must support priority queue operations "insert" and "pop_min" (each O(log n), using a min-heap) • At each iteration, two elements are removed from Complexity of Huffman Coding

the priority queue, and then combined tree's root is added back to the list. Since the size reduces by one at each iteration it is O(n). • Therefore, total time complexity is O(n log(n)).

• The encoding information must be transmitted with Disadvantages of Huffman Encoding

the text to the decoding system. • The whole doc must be processed first. • Can't do local optimisation (not a big deal) • encoding table must itself be encoded.

• Uses memorisation to store results of subTop-Down Recurrence.

problems, so they can be retrieved if they are needed in future.

• Build a table of solutions starting with the simplest bottom up

sub-problems. • Fill out the table case by case. combining known sub-solutions, until the target problem is reached.

• Top-down approach -> Start at the final row, for each cell in the final row use the value. But when you move up a cell find the minimum of the three The Minimum Cost Path

possible cells below it.

Problem

• Bottom-up -> Build a table of equal size to the grid, start at the top (the top row's values are there own). For each cell in grid assign it the value of the cell + the minimum of the three possible parents.

COSC262 https://quizlet.com/nz/511328706/cosc262-flash-cards/

4/15

08/06/2021

COSC262 Flashcards | Quizlet

• For each node, we add the value of the minimum Multistage Graphs

previous node, and assign its parent to it. This helps with back tracking.

• Top-Down => We perform the recursion s.t. we either pick up the coin or not. If we reach 0 then we return 0. Otherwise if the value is below 0 return inf (no solution). Otherwise the min of the possible Coin changing

coins. • Bottom-up => Create an array, if the coin value = 0, then we assign 0. Otherwise for each coin value between 1 and the value we want. We find the minimum of we do the minimum of value we are looking at it minus the coin.

• Top-Down => If number of items left = 0 then return 0. Otherwise if the weight is too heavy return the recursive call of the next item. Otherwise return the max value of either picking up the item or going to the next item. 0-1 Knapsack Problem

• Bottom-Up => We go through the table of size n x w (n = item indexes, w = weights between 0 and max weight). For each cell we check the maximum between the value in the row above, or if we pick up and value of the current item + the value at the row above and minus the weight in the cols.

Go up from the current point and if the row above Backtracking 0/1 Knapsack

has a change, then move to the col with the current weight minus the current item's wight. Until you reach (0, 0).

COSC262 https://quizlet.com/nz/511328706/cosc262-flash-cards/

5/15

08/06/2021

COSC262 Flashcards | Quizlet

We can either remember the parent, or we can find Backtracking Coinage

the minimum of the possible options (if the coin was used), and repeat till we reach 0.

• Top Down => Once we reach (0, 0) then we have 0. Otherwise if the letters are equal at (i, j) we return Longest Common Subsequence Problem

the recursive call at (i-1, j-1) + 1. Otherwise if they are not equal we return the max of [(i, j-1), (i-1, j)]. Bottom up => Same as the recursion in the topdown, just that we start at the simpler cases first and work are way up.

Starting at cell at (A.Length, B.length), where A is the first word and B is the second word. Longest Common

Then we simply do the following till we reach (0, 0).

Subsequence Back tracking

If the letters at (i, j) are equal then we move to (i-1, j1). Otherwise we move to the cell of max [(i-1, j), (i, j1)]. Then we need to reverse this.

• A solution is to create a copy of the word and sort Longest Increasing

it alphabetically. Then perform an LCS on them

Subsequence

both. •

COSC262 https://quizlet.com/nz/511328706/cosc262-flash-cards/

6/15

08/06/2021

COSC262 Flashcards | Quizlet

Where A = start-text and B = end-text. i selects a letter from A, and j selects a letter from B. Recursion: Base Cases: • i and j = 0 => value = 0 • i = 0 and j != 0 => value = (i, j-1) + 1 • i != 0 and j = 0 => value = (i-1, j) + 1 Edit distance Algorithm

If i == j => value = (i-1, j-1) Otherwise: value = min [ (i-1, j) + 1, del (i, j-1) + 1, inse (i-1, j-1) +1, sub ]

• Starting at the (A.length, B.length). • If i == j, then we go to (i-1, j-1). • Otherwise, The next value is the min of [ Edit distance Backtracking

(i-1, j) + 1, del (i, j-1) + 1, inse (i-1, j-1) +1, sub ] • Stop at (0, 0), and reverse the string.

• Two arrays, one has the queue only with the start vertex, then the second array contains the seen vertices, with the start vertex being true and the rest BFS

false. • While the queue is not empty, remove the first in the queue and go through all its edges and add any unseen vertices to the queue. Complexity O(V+E)

COSC262 https://quizlet.com/nz/511328706/cosc262-flash-cards/

7/15

08/06/2021

COSC262 Flashcards | Quizlet

• have an array, that stores all the seen variables, and set the start vertex to true and the rest to false. • For each adjacent vertex, we call the recursive DFS

DFS

call and mark it seen. Complexity O(V+E)

• Generate a components array, seen and a seen array. Connected Components

• For each of the vertices, we perform a BFS if it's unseen and add the parts it finds as a component, and mark any seen vertices as seen.

Strong Connectivity Definition

Defined by at any vertex you can reach any other vertex.

Upgrade to remove adverts

Only NZ$5/month

• Perform a DFS from a start vertex. If all vertices have been visited then move to the next step. Otherwise return false. Strong Connectivity Algorithm

• Perform a DFS on the transformed graph, and if you visit all vertices then you are strongly connected. Otherwise false. Complexity: O(V + E)

For a directed graph that doesn't contain a cycle. Topological Ordering

It's finding an order of s.t. any node on the stack has all it's dependencies before it.

COSC262 https://quizlet.com/nz/511328706/cosc262-flash-cards/

8/15

08/06/2021

COSC262 Flashcards | Quizlet

• Create a seen array and stack. • For each vertex in the graph perform a DFS, and when we see a vertex mark it as seen and push it Topological Ordering

onto the stack.

Algorithm

• Pop all the items from the stack and that's the ordering. Complexity: O(V+E)?

• We create a distance, parent and in tree arrays, with the start vertex marked in each. • While all of the vertices are not in the tree, then we go through each of the adjacent vertex (set this to Prim's Algorithm

true) of the next vertex (closest and not in tree). If the current adjacent vertex is not in the tree and it's weight is smaller then the distance it has then we change it's distance value. • Complexity: O(V^2)

• We create a distance, parent and in tree arrays, with the start vertex marked in each. • While all of the vertices are not in the tree, then we go through each of the adjacent vertex (set this to Dijkstra's algorithm

true) of the next vertex (closest and not in tree). If the current adjacent vertex is not in the tree and if the distance value of the next vertex and the edge's weight is smaller then the distance value of the adjacent vertex, then we change the distance value. • Complexity: O(V^2)

• Dynamic programming d(i, j, k), all-pair shortest Floyd-Warshall Algorithm

paths. • Complexity: O(n^3)

COSC262 https://quizlet.com/nz/511328706/cosc262-flash-cards/

9/15

08/06/2021

COSC262 Flashcards | Quizlet

• points: a, b, c • p = b-a Finding the signed area of

• q = c- a

three points

• area = p.x q.y - q.x p.y

Depends on the signed area of three points: • If it's positive, it's to the left.

Counter Clock Wise test

• If it's Negative, it's to the right. • If it's 0 it's co-linear.

• Given two edges AB and CD. • If the counter clock wise test, gives two different results for point sets ADB and ACB. continue. Line Segment Test

Otherwise return false. • Here we perform the same check again, with the point sets CAD and CBD. If these are different then return true. Otherwise false.

• An end point of a line segment is on the other line Line Segment Test Special

segment.

Cases

• All four points are co-linear. • Solution, create two special cases for them.

Upgrade to remove adverts

Define Simple Polygon

Only NZ$5/month

A sequence of vertices connected by straight lines, whose edges don't intersect.

COSC262 https://quizlet.com/nz/511328706/cosc262-flash-cards/

10/15

08/06/2021

COSC262 Flashcards | Quizlet

Point inclusion Test for Simple Polygons

• For some point, we fire a horizontal line along the x axis. If we go through an odd number of edges then we are inside the polygon. Otherwise false.

• The line passes through a vertex. • The line passes through a horizontal edge. • Solution is too count only the start vertex of the Point Inclusion Test Special Cases

edge if the edge is going downwards, and count only the end vertex of the edge if it's pointing upwards. • Simpler solution is to offset the point by a very small float, so it won't line up with any of the other points.

• The smallest possible simple Polygon that contains all the points in it or on it's borders. Convex hull

• The convex hull is unique • the minimum and maximum of all x and y's are part of the convex hull.

• We go through every possible edge, and if all Convex Hull Brute Force

other points are to the left of it, then we add it to the convex hull. • Complexity O(n^3)

• Start with the bottom most left point. • Then while the hull isn't complete, for each point in Gift Wrap

the set add the most right point candidate to the convex hull. • Complexity O(n*m), worst case: O(n^2)

COSC262 https://quizlet.com/nz/511328706/cosc262-flash-cards/

11/15

08/06/2021

COSC262 Flashcards | Quizlet

• We first construct a "simple closed path" by first choosing a minimum (x.min, y.min). This is the anchor. • Then we sort all the points in counter clock wise order. This can be done by sorting it by counter clock wise order. • There are some issues with this. if several points are co-linear. The solution, ignore it lol. Graham Scan

• The next step. We walk around the path and add points to the stack that are counter clock wise (using the last 2 points in the stack, and the candidate). • If the candidate is not counter clock wise too the previous 2 points. We pop off the last point on the stack. And try again. • This is repeated until you reach all the points. • Complexity: O(n log(n))

Range Searching

• Given a large number of geometric points. • We try and find all points within a rectangle.

Two approaches: • We can perform a linear scan, which we can then check each item if its in the range. O(n) 1D Range searching.

• We can also sort the array once in O(n log n) time. But then every query call is done using a binary search to find the min item and then we just move forward until we are out of bounds. O(log(n) + m), where m is the result set size.

COSC262 https://quizlet.com/nz/511328706/cosc262-flash-cards/

12/15

08/06/2021

COSC262 Flashcards | Quizlet

• First we sort the array. • We can build a tree, such that every internal node is a median value (median ish, we get the middle index of the sub-array we are looking at. Call that

1-D k-d tree - constructing

the median). • Then we make it so, every item that is smaller or equal to the item at that index to the left sub-tree. And the rest in the right sub-tree.

Upgrade to remove adverts

Only NZ$5/month

• We perform a BST search with a twist, that we go down the paths that are included in the range. 1-D k-d Tree - Searching

• If the value is in between the values, then we go down both paths. • Note that the range search is n1 < x O(n log(n)), Worst Case => O(d*n), where d is max-depth.

• Traverse the tree from the root node and try to Quad tree - finding/inserting a

determine if the node will be in the rectangle of that

point

child. • And go down it if it should contain it.

• We go down to all childs that are included in the Quad Tree - Range Searching

range. • If it's on the line we go down both rectangle on either side of the line.

• K-D trees are more efficient with clustered data. • Quad trees are better if all the points are spread Quad tree vs K-D Trees

out evenly. But then it's still quite useless. But you can add nodes to it while using it, unlike with the KD tree, which needs to be re-processed.

COSC262 https://quizlet.com/nz/511328706/cosc262-flash-cards/

14/15

08/06/2021

COSC262 Flashcards | Quizlet

• Generally the pre-processing step often involves O(n log(n)) sorting. Remaining computations are similar or lower generally. Line sweeping

• Helpful with reducing the number of comparisons between points using information gathered at each point position of the sweep line.

• We perform a line sweep, the first two points are set as the closest. • Then we go through each point and check for any points that are in the range (d = shortest distance, d 2D Closest Pair - Algorithm

away on the x-axis towards the back, d up and down the y axis). • If any of these points are closer the shortest distance d is set to that, and we continue till all points have been "swiped".

• Sorting is O(n log(n)) 2D Closest Pair - Complexity

• The search for the closest pair at each step takes

Analysis

O(log(n)) • Total complexity: O(n log(n))

https://quizlet.com/nz/511328706/cosc262-flash-cards/

15/15...