comp 215 test #4

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/101

encourage image

There's no tags or description

Looks like no tags are added yet.

102 Terms

1
New cards

Define sentence (in the context of grammars)

A sequence of words

2
New cards

Define grammar

The definition of a language's syntax; any syntactically valid sentence in the language can be "matched" by its grammar

3
New cards

Define terminal symbol

A token, i.e. a literal string in the grammar

4
New cards

Define non-terminal symbol

A name for a grammar rule (production)

5
New cards

Define start symbol

The non-terminal on the left-hand side of the first production rule

6
New cards

Define syntax

Whether a sentence is structurally valid

7
New cards

Define semantics

Whether a sentence is meaningful

8
New cards

Define parsing

Analyzing a sequence of symbols to see if they conform to a grammar

9
New cards

Define natural language

A language developed by people to speak with each other

10
New cards

Define delimiter

A separator character

11
New cards

How do you structure a recursive descent parser for a grammar?

One function per production, with one branch per acceptable expansion

12
New cards

pros + cons of ad hoc string processing?

Quicker and easier to write when the grammar is simple

Less structured and extensible; easier to miss cases

13
New cards

pros and cons of recursive descent parsing

Closely mirrors the grammar; highly structured and easily extensible

Can be longer and harder to write than needed when the grammar is simple

14
New cards

Define language (in the context of regular languages)

Something defined by its syntax and semantics

15
New cards

Define regular language

A language whose syntax can be formally described using a finite state machine

16
New cards

Define finite state machine

An abstract model of computation made up of states and transitions

17
New cards

Define regular expression

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

18
New cards

How many starting states can a finite state machine have?

Exactly one

19
New cards

How many accepting states can a finite state machine have?

One or more

20
New cards

When an FSM models a regular language, what does a valid word correspond to?

A sequence of transitions (a path) that starts at the initial state and ends in an accepting state

21
New cards

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

(1) Every transition requires an event (a character is consumed); (2) from any state, reading a given character takes you to max one state (not multiple options)

22
New cards

precede

23
New cards

What does concatenation do in a regex, and what is its precedence?

Matches one regex immediately followed by another; precedence 5

24
New cards

What does | do in a regex, and what is its precedence? + fsm

Matches either string; precedence 6 (last)

<p>Matches either string; precedence 6 (last)</p>
25
New cards

What does [_] do in a regex, and what is its precedence? + fsm

Matches one single character contained in the brackets; precedence 2

<p>Matches one single character contained in the brackets; precedence 2</p>
26
New cards

What does [-] do in a regex, and what is its precedence?

Matches one single character from a contiguous range of ASCII characters; precedence 2

27
New cards

What does \_ do in a regex, and what is its precedence? + fsm

Treats the next character literally rather than as an operator; precedence 1 (first)

<p>Treats the next character literally rather than as an operator; precedence 1 (first)</p>
28
New cards

What does _? do in a regex, and what is its precedence? + fsm

Matches zero or one instances of the preceding character/group; precedence 4

<p>Matches zero or one instances of the preceding character/group; precedence 4</p>
29
New cards

What does _* do in a regex, and what is its precedence? + fsm

Matches zero or more instances of the preceding character/group; precedence 4

<p>Matches zero or more instances of the preceding character/group; precedence 4</p>
30
New cards

What does _+ do in a regex, and what is its precedence? + fsm

Matches one or more instances of the preceding character/group; precedence 4

<p>Matches one or more instances of the preceding character/group; precedence 4</p>
31
New cards

What does (_) do in a regex, and what is its precedence?

Groups operations in order to make structure clearer or change the order of operations; precedence 3

32
New cards

What is the regex order of operations, first to last?

  1. Escape (\)

  2. brackets ([ ] and [ - ])

  3. parentheses

  4. quantifiers (? * +)

  5. concatenation

  6. alternation (|)


33
New cards

Which String methods from the String Processing video mutate the String they're called on?

None; Java Strings are immutable

34
New cards

Define serialization

Converting an object into a series of bytes

35
New cards

Define deserialization

Converting a series of bytes back into an object

36
New cards

What is the benefit of a standardized serialization format like CSV, YAML, XML, or JSON?

Programs written in different languages can read the serialized object

37
New cards

What is the internal representation of a JSONArray?

List<Object>

38
New cards

What is the internal representation of a JSONObject?

