Class Notes (1,050,137)
CA (601,111)
U of S (3,566)
CMPT (50)
Lecture 2

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

18 pages27 viewsWinter 2016

Department
Computer Science
Course Code
CMPT 115
Professor
Jason Bowie
Lecture
2

This 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 MeasuringAlgorithmEciency................................... 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.