1st 10

Question 1

capture reusable pieces of design wisdom.

Answer 1

Design patterns

Goals:
Quickly communicate design wisdom to new designers
Give a shared vocabulary to designers

Question 2

Notation OF LIFO
Insert:
Remove:
The accessible element is called BLANK

Answer 2

PUSH
POP
TOP.

Question 3

Restricted form of list: Insert and remove only at front of list.

Answer 3

LIFO: Last In, First Out.

Question 3

Restricted form of list: Insert at one end, remove from the other.

Answer 3

FIFO: First in, First Out

Question 4

Notation OF FIFO
Insert:
Delete:
First element:
Last element:

Answer 4

Enqueue
Dequeue
Front
Rear

Question 5

Often want to insert records, delete records, search for records.

Answer 5

Dictionary

Question 6

Required concepts FOR DICTIONARY
Search key:
Key comparison
Equality:
Relative order:

Answer 6

Describe what we are looking for
Sequential search
sorting

Question 7

Problem: How do we extract the key from a record?

Can’t just compare records to each other. Need to extract the key.
How? Could have an explicit key field? No. Explicit key method? No. Records can have multiple keys.
Could the key method be type-sensitive? No, multiple fields in the record can have the same type.

There is a fundamental problem: They key is not a property of the record, it is a property of the context in which the record is being used.

Answer 7

Can’t just compare records to each other. Need to extract the key.
How? Could have an explicit key field? No. Explicit key method? No. Records can have multiple keys.
Could the key method be type-sensitive? No, multiple fields in the record can have the same type.

There is a fundamental problem: They key is not a property of the record, it is a property of the context in which the record is being used.

Question 8

Problem: How do we extract the key from a record?

Answer 8

We will explicitly store the key with the record.

NOTE: Fundamentally, the key is not a property of the record, but of the context.

Question 9

SORTED VS UNSORTED LIST

If list were blank it Could use binary search to speed search
Would need to insert in order, WHICH would is not time efficient thus slowing insert

Which is better?
If lots of searches, blank list is good
If inserts are as likely as searches, then blank blank

Answer 9

sorted
sorting is no benefit.