共计 6068 个字符,预计需要花费 16 分钟才能阅读完成。
MCD4710 Workbook
July 22, 2020
Contents
Preface 3
I Programming Fundamentals 4
1 Expressions 5
1.1 Numerical Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Boolean Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Control Flow 9
2.1 Conditionals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.1 While-Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.2 For-Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.2.3 Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3 Sequences 20
3.1 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.2 Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3 Range . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4 Functions 24
5 Code Traces 31
6 Recursion 32
II Data Structures 36
7 Tables and Matrices 37
7.1 Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
7.2 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
8 Graphs 45
8.1 Paths, cycles, and connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
8.2 Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
8.3 Graph Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
9 Stacks and Queues 52
III Algorithm Analysis 53
10 Invariants 54
10.1 Finding Loop Invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
1
11 Computational Complexity 59
11.1 Big-Oh Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
11.2 Computational Complexity of Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
IV Additional Resources 67
12 Practice Exam Questions 68
12.1 Discussion of Theoretical Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
12.2 Computational Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
12.3 Invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
13 Solutions to Practice Exam Questions 72
13.1 Solutions: Discussion of Theoretical Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
13.2 Solutions: Computational Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
13.3 Solutions: Invariants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
2
Preface
This workbook is an additional learning resource for FIT1045 and FIT1053. This is our first semester offering a
workbook, so the workbook will grow as the semester progresses. This workbook is not sufficient for the unit. You
must also complete lectures, workshops, and tutorials.
The workbook will be useful in tutorials during time dedicated to self-directed-learning; as a tool for identifying
any gaps in your knowledge; and for providing materials with which to practice. You can use the workbook as much
or as little as is useful for you.
The questions in this workbook reflect the questions you can expect to see on the in-semester tests, and the final
exam. The difficulty of the questions can be understood like so:
- Clarify questions allow you to identify any misunderstandings you may have with the fundamental tools you
will learn. These are very simple questions. If you can do the practice questions, there is no need to do these
questions. - Practice questions allow you to practice the kinds of questions you will see in your tests and exam. Some will
be knowledge-based, some will be problem solving. If you can do all the practice questions, you will be fully
prepared for the content of the tests and exam. Always start with the practice questions, and if you cannot
do them switch to clarify; if they are too easy switch to challenge. - Challenge questions allow you to practice questions that are more difficult than most of the questions you
will see in your tests and exam. It can be difficult to problem-solve under test conditions, so practicing on
questions that are more difficult than what you might expect to see can be useful. Some questions on the final
exam will be similar to challenge level questions. Solutions will not be provided for Challenege questions. - Extension questions are questions that contain non-assessable content. They may contain a taster of material
that will be taught in later units, or they may show you something cool you can do with the tool you are
being taught.
If you are ever confused by a workbook question, feel free to ask about it in your tutorial, on Moodle, or at a
consult.
Enjoy!
3
Part I
Programming Fundamentals
4 - | Expressions
1.1 Numerical Expressions
Clarify
What do each of these numerical expressions yield? - 9+5
- 7/2
- 3**2
- 10%3
- 4/2
- -9%2
- -10%-4
- 8//4
- 14//5
- 9.5//3
- 6//3.0
- 9.5%2
- 8.0%3
- 223
- 4-3*2
- 13/(5%3)
Practice
What do each of these numerical expressions yield? Make sure you understand when the expression yields a float
and when it yields an integer. - 10/(5%2)
- 4+11%6//2**2
- 2**(9%3+2)+12//(5.5-7.5)
- 12*(3%2+2)+14//5
- 3*22(5//7+1)
- 3+23*(10//5)-7
- 7-4*4
- -8%-6//3
- 3*3/-4
- -1//-5*-8
- 5**1-4
- -2-7%4
- 1+0%7-9%1
- -8*6//2%2+-1
- 684/-6//-4
- 8+4+2*-3/-3
- -9+-1%-7–8%-4
- 9/1-7//7%9
- 4–8*-4-5%-9
- -8/-7-7//-5-9
- 0-5-4%6//-2
- -6%8+2+-8//-2
- -6/8//8%8/4
- 7–4//-4*69
- -5+-2-3-9**2
- -44%-12//8
- 7-10//2-10/6
- -4+223–9
- -17//4*-24
- -5+4+-3//-1*2
- -2%43-29
- -4–2+8*-70
5
Test 1
Test 2
Exam
Challenge
What do each of these numerical expressions yield? - int(False or True)22(14//52%3+2)+2
Answers
Write the expression in the Python shell and compare output.
6
1.2 Boolean Expressions
When answering the following questions, keep in mind Python operator precedence given in the lectures, or found in
the Python documentation.1 It can be helpful to think of operators with higher precedence as having brackets around
them. For example, to think of False or not True and True as being False or ((not True) and True).
Also keep in mind the behavior of the boolean operators given in the lectures, or found in the Python documen-
tation.2
Finally, be aware of when type coercion occurs.
Clarify
What do each of these function calls return or boolean expressions yield?3 - bool(3)
- bool(”)
- bool([0])
- bool(‘cat’)
- not ‘dog’
- not []
What do each of these boolean expressions yield? Assume each expression is self-contained and identify which will
result in a NameError.
Boolean operators - True or False
- True and False
- False or False
- not True or True
- not (True or True)
- not not True
Booleans – with short-circuiting - x or True
- True or x
- False and x
- False or x
- True and False or x
- False and True or True or x
Comparison operators - 7 <= 3
- 2 > 2
- 1 != 0
- 10 < 5 < 20
- 3 > 2 < 20
- 2 == 2 > -4
Comparisons – with booleans - True == 1
- False < 3
- False >= 0
- True == 6
- True == (not not 6)4
- False == []
Practice
What do each of these boolean expressions yield? Assume each expression is self-contained and identify which will
result in a NameError. - ” or not 0
- False or False and True or True or x
- True or False or 2
- 5 or True and False
- 3>7 or 9>=15 and 4<5 or not 10==4
- not [] and 2<2 and ‘cat’or 7>4<12
1Operator precedence at url: https://docs.python.org/3/ref…
2Boolean Operator behavior at url: https://docs.python.org/3/lib…
3Truth value testing at url: https://docs.python.org/3/lib…
4Note that == has higher precedence than not, which means brackets must be used to avoid a SyntaxError.
7