Slides modified by Erin Chambers

Problem Solving
and Algorithm Design, part 2

Programming

We have seen various examples of programming languages

C was an example of a procedural language

Imperative or procedural model

Program executes a sequence of instructions to accomplish a task

FORTRAN, COBOL, BASIC, C, Pascal,
Ada, and C++

Taking a step back

Suppose I want to describe a program for you to write, but I don't know which language you will use.

We saw an example of this last time, when I described an algorithm using comments and asked you to fill it in.

Write a program to count the length of a message

#include <stdio.h>

main(void)

{

char ch;

int length = 0;

//Prompt the user for a message

//Read the first character of the message

//while loop to count how the message is

//print length of message

return 0;

}

Pseudocode

But remember, even comments are different in various languages!

For example, in python, comments are put after % sign instead of //

We need a way to describe a program which is independent of a specific language.

<number>

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

Why must instructions be unambiguous?

Why must time and data be finite?

<number>

Pseudocode

Pseudocode

A way of expressing algorithms that uses a mixture of English phrases and indention to make the steps in the solution explicit

There are no grammar rules in pseudocode

Pseudocode is not case sensitive

<number>

Pseudocode

Pseudocode

A mixture of English and formatting to make the steps in an algorithm explicit

Algorithm to Convert base-10 number to other bases

While ( the quotient is not zero )

Divide the decimal number by the new base

Make the remainder the next digit to the left in the answer

Replace the original decimal number with the quotient

<number>

Following Pseudocode

What is 93 in base 8?

93/8 gives 11 remainder 5

11/6 gives 1 remainder 3

1/ 8 gives 0 remainder 1

answer 1 3 5

While ( the quotient is not zero )

Divide the decimal number by the new base

Make the remainder the next digit to the left in the answer

Replace the original decimal number with the quotient

<number>

Pseudocode for Complete Computer Solution

Write "Enter the new base"

Read newBase

Write "Enter the number to be converted"

Read decimalNumber

Set quotient to 1

While (quotient is not zero)

Set quotient to decimalNumber DIV newBase

Set remainder to decimalNumber REM newBase

Make the remainder the next digit to the left in the answer

Set decimalNumber to quotient

Write "The answer is "

Write answer

Abstract Data Type

Abstract data type

A data type whose properties (data and operations) are specified independently of any particular implementation

Most languages will be able to create some implementation of an abstract data type

Example - Arrays

Suppose we have a collection of data, and want to store it together

If we wish to have random access – meaning, we can look at the 15th element in the collection without scanning the first 14 elements – we call this an array

Picture of an array

The array is given a name, just like any other variable

We access element number 15 by the command:

arrayname[15]

Example – an unsorted array

How do we find out

the value stored at location

4 in the array?

How would we change that

value (in pseudocode)?

Example – a sorted array

Notice that this time,

the underlying data is

actually a sorted list.

How can we find the

largest element in this list?

Array operations

What type of operations should we support, and how do we implement them?

Add item	given an index, shift following

items down and store item at index

(can do only if length < max_length)

Remove item	given an index, shift following

items up one

Get next item	increment value of index and

return value at that position

Array in programming languages

Most programming languages have support for arrays

For example, in C, we declare them by saying:

vartype variablename[length]

This creates an array of max_length = length, where each variable is of type vartype

Example in C

#include <stdio.h>

main(void)

{

//create an array

int myarray[5];

//put values in the array

myarray[0] = 3;

myarray[1] = 10;

myarray[2] = 15;

myarray[3] = myarray[1] + myarray[2];

myarray[4] = 6*myarray[0] + 12;

//print contents of array

printf("The array holds: %d, %d, %d, %d, %d\n", myarray[0], myarray[1], myarray[2], myarray[3], myarray[4]);

return 0;

}

Another Example

We can do more complicated things with arrays, also, like input arrays which are of different lengths

(See example in Kate)

Challenge – convert this example to floating point, so that it accepts and computes with decimal numbers

When are arrays not right?

