Week 9 (FL2)

COMP1010/COMP1002
Week 9 (FL2)

In computer science, a road network is often modeled as a graph.

• This is not a graph in mathematics.

• This is also not to be confused with graphics in design.

• This is further not to be confused with computer graphics.

Abstraction

Multiple Choice

In computer science, a road network is often modeled as a:

• Graph

• Equation

• Image

• Table

Multiple Choice

Among following options which is the highest level of data abstraction

• Variable storage in main memory (RAM)

• How OS handles the memory management

• Data created in Python

• Logical view of data, such as Graphs

Why graphs are so common?

They naturally represent entities (as nodes) and their relationships (as edges).

Abstraction

Multiple Select

Why is abstraction important in computer science, especially when modeling complex systems like road networks?

• It helps us solve simple

• -

• -

• -

Multiple Choice

Which of the following is NOT a reason why graphs are commonly used to represent data?

• They naturally represent entities and relationships

• They can model social networks

• They are only used for mathematical equations

• They can represent any network

Multiple Choice

How the Seven Bridges of Königsberg problem can be modeled using a graph. What do the nodes and edges represent in this context?

• In this context, nodes represent land and edges represent the bridges connecting them.

• Nodes represent bridges and edges represent landmasses.
• Nodes represent cities and edges represent railways.
• Nodes represent water bodies and edges represent roads.

Multiple Choice

What is the main challenge in the Seven Bridges of Königsberg problem as described in the slides?

• Finding the shortest path between two points

• Crossing each bridge exactly once

• Visiting each node exactly once

• Coloring the map with minimum colors

Multiple Choice

How the map coloring problem can be represented as a graph and what is the significance of conflict edges.

• Conflict edges are used to connect non-adjacent regions.
• Conflict edges represent regions that can have the same color.
• The map coloring problem involves coloring edges instead of regions.
• In the map coloring problem, conflict edges represent adjacent regions that cannot have the same color.

Multiple Choice

Which of the following are constraints that must be considered when scheduling exams?

• Two exams cannot be scheduled at the same time if a student is taking both

• All exams must be scheduled in the same room

• Exams must be scheduled on different days

• Each exam must be scheduled for two time slots

Multiple Choice

Modeling the exam scheduling problem as a graph, what does an edge between two nodes represent?

• An edge represents the duration of an exam.
• An edge indicates the number of students enrolled in an exam.
• An edge shows the location of the exam.
• An edge represents a conflict or dependency between two exams.

Open Ended

What additional considerations must be taken into account when assigning exams to time slots and rooms, as described in the final slide?

Multiple Choice

Which of the following best describes how the day change problem can be modeled?

• As a cycle in a graph

• As a non-cyclic graph

• As a sequence of unrelated events

• As a list of numbers

Multiple Choice

What happens if you pay $1 from state 100 in the vendor machine?

• It brings you to state 150 and dispatches the candy.

• It brings you to state 50.

• It brings you to state 0.

• It brings you to state 100.

Open Ended

Explain how the concept of a state diagram applies to both the day change problem and the vendor machine example.

Multiple Select

Which of the following are constraints in the Man, Cabbage, Goat, Wolf problem?

• The man can bring only one item at a time.

• The goat cannot stay alone with the cabbage.

• The wolf cannot stay alone with the goat.

• The man must always stay with the cabbage.

Multiple Choice

In a systematic approach to solve the Man, Cabbage, Goat, Wolf problem as outlined in the slides, which one item should be moved to the other side first.

• Man

• Cabbage

• Goat

• Wolf

Multiple Select

After making the first 'good' move in the MCGW problem, what are the two possible next moves?

• | MCGW -> MG | CW -> | MCGW

• | MCGW -> MG | CW -> G | MCW

• | MCGW -> MC | GW -> | MCGW

• | MCGW -> MW | CG -> | MCGW

Open Ended

Why is a tuple preferred over a list in Python when modeling the states in the MCGW problem?

Multiple Choice

Which of the following represents the correct initial state for [man, cabbage, goat, wolf] in the tuple model of the MCGW problem?

• (E, E, E, E)

• (W, W, W, W)

• (E, W, E, W)

• (W, E, W, E)