# CMPT 115 Lecture Notes - Lecture 2: Pseudocode, Dynamic Array, Bubble Sort

18 pages21 viewsWinter 2016

Department

Computer ScienceCourse Code

CMPT 115Professor

Jason BowieLecture

2This

**preview**shows pages 1-3. to view the full**18 pages of the document.**Algorithms

CMPT 115 lecture notes

Notes written by Michael Horsch, Mark Eramian, Ian McQuillan, Lingling Jin, and Dmytro Dyachuk

Objectives

By the end of this lecture topic, you are expected to be able to

1. explain the relationships between problems, algorithms, and functions

2. deﬁne what pseudocode is as well as its components

3. explain the beneﬁts of writing an algorithm in pseudocode before implementing it

4. represent an algorithm in pseudocode

5. count the number of primitive operations of a given pseudocode algorithm

6. compare the eﬃciencies of diﬀerent algorithms using their asymptotic complexities (Big-O notations)

7. analyze the best and worst case complexities of an algorithm

8. deﬁne intractable and undecidable problems in terms of the computational complexity

Contents

1 Problems versus Algorithms 2

1.1 Problems ............................................... 2

1.2 Algorithms .............................................. 2

1.3 Functions ............................................... 3

2 Pseudocode 4

2.1 Pseudocode .............................................. 4

2.2 Variables ............................................... 4

2.3 AlgorithmHeader .......................................... 4

2.4 StatementConstructs ........................................ 6

3 Algorithm Analysis 7

3.1 MeasuringAlgorithmEﬃciency................................... 7

3.2 PrimitiveOperations......................................... 8

3.3 Big-ONotation............................................ 11

3.4 AnalysisExamples .......................................... 14

3.4.1 LinearLoops ......................................... 14

3.4.2 LogarithmicLoops...................................... 14

3.4.3 NestedLoops......................................... 14

3.4.4 CompleteAlgorithms .................................... 16

1

###### You're Reading a Preview

Unlock to view full version

Only half of the first page are available for preview. Some parts have been intentionally blurred.

4 Computability 17

4.1 HardProblems ............................................ 17

4.1.1 TravelingSalesman...................................... 17

4.1.2 Knapsack ........................................... 17

4.2 Undecidability ............................................ 18

4.2.1 Post’s Correspondence Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

Contents

1 Problems versus Algorithms

1.1 Problems

Problems vs. Algorithms

The diﬀerence between a problem and an algorithm is subtle but important.

Deﬁnition 1. Aproblem is a description which associates inputs to output states.

Problem sort(list,n)

Sort the array list of integers into ascending order.

Pre: list is the array of integers to be sorted, of length n

Post: list contains the same elements, rearranged into ascending order.

Problems

•The preconditions describe the inputs to the problem.

•The postconditions describe the resulting states of the variables.

•A problem statement itself does not indicate how to solve the problem.

1.2 Algorithms

Algorithms

Deﬁnition 2. An algorithm describes a sequence of steps which, when carried out, solves a problem (by

meeting the postconditions upon completion).

•There can be more than one algorithm which solves the same problem.

•For example, bubble sort,selection sort, and mergesort are three algorithms which solve the sorting

problem.

•There may be various advantages and disadvantages of each algorithm, but all solve the problem.

Example Pseudocode Algorithm

2

###### You're Reading a Preview

Unlock to view full version

Only half of the first page are available for preview. Some parts have been intentionally blurred.

Algorithm quickSort(list,n)

Sort the array list of integers into ascending order.

Pre: list :: shared array OfInteger

n:: Integer -- the length of list

Post: list contains the same elements, rearranged into ascending order.

if not(isEmpty(list))

then

Integer pivot ←ﬁrst(list)

ListOfInteger smaller ←selectSmaller (list,pivot)

ListOfInteger larger ←selectLarger (list,pivot)

quickSort(smaller )

quickSort(larger)

list ←glueTogether(smaller ,pivot,larger )

1.3 Functions

Functions

•The Problem versus Algorithm comparison works equally well for subroutines, or functions, of a larger

program.

•If we are writing a spreadsheet application, and we would like to take a column of marks and sort them

into ascending order, we could call the sort function.

•If we know the sort function solves the sorting problem, we don’t need to know how the algorithm, or

function, works.

•The details of the function can be hidden.

•If the function sort implements bubble sort, we could replace its contents with selection sort and the

spreadsheet app would still work!

•A pseudocode algorithm is easier to write than a complete program (in any language)

•You can solve most software design problems using pseudocode (C.E.R.A.R.)

•You can compare diﬀerent solutions to a problem before you implement any of them.

•After you’re happy with your pseudocode algorithm, you can implement it (i.e., convert it to source

code)

•Implementing a well-understood pseudocode algorithm allows you to focus on technical aspects of

programming, after you’ve done all the software design problem-solving.

Levels of Abstraction:

3

###### You're Reading a Preview

Unlock to view full version

#### Loved by over 2.2 million students

Over 90% improved by at least one letter grade.