CS Chapter 2 Problem Solving and Theory of Computation

What is computational thinking?

The ability to think logically about a problem and apply techniques to solve it.

What is simulation?

Designing a model of a real system to understand how it works.

What are some uses of simulation?

Amusement park rides, population problems, queueing problems, etc.

What is enumeration?

Listing out all the cases of a problem to find the best possible solution.

How does an anagram solver use enumeration?

It lists out all combinations of a set of letters to find all possible anagrams.

What is trial and error?

Experimenting with different approaches to a problem until a successful one is found.

Give an example of trial and error.

Trying on different shoe sizes to find the perfect fit.

What is a theoretical approach?

Using published knowledge to make an educated guess about how effective a solution is.

Give an example of using a theoretical approach.

Predicting if a biker will clear a ramp using physics and measurements.

What is a creative solution?

Thinking outside the box to solve problems where traditional methods may fail.

Give an example of a creative solution.

Solving trolling issues on Twitter creatively.

What is structured programming?

A method of writing a program using top-down analysis, modularisation, and structured code.

What is top-down analysis?

Breaking down a problem into modules that are easier to solve.

What is modularisation?

Structuring a program into modules that can be organised and reused.

What are the features of structured programming?

Sequence, Selection, Iteration.

What is a sequence?

One or more statements executed one after another.

What is selection?

Choosing an option using IF…THEN…ELSE or CASE statements.

What is iteration?

Repeating a set of steps (looping).

What are the three types of iteration?

Condition tested before loop (WHILE), Count controlled (FOR), Condition tested after loop (REPEAT UNTIL).

What is top-down design?

Dividing a program into modules and sub-tasks, where each performs a single function.

What do hierarchy charts show?

The overall structure of a program.

What does a module shown below another module mean in a hierarchy chart?

It is part of the module above.

How does execution occur in a hierarchy chart?

From left to right at the lowest level component.

Are selection and iteration shown in a hierarchy chart?

No, they are not shown.

Why are structured programs easier to write?

Because large programs are broken into manageable sub-tasks.

Can modules be tested individually?

Yes, each module can be tested on its own.

Can modules be reused?

Yes, they can be reused many times and saved to a library.

How does structured programming speed up development?

Multiple programmers can work on different modules simultaneously.

Are structured programs more reliable?

Yes, they have fewer errors and are easier to test and debug.

Are structured programs easier to maintain?

Yes, they are easier to follow and modify.

Do changes in one module affect others?

No, because each module is self-contained.

Can new features be added easily?

Yes, by adding new modules.

What names should be used for variables?

Meaningful names.

What should be added to explain each module?

Comments.

What should each module do?

Perform a specific task.

How many entry points should selection/iteration structures have?

A single entry point.

How should modules stay self-contained?

By passing parameters and using local variables.

What is an algorithm?

A set of steps to solve a problem.

What are the properties of a good algorithm?

Clear steps, handles valid/invalid inputs, has termination, efficient, and easy to understand.

What tools are used to design algorithms?

Hierarchy charts, flowcharts, pseudocode.

What is insertion sort good for?

Sorting a small number of elements.

How does insertion sort work?

A data item is picked and inserted into the correct position.

How does insertion sort compare to bubble sort?

It has fewer swaps and is faster.

When is bubble sort useful?

When only a small number of items need sorting.

How does bubble sort work?

Items are compared and swapped over multiple passes.

How many passes does bubble sort need?

n-1 passes for n items.

What is merge sort good for?

Sorting large data sets.

How does merge sort work?

It splits values and merges them in order.

How fast is merge sort compared to other sorting algorithms?

Much faster for large data sets.

How does linear search work?

It checks each item from the start of the list (brute force).

Does linear search require a sorted list?

No.

How efficient is linear search for large data sets?

It can be very slow.

How does binary search work?

It halves the search area each time (divide and conquer).

Does binary search require a sorted list?

Yes.

Is binary search faster for large data sets?

Yes, much faster than linear search.

Why are programs tested?

To reveal errors, not to prove they work.

What types of data should be used in testing?

Normal, boundary, and erroneous data.

What is module testing?

Checking if each subroutine works properly.

What is program testing?

Checking if each individual program works.

What is system testing?

Making sure the entire system works correctly and meets requirements.

What is a trace table used for?

Hand-tracing an algorithm and tracking variable values.

What goes in the first column of a trace table with a loop?

The loop condition.

What is decomposition?

Breaking a problem into sub-problems that perform identifiable tasks.

What is composition?

Combining procedures to form a compound procedure.

What is abstraction?

Removing non-essential details from a problem to simplify it.

What is an example of abstraction?

The London Underground map.

What is information hiding?

Hiding details of a data object that don’t define its essential characteristics.

What is problem abstraction?

Removing details until a solvable version of the problem is left.

What is procedural abstraction?

Reusing procedures without showing internal values or logic.

What is functional abstraction?

Calling a built-in function without knowing how it works internally.

What is data abstraction?

Hiding the specifics of data representation to allow abstract data structures.

What is automation?

Putting real-world abstractions into action through algorithms and code.

What does automation involve?

Creating algorithms, implementing models in data structures, and executing code.

What is a finite state machine?

An abstract model representing how a system changes from one state to another.

How many states can an FSM be in at once?

Only one.

What is a transition in an FSM?

A change from one state to another based on a condition or event.

What defines an FSM?

Its states and the conditions for each transition.

Where are FSMs used?

Robotics, video games, compilers, protocols, hardware, and language design.

What is finite state automation?

An FSM used to accept or reject inputs without producing outputs.

What are the key parts of finite state automation?

Start state and end/accept states.

When is input accepted in an FSM?

When it reaches an end/accept state.

How does finite state automation process input?

It starts from the start state and transitions through symbols to the target state.

What does a state transition table show?

The next state for any given input.