MCD4710代写、代写Python程序语言

日期：2022-01-08 05:07

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

5

Test 1

Test 2

Exam

Challenge

What do each of these numerical expressions yield?

1. int(False or True)*2**2**(14//5*2%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

1. bool(3)

2. bool('')

3. bool([0])

4. bool('cat')

5. not 'dog'

6. 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

1. True or False

2. True and False

3. False or False

4. not True or True

5. not (True or True)

6. not not True

Booleans - with short-circuiting

1. x or True

2. True or x

3. False and x

4. False or x

5. True and False or x

6. False and True or True or x

Comparison operators

1. 7 <= 3

2. 2 > 2

3. 1 != 0

4. 10 < 5 < 20

5. 3 > 2 < 20

6. 2 == 2 > -4

Comparisons - with booleans

1. True == 1

2. False < 3

3. False >= 0

4. True == 6

5. True == (not not 6)4

6. False == []

Practice

What do each of these boolean expressions yield? Assume each expression is self-contained and identify which will

result in a NameError.

1. '' or not 0

2. False or False and True or True or x

3. True or False or 2

4. 5 or True and False

5. 3>7 or 9>=15 and 4<5 or not 10==4

6. not [] and 2<2 and 'cat'or 7>4<12

1Operator precedence at url: https://docs.python.org/3/reference/expressions.html#operator-precedence

2Boolean Operator behavior at url: https://docs.python.org/3/library/stdtypes.html#boolean-operations-and-or-not.

3Truth value testing at url: https://docs.python.org/3/library/stdtypes.html#truth

4Note that == has higher precedence than not, which means brackets must be used to avoid a SyntaxError.

7