Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Data Structures and Algorithms 3 > Exam > Flashcards

Exam Flashcards

Prepare for the exam :')

1
Q

Teorija: Neusmeren graf

Definicija, terminologija(1)

A
  • Skup čvorova i kolekcija grana gde svaka povezuje neuređen par čvorova.
  • Definicija: susedne grane, incidentnost, stepen čvora
  • Podgraf: podskup grana grafa i povezanih čvorova
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Teorija: Neusmeren graf

Povezanost, put (2)

A
  • Put: sekvenca čvorova povezanih granama.
  • Staza: put bez ponovljenih čvorova
  • Kontura: put sa bar jednom granom čiji su prvi i poslednji čvor isti.
  • Dva čvora povezana ako postoji put između.
  • Povezan graf: postoji put između svaka dva čvora; u suprotnom, skup povezanih komponenti koji predstavljaju maksimalno povezane podgrafove.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Teorija: Neusmeren graf

Stablo, bipartitnost (3)

A
  • Stablo: acikličan povezan graf. Ima V-1 granu i nema konture, povezan je, ali uklanjanjem jedne grane neće biti, ako mu se doda jedna grana dobija konturu i tačno jedna snaza povezuje svaki par čvorova.
  • Šuma: disjunktan skup stabala.
  • Pokrivajuće stablo je podgraf koji sadrži sve čvorove u stablu.
  • Pokrivajuća šuma je unija pokrivajućih stabala povezanih komponenti datog grafa.
  • Bipartitan graf: može da podeli svoje čvorove u 2 disjunktna skupa tako da sve grane povezuju čvorove iz različith skupova.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

API: Graph

A 
public class Graph
Graph(int V)
Graph(In in)
int V()
int E()
void addEdge(int v, int w)
Iterable<Integer> adj(int v);
String toString()
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Teorija: reprezentacije grafa

A
  1. Matrica susedstva: V×V boolean niz, v×w true ako postoji grana između njih
    * prostor: V²
    * dodavanje grane, provera postojanja grane u konstantnom vremenu (multi grane zabranjene)
    * iteracija kroz susede čvora: V
  2. Niz grana: klasa Edge i dve instance tipa int, direktna reprezentacija jednostavna, implemenacija adj() zahteva prolazak kroz sve grane
    * prostor: E
    * dodavanje grane u konstantnom vremenu
    * provera postojanja grane i iteracija kroz susede čvora: E
  3. Lista susedstva: niz čvorova i liste sa susedima
    * prostor: V+E
    * dodavanje grane u konstantnom vremenu
    * provera postojanja grane i iteracija kroz susede čvora: degree(v)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Teorija: pretraživanje grafa u dubinu

Neusmeren graf

A

Cilj korišćenja DFS-a: sistematičan prolazak kroz graf (prolazak kroz lavirint)
Primena: za pronalazak svih čvorova povezanih sa datim i pronalazak puta između 2 čvora

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Dizajn: pretraživanje grafa u dubinu

Neusmeren graf

A 
public class Paths
Paths(Graph G, int s)
boolean hasPathTo(int v)
Iterable<Integer> pathTo(int v)

DFS(to visit a vertex v)
Mark v as visited
Recursively visit all unmarked vertices w adjacent to v

Strukture:
marked[] - boolean niz za obeležavanje posećenih čvorova
edgeTo[] - integer niz za čuvanje puteva
stack za rekurziju

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Pretpostavka: DFS označava sve čvorove povezane sa s u vremenu E+V.

A

Tačnost: ako je w označeno, onda je povezano sa s, jer DFS pronalazi čvorove isključivo praćenjem grana.
Vreme: svaki čvor povezan sa s je posećen jednom.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Pretpostavka: može se proveriti da li je v povezano sa s u konstantnom vremenu i može se naći v-s put (ako postoji) u vremenu proporcionalnom njegovoj dužini.

A

edgeTo[] predstavlja stablo sa korenom u s (dokaz indukcijom).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Kompleksnost: DFS kod neusmerenih grafova

A

Preprocessing time: E+V
Query: konstantno
Prostor: E+V

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Teorija: tabele simbola

A
  • struktura za parove vrednost-ključ; očekuje se da je klijentu dostupno ubacivanje vrednosti u tabelu i da je pretražuje po zadatom ključu
  • upotreba: rečnik, web pretraga, account management…
  • u tabeli nema duplikata, ubacivanje novog para sa istim vrednostima radi samo update vrednosti vezane za prosleđeni ključ; ključ ne može biti null i ne može biti vezan za null vrednost
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

API: tabela simbola

Neuređena lista

A

Prednosti: odličan za male ST
Mane: spor za velike ST

public class ST<Key, Value>
ST()
void put(Key key, Value value)
Value get(Key key)
void delete(Key key)
boolean contains(Key key)
boolean isEmpty()
int size()
Iterable<Key> keys()
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

API: tabela simbola

Uređen niz

A

Sve metode kao za standardni ST + operacije koje zavise od poretka

Prednosti: optimalna pretraga i prostor, operacije zavise od uređenosti
Mane: sporo ubacivanje

public class ST<Key extends Comparable<Key>, Value>
Key min()
Key max()
Key floor(Key key)
Key ceiling(Key key)
int rank(Key key)
Key select(int k)
void deleteMin()
void deleteMax()
int size(Key low, Key high)
Iterable<Key> keys(Key low, Key high)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Kompleksnost: tabela simbola

Neuređena lista

A
  • Pretraživanje i ubacivanje (zagarantovano): N
  • Pretraživanje (hit): N/2; ubacivanje: N (average case)
  • Ključni interfejs: equals()
  • Sve operacije osim uređene iteracije: N; uređena iteracija: N log N

