FIT1045/53: Algorithms and Programming

Fundamentals in Python
Lecture 1
Introduction to Algorithms
Images at http://bloggertowordpresstestblog.blogspot.com.au/2009/11/michael-hansmeyer-solids-at-smallspace.html:

COMMONWEALTH OF AUSTRALIA
Copyright Regulations 1969
WARNING
This material has been reproduced and communicated to you by or on behalf of Monash University pursuant to Part VB of the Copyright Act 1968 (the Act).The material in this communication may be
subject to copyright under the Act.Any further reproduction or communication of this material by you may be the subject of copyright protection under the Act. 1
Do not remove this notice.
What’s this unit about
Algorithms
— Sequence of instructions to solve problem
— Will cover variety of algorithms for different problems

The Python programming language

— Mean to communicate with computer and to implement algorithms
— Like any language: practice is key

Unit Objectives
— Learn to develop and reason about algorithms
— Be able to program them in Python
— Start to understand the limitations of algorithms

2
Transferrable skills from this unit
“Hard” skills
• Python programming
• Algorithm design and analysis

“Soft” skills
• Teamwork (workshops and tutorials)
• Planning (assignments, workshops)
• Communication (workshops and tutorials)

Overall
• Problem solving…

3
Computer Science enables people to do
amazing things
Annie Easley;
Computer scientist, Mathematician, Rocket scientist with NASA for ~32 years
Helped develop the Centaur rocket system (got Cassini to Saturn!)
(left)

Admiral Grace Hopper;

Computer scientist, American Navy Admiral; involved in
development of FORTRAN, COBOL
(right)

Ramanathan V. Guha;
Computer scientist, creator of RSS, worked on Google’s custom
search and adwords
(left)

Donald Knuth;
Computer scientist, mathematician, author. Developed the TeX
typesetting system, and wrote the widely read “The Art of
Computer Programming” (Turing award worthy)
(right)

Satoshi Nakamoto;
Computer scientist/cryptographer. Developer of the bitcoin; ???
(left) 4
…by improving their thinking
“This knowledge [on algorithms] […] is a general-purpose mental
tool that will be a definite aid to the understanding of other subjects,
whether they be chemistry, linguistics, or music, etc. The reason for this
[…]: It has often been said that a person does not really understand
something until after teaching it to someone else. Actually, a person
does not really understand something until after teaching it to
a computer, i.e., expressing it as an algorithm...”

Donald Knuth
5
Requires investment of time and
attention

Contact hours
— Lectures (2h per week)
— Tutorials (2h)
— Workshops (2h)
— Optional: Coding for insufficient recommended hardcore
Beginners (2h)

Self study (5-7h)

— Practice (4-5h)
— Reading (1-2h)

6
Recommended literature
Levitin, A. (2012) Introduction to the
Design and Analysis of Algorithms (3rd
Edition) Pearson

Perkovic, L. (2012) Introduction to

Computing using Python: An Application
Development Focus. John Wiley & Sons, Inc.

7
Where am I?
1. Introduction to unit
2. Unit structure and assessment
3. Getting help
4. What are algorithms

8
Staff
Mario Boley (Chief Examiner, Clayton and
Malaysia, and Lecturer, Clayton)
[email protected]

Tan Hui Xuan and Ganesh Krishnasamy

(Lecturers, Malaysia)
[email protected], [email protected]

Rebecca Young and Simon Teshuva (Head

Tutors)
[email protected], [email protected]

[email protected]
9
Conventional Lectures

http://www.pedagogygeek.com/category/uncategorized/
10
Quiz time
1. Visit https://flux.qa
2. Log in (your Authcate details)

11
Quiz time
1. Visit https://flux.qa
2. Log in (your Authcate details)
3. Touch the + symbol
4. Enter your audience code
◦ Clayton 1pm, 2pm: GISNZ3
◦ Clayton 4pm, 6pm: ZWE2WD
◦ Malaysia: 4SZI61
5. Answer questions

12
Assessment
In-semester Marks (max of 60%)
— Assignment Part 1 (10%)
— Assignment Part 2 (12%)
— Workshops (19%)
— Tutorial Preparation (8%)
— In-tutorial test 1 (3%)
— In-tutorial test 2 (8%)

Exam (40%) (2 hours)

13
Assessment:
Assignment Parts 1 and 2 (10%, 12%)
— Complex programming tasks covering different types of
important problems
— Individual work in your own time
◦ Part 1 due week 6
◦ Part 2 due week 11

