关于算法:MCD4710-Workbook

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
5. | Expressions
   1.1 Numerical Expressions
   Clarify
   What do each of these numerical expressions yield?
6. 9+5
7. 7/2
8. 3**2
9. 10%3
10. 4/2
11. -9%2
12. -10%-4
13. 8//4
14. 14//5
15. 9.5//3
16. 6//3.0
17. 9.5%2
18. 8.0%3
19. 223
20. 4-3*2
21. 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.
22. 10/(5%2)
23. 4+11%6//2**2
24. 2**(9%3+2)+12//(5.5-7.5)
25. 12*(3%2+2)+14//5
26. 3*22(5//7+1)
27. 3+23*(10//5)-7
28. 7-4*4
29. -8%-6//3
30. 3*3/-4
31. -1//-5*-8
32. 5**1-4
33. -2-7%4
34. 1+0%7-9%1
35. -8*6//2%2+-1
36. 684/-6//-4
37. 8+4+2*-3/-3
38. -9+-1%-7–8%-4
39. 9/1-7//7%9
40. 4–8*-4-5%-9
41. -8/-7-7//-5-9
42. 0-5-4%6//-2
43. -6%8+2+-8//-2
44. -6/8//8%8/4
45. 7–4//-4*69
46. -5+-2-3-9**2
47. -44%-12//8
48. 7-10//2-10/6
49. -4+223–9
50. -17//4*-24
51. -5+4+-3//-1*2
52. -2%43-29
53. -4–2+8*-70
    5
    Test 1
    Test 2
    Exam
    Challenge
    What do each of these numerical expressions yield?
54. 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
55. bool(3)
56. bool(”)
57. bool([0])
58. bool(‘cat’)
59. not ‘dog’
60. 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
61. True or False
62. True and False
63. False or False
64. not True or True
65. not (True or True)
66. not not True
    Booleans – with short-circuiting
67. x or True
68. True or x
69. False and x
70. False or x
71. True and False or x
72. False and True or True or x
    Comparison operators
73. 7 <= 3
74. 2 > 2
75. 1 != 0
76. 10 < 5 < 20
77. 3 > 2 < 20
78. 2 == 2 > -4
    Comparisons – with booleans
79. True == 1
80. False < 3
81. False >= 0
82. True == 6
83. True == (not not 6)4
84. False == []
    Practice
    What do each of these boolean expressions yield? Assume each expression is self-contained and identify which will
    result in a NameError.
85. ” or not 0
86. False or False and True or True or x
87. True or False or 2
88. 5 or True and False
89. 3>7 or 9>=15 and 4<5 or not 10==4
90. 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