Brainscape's Knowledge GenomeTM

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


See full index

Software Dev II > Exam 3 > Flashcards

Exam 3 Flashcards

1
Q

A graph comprises __, each of which holds some kind of __

A

Vertices, Data

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

Two vertices can be connected by an __

A

Edge

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

Neighbors

A

Connected vertices in a graph

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

Graphs are conceptually

A

Linked-node structures

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

T/F: An empty graph of no nodes can exist

A

True

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

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

Graphs are ideal data structures for representing systems with ___ between entities

A

many-to-many

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

T/F: A binary tree is a type of graph

A

True. Any formation of nodes is.

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

Path

A

A series of edges that connect two vertices

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

If a path exists between vertices, they are part of the same __

A

Connected component

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

Search

A

An algorithm that determines if a path between vertices exists

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

Undirected Edges

A

Edges can be traversed in both directions

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

Directed Edges

A

Edges can only be traversed in one direction. Indicated by an arrow.

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

A graph should provide the following behavior

A
  1. Add value to graph
  2. Boolean check if value in graph
  3. Size
  4. Connect directed
  5. Connect undirected
  6. Boolean check if two values are connected
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

T/F: graphs can only be implemented with nodes

A

False. Can use arrays to get similar result

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

Adjacency List

A

Method for vertices to keep track of their unique neighbors. Can be represented by a table:
Vertex | Adjacency List

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

If no path exists between vertices, they are in __

A

Different connected components

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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)

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

Nodes should be searched in ___

A

Alphabetical/numeric order (for this class)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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.

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

BFS VS DFS

A

DFS explores deeper and deeper into the graph. BFS explores all nodes one edge away first.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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

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

DFS can be implemented with

A

A stack or through recursion

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

BFS use a ___ to keep track of predecessors. DFS uses ___

A

A map. A recursive call.

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

T/F: BFS guarantees the shortest path

A

True (fewest edges)

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

T/F: DFS guarantees the shortest path

A

False

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

BFS and DFS time complexity

A

O(V + E) for both

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

Algorithm

A

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.

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

Algorithms often begin as __

A

Psuedocode

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

Problem solving by breaking problem down into a series of discrete steps

A

Algorithmic approach

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

Psuedocode

A

High-level descriptions of what the computer will do

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

T/F: psuedocode should be written with the syntax of the language in mind

A

False. It should be programming-language agnostic and written in English. There are no grammar or syntax rules.

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

The purpose of psuedocode

A

To sketch out an algorithm quickly

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

A greedy algorithm

A

Makes decisions based on what appears to be the optimal choice at the time

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

Local Optimum

A

Optimal choice at the time

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

Global Optimum

A

The best possible answer for the problem

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

T/F: Greedy algorithms never produce the best possible result for the problem

A

False. Sometimes they do. Usually they produce a result that is “good enough”

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

The problem with finding the best answer is that

A

It can take too long. Greedy algorithms can get close enough much faster

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

Greedy algorithms make decisions based on

A

Limited information. No memory of what came before. No idea what comes next.

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

Weighted graph

A

A graph that adds a weight to each edge between vertices

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

Nearest neighbor algorithm

A

Modification of DFS. Always chooses the neighbor connected by the edge with the lowest weight.

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

Information Expert

A

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)

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

T/F: If the shortest distance (cost) path has more edges, BFS will never find it

A

True

44
Q

T/F: Nearest Neighbor is guaranteed to find the path with the lowest cost

A

False. It will only choose an unexplored neighbor with the lowest cost

45
Q

A key principle of Dijkstra’s Algorithm

A

Optimal paths can be found by finding the optimal subpaths from start to every vertex that is along the path to end.

46
Q

Dijkstra’s Algorithm uses __ to keep track of the paths

A

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
Q

Dijkstra’s Algorithm works by choosing which vertex?

A

The vertex that has the shortest distance from the starting vertex

48
Q

T/F: Java’s priority queue can be used for Dijkstra’s Algorithm

A

False. It will not rearrange the vertices into priority order, and will dequeue wrong

49
Q

In Dijkstra’s Algorithm, what does it mean if the only remaining values in the priority queue have a distance of infinity?

A

There is no path from the start to any of those vertices

50
Q

Dijkstra’s final path is

A

Built in reverse from the end

51
Q

Configuration

A

An attempted solution at any stage

52
Q

Successor

A

A configuration where one of the possible next choices has been made

53
Q

A configuration is invalid if

A

It breaks the rules of the problem being solved

54
Q

Goal

A

A configuration that is a valid solution to the problem

55
Q

Configuration interface should include

A

isValid()
isGoal()
getSuccessors()

56
Q

Backtrack

A

When a successor is invalid, it backtracks to a valid configuration