Average: posle N random ubacivanja

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Kompleksnost: tabela simbola

Uređeni niz

A
  • Pretraživanje: log N; ubacivanje N (zagarantovano)
  • Pretraživanje (hit): log N; ubacivanje N/2 (average case)
  • Ključni interfejs: compareTo()
  • Ubacivanje, brisanje i uređena iteracija: N
  • Pretraživanje, floor/ceiling, rank: log N
  • min/max, select: konstantno vreme

Average: posle N random ubacivanja

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Teorija: pretraživanje grafa u širinu

Neusmeren graf

A

Primena: provera postojanja puta od s do ciljnog čvora v, ako postoji, prnađi najkraći.
BFS proverava čvorove rastuće po udaljenosti od s.
Korsti se za: rutiranje, Kevin Bacon numbers, Erdos numbers…

17
Q

Dizajn: pretraživanje grafa u širinu

Neusmeren graf

A 
public class Paths
Paths(Graph G, int s)
boolean hasPathTo(int v)
Iterable<Integer> pathTo(int v)

BFS(from source vertex s)
put s on a queue, and mars s as visited
repeat until queue is empty:
remove the least recently added vertex v
add each of v’s unvisited neighbours to the queue and mark them as visited

18
Q

Pretpostavka: neusmeren graf. Pretraživanje grafa u širinu.

A

U povezanom grafu G, BFS računa najkraći put od s ka svim ostalim čvorovima u vremenu proporcionalnom E+V

Bez dokaza

19
Q

Teorija: nalaženje povezanih komponenti

Definicija, terminologija

A

Primena: detekcija kontura i provera 2-obojenosti, tj. da li je graf bipartitan.
Dva čvora su povezana ako postoji put između njih. Cilj je da graf odgovara na pitanje povezanosti u konstantnom vremenu.
DFS za pronalazak puteva.
Relacija povezanosti se može svesti na RST relaciju.

Povezana komponenta: maksimalan skup povezanih čvorova. Cilj je razbiti graf u komponente (tj. V(G)).

Primena: detekcija čestica, spread of STDs…

20
Q

Dizajn: konture

A 
public class CC
CC(Graph G)
boolean connected(int v, int w)
int count()
int id(int v)

Connected Components
initialize all vertices v as unmarked
for each unmarked vertex v, run DFS to identify all verticles discovered as part of the same component.

21
Q

Teorija: Binarno stablo pretraživanja

Definicija, terminologija

A
  • binarno stablo u simetričnom rasporedu, tako da se u levom podstablu nalaze čvorovi sa manjim ključevima od posmatranog, a sa desne strane oni veći od posmatranog.
  • ili prazno stablo ili se sastoji iz 2 disjunktna binarna stabla
  • čvor predstavljen klasom Node
  • Jedan skup ključeva može biti predstavljen na više načina i to zavisi od redosleda ubacivanja ključeva u stablo
  • Broj poređenja za pretragu i ubacivanje je 1 + dubina čvora
22
Q

Kompleksnost: binarno stablo pretraživanja

A

Pretraga i ubacivanje: N (zagarantovano)
Uspešna pretraga i ubacivanje: 1.39 log N ~ 2 ln N.
Glavni interfejs: Comparable (operacija comapreTo())

23
Q

Teorija: usmeren graf

Definicija, terminologija(1)

A
  • skup čvorova i kolekcija usmerenih grana, gde svaka povezuje uređen par čvorova
  • usmeren put: sekvenca čvorova u kojoj postoji usmerena grana od svakog čvora ka njegovom detetu
  • Upotreba: navigacija, graf implikacije, logička kola, zakazivanje, citiranje…
24
Q

Teorija: reprezentacija digrafa

A
  • skup grana kroz listu ili niz: zauzima E prostora; provera postojanja grane i iteriranje kroz out-susede u vremenu proporcionalnom E; dodavanje grane u konstantnom vremenu
  • matrica susedstva: zauzima V² prostora; provera postojanja grane u konstantnom vremenu kao i dodavanje grane (multigrane zabranjene); iteriranje kroz out-susede u vremenu proporcionalnom V
  • lista susedstva: zauzima E+V prostora; dodavanje grane u konstantnom vremenu; iteriranje kroz out-susede i postojanje grane je u vremenu proporcionalnom outdegree(v).
25
Q

API: Digraph

A 
public class Digraph
Digraph(int v)
Digraph(In in)
void addEdge(int v, int w)
Iterable<Integer> adj(int v)
int V()
int E()
Digraph reverse()
String toString()
26
Q

Teorija: pretraživanje digrafa u dubinu

A
  • rešava problem pronalaska svih usmerenih puteva iz S
  • koristi se za: eliminaciju mrtvog koda i detekciju beskonačnih petlji (dostupnost čvora)
  • mark-sweep tip garbage collector-a:
  • koren su svi objekti kojima se može direktno pristupiti od strane programa
  • dostupni objekti su svi objekti kojima se indirektno može pristupiti od korena koji se obeležavaju, svi ostali se čiste (koristi se jedno dodatno obeležavanje po objektu plus stack).
27
Q

Dizajn: pretraživanje digrafa u dubinu

A

DFS(to visit a vertex v)
mark v as visited
recursively visit all unmarked vertices w pointing from v

28
Q

Kompleksnost: BST operacije koje zavise od uređenosti

A

BST omogućavaju poredak elemenata
Za sve operacije je vreme proporcionalno visini stabla ~ log N (ako su ključevi redom ubačeni); za uređeno iteriranje je N.

Data Structures and Algorithms 3 (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions