Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

RTL to GDSII > Algorithms, Naveed > Flashcards

Algorithms, Naveed Flashcards

1
Q

What is a graph?

A

A pair of sets G=(V,E) where V is a set of vertices and E is a set of edges

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

What is a edge?

A

A pair of distinct vertices

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

How to know if v is adjacent to u?

A

If (v,u) is element of E

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

When is an edge incident on a vertice?

A

When e = (u,v)

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

What is the degree of a vertex?

A

The number of edges that are incident on it

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

What is a complete graph?

A

A graph where every vertex is adjacent to every other vertex. We use Kn to denote a complete graph

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

What is the complement of graph G?

A

G=(V,E) H is a compliment of G iff H=(V,F) where F = E(Kv)-E

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

When is G’ a subgraph of G?

A

iff V’≤V and E’≤E

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

when is G’ a vertex induced subgraph of G?

A

iff E’={(u,v)|(v,u) element of E and u,v ≤ V’}

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

what is a walk of a graph G

A

a walk P of graph G is a finite sequence P=v0,e0,v1,…,ek,vk begining and ending with a vertex, each edge is incident on the vertex preceding and following it

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

what is a tour?

A

A walk with distinct edges

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

what is an open walk?

A

a walk with distinct terminal vertices

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

what is a path?

A

an open walk with no vertex appearing more than once

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

what is the length of a path?

A

the number of edges in it

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

what is a cycle?

A

a path with identical terminal vertices and length > 2

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

When are to vertices connected?

A

When there is a path between them.

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

When is a graph connected?

A

For each u,v in G there is a path (u,v)

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

What is a maximal subgraph?

A

The largest subgraph that has a given property. i.e. if one more vertex was added from the superset to the subgraph, then the property would break

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

What is a maximally connected subgraph?

A

The largest subgraph with all the vertices connected.

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

What is the connected component of a graph?

A

The maximally connected subgraph

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

What is a tree

A

a connected graph with no cycles

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

What is a clique

A

a subset if vertices such that every two distinct vertices in the clique are adjacent.

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

What is a directed graph?

A

Like a normal graph but the order of the vertices in an edge matter

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

When is v in-edge?

A

When v is the second vertice in directed edge (u,v)

25
When is u out-edge?
When u is the first vertice in directed edge (u,v)
26
When is the orientation of a G transitive?
If E has edges (u,v) and (v,w) there is also edge (u,w)
27
What is a directed path?
A path (u,v) on G where u is an ancestor of v and v is a descendent of u
28
What is a rooted tree
A DAG in which all vertices have an in-degree of 1 except the root which has an in-degree of 0
29
What is a leaf?
A vertice in a tree, which is a DAG, with no descendants.
30
What is a hypergraph?
A generalization of a graph where edges can connect more than two vertices unlike an ordinary graph where an edge connects exactly two vertices.
31
What is a bipartite graph?
no edge connects two vertices within the same set a graph where the vertices can be divided into two distinct sets, such that every edge connects a vertex from one set to a vertex in the other set
32
What is a complete bipartite graph
A graph with bipartition (X,Y) that each vertex of X is adjacent to each vertex in Y. If |X|=m and |Y|=n then a complete bipartite graph is denoted as Km,n
33
How to know if a graph is bipartite
IFF there is no odd cycle
34
When is a graph planar?
it can be drawn on the plane in such a way that its edges intersect only at their endpoints
35
How to test is a graph is planar
Kuratowski's theorem that a graph is planar if and only if it does not contain a subgraph that is a subdivision of K5 (the complete graph on five vertices) or K3,3 (the utility graph).
36
What is a greedy algorithm?
A greedy algorithm is a problem-solving approach where at each step, the algorithm chooses the option that appears to be the best at that moment, without considering the long-term consequences, hoping that this series of locally optimal choices will lead to a globally optimal solution for the entire problem; essentially, it always makes the "greediest" choice available at each stage.
37
What is a divide and conquer algorithm?
A "divide and conquer" algorithm is a problem-solving technique where a large problem is broken down into smaller, more manageable subproblems, which are then solved individually, and finally, the solutions to those subproblems are combined to solve the original problem; essentially, "divide" the problem into smaller parts, "conquer" each part by solving it, and then "combine" the solutions to get the final answer.
38
What is a dynamic programming algorithm?
A dynamic programming algorithm is a problem-solving technique in computer science where a complex problem is broken down into smaller, overlapping subproblems, and the solutions to these subproblems are stored and reused to efficiently calculate the solution to the larger problem, often by finding the optimal choice at each step based on previously calculated results
39
What is an overlapping subproblem?
An "overlapping subproblem" in programming refers to a situation where a problem can be broken down into smaller subproblems that are solved multiple times during the calculation process and the answer can be reused
40
What is a network flow algorithm?
A network flow algorithm is a method for calculating the maximum amount of flow that can pass through a network. The Ford-Fulkerson algorithm is a common network flow algorithm.
41
In P and NP what is P
The class P of all problems that can be solved by a deterministic turing machine in polynomial time.
42
What are examples of algorithms in P?
Minimum cost spanning tree, single shortest path, graph matching problems
43
In P and NP what is NP
The class P of all problems that can be solved by a *nondeterministic* turing machine in polynomial time.
44
What is the example of a *nondeterministic* turing machine
A parallel computer with as many cores as we need. Basically, whenever there is a branch a new computer core is created so that both paths can be followed simultaneously
45
What does NP-complete mean?
A problem L, in NP, is NP-complete if all other problems in NP can be reduced to L in polynomial time. If any NP-complete problem can be solved in polynomial time, then every problem in NP can be solved in polynomial time. NP-complete problems are the hardest problems in the NP set.
46
What is the decision and optimization version of a problem
Asking if something exists is a decision version, asking for the best solution in a space is the optimization version
47
What is NP-Hard?
For a given problem Q, if the optimization of Q is NP-complete but the decision version of Q is P, then Q is NP-Hard. Most optimization problems in physical design are NP-hard
48
When is a decision problem L NP-complete?
1. L is in NP (Any solution to NP-complete problems can be checked quickly, but no efficient solution is known). 2. Every problem in NP is reducible to L in polynomial time.
49
What is "canonical form"?
A representation of the boolean function that does not depend on the gate implementation Example: truth table
50
What is the global ordering requirement of variables in a BDD?
That every path from root to leaf visits variables in same order except omitted variables.
51
What is ROBDD
Reduced Ordered Binary Decisions Diagram, A ROBDD is a canonical form of a BDD
52
What are the three reduction rules to make a BDD a ROBDD?
1) eliminate redundant leaves 2) merge isomorphic nodes 3) eliminate redundant tests
53
In a BDD, when are two nodes isomorphic?
When they have the same variable and identical children (the exact same child, not just identical labels on child)
54
In a BDD what is a redundant test?
When both edges in a vertex go to the physically same child
55
When are two boolean functions identical?
When their ROBDD is isomorphic
56
What is a special case algorithm?
When we add artificial restrictions to the program to change it from a NP-complete to P. Example: graph coloring is NP-complete for general graphs but can be P for special cases that can be used in physical design Example: placement -> equal height cells into rows rather than general rectangles in a plane Example: General Steiner-Tree problem is NP-hard but single trunk Steiner-Tree problem is O(n)
57
What is a heuristic algorithm?
A strategy that uses rules of thumb to find a solution to a problem and is often based on special cases of the problem that are known to have optimal solutions.
58
What is a good example of a heuristic algorithm?
channel routing
59

RTL to GDSII (3 decks)

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