Exam 3 Flashcards
(106 cards)
1
Q
A graph comprises __, each of which holds some kind of __
A
Vertices, Data
2
Q
Two vertices can be connected by an __
A
Edge
3
Q
Neighbors
A
Connected vertices in a graph
4
Q
Graphs are conceptually
A
Linked-node structures
5
Q
T/F: An empty graph of no nodes can exist
A
True
6
Q
Graphs differ from N-ary Trees and other tree structures in that
A
-there is no parent/child relationship between nodes
-any node can be connected to any other node
7
Q
Graphs are ideal data structures for representing systems with ___ between entities
A
many-to-many
8
Q
T/F: A binary tree is a type of graph
A
True. Any formation of nodes is.
9
Q
Path
A
A series of edges that connect two vertices
10
Q
If a path exists between vertices, they are part of the same __
A
Connected component
11
Q
Search
A
An algorithm that determines if a path between vertices exists
12
Q
Undirected Edges
A
Edges can be traversed in both directions
13
Q
Directed Edges
A
Edges can only be traversed in one direction. Indicated by an arrow.
14
Q
A graph should provide the following behavior
A
- Add value to graph
- Boolean check if value in graph
- Size
- Connect directed
- Connect undirected
- Boolean check if two values are connected
15
Q
T/F: graphs can only be implemented with nodes
A
False. Can use arrays to get similar result
16
Q
Adjacency List
A
Method for vertices to keep track of their unique neighbors. Can be represented by a table:
Vertex | Adjacency List
17
Q
If no path exists between vertices, they are in __
A
Different connected components
18
Q
Breadth-First Search
A
Path search algorithm. Creates queue with the start vertex. While the queue isn’t empty,
Dequeues next vertex
If value is the goal, return true
Otherwise, add the vertex’s neighbors to the queue (if not previously added)
19
Q
Nodes should be searched in ___
A
Alphabetical/numeric order (for this class)
20
Q
Depth-First Search
A
Path Finding Algorithm. Uses a queue to search vertices in order based on distance from start. One edge away will be searched first, two, three, etc.
21
Q
BFS VS DFS
A
DFS explores deeper and deeper into the graph. BFS explores all nodes one edge away first.
22
Q
When using DFS, if arrived at a vertex without any unexplored neighbors:
A
Backtracks along it’s path only as far as necessary to find a vertex with at least one unexplored neighbor
23
Q
DFS can be implemented with
A
A stack or through recursion
24
Q
BFS use a ___ to keep track of predecessors. DFS uses ___
A
A map. A recursive call.
25
T/F: BFS guarantees the shortest path
True (fewest edges)
26
T/F: DFS guarantees the shortest path
False
27
BFS and DFS time complexity
O(V + E) for both
28
Algorithm
A finite procedure, written in a fixed symbolic vocabulary, governed by precise instructions, moving in discrete steps, whose execution requires no insight, cleverness, intuition, intelligence, or perspicuity, and that sooner or later comes to an end.
29
Algorithms often begin as __
Psuedocode
30
Problem solving by breaking problem down into a series of discrete steps
Algorithmic approach
31
Psuedocode
High-level descriptions of what the computer will do
32
T/F: psuedocode should be written with the syntax of the language in mind
False. It should be programming-language agnostic and written in English. There are no grammar or syntax rules.
33
The purpose of psuedocode
To sketch out an algorithm quickly
34
A greedy algorithm
Makes decisions based on what appears to be the optimal choice at the time
35
Local Optimum
Optimal choice at the time
36
Global Optimum
The best possible answer for the problem
37
T/F: Greedy algorithms never produce the best possible result for the problem
False. Sometimes they do. Usually they produce a result that is "good enough"
38
The problem with finding the best answer is that
It can take too long. Greedy algorithms can get close enough much faster
39
Greedy algorithms make decisions based on
Limited information. No memory of what came before. No idea what comes next.
40
Weighted graph
A graph that adds a weight to each edge between vertices
41
Nearest neighbor algorithm
Modification of DFS. Always chooses the neighbor connected by the edge with the lowest weight.
42
Information Expert
Object-oriented design principle, "behavior follow state."
If methods are to be added to existing code, they should be added to the classes that contain the necessary data (states)
43
T/F: If the shortest distance (cost) path has more edges, BFS will never find it
True
44
T/F: Nearest Neighbor is guaranteed to find the path with the lowest cost
False. It will only choose an unexplored neighbor with the lowest cost
45
A key principle of Dijkstra's Algorithm
Optimal paths can be found by finding the optimal subpaths from start to every vertex that is along the path to end.
46
Dijkstra's Algorithm uses __ to keep track of the paths
Modified Priority Queue and a Map. Key is each vertex, value is a tuple of the path to the vertex and the distance (start distance is 0, all others infinity)
47
Dijkstra's Algorithm works by choosing which vertex?
The vertex that has the shortest distance from the starting vertex
48
T/F: Java's priority queue can be used for Dijkstra's Algorithm
False. It will not rearrange the vertices into priority order, and will dequeue wrong
49
In Dijkstra's Algorithm, what does it mean if the only remaining values in the priority queue have a distance of infinity?
There is no path from the start to any of those vertices
50
Dijkstra's final path is
Built in reverse from the end
51
Configuration
An attempted solution at any stage
52
Successor
A configuration where one of the possible next choices has been made
53
A configuration is invalid if
It breaks the rules of the problem being solved
54
Goal
A configuration that is a valid solution to the problem
55
Configuration interface should include
isValid()
isGoal()
getSuccessors()
56
Backtrack
When a successor is invalid, it backtracks to a valid configuration
57
To keep the elements of all configurations between successors, a __ will need to be done with any __
Deep copy. Mutable reference type
58
If a deep copy isn't made in backtracking algorithms
Reference types will be overwritten on each successor. Configurations will change each other's data!
59
Pruning
If a configuration is invalid, no additional successor configurations are tried from that point. This branch is abandoned.
60
The computational intensity of backtracking algorithms can be partially mitigated by
Pruning
61
Backtracking occurs
Whenever one of configuration's successors fails to return a solution (backtracks to configuration and tries next successor)
62
Inner classes
Defined within another class
63
An inner class has access to:
All of the data in the containing class, regardless of access modifiers
64
T/F: The containing class has full visibility of the inner class?
True
65
Outside of the containing class, how to access aspects of inner class
Dot notation. OuterClass.InnerClass class = new OuterClass.InnerClass
66
T/F: an inner class can be made private to prevent access outside of the containing class?
True
67
Static variables
Are shared between all instances of a class.
Can be accessed from the class directly.
Often initialized when created.
68
Static methods
Can be called from the class directly.
Can only access other static methods or variables.
69
Static block
Code written outside of methods using the word "static". Only executed once when the class containing the block is loaded for the first time. Often used for complex initialization of static variables.
70
Anonymous classes
Classes without a name that are created in another class and used once
71
When declaring an anonymous class a __ or __ must be specified
Base class. Interface. Then any additions/customizations can be added
72
T/F: Anonymous classes must override any inherited abstract methods at the time of creation
True
73
T/F: Anonymous classes can't override any methods other than abstract ones
False. They may, but aren't required too.
74
The anonymous class will be stored in a __ of the base class and __ will be used to access the anonymous portions
Variable. Polymorphism.
75
When are anonymous classes useful?
If they are needed in only one place and they contain a small amount of code
76
T/F: An inner class is a better choice than an anonymous class if the code inside will be long/complicated
True
77
Anonymous classes level of access
Everything in the containing class
78
Anonymous classes have access to __ in the method where it is created. These are __ by the class
Local variables. Captured.
79
Variables used in an anonymous class must be
Final or effectively final. Changing them after use in the class will return a compilation error.
80
T/F: The state in an anonymous class is easily accessible outside the class
False. The state is most often referenced through an interface or base class that doesn't give visibility to any new state
81
Functional Interface
An interface with only one method
82
Because they are so small, functional interfaces are often implemented as __
Anonymous classes
83
Lambda Expressions
Syntactic shorthand for anonymous classes
84
When using lambda expressions, the __ information will not be typed __
Inferred. Explicitly.
85
Lambda syntax
parameter list -> function body
86
Lambda expressions can often infer:
Method names.
Parameter types.
Return statement.
87
Method reference
Class/Variable::methodName
Most compact kind of lambda. The parameters and return types must match the functional interface
88
Streams
Sequence of elements that can be acted on and manipulated
89
Stream.forEach
Used to perform some operation on each element in steam
90
Stream.filter
Filter data on specific criteria before doing other work. Returns a modified stream to work on.
91
Procedural Programming
Programs that primarily use procedures (functions) to encapsulate statements that are executed step by step
92
Object-oriented Programming
Includes state and behavior defined by classes. Objects of a class encapsulate their own copy of the state and behavior. Polymorphism.
93
Programming Paradigm
A specific method of writing programs (procedural, object-oriented, etc.)
94
Functional Programming
A declarative programming paradigm in which function definitions are trees of expressions that map values to other values.
Functions are first-class citizens.
Functions can be assigned to variables, passed as arguments, and returned by functions
95
Functional Programming in Java
Creating classes that define functional interfaces
96
Pure Functions
Are not affected by state. Don't change state. Always return the same result with the same arguments.
97
T/F: Lambdas are always pure functions
False. They can modify the state
98
Reduction
Process of converting an expression to a simpler form
99
String.matches(regex)
Returns true if string matches the regular expression
100
Stream.map
Applies mapper function to each element in stream (intermediate operation)
101
Stream.collect
Adds each element in stream to collection
102
IntStream.range
Creates stream of ints
103
Arrays.stream
Uses array (or part of it) as a stream.
104
Files.lines
Uses file interpreter as lines as source for stream
105
Collection.stream
Uses collection as source of stream
106
Collectors.toList
Accumulates a stream into a list