— IMPORTANT: you need to explain your code to

demonstrators in interviews (weeks 7 and 12). Not doing the
interview yields 0 marks for respective assignment
— Last semester many students simply did not come to their
interview, leading to many students getting 0
— Past students consistently recommend: “start early, plan
ahead!!!”

14
Assessment:
Workshops (max 16% and 3%)
— All about programming practice with Python
◦ Active learning
◦ Preparation for assignments

— Marked workshops released in weeks 1,2,3,4,5,7,8,9,10

◦ Assisted programming in workshop (instructor is around to help)
◦ Finish the rest in your own time
◦ Workshop n must be uploaded on Moodle by midnight on
Tuesday of week n+1
◦ In weeks 7 and 12 we do assignment interviews. There is still a
worksheet for the earlier week (6 and 11), but it is not assessed.

— Each week is worth 2 marks to maximum of 16 marks

◦ Mark is given based on number of tasks solved…and ability to
explain solution to instructor
◦ Students are marked individually (even if work done as a pair) 15
Assessment:
Workshops cont. (max 16% and 3%)
— Marked workshops from Workshop 2 will contain an
advanced problem that is worth 3 marks
◦ The advanced problem may be attempted as many times as
desired
◦ The final mark is the best mark of the attempts
◦ Marks are given based on how well the task is solved
◦ … and ability to answer instructor questions
◦ Students may collaborate to implement a solution, but will be
interviewed individually

16
Assessment:
Tutorial preparation (max 8%)
— Every tutorial from week 2 onwards contains a preparation
question (weeks 2-12)
◦ Tutorial prep n must be posted in the Moodle forum of your
tutorial by midnight on Tuesday of week n

— Each week is worth 1 mark to maximum of 8 marks

◦ Mark is given based on whether there was a genuine attempt to
answer the question

17
Assessment:
In-semester tests (3%, 8%)
2x in-semester tests
— In week 4, and week 9, on Moodle
— Timed test, ~30 minutes duration
— Covers content taught in first 3 and 8 weeks
respectively
— Designed to give you a feeling for exam-style
questions

18
Assessment:
Final Exam (40%) (2 hours)
During Exam period

Contains questions on:

• Definitions
• Programming/Python
• Analysis of algorithms
• Algorithm design
• Running algorithms by hand
• And more…
19
Submission of Assignments
Submission details will be specified on each assignment part
— You will submit your assignment parts through Moodle
— Whenever you submit you must complete a submission form
— Late submission will have 10% off the maximally achievable assignment
marks per day (including weekends)
— Assignments submitted 7 days after the due date will not be accepted.

Extensions
— Compelling and exceptional reasons only (must be unforeseeable
circumstances) via special consideration request
— Send to [email protected] with supporting
documentations BEFORE deadline
— Don’t stop working!

20
Quiz time
1. Visit https://flux.qa
2. Log in (your Authcate details)
3. Touch the + symbol
4. Enter your audience code
◦ Clayton 1pm, 2pm: GISNZ3
◦ Clayton 4pm, 6pm: ZWE2WD
◦ Malaysia: 4SZI61
5. Answer questions

21
Hurdles (see Unit Guide)
To pass this unit a student must obtain:
◦ 45% or more in the unit's examination, and
◦ 45% or more in the unit's total non-examination assessment, and
◦ an overall unit mark of 50% or more.
If a student does not pass these hurdles then a mark of
no greater than 45-NH will be recorded for the unit.

22
Week Lecture a Lecture b Assessment
1 Introduction to Algorithms Introduction to Python
2 Functions and Selection While-loops and Workshops due from
Sequences week 2-11 (excluding 7)
3 For-loops and Sequences Tables and Matrices

4 Decomposition Understanding Python Test 1 in tutorial (3%)

5 Sorting Problem Invariants
6 Introduction to Complexity Search Problem Assignment Part 1 (10%)

7 Divide and Conquer Divide and Conquer Interview in workshop

cont.
8 Recursion Guest Lecture
9 Graphs, Stacks and Queues Transform and Conquer Test 2 in tutorial (8%)

10 Solving Linear Systems Combinatorial

Optimisation Problems
11 Brute Force Backtracking Assignment Part 2 (12%)

12 Complexity Classes Revision Interview in workshop

Where am i?
1. Introduction to unit
2. Unit structure and assessments
3. Getting help
4. What are algorithms?

