26 Algorithmic Problem Solving #2: Sudoku 26 [A Peek at Programming, June 2010]
A Peek at Programming or, problem solving in Computer Science
Aaron Tan http://www.comp.nus.edu.sg/~tantc/bingo/
2
Contents What is Computer Science (CS)? What is Problem Solving? What is Algorithmic Problem Solving? What is Programming? Control structures Recursion [A Peek at Programming, June 2010]
3
What is Computer Science? Computing Curricula 2001 (Computer Science) Report identifies 14 knowledge focus groups Discrete Structures (DS) Programming Fundamentals (PF) Algorithms and Complexity (AL) Architecture and Organization (AR) Operating Systems (OS) Net-Centric Computing (NC) Programming Languages (PL) Human-Computer Interaction (HC) Graphics and Visual Computing (GV) Intelligent Systems (IS) Information Management (IM) Social and Professional Issues (SP) Software Engineering (SE) Computational Science (CN) 3 [A Peek at Programming, June 2010] P = NP ? O(n2)
4
Problem Solving Exercises The exercises in the next few slides are of varied nature, chosen to illustrate the extent of general problem solving. Different kinds of questions require different domain knowledge and strategies. Apply your problem solving skills and creativity here! [A Peek at Programming, June 2010]
5
Warm-up #1: Glasses of milk Six glasses are in a row, the first three full of milk, the second three empty. By moving only one glass, can you arrange them so that empty and full glasses alternate? [A Peek at Programming, June 2010]
6
Warm-up #2: Bear A bear, starting from the point P, walked one mile due south. Then he changed direction and walked one mile due east. Then he turned again to the left and walked one mile due north, and arrived at the point P he started from. What was the colour of the bear? [A Peek at Programming, June 2010]
7
Warm-up #3: Mad scientist A mad scientist wishes to make a chain out of plutonium and lead pieces. There is a problem, however. If the scientist places two pieces of plutonium next to each other, KA-BOOM!!! [A Peek at Programming, June 2010] In how many ways can the scientist safely construct a chain of length 6? General case: What about length n?
8
Warm-up #4: Silver chain A traveller arrives at an inn and intends to stay for a week. He has no money but only a chain consisting of 7 silver rings. He uses one ring to pay for each day spent at the inn, but the innkeeper agrees to accept no more than one broken ring. [A Peek at Programming, June 2010] How should the traveller cut up the chain in order to settle accounts with the innkeeper on a daily basis?
9
Warm-up #5: Dominoes Figure 1 below shows a domino and Figure 2 shows a 44 board with two squares at opposite corners removed. How do you show that it is not possible to cover this board completely with dominoes? Figure 1. A domino. Figure 2. A 44 board with 2 corner squares removed. General case: How do you show the same for an nn board with the two squares at opposite corners removed, where n is even? Special case: How do you show the same for an nn board with the two squares at opposite corners removed, where n is odd? [A Peek at Programming, June 2010]
10
Warm-up #6: Triominoes Figure 3 below shows a triomino and Figure 4 shows a 4 4 board with a defect (hole) in one square. How do you show that the board can be covered with triominoes? General case: How do you show that a 2n 2n board (where n 1) with a hole in one square (anywhere on the board) can be covered with triominoes? Figure 3. A triomino. Figure 4. A 44 board with a hole. [A Peek at Programming, June 2010]
11
[A Peek at Programming, June 2010] Problem Solving Process (1/5) Analysis Design Implementation Testing Determine the inputs, outputs, and other components of the problem. Description should be sufficiently specific to allow you to solve the problem.
12
Problem Solving Process (2/5) Analysis Design Implementation Testing Describe the components and associated processes for solving the problem. [A Peek at Programming, June 2010]
13
Problem Solving Process (3/5) Analysis Design Implementation Testing Develop solutions for the components and use those components to produce an overall solution. [A Peek at Programming, June 2010]
14
Problem Solving Process (4/5) Analysis Design Implementation Testing Test the components individually and collectively. [A Peek at Programming, June 2010]
15
Problem Solving Process (5/5) [A Peek at Programming, June 2010] Analysis Design Implementation Testing Determine problem features Write algorithm Produce code Check for correctness and efficiency Rethink as appropriate
16
Algorithmic Problem Solving An algorithm is a well-defined computational procedure consisting of a set of instructions, that takes some value or set of values, as input, and produces some value or set of values, as output. Algorithm Input Output [A Peek at Programming, June 2010]
17
Programming [A Peek at Programming, June 2010] Java constructs Problem solving Program
18
A Java Program (Bingo.java) [A Peek at Programming, June 2010] // Display a message. public class Bingo { public static void main(String[] args) { System.out.println("B I N G O !"); } } Comment Class name Method name Method body Output
19
Another Java Program (Welcome.java) [A Peek at Programming, June 2010] // Author: Aaron Tan // Purpose: Ask for user’s name and display a welcome message. import java.util.*; public class Welcome { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); System.out.print("What is your name? "); String name = scanner.next(); System.out.println("Hi " + name + "."); System.out.println("Welcome!"); } } API package Creating a Scanner object Input An object of class String
20
Control Structures Control structures determine the flow of control in a program, that is, the order in which the statements in a program are executed/evaluated. 20 [A Peek at Programming, June 2010]
Comments