What disadvantages do you have when you store a list in an array?

How can we fix it with a different abstract data type?

Linked Implementation

Linked implementation

An implementation based on the concept of a node

Node

A holder for two pieces of information

the item that the user wants in the list (item)

a pointer to the next node in the list (next)

Linked Implementation

Figure 9.4 Anatomy of a linked list

Figure 9.4 Anatomy of a linked list

Linked Implementation

Figure 9.5 An unsorted linked list

Linked Implementation

Figure 9.6 A sorted linked list

Linked Implementation

How do we implement the operations?

Add item	given current, insert a new node

with item in the info part between

current and next(current)

Remove item	given current, remove

next(current)

Get next item	set current to next(current)

more items	current does not contain null

Linked Implementation

Figure 9.7 Store a node with info of 67 after current

Linked Implementation

Figure 9.8 Remove node next(current)

Operations on lists

What other operations do we do with lists on a computer?

Think about basic database-type operations

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

Why is sorting important?

Selection Sort

Given a list of names, put them in alphabetical order

Find the name that comes first in the alphabet,
and write it on a second sheet of paper

Cross out the name off the original list

Continue this cycle until all the names on the original list have been crossed out and written onto the second list, at which point the second list contains the same items but in sorted order

Selection Sort

A slight adjustment to this manual approach does away with the need to duplicate space

As you cross a name off the original list, a free space opens up

Instead of writing the value found on a second list, exchange it with the value currently in the position where the crossed-off item should go

Selection Sort

Figure 9.9 Example of a selection sort (sorted elements are shaded)

Bubble Sort

Bubble Sort uses the same strategy:

Find the next item

Put it into its proper place

But uses a different scheme for finding the next item

Starting with the last list element, compare successive pairs of elements, swapping whenever the bottom element of the pair is smaller than the one above it

Bubble Sort

Figure 9.10 Example of a bubble sort

Which one is better?

Frequently, we ask how many operations an algorithm will take as a measure of speed.

Since actual time will vary depending on memory, processor speed, etc., the number of comparisons or swaps is a good measure that is independent of the platform.

Selection Sort and Bubble Sort

How many comparisons did selection sort do in the worst case?

How about bubble sort?

Is there a better way? What other sorting method did you do yesterday?

Mergesort

Remember recursion?

We can use the idea of recursion to sort also.

Algorithm:

Recursively sort the first half and second half of the list.

Merge the two sorted lists together.

How long does mergesort take?

We won't analyze exactly – but notice that we don't compare everything to everything else!

Next problem - searching

If you have your book, open it to page 222.

Now how did you do that?

Searching involved looking for an element in a list.

If the list is unsorted, you have to look at everything.

But what about if the list is sorted?

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

Say that again…

Binary Search

Boolean Binary Search (value, mylist, first, last)

If (first = last)

return (mylist[first] = value)

Else

Set middle to (first + last)/2

if (mylist[middle] = value)

return true

If (mylist[middle] > value)

Binary Search(value, mylist first, middle-1)

Else

Binary Search(value, mylist, middle+1, last)

Binary Search

Figure 9.14 Trace of the binary search

Binary Search

Table 9.1 Average Number of Comparisons

Is a binary search

always better?

More complicated abstract data types

What if we want to store lists which access information in a particular order?

Think about standing in a line at the grocery store:

Where do you get added to the list?

Where do you get removed from?

Queues

Queue

An abstract data type in which items are entered at one end and removed from the other end

FIFO, for First In First Out

No standard queue terminology

Enqueue, Enque, Enq, Enter, and Insert
are used for the insertion operation

Dequeue, Deque, Deq, Delete, and Remove
are used for the deletion operation.

Name

three

everyday

structures

that are

queues

Stacks

Stack

An abstract data type in which accesses are made at only one end

LIFO, which stands for Last In First Out

The insert is called Push and the delete is called Pop

Name three everyday

structures that are stacks

PowerPoint Presentation

Jones & Bartlett Publishers

2002-06-09T09:11:33