Map<String, Object>

39
New cards

When you build a JSONObject from a Java object (new JSONObject(obj)), what becomes its keys and values?

Its public getters: the key is the getter name without "get" with the first letter lowercased (getValueOfB → "valueOfB"), and the value is whatever the getter returns. Fields without getters are left out

40
New cards
Define design pattern
A general approach to addressing a recurring design challenge in object-oriented systems
41
New cards
Define creational pattern
A design pattern concerning the creation of objects
42
New cards
Define structural pattern
A design pattern concerning how objects and components are structured
43
New cards
Define behavioral pattern
A design pattern concerning how responsibilities and algorithms are assigned and/or distributed across objects
44
New cards

What design patterns are creation patterns? (3)

singleton, factory, builder

45
New cards

What design patterns are structural patterns? (2)

composite, adapter

46
New cards

What design patterns are behavorial patterns? (3)

observer, strategy, visitor

47
New cards
When is the singleton pattern a good design?
When you want only one instance of a class
48
New cards
What are the key structural features of the singleton pattern?
A static field pointing to the single instance; a getter method that returns that instance; using the getter instead of the constructor
49
New cards
What is the difference between eager and lazy instantiation in the singleton pattern?
Eager creates the singleton immediately, whether or not it's used; lazy waits until the first time it's requested
50
New cards
When is the individual factory pattern a good design?
When you want to create multiple instances but abstract away the details of the creation process
51
New cards
What are the key structural features of the individual factory pattern?
An (often static) factory method inside the class/interface you want to instantiate, used instead of the constructor
52
New cards
When is the polymorphic factory pattern a good design?
When you want to abstract away creation details AND have a polymorphic way of creating instances that could belong to many different subclasses
53
New cards
What are the key structural features of the polymorphic factory pattern?
Same as the individual version: a factory method on the class/interface, used instead of the constructor (it can return instances of different subclasses)
54
New cards
When is the builder pattern a good design?
When creating an instance of type T takes many steps, including instantiating many other objects
55
New cards
What are the key structural features of the builder pattern?
A separate builder class with a top-level method that constructs the T and helper methods that construct its sub-objects; you use the builder instead of the constructor
56
New cards
What is the key difference between the factory and builder patterns?
A factory creates an object in a single method call; a builder constructs a complex object step by step
57
New cards
When is the composite pattern a good design?
When many parts make up a whole and you want to define functionality across the entire structure
58
New cards
What are the key structural features of the composite pattern?
A tree-like structure: leaf objects and composite objects share a common interface, and a composite holds a collection of components and performs operations by delegating to its children
59
New cards
When is the adapter pattern a good design?
When you want to connect two incompatible classes or interfaces
60
New cards
What are the key structural features of the adapter pattern?
A separate adapter class that wraps one or both endpoints; you communicate through the adapter instead of directly with the adaptee
61
New cards
When is the observer pattern a good design?
When you want one or more components to "subscribe" to automatic updates from another component
62
New cards
What are the key structural features of the observer pattern?
A subject that keeps a list of observers and has methods to add and remove them; observers that each implement an update method; when the subject's state changes, it calls update on every registered observer
63
New cards
When is the strategy pattern a good design?
When you want to choose from multiple interchangeable algorithms or implementations
64
New cards
What are the key structural features of the strategy pattern?
A strategy interface with one or more methods; multiple classes implementing it with different strategies; a method elsewhere that uses whichever strategy it's given to perform a task
65
New cards
When is the visitor pattern a good design?
When you want to decouple an algorithm from the structures it operates on
66
New cards
What are the key structural features of the visitor pattern?
A visitor with one visit method per visitable type; a visitable interface with one method, accept; each concrete visitable defines accept to call v.visit(this)
67
New cards
What is the difference between overriding and overloading a method in Java?
Overriding: a subclass redefines a method with the same name and parameter types. Overloading: methods share a name but have different parameter lists (number or types of parameters)
68
New cards
How does Java decide which version of an overridden vs. an overloaded method gets called?
Overridden calls are resolved at runtime based on the object's concrete (runtime) type; overloaded calls are resolved at compile time based on the declared (static) types of the arguments
69
New cards
What is double dispatch?
Choosing which code to run based on the runtime types of two objects instead of one
70
New cards
Why does the visitor pattern need double dispatch and the accept() method?
The right code depends on the types of both the visitor and the visitable; accept() splits that into two single-dispatch calls, so the visitable effectively tells the visitor its own concrete type, with no type checking needed
71
New cards
Why must every concrete visitable class redefine accept() instead of inheriting it?
Overloads are resolved at compile time, so v.visit(this) in a shared parent would pick visit(IVisitable) instead of the specific overload like visit(Circle); in each concrete class, "this" has the concrete static type
72
New cards
What is the key difference between the strategy and visitor patterns?
Strategy runs the same way no matter what concrete type the data is (you just plug in a different algorithm); visitor is one algorithm with different cases depending on the concrete type of the data
73
New cards
What are the two ways memory can be allocated within a program?
Manual: the programmer asks for memory when they need it (e.g. C, Assembly). Automatic: the runtime system does it for you (e.g. Java, Go)
74
New cards
What are the three regions memory is organized into?
Code, stack, and heap
75
New cards

What is the stack region of memory and what’s it?

The call stack; the compiler allocates enough space in each frame to store each local variable, and frames are deallocated automatically when their function returns
76
New cards

What is the heap region of memory?

Where objects and arrays (longer-lasting data) are stored; as opposed to the stack, which holds local variable

not the heap data structure!

77
New cards
Where is a primitive-type local variable stored?
Directly in the stack frame
78
New cards

Where is a primitive-type field (NOT local variable, a field for an object) or array element stored?

Its value is stored directly inside the containing array/object (on the heap)

79
New cards
Where is a reference-type local variable stored?
Its address is stored in the stack frame; the array/object itself is stored on the heap
80
New cards
Where is a reference-type field or array element stored?
Its address is stored in the containing array/object; the referenced array/object itself is on the heap
81
New cards
Do primitive sizes or address sizes vary between machines?
Primitive sizes are constant; address sizes vary (4 bytes on a 32-bit machine, 8 bytes on a 64-bit machine)
82
New cards
What is the formula for the size of an array in memory?
Header size + (number of elements × element size) + padding
83
New cards
What is the formula for the size of an object in memory?
Header size + Σ(field sizes) + padding
84
New cards
In this class, at what address do we assume arrays and objects are allocated?
The lowest possible starting address
85
New cards
What are the two ways the heap can be deallocated?
Manual: the programmer explicitly frees memory. Automatic: the runtime system detects objects that are no longer in use and frees them
86
New cards
How is the stack deallocated?
Automatically; each frame is freed when its function returns
87
New cards
Define garbage collection
Automatic detection and deallocation of memory on the heap that's no longer live
88
New cards
What are the two types of garbage collection?
Reference counting and trace-based
89
New cards
How does reference counting garbage collection work?
It keeps a reference count for each object; an object is live if there is at least one reference to it, and it is freed when its count hits zero
90
New cards
In reference counting, what does the compiler insert?
Operations to increment and decrement reference counts
91
New cards
In reference counting, how are counts updated on an assignment?
Increment the count of the new referent, decrement the count of the old one
92
New cards
In reference counting, how are counts updated on a function call?
Increment the counts for all arguments
93
New cards
In reference counting, how are counts updated on a function return?
Increment the count for the return value; decrement for all references from the stack frame
94
New cards

In reference counting, what does the runtime system do? (4)

Allocates extra space to store reference counts; executes the increment/decrement operations inserted by the compiler; when freeing an object, decrements the counts of its fields or elements; frees objects when their counts hit zero

95
New cards

pros + cons of reference counting

Easy to implement, quick reclamation, good performance

Self-referential garbage: an object that references itself directly or in a cycle never reaches a count of zero, so it's never freed

96
New cards
In trace-based garbage collection, when is an object live?
When it's reachable from the running code
97
New cards

What is the basic idea of trace-based (mark-sweep/mark-compact) garbage collection?

Find and mark all objects reachable from the root set; everything unmarked is garbage

98
New cards
In trace-based garbage collection, what does the runtime system do?

Allocates extra space to store a mark bit; periodically (implementation-dependent) finds and collects garbage

99
New cards
What happens in the mark phase of trace-based garbage collection?
Perform a graph search from each element in the root set and mark each object you reach with a 1
100
New cards
What happens in the sweep phase of trace-based garbage collection?
Linear sweep over the heap contents, freeing each object whose mark bit is still 0