24
Help is Available
We want to help you succeed!
• Lecturer
• Tutors
• Consultations
• Coding for Beginners Workshop
• Moodle forums
• PASS

25
PARTICIPATE & ACHIEVE BETTER RESULTS

PEER-ASSISTED STUDY
SESSIONS (PASS)
§ Available for FIT1045
§ Receive support and mentoring from a senior
student successful in this unit
§ Weekly study sessions to keep you up-to-date
§ Learnthrough samples, teamwork, and group
study games
§ Fine-tune study skills
§ Make new friends

THE PASS EQUATION

1 hour of PASS =
3 hours struggling on your own
26
PARTICIPATE & ACHIEVE BETTER
RESULTS
FIT1045 S2 2018

PASS GETS RESULTS

60%

50%

40%

Students who regularly attend PASS 30%

§ are more likely to score a D or HD 20%

§ are less likely to fail the unit 10%

0%
N P C D HD

Regularly attended PASS (5 or more sessions) Did not attend PASS

The comparative PASS results for FIT1045 last year

PARTICIPATE & ACHIEVE BETTER
RESULTS
SIGN UP TO PASS
— Sign up for PASS via Allocate+ in Week 1

— Select a FIT1045 PASS session that fits your schedule

— No spots left in Allocate+? Drop into the session anyway.
Most classes do not have full attendance
— For any other requests, please
email [email protected]

— PASS study sessions begin in Week 2. See you there!

Seek assistance as a preventative
measure
Take the following relevant preventative measures as soon as
possible, if you are falling behind in your studies:

§ Study difficulties: Discuss any difficulties you are experiencing with

your tutor or lecturer.
These staff members can assist you in identifying your problem areas and
explore the options available to you in your course.
§ Language and learning online can help you with study methods,
language skills and work presentation (organised by the library)
http://www.monash.edu.au/lls/llonline/
§ Student life and support services can be found at
http://monash.edu/students/support/ and include: Health services,
support and services, clubs and sports etc

29
Disability Support Services
Do you have a disability, medical or mental health
condition that may impact on your study?
Disability Support Services provides a range of services for registered
students including:
§ Note takers and Auslan interpreters
§ Readings in alternative formats
§ Adaptive equipment and software
§ Alternative arrangements for exam and class tests

Disability Support Services also support students who

are carers of a person with a disability, medical or
mental health condition, or who is aged and frail.
For further information and details about how to register:
T: 03 9905 5704
E: [email protected]
monash.edu/disability

30
Special consideration
— If something beyond your control is
affecting your performance on
assessment we might be able to do
something for you!
— Please send requests with documentation
to the role account:
[email protected]
— See special consideration policy
(https://www.monash.edu/exams/changes/
special-consideration)
31
Cheating, Collusion, Plagiarism
— Cheating: Seeking to obtain an unfair advantage in an
examination or in other written or practical work
required to be submitted or completed for assessment.

— Collusion: Unauthorised collaboration on assessable

work with another person or persons.

— Plagiarism: To take and use another person’s ideas and

or manner of expressing them and to pass them off as
one’s own by failing to give appropriate acknowledgement.
This includes material from any source, staff, students or
the Internet – published and un-published works.

http://infotech.monash.edu.au/resources/student/assignments/policies.html
32
Cheating, Collusion, Plagiarism
MOSS

http://lightonphiri.org/wp-content/uploads/2015/09/moss_sample-initial_result-masked-
021.png

33
Where am I?
1. Introduction to unit
2. Unit structure and assessment
3. Getting help
4. What are algorithms

Learning outcomes:
— 1, translate between problem descriptions and program
design with appropriate input/output representations

34
Image at: vindelz.wordpress.com/2009/11/algorismi1.jpg

What is an Algorithm?
Question: what is 653+274?

1 1 al-Khwarizmi
653 653 653 653 (c. 780 – 850)

274 274 274 274

7 27 927

Instructions:
write given numbers on top of each other
for each column:
find result digit for column
“carry over” potential overflow
35
Definition
[Levitin, p3]
“An algorithm is a sequence of instructions for solving a
problem.”

36
Definition
[Levitin, p3]
“An algorithm is a sequence of instructions for solving a
problem, i.e., for obtaining a required output for any
legitimate input in a finite amount of time.”

— Input (zero or more)

— Output (one or more)

— Finiteness (must always terminate)

