Computational Thinking in CSC 235: Problem Solving

Iyan Kanj
School of Computing
DePaul University
ikanj@cdm.depaul.edu

April 4, 2009

Concept 1

Defining Subgoals.

This technique aims at defining a simpler problem (or problems) than the original problem, whose solution leads to a solution to the original problem.

Learning goal

The students should demonstrate a good understanding of the Defining Subgoals technique, and be able to apply it. The technique and its general applicability will be discussed in class, and the students will be presented with an illustrative example, such as the Towers of Hanoi problem discussed below.

Example: Towers of Hanoi

Given 3 pegs labeled A, B, C and n disks (of different sizes) placed on top of each others on peg A in a decreasing order of their size (largest at the bottom). The problem is to transfer the disks from peg A to peg C under the restriction that no disk can be placed on top of a smaller one.

Questions & Discussion

  1. Demonstrate a solution to the Towers of Hanoi problem with 4 disks. How many steps does your solution take?
  2. Your ultimate goal is to transfer the n disks from peg A to peg C. Define an appropriate subgoal. (Hint. transfer n-1 disks from peg ? to peg ?)
  3. Show how using the subgoal defined above you can achieve the ultimate goal of transferring the n disks from peg A to C.

Assessment

To test the students’ understanding on the Defining Subgoals technique, they will be given a relevant problem and they need to identify the subproblem (a reduction) within it whose solution leads to a solution of the original problem. They also need to illustrate the process of going from a solution of the subproblem to a solution for the original problem. Here is an example of a problem relevant to this technique, that appeared on a previous exam for this course.

Problem

Constructing a straight-line passing through a given point and parallel to a given straight-line.

  1. Using a compass and a straight-edge ruler, describe how to implement the following task.
  2. Task. Given a straight line (L), and a point M outside of (L), draw the perpendicular line from M to (L). (2) Let (L) be a straight-line and M be a point not on (L). Our goal is to draw the line
    passing through M and parallel to (L). Define an appropriate subgoal using the above
    task, and show how achieving this subgoal leads to achieving the original goal.
Concept 2: Searching and Pruning. This technique uses heuristics and exhaustive
search methods to arrive at a solution. It is usually used to solve problems which do
not possess “easy solutions”. For such problems one may need to perform a
systematic search to check all possible choices that may lead to a solution.

Learning goal: The student should learn how to apply systematic search procedures
and understand how they can be automated. The students will also learn some basic
searching and pruning algorithms, such as depth-first search. The technique and its
general applicability will be discussed in class, and the students will be presented with an
illustrative example, such as the following example.

Example: Queens of Chess.

The problem asks to place 8 queens on a chessboard (in general, to place n queens on a chess board) such that no two queens can attack each other.

Questions and Discussion:

  1. Find a solution to the problem on an 8x8 chessboard by trial and error.
  2. Suppose that, in your search, you were able to place the ith queen successfully on the board but you couldn’t place the (i+1)st queen. How do you modify your search?
  3. Can you devise a systematic method to list all solutions to the problem?

Assessment

To test the students’ understanding of this technique, they will be given a relevant problem and they need to illustrate how to apply the process of searching and pruning to arrive at a solution. Here is an example of a problem relevant to this technique that was given in class before.

Problem. Consider the maze given below.

  1. Show how to model the maze using a graph. What are the vertices and edges?
  2. Apply depth-first search to the graph to find a solution to the maze.