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:
1. 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.
2. 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.
3. 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.
4. 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
1 | Expressions
1.1 Numerical Expressions
Clarify
What do each of these numerical expressions yield?
1. 9+5
2. 7/2
3. 3**2
4. 10%3
5. 4/2
6. -9%2
7. -10%-4
8. 8//4
9. 14//5
10. 9.5//3
11. 6//3.0
12. 9.5%2
13. 8.0%3
14. 2**2**3
15. 4-3*2
16. 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.
1. 10/(5%2)
2. 4+11%6//2**2
3. 2**(9%3+2)+12//(5.5-7.5)
4. 1*2**(3%2+2)+14//5
5. 3*2**2**(5//7+1)
6. 3+2*3**(10//5)-7
7. 7*-4**4
8. -8%-6//3
9. 3*3/-4
10. -1//-5*-8
11. 5**1-4
12. -2-7%4
13. 1+0%7-9%1
14. -8*6//2%2+-1
15. 6*8*4/-6//-4
16. 8+4+2*-3/-3
17. -9+-1%-7--8%-4
18. 9/1-7//7%9
19. 4--8*-4-5%-9
20. -8/-7*-7//-5*-9
21. 0-5-4%6//-2
22. -6%8+2+-8//-2
23. -6/8//8%8/4
24. 7--4//-4**6*9
25. -5+-2**-3**-9**2
26. -4**4%-1**2//8
27. 7**-10//2**-10/6
28. -4+2**2**3--9
29. -1**7//4*-2**4
30. -5+4+-3//-1*2
31. -2%4**3-2**9
32. -4--2+8**-7*0