37
Quiz time
1. Visit https://flux.qa
2. Log in (your Authcate details)
3. Touch the + symbol
4. Enter your audience code
◦ Clayton 1pm, 2pm: GISNZ3
◦ Clayton 4pm, 6pm: ZWE2WD
◦ Malaysia: 4SZI61
5. Answer questions

38
But what is a problem?
A computational problem is a typically infinite collection of
questions (called inputs or instance), each of which has at least
one correct associated answer (called output).
Example: Addition
— 17+4 is an input (question) of the comp. problem Addition
— The output (answer) to this instance is 21

(17, 4) 12
(43, 57) 100
inputs (0, 12) 21
problem outputs
(instances) (37294, 364026) 401320
… solves …

algorithm
executes

input “computer” output 39

But what is a problem?
A computational problem is a typically infinite collection of
questions (called inputs or instance), each of which has at least
one correct associated answer (called output).
Addition Problem
Input: two numbers ! and "
Output: the sum ! + "

(17, 4) 12
(43, 57) 100
inputs (0, 12) 21
problem outputs
(instances) (37294, 364026) 401320
… solves …

algorithm
executes

input “computer” output 40

Image at: vindelz.wordpress.com/2009/11/algorismi1.jpg

What is an Algorithm?
Problem: 1203 + 98 = ?

al-Khwarizmi
1203 (c. 780 – 850)

98

Instructions:
write given numbers on top of each other
for each column:
find result digit for column
“carry over” potential overflow
41
Image at: vindelz.wordpress.com/2009/11/algorismi1.jpg

What is an Algorithm?
Problem: 1203 + 98 = ?

al-Khwarizmi
1203 1203 (c. 780 – 850)

98 98
1

Instructions:
write given numbers on top of each other (right-aligned)
for each column:
find result digit for column
“carry over” potential overflow
42
Image at: vindelz.wordpress.com/2009/11/algorismi1.jpg

What is an Algorithm?
Problem: 1203 + 98 = ?

1 al-Khwarizmi
1203 1203 (c. 780 – 850)

98 98 Instructions need
1 to be definite

Instructions:
write given numbers on top of each other (right-aligned)
for each column (from right to left):
find result digit for column
“carry over” potential overflow
43
Image at: vindelz.wordpress.com/2009/11/algorismi1.jpg

What is an Algorithm?
Problem: 1203 + 98 = ?

1 al-Khwarizmi
1203 1203 “computer” needs (c. 780 – 850)

98 98 to be able to
1 effectively carry
out instruction
Instructions:
write given numbers on top of each other (right-aligned)
for each column (from right to left):
find result digit for column
“carry over” potential overflow
44
Quiz time
1. Visit https://flux.qa
2. Log in (your Authcate details)
3. Touch the + symbol
4. Enter your audience code
◦ Clayton 1pm, 2pm: GISNZ3
◦ Clayton 4pm, 6pm: ZWE2WD
◦ Malaysia: 4SZI61
5. Answer questions

45
Definition
[Levitin, p3]
“An algorithm is a sequence of unambiguous instructions
for solving a problem, i.e., for obtaining a required output for
any legitimate input in a finite amount of time.”

— Input (zero or more)

— Output (one or more)

— Finiteness (must always terminate)

— Definiteness (each step sufficiently well defined)

— Effectiveness (“computer” can perform each step)

46
Example: Greatest Common Divisor

18 3
=
24 4
gcd(18, 24) = 6

Greatest Common Divisor Problem

Input: two non-negative integers m and n
Output: greatest common divisor of m and n

Do you already know an algorithm to solve this problem?

47
Example: Robbing a Museum

4kg 9kg 10kg

400$ 1800$ 3500$

20kg 2kg 1kg

4000$ 1000$ 200$
http://www.unusualbag.com/

Museum Robbing Problem

Input: collection of items (with a weight and dollar
value) and a knapsack (with a set capacity)
Output: collection of items to put in the knapsack to
maximise value? 48
Example: Moving disks
Towers of Hanoi Problem
Input: stack of disks on a peg, where every disk is
smaller than the one directly below
Output: sequence of moves that transfers all disks to a
different peg without ever having to stack a larger
disk on a smaller

49
Before Next Lecture
Log onto the FIT1045/53 Moodle site

Make sure you have flux.qa set up

Attempt the online quiz module on Moodle

Think about how to write an algorithm to solve

the Greatest Common Devisor problem

50