Brainscape's Knowledge GenomeTM

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


See full index

COMP 215 > TEST 3 > Flashcards

TEST 3 Flashcards

1
Q

Language

A

language defines a set of strings of comprised of characters from an “alphabet” of symbols – defines valid words and combos of words in a sentence

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

Regular language

A

a language that can be formally described using a finite state machine

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

Finite state machine

A

an abstract model of computation comprised of states + transitions

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

Regular expression

A

a pattern used to search for a match within a string of text

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

What two properties must hold in order for a finite state machine to be considered deterministic?

A
  1. Every transition requires that an event occur (char. be consumed)
    2.There is at most one transition on the same event (character) out
    of a particular state
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

|

A

or

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

[]

A

any single letter in word brackets

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

[-]

A

match one single character from contgious range **a-c valid but c-a is not

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

\

A

treat the next character literally, rather than as an operator; ie \“[cat]”\ then [cat] will be accepted

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

why double \ not single

A

bc \ has special meaning as an example ie if we want to do a literal double qoute in a string and not end the string there we use \ to escape the literal

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

?

A

match 0 or 1 instances of the preceding character or group;

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

*

A

match 0 or more instances of the preceding character or group;

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

+

A

match 1 or more instances of the preceding character or group;

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

what is difference between + and *

A

+ means at least 1 * means can be 0

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

Order of operations

A
  1. \
  2. [] including -
  3. ()
      • ?
  5. concatenation (valid regex back to back)
  6. |
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

public String substring(int startIdx)

A

returns the substring
from startIdx (inclusive) to the end

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

String substring(int startIdx, int endIdx)

A

returns the substring from startIdx (inclusive) to endIdx (exclusive)

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

public int indexOf(String str)

A

returns the start index of the
first occurrence of str in the string; returns -1 if str is not found

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

public String replaceAll(String regex, String new)

A

a copy of the original string with every substring that matches regex replaced by new– can pass string literal or reg ex – reg ex adds additonal flexibality

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

sentence

A

a sequence of strings in the language

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

language

A

defines a set of strings of comprised of characters from an “alphabet” of symbols (does not have to be A-Z)

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

sentence

A

a sequence of strings in the language

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

grammar

A

definition of the structure of a valid sentence in the language

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

syntax

A

the structural validity of a sentence

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

semantics

A

the meaning of a sentence

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

int x = “abc is

A

is syntactically valid, but semantically invalid

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

syntax analysis

A

the process of analyzing a sequence of symbols to see if they conform to a grammar

28
Q

To implement a recursive descent parser for a given grammar, you need to define one function per [Your answer] , and each function should have one branch per [Your answer] .

A

production rule, delimiter

29
Q

ad hoc pros and cons

A

Pros: often quicker & easier to write
when the grammar is simple
● Cons: less structured; less extensible; difficult to cover all cases for a more complex grammar

30
Q

Recursive Descent

A

Pros: closely mirrors the grammar; highly
structured and easily extensible
● Cons: can be longer and more difficult to write if the grammar is simple (or if the grammar isn’t formally expressed)

31
Q

Why JSON

A

Pros:
● Lightweight syntax (unlike XML)
● Designed to represent program data (unlike all others shown)
● Human readable (unlike protocol buffers)
hierarchal structure (unlike csv)
clear and concise way to rep arrays (unlike XML)

32
Q

what are the internal representations of each of the following Java classes?

A

JSONArray: List<object>
Map<String, Object></object>

33
Q

Creational Patterns:

A

Singleton, Factory, Builder
Patterns concerning creation of objects;
alternatives to invoking a constructor using new

34
Q

Singleton Pattern:

A
35
Q

Structural Patterns:

A

Composite, Adapter
Patterns concerning how objects and
components are structured

36
Q

Behavioral Patterns:

A

Observer, Strategy, Visitor
Patterns concerning how responsibilities and algorithms are assigned and/or distributed across objects

37
Q

Override:

A
38
Q

Overload:

A
39
Q

What is double dispatch? and why is it important?

A
40
Q

Storage:

A

Long-term (files)

41
Q

Memory:

A

Short-term (program data)

42
Q

How is memory allocated?

A

Memory TO a program: done by OS
Memory WITHIN a program:
Manual: Programmer asks
Automatic: Runtime does it

43
Q

Memory Organization:

A

Code: Instructions to be executed
Stack: One frame per function
Heap: Chunk of memory for longer-lasting data

44
Q

How are primitive types stored?

A

Local variables value in stack frame
Fields/elements value in array/object

45
Q

How are reference types stored?

A

Array/object always on heap
local variables address in stack frame
Fields/elements address in array/object

46
Q

How is memory deallocated/freed?

A

