algorithms Flashcards

Question

Tree Terminology: inner nodes depth of a nofe height of a node Number of leavews of binary tree #comparisons in worse case

Answer 1

all nodes with children length of the path to its root length of longest downard path to a leaf from that node n! h(T)

Answer 2

Base case h(T) = 0 and , λ(T) = 1 so base case true Hypothesis : assume that , λ(T) <= 2^h(T) for height h(T) = k-1 Step: show it true for h(T) = k Consider any tree T of height k. If the last level of T was removed, the resulting tree T' would have height k-1, which allows us to apply hypothesis. λ(T') <= 2^H(T') = 2^k-1 By restoring last level, the number of leaves are at most doubled compared to T' as every leaf of T' has at most two children in T. This implies , λ(T) <= 2* λ(T') <= 2 * 2^h(T') = 2 * 2^k-1 = 2^k

Answer 3

searches for element of rank k in every round, we pick a pivot element x, partititon the array and determine the rank p of x If k = p, then x is the eleement we are looking for. if k< p then continue search only in the left part if k > p, continue search only in right part

Answer 4

Quick_Select(A,l,r,k) // input array A, bounds, rank k p <-- Partiton(A,l,r) // p is split position(pivot) if p == k-1 then return A[p] if p > k-1 then return Quick_Select(A,l,p-1) else return Quick_Select(A,p+1,r) O(n^2)

Answer 5

an edge e is incident on a vertex v if v is an endpoint of e.

Answer 6

edges that are incident to the same two vertices edge that connects a vertex with iteself graph does not contain multiple edges and loops

Answer 7

number of edges that are incidenet on v

Answer 8

The sum of all vertex degrees is equal to two times the number of edges Since every edge has 2 endpoints, the sum must be equal to two times the number of edges

Answer 9

sequence of edges for which there is a sequence of verticies all adjacent trail is walk which edges are used once Path is walk which verticies are used once circuit is a closed trail cycle is a circuit in which only the first and last vertex are equal

Answer 10

cycle-free and connected G has n-1 edges where n is number of verticies

Answer 11

undirected, cycle free graph that has multiple trees(not connected)

Answer 12

tree which every node has at most d children

Answer 13

-vertex, left subtree, right subtree in the right subtree it goes to all left first

Answer 14

-left subtree, vertex, right subtree look at eg

Answer 15

left subtree , right subtree, vertex

Answer 16

list of veticies to which it is adjacenet to requires n list each list represented twice for each endpoint 2 * m nodes storing data and reference requires 2 space n + 2 * 2 *m = O(n + m)

Answer 17

matrix which element at row i and column j is 1 if there is an edge from vertex vi to vertex vj, otherwise 0

Answer 18

Each node have a list or array of references pointing to the children Every node has two pointers left pointers points to the first child of a vertex(which will be left) right pointer points to its next siblings(vertex on same lvl)

Answer 19

ismemeber O(log(n)) // binary search insert O(log(n)) // also binary search when inserting k, we must shift all subsequent elements to the right delete(key k) O(log(n)) also binary search shift all subsequent elemtns the the left

Answer 20

get fixed income which i have to guess for every insert operation(must be lowest i think). Prove income is sufficient to pay for a sequence of n insert operations. derive s * n is the running time

Answer 21

search(k) if k == key then return data If k < key and left != null then return left.search(k) if k > key and right != null then return right.search(k) return null O(h(T))

Answer 22

insert(k,d) // key k and data d if k == key then data <-- d else if k < key then if left != null then left.insert(k,d) else newnode <-- create new treenode T with k and d left <-- refrence to T else if right != null then right.insert(k,d) else NewNode <--- create new TreeNode T with k and d right <-- refrence to T O(H(T))

Answer 23

How do we delete a key x? 1. Search for this key x 2. If x has no children (i.e. is a leaf), simply remove x 3. If x has exactly one child, then remove x by connecting x’s child to x’s parent 4. If x has two children, then replace x by the smallest vertex s in the right subtree of x and attach the right subtree of s to the parent of s. O(H(T))

Answer 24

h(k) = k mod n h(k) = ⌊n · (k · a − ⌊k · a⌋)⌋ The square brackets gives the integer value a = 0.61803????

Answer 25

let p(k) be probability for the occurence of key k in U. ideal hash function h is ideal for U if sum p(k) = 1/n

Answer 26

α =m/n where this is number of keys divided by size of hash table Checking if a hash table position is free Cache Locality allows faster data access

Answer 27

All keys that are mapped to the same position are stored in a sorted linked list Search for 87 Access array at index 4(one probing) Check first element stored 11!= 87(one probing) Check second element 87=87(one probing) so three probings

Answer 28

unsuccessful search Mapping is one probing Every list element must be probed list probings have average length of α avg cost is 1 + α Successful search Mapping is one probing on average we probe half the list elements to find right one so cost is 1 +α/2 worse case for all operations is O(m) // number of elements stored

Answer 29

keys stored in array itself incase of collision, insert tries to find another posisition - uses function h(k, i) = (h(k) + i) mod n h(k) is modulo hash function

Answer 30

Map k to index in hash table using h(k, 0) = h(k) * If position h(k) is free, stop (element not in hash table) * If h(k) contains k, stop (search successful) * If h(k) contains different key, repeat for h(k) + 1 mod n * If h(k) + 1 mod n also contains different key, try h(k) + 2 mod n, and so on

Answer 31

primary clustering for every pair keys k and k` theres i and i` such that h(k,i+j) = h(k`,i` + j) h(33, i) sequence: 3, 4, 5, 6, 7, 8, 9, 0, 1, 2 h(54, i) sequence: 4, 5, 6, 7, 8, 9, 0, 1, 2, 3 primary clustering between h(33,1 + j) = h(54,j) Secondary clustering is for every pairs of keys k, k` with h(k) = h(k`) the probe sequences are identical h(54, i) sequence: 4, 5, 6, 7, 8, 9, 0, 1, 2, 3 h(94, i) sequence: 4, 5, 6, 7, 8, 9, 0, 1, 2, 3 Secondary clusering for h(54,i) = h(94,i)

