online exsam
fadoo
module7.pdf
2/18/2015
1
1 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Module 7 – Problem Solving and Algorithms
Instructor: Kera Watkins 479 Joshi Research Center 937-775-5138 [email protected]
CS1150 Intro to Computer Science
Sources: Jones & Bartlett Learning; Nell Dale and John Lewis – Computer Science Illuminated; Karen Myers – Wright State University; Vance Saunders – Wright State University
2 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Chapter Goals
Distinguish between a simple type and a composite type
Describe two composite data-structuring mechanisms
Distinguish between an unsorted array and a sorted array
Be able to apply an insertion sort to an array of items by hand
Be able to apply either a sequential search or a binary search to an array of items
Demonstrate an understanding of different algorithms by hand-simulating them with a sequence of items
2
3 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Problem Solving
Problem solving
The act of finding a solution to a perplexing, distressing, vexing, or unsettled question
How do you define problem solving?
3
2/18/2015
2
4 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Problem Solving
How do you solve problems?
Understand the problem
Devise a plan
Carry out the plan
Look back
4
5 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Strategies
Ask questions!
– What do I know about the problem?
– What is the information that I have to process in order the find the solution?
– What does the solution look like?
– What sort of special cases exist?
– How will I recognize that I have found the solution?
5
6 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Strategies
Ask questions! Never reinvent the wheel!
Similar problems come up again and again in different guises
A good programmer recognizes a task or subtask that has been solved before and plugs in the solution
Can you think of two similar problems?
6
2/18/2015
3
7 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Strategies
Divide and Conquer!
Break up a large problem into smaller units and solve each smaller problem
– Applies the concept of abstraction
– The divide-and-conquer approach can be applied over and over again until each subtask is manageable
7
8 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Computer Problem-Solving
8
Analysis and Specification Phase
Analyze
Specification
Algorithm Development Phase
Develop algorithm
Test algorithm
Implementation Phase
Code algorithm
Test algorithm
Maintenance Phase
Use
Maintain
9 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Phase Interactions
9
2/18/2015
4
10 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Algorithms
Algorithm
A set of unambiguous instructions for solving a problem or subproblem in a finite amount of time using a finite amount of data
Abstract Step
An algorithmic step containing unspecified details
Concrete Step
An algorithm step in which all details are specified
10
11 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Developing an Algorithm
Two methodologies used to develop computer solutions to a problem – Top-down design focuses on the tasks to be done
– Object-oriented design focuses on the data involved in the solution (We will discuss this design in Ch. 9)
11
12 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Summary of Methodology
Analyze the Problem Understand the problem!!
Develop a plan of attack
List the Main Tasks (becomes Main Module) Restate problem as a list of tasks (modules)
Give each task a name
Write the Remaining Modules Restate each abstract module as a list of tasks
Give each task a name
Re-sequence and Revise as Necessary Process ends when all steps (modules) are concrete
12
2/18/2015
5
13 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Top-Down Design
Process continues for as many levels as it takes to make every step concrete
Name of (sub)problem at one level becomes a module at next lower level
13
14 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Control Structures
Control structure
An instruction that determines the order in which other instructions in a program are executed
Can you name the ones we defined in the functionality of pseudocode?
14
15 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Selection Statements
15
Flow of control of if statement
2/18/2015
6
16 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science 16
Algorithm with Selection
Problem: Write the appropriate dress for a given
temperature.
Write "Enter temperature"
Read temperature
Determine Dress
17 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science 17
Algorithm with Selection
IF (temperature > 90)
Write “Texas weather: wear shorts”
ELSE IF (temperature > 70)
Write “Ideal weather: short sleeves are fine”
ELSE IF (temperature > 50)
Write “A little chilly: wear a light jacket”
ELSE IF (temperature > 32)
Write “Philadelphia weather: wear a heavy coat”
ELSE
Write “Stay inside”
Determine Dress
18 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Looping Statements
18
Flow of control of while statement
2/18/2015
7
19 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Looping Statements
19
Set sum to 0
Set count to 1
While (count <= limit)
Read number
Set sum to sum + number
Increment count
Write "Sum is " + sum
Why is it called a count-controlled loop?
A count-controlled loop
20 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Looping Statements
20
Set sum to 0
Set allPositive to true
WHILE (allPositive)
Read number
IF (number > 0)
Set sum to sum + number
ELSE
Set allPositive to false
Write "Sum is " + sum
Why is it called an event-controlled loop? What is the event?
An event-controlled loop
21 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Composite Data Types
Records
A named heterogeneous collection of items in which individual items are accessed by name. For example, we could bundle name, age and hourly wage items into a record named Employee
Arrays
A named homogeneous collection of items in which an individual item is accessed by its position (index) within the collection
21
2/18/2015
8
22 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Composite Data Types
Employee
name
age
hourly/Wage Following algorithm, stores values into the fields of record:
Employee employee // Declare and Employee variable Set employee.name to “Frank Jones” Set employee.age to 32 Set employee.hourlyWage to 27.50
22
23 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Composite Data Types
23
numbers[0]
numbers[4]
24 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Arrays
As data is being read into an array, a counter is updated so that we always know how many data items were stored
If the array is called list, we are working with
list[0] to list[length-1] or
list[0]..list[length-1]
24
2/18/2015
9
25 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
An Unsorted Array
25
data[0]...data[length-1]
is of interest
26 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science 26
Composite Data Types
integer data[20]
Write “How many values?”
Read length
Set index to 0
WHILE (index < length)
Read data[index]
Set index to index + 1
Fill array numbers with limit values
27 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Sequential Search of an Unsorted Array
A sequential search examines each item in turn and compares it to the one we are searching.
If it matches, we have found the item. If not, we look at the next item in the array.
We stop either when we have found the item or when we have looked at all the items and not found a match
Thus, a loop with two ending conditions
27
2/18/2015
10
28 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Sequential Search Algorithm
Set Position to 0
Set found to FALSE
WHILE (position < length AND NOT found )
IF (numbers [position] equals searchitem)
Set Found to TRUE
ELSE
Set position to position + 1
28
29 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Booleans
Boolean Operators
A Boolean variable is a location in memory that can contain either true or false
Boolean operator AND returns TRUE if both operands are true and FALSE otherwise
Boolean operator OR returns TRUE if either operand is true and FALSE otherwise
Boolean operator NOT returns TRUE if its operand is false and FALSE if its operand is true
29
30 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Sorted Arrays
The values stored in an array have unique keys of a type for which the relational operators are defined
Sorting rearranges the elements into either ascending or descending order within the array
A sorted array is one in which the elements are in order
30
2/18/2015
11
31 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Sequential Search in a Sorted Array
If items in an array are sorted, we can stop looking when we pass the place where the item would be it were present in the array
31
Is this better?
32 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
A Sorted Array
32
A sorted array of
integers
33 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science 33
A Sorted Array
Read in array of values
Write “Enter value for which to search”
Read searchItem
Set found to TRUE if searchItem is there
IF (found)
Write “Item is found”
ELSE
Write “Item is not found”
2/18/2015
12
34 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science 34
A Sorted Array
Set found to TRUE if searchItem is there
Set index to 0
Set found to FALSE
WHILE (index < length AND NOT found)
IF (data[index] equals searchItem)
Set found to TRUE
ELSE IF (data[index] > searchItem)
Set index to length
ELSE
Set index to index + 1
35 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Binary Search
Sequential search
Search begins at the beginning of the list and continues until the item is found or the entire list has been searched
Binary search (list must be sorted)
Search begins at the middle and finds the item or eliminates half of the unexamined items; process is repeated on the half where the item might be
35
Say that again…
36 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Binary Search
36
Set first to 0
Set last to length-1
Set found to FALSE
WHILE (first <= last AND NOT found)
Set middle to (first + last)/ 2
IF (item equals data[middle]))
Set found to TRUE
ELSE
IF (item < data[middle])
Set last to middle – 1
ELSE
Set first to middle + 1
RETURN found
2/18/2015
13
37 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Binary Search
37
Figure 7.10 Trace of the binary search
38 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Binary Search
38
Table 7.1 Average Number of Comparisons
Is a binary search always better?
39 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Sorting
Sorting
Arranging items in a collection so that there is an ordering on one (or more) of the fields in the items
Sort Key
The field (or fields) on which the ordering is based
Sorting algorithms
Algorithms that order the items in the collection based on the sort key
39
Why is sorting important?
2/18/2015
14
40 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Insertion Sort
If you have only one item in the array, it is already sorted.
If you have two items, you can compare and swap them if necessary, sorting the first two with respect to themselves.
Take the third item and put it into its place relative to the first two
Now the first three items are sorted with respect to one another
40
41 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Insertion Sort
The item being added to the sorted portion can be bubbled up as in the bubble sort
41
42 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Insertion Sort
InsertionSort Set current to 1 WHILE (current < length)
Set index to current Set placeFound to FALSE WHILE (index > 0 AND NOT placeFound)
IF (data[index] < data[index – 1]) Swap data[index] and data[index – 1] Set index to index – 1
ELSE Set placeFound to TRUE
Set current to current + 1
42
2/18/2015
15
43 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Subprogram Statements
We can give a section of code a name and use that name as a statement in another part of the program
When the name is encountered, the processing in the other part of the program halts while the named code is executed
43
Remember?
44 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Subprogram Statements
What if the subprogram needs data from the calling unit?
Parameters
Identifiers listed in parentheses beside the subprogram declaration; sometimes called formal parameters
Arguments
Identifiers listed in parentheses on the subprogram call; sometimes called actual parameters
44
45 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Subprogram Statements
45
Figure 7.14 Subprogram flow of control
2/18/2015
16
46 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Subprogram Statements
46
47 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Important Threads
Information Hiding
The practice of hiding the details of a module with the goal of controlling access to it
Abstraction A model of a complex system that includes only the
details essential to the viewer
Information Hiding and Abstraction are two sides of the same coin
47
48 Wright State University, Department of Computer Science Dr. Kera Z. Watkins, Computer Science & Engineering
CS1160 Intro to Programming
CS1150
Introduction to Computer Science
Important Threads
Identifiers
Names given to data and actions, by which – we access the data and
Read firstName, Set count to count + 1
– execute the actions Split(splitVal)
Giving names to data and actions is a form of abstraction
48