Stack automatically after each function terminates
Heap:
Manual: Programmer frees memory
Automatic: Runtime detects and frees
variables not in use

47
Q

Reference Counting:

A

Compiler: Inserts operations for incrementation
Runtime: Allocates, executes, frees

47
Q

Reference Counting pros and cons:

A

Pros: Easy, happens immediately, good performance.
Cons: Single self-referencing, cycles

48
Q

factory pattern

A

When to use it? When you want to create multiple instances, but
want to abstract away details of the creation process
KEYWORDS: method to use instead of constructor

49
Q

builder

A

When to use it? When the logic for creating an instance of type T
involves many steps, including instantiating many objects
KEYWORDS: streamline, hierarchy, components

50
Q

Composite Pattern

A

When to use it? When many parts comprise a whole, and you
want to define a functionality across the entirety of the structure
think about a figure composed of multiple shapes– tree like structure
KEYWORDS: delegate

51
Q

adapter pattern

A

When to use it? When you want to connect two incompatible
classes or interfaces (A and B)
■ Helps improve flexibility and reusability
■ If A interacts with B, you can change how one works without
changing the other

52
Q

Trace-Based (Mark-Sweep):

A

Compiler: does nothing
Runtime: Allocates marks and sweeps

53
Q

Trace-Based (Mark-Sweep) pros and cons:

A

Pros: Handles self-references, no overhead
Cons: “Stop the world” causes delays

54
Q

Fragmentation:

A

Free space becomes non-contiguous

55
Q

Mark-Sweep Compacts:

A

Removes dead objects and readdresses live objects so freed space is contiguous

56
Q

observer pattern

A

When to use it? When you want one or more components to
“subscribe” to automatic updates from another component
KEYWORD: updates, notifies

57
Q

strategy

A

When to use it? When you want to be able to choose from one of
multiple interchangeable algorithms or implementations
■ Decouples the algorithm from the class that it operates on
KEYWORD: single metric

58
Q

visitor

A

When to use it? When you want to decouple an algorithm from
the structures that it operates on
■ Similar to the strategy pattern in this decoupling, but targets
algorithms that are distributed across multiple data types
■ More complex but more flexible than the strategy pattern
decouple, contiguous , multiple data types

59
Q

double dispatch

A

instead of directly calling the method that encapsulates the algorithms we go through an extra layer of indirection thus 2 methods call are made to ensure correct algorithms executes

60
Q

override

A

use the same signature (name + parameter types);
can optionally make the return type more specific
■ Multiple implementations within the same hierarchy

61
Q

overload

A

use the same signature (name + parameter types);
can optionally make the return type more specific
■ Multiple implementations within the same hierarchy

62
Q

difference between overriding and overloading

A

overloading differs in that one implenmentation isnt replacing another but rather they are coexisting with the context of the same class

63
Q

The factory and builder patterns are similar in that they are each designed to
make it easier to construct a new instance of an object. What is the key
difference between them? (Hint: It has to do with the nature of the object being
constructed!)

A

The factory pattern is more focused on creating objects with a simple and
uniform construction process and provides a way to address the creation of
different related objects. On the other hand, the builder pattern is designed for
more complex object construction with a complex internal structure.

64
Q

The strategy and visitor patterns are similar in that they both decouple an algorithm from the class on which it operates. What is the key difference between them?

A

The key difference lies in how the nature of the object influences the algorithm. In the strategy pattern, the algorithm’s behavior is influenced by the strategy chosen at runtime for a specific context. In contrast, the visitor pattern is designed for scenarios where the algorithm needs to operate on various types of objects, and the double dispatch mechanism ensures that the correct algorithm is executed based on both the type of the object and the type of the visitor.

65
Q

What is double dispatch, and why is it necessary in the visitor pattern? You should address the need for the accept() method as well as the need to re-define the accept() method within each concrete subclass of IVisitable.

A

Double dispatch in the Visitor pattern involves making two method calls to ensure the correct algorithm is executed. The first dispatch occurs when the accept() method is called on the object being visited, and the second dispatch happens when the visit() method is invoked on the visitor. This mechanism is necessary because the algorithm is distributed across multiple data types. The accept() method is crucial for the first dispatch, and re-defining it in each concrete subclass ensures polymorphic behavior, allowing the correct visit() method to be bound at runtime based on the types of both the object and the visitor.

66
Q

how java determines between overriding and overloading

A

Overriding: The method to be executed is determined at runtime based on the actual type of the object. It’s called dynamic dispatch. The JVM decides which version of the method to execute based on the actual type of the object at runtime.
Overloading: The method to be called is determined at compile time based on the method signature. The compiler selects the appropriate method to call based on the number and types of arguments used in the method invocation.

COMP 215 (3 decks)

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