Answer 32

uses different hash function h(k, i) = (h(k) + (−1)^i+1·⌊i/2⌋^2) mod n

Answer 33

uses second hash function h' h(k, i) = (h(k) + i · h′(k)) mod n

Answer 34

Circuit that contains every edge of g exactly once Trail that contains every edge of g once ( semi- Eulerinan graph)

Answer 35

Part 1 eulerain then every vertex degree is even Let T be an Euler circuit in G and v an arbitrary vertex that occurs k times in T Everytime v is visited, there must be an ingoing edge and an outgoing edge. Since every edge is used exactly once, degree of v is 2 * k and thus even Part2: if every vertex degree is even then G is eulerian Assume T is a trail of max length in G but not an Euler circuit According to the lemma, T must be a ciruit Assume That there are edges not contained in T Since G is connected, there must be at least one such edge e that is incident on a vertex vi in T Then T` = (e, ei ,.. ek.., ei-1) is a trial that is longer than T.. contradiction

Answer 36

1 Start at any vertex and create a trail K of maximum length by following consececutive unvisisted edges. 2. If K contains all edges, return K 3. Otherwise start from any vertex of K that is incident to an unvisited edge and form a new circuit K′ by following unvisited edges 4. Combine K and K′to a new circuit K′′ 5. K ← K′′ 6. Go to Step 2

Answer 37

//Input graph G=(V,E) which all vertices have an even degree Output: Euler Circuit 4. Select some vertex v0 in V 5. Extend v0 to maximal trail K = (Vk,Ek) by adding unvisited incident edges to trail's end vertices 6. while Ek != E do 7. Select vertex v in Vk that is incident to an edge e not in Ek extend v to maximal trail K' using only unvisited edges from E\Ek K"" <-- combination of K and K' K<--K"" return K

Answer 38

Start from vertex Explore branch as far as possible then bactrack, explore next branch and so on

Answer 39

Start from vertex visit every vertex at depth 1 then every vertex at depth 2 and so on

Answer 40

source vertex s to destination vertex t in G if its weight is as small as the weight of any other (s-t)-path.

Answer 41

v0 ̸= vk . Then every time vk was visited before the last visit, we must have used two edges, one to reach vk and one to leave it. For the last visit we use one edge to go to vk , and according to the assumption, there is no further edge incident to vk (since all edges incident to vk are in T). Hence, vk is incident to an odd number of edges, 6 i.e. has an odd degree, which is a contradiction to fact that all graph vertices have an even degree

Answer 42

find shortest path from s to t find shortest paths from s to all other vertices in the graph Find shortest path between every pair of vertices

Answer 43

at every step make the best possible move

Answer 44

solves the single-source shortest path problem from some vertex s using greedy strat -start from s -keep data structure U with all vertices not yet added to the tree -In every round , add new vertex v in U to tree with minimal distance to s, i.e. min{dist(s,v)} Update info for neightbours of v in data structure(distance and predecessor)

Answer 45

Dijkstra(G,s) // G=(V,E) with positive weights, vertex s 1: dist(v) ← ∞ ∀v ∈ V; dist(s) ← 0 2: pred(v) ← NULL ∀v ∈ V; pred(s) ← s 3. U = createPriorityQueue(V) 4.while not isEmpty(U) do v <-- extractMin(U) for all u ∈ N(v) ∩ U do // look at all neightbors u of v if dist(v) + w(v, u) < dist(u) then decreaseKey(u, dist(v) + w(v, u))) 9: pred(u) ← v 10.return (pred, dist) // shortest-path tree For managing U and dist, we need a so-called priority queue offering * extractMin * decreaseKey * insert * isEmpty

Answer 46

if a subgraph of G that contain all vertices of G spanning subgraph and a tree Spanning tree of minimum weight

Answer 47

Start with an empty edge set E in every step, add next edge of minimal weight from G to E whilst not introducing cycles Stop once a connected graph is reached

Answer 48

Kruskal(G) // G = (V,E) undirected and connected 1: T ← ∅ // ∅ is the empty set 2: E′ ← E 3: Sort edges in E′in ascending order 4: while E′ ̸= ∅ do Pick an edge e in E' with minimum weight if adding e to T does not form cycle then Add e to T remove e from E' 9. return (V,T)

Answer 49

makeset(x) ... creates a one-element set {x}; * find(x) ... returns a subset containing x; * union(x, y) ... constructs the union of the disjoint subsets Sx and Sy containing x and y, respectively, and replaces Sx and Sy by this union

Answer 50

The smallest element from each subset is used as its represetntative Array used to find the represetntative of an element Linked list used to store subset

Answer 51

store each vertex ID x in a seperate set using makeset(x) Each time an edge(i,j) is considered to be added to the MST it must be checked if it create a cycle. if find(i) = find(j) if edge can be added, perfrom union(i,j)

Answer 52

Every find operations takes O(1) and at most are 2*m of then A sequence of n union operations takes O(nlog(n)) so O(m*log(n))

Answer 53

select arbitrary vertex v0 to start the tree While there are vertices not in the tree do select an edge of min weight among all edges between a vertex in the tree and an outside vertex not in the tree Add the selected edge and its end vertex to the tree return resulting tree

Answer 54

ALGORITHM Prim(G) // G = (V, E) undirected and connected 1: VT ← {v0} // 2: ET ← ∅ // 3: for i ← 1 to |V| − 1 do 4: Find a minimal weight edge e∗ = (v∗, u∗) among all edges (v, u) such that v is in VT and u is in V \ VT 5: VT ← VT ∪ {u∗} 6: ET ← ET ∪ {e∗} 7: return (V, ET ) // ET is the set of edges of the MST

Answer 55

* It is used for problems in which subproblems are not independent, i.e. subproblems share subsubproblems

Answer 56

compute each F(i) exactly one time and store it in an array Next time we need F(i) we look it up in array

Answer 57

input// row of n coins, whose values are some positive integer. output// max amount of money subject to the constraint that no two coins which are adjacent can be picked up

Answer 58

F(0) = 0 F(1) = c1 F(n) = max{cn + F(n − 2), F(n − 1)} for n > 1

Answer 59

//Input array C of coin values F[0] <-- 0 F[1] <-- C[1] for i <--2 to n do F[i] <-- Max(C[i] + F[i-2],F[-1]) return F[n]

Answer 60

coins placed on n x m board. robot in upper left cell of board and needs to collect as many coins as possible to the bottom right only moving one cell right or down each step.

Answer 61

let (i,j) denote the cell in ith row and jth column(starts from 1) Let F(i,j) be the largest number of coins the robot can collect and bring to cell(i,j) F(0,j) = 0 F(i,0) = 0 F(i, j) = max{F(i − 1, j), F(i, j − 1)} + cij where cij = 1 if coin in cell (i,j) and 0 otherwise

Answer 62

finite set of symbols Sequence of symbols from an alphabet empty word- length 0 if subword,prefix,suffix is proper if s` != s

Answer 63

loop through all indicies of i of the text t for each index i, check whether ti, ti+1.. matches search string, if do retun true Simple_Search(t,s)// text t, string s n <-- length(t); m<-- length(s) i <--0; j<--0 while i<= n-m do while t[i+j] == s[j] do j++ if j==m then return i i <-- i + 1 j <-- 0 return -1

Answer 64

s is a word, s` is a border of s if s` is a prefix and a suffix of s. if it is a proper prefix and proper suffix of s if it is the longest proper border of s

Answer 65

stores the actual border length of every prefix of the search string s in an array

Answer 66

loop through all indices i of the text t for each i check if Ti matches search string if whole search string match return true if first j characters of search string are matched, continue search at i= i+j(skip indices in loop) if ti.. ti+1 .. has an actual border of size b, assume that b characters are already matched

Answer 67

kmp(t,s) 1: n ← length(t); m ← length(s) 2: Create array border of size m + 1 3: compute borders(border, m, s) 4: i ← 0; j ← 0 5: while i ≤ n − m do 6: while t[i + j] == s[j] do 7: j + + 8: if j == m then 9: return i 10: i ← i + j − border[j] // previously i ← i + 1 11: j ← max{0, border[j]} // previously j ← 0 12: return −1

Answer 68

Unsuccessful comparisons: i is increasded by at least 1 hence there will be at most n -m + 1 such comparisons Successful comparisons Consider sum i +j after a succ comparisson, i+j grows by 1 because as j is incremeneted. i+j < (n-m)+m= n so at most n successful performed

Answer 69

encoding info which uses fewer bits than og representation lossless if og representation can be restored from compressed version. Lossy otherwise

Answer 70

Assume that every sequenece of n bits is a text exactly 2^n texts of length n how many text of length at most n-1 are there? sum from i=1 to n-1 ( 2^i) therefore at least one text is mapped to text of length n

Answer 71

code which no code word is the prefix of another code {101, 001, 10, 1100} prefix codes?

Answer 72

prefix code that maps letters to bit strings uses binary tree T leaves represent letters code word of a letter is given by the path from root to its leaf at every node one bit is added to the code word, a 0 for left, a one for right

Answer 73

length of its path in T Sum of all (Probability of word * length of word)

Answer 74

every letter represented by single vertex the p of the letter is stored with it the vertices form the trees of the initial forest While there is more than one tree , do Assume T1 and T2 are the trees of smallest p replace T1 and T2 by a new tree T1,2 consisting of a new vertex and T1 and T2 as its subtrees

algorithms Flashcards

U (101 cards)