57
Q

To keep the elements of all configurations between successors, a __ will need to be done with any __

A

Deep copy. Mutable reference type

58
Q

If a deep copy isn’t made in backtracking algorithms

A

Reference types will be overwritten on each successor. Configurations will change each other’s data!

59
Q

Pruning

A

If a configuration is invalid, no additional successor configurations are tried from that point. This branch is abandoned.

60
Q

The computational intensity of backtracking algorithms can be partially mitigated by

A

Pruning

61
Q

Backtracking occurs

A

Whenever one of configuration’s successors fails to return a solution (backtracks to configuration and tries next successor)

62
Q

Inner classes

A

Defined within another class

63
Q

An inner class has access to:

A

All of the data in the containing class, regardless of access modifiers

64
Q

T/F: The containing class has full visibility of the inner class?

A

True

65
Q

Outside of the containing class, how to access aspects of inner class

A

Dot notation. OuterClass.InnerClass class = new OuterClass.InnerClass

66
Q

T/F: an inner class can be made private to prevent access outside of the containing class?

A

True

67
Q

Static variables

A

Are shared between all instances of a class.
Can be accessed from the class directly.
Often initialized when created.

68
Q

Static methods

A

Can be called from the class directly.
Can only access other static methods or variables.

69
Q

Static block

A

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
Q

Anonymous classes

A

Classes without a name that are created in another class and used once

71
Q

When declaring an anonymous class a __ or __ must be specified

A

Base class. Interface. Then any additions/customizations can be added

72
Q

T/F: Anonymous classes must override any inherited abstract methods at the time of creation

A

True

73
Q

T/F: Anonymous classes can’t override any methods other than abstract ones

A

False. They may, but aren’t required too.

74
Q

The anonymous class will be stored in a __ of the base class and __ will be used to access the anonymous portions

A

Variable. Polymorphism.

75
Q

When are anonymous classes useful?

A

If they are needed in only one place and they contain a small amount of code

76
Q

T/F: An inner class is a better choice than an anonymous class if the code inside will be long/complicated

A

True

77
Q

Anonymous classes level of access

A

Everything in the containing class

78
Q

Anonymous classes have access to __ in the method where it is created. These are __ by the class

A

Local variables. Captured.

79
Q

Variables used in an anonymous class must be

A

Final or effectively final. Changing them after use in the class will return a compilation error.

80
Q

T/F: The state in an anonymous class is easily accessible outside the class

A

False. The state is most often referenced through an interface or base class that doesn’t give visibility to any new state

81
Q

Functional Interface

A

An interface with only one method

82
Q

Because they are so small, functional interfaces are often implemented as __

A

Anonymous classes

83
Q

Lambda Expressions

A

Syntactic shorthand for anonymous classes

84
Q

When using lambda expressions, the __ information will not be typed __

A

Inferred. Explicitly.

85
Q

Lambda syntax

A

parameter list -> function body

86
Q

Lambda expressions can often infer:

A

Method names.
Parameter types.
Return statement.

87
Q

Method reference

A

Class/Variable::methodName
Most compact kind of lambda. The parameters and return types must match the functional interface

88
Q

Streams

A

Sequence of elements that can be acted on and manipulated

89
Q

Stream.forEach

A

Used to perform some operation on each element in steam

90
Q

Stream.filter

A

Filter data on specific criteria before doing other work. Returns a modified stream to work on.

91
Q

Procedural Programming

A

Programs that primarily use procedures (functions) to encapsulate statements that are executed step by step

92
Q

Object-oriented Programming

A

Includes state and behavior defined by classes. Objects of a class encapsulate their own copy of the state and behavior. Polymorphism.

93
Q

Programming Paradigm

A

A specific method of writing programs (procedural, object-oriented, etc.)

94
Q

Functional Programming

A

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
Q

Functional Programming in Java

A

Creating classes that define functional interfaces

96
Q

Pure Functions

A

Are not affected by state. Don’t change state. Always return the same result with the same arguments.

97
Q

T/F: Lambdas are always pure functions

A

False. They can modify the state

98
Q

Reduction

A

Process of converting an expression to a simpler form

99
Q

String.matches(regex)

A

Returns true if string matches the regular expression

100
Q

Stream.map

A

Applies mapper function to each element in stream (intermediate operation)

101
Q

Stream.collect

A

Adds each element in stream to collection

102
Q

IntStream.range

A

Creates stream of ints

103
Q

Arrays.stream

A

Uses array (or part of it) as a stream.

104
Q

Files.lines

A

Uses file interpreter as lines as source for stream

105
Q

Collection.stream

A

Uses collection as source of stream

106
Q

Collectors.toList

A

Accumulates a stream into a list

Software Dev II (4 decks)

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