乐趣区

关于算法: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
退出移动版