CP164 Study Guide - Midterm Guide: Priority Queue

21 views2 pages

maroonmacaw543

14 Jun 2018

School

Department

Course

Professor

For unlimited access to Study Guides, a Grade+ subscription is required.

Applying Prim's Algorithm

Prim's Algorithm Outline

• Initialize a priority queue.

• Start with an arbitrary node in the graph (base station, in this case).

• Insert all of the edges connected to the node into the priority queue (i.e. the tunnel costs).

• While we have not yet visited all the nodes, remove the first (cheapest) edge from the priority

queue. Add the node at the opposite end of that edge to our list of visited nodes. Now insert all of

the other edges from that node into the priority queue.

•

Solving this example would look like this:

Node Kept

Edge Removed

Priority Queue

A → B, 2

A → C, 3

A → D, 7

A → C, 3

A → D, 7

B → C, 6

B → G, 4

C → E, 1

A → D, 7

B → C, 6

B → G, 4

C → E, 1

C → F, 8

B → G, 4

A → D, 7

B → C, 6

B → G, 4

C → F, 8

E → D, 5

E → F, 4

G → F, 2

A → D, 7

B → C, 6

C → F, 8

E → D, 5

E → F, 4

G → F, 2

E → F, 4

A → D, 7

B → C, 6

C → F, 8

E → D, 5

E → F, 4

E → D, 5

A → D, 7

B → C, 6

C → F, 8

E → D, 5

A → D, 7

B → C, 6

C → F, 8

Note that when node E is added to the list of visited nodes, the edge from E → F (cost 4), is

added to the priority queue. It is eventually removed from the priority queue when the current

node is F because it has the lowest cost. However, both ends of this edge (E and F) are already in

the final node list, so this edge is discarded, and the next cheapest edge, E → D is used instead.

Unlock document

This preview shows half of the first page of the document.
Unlock all 2 pages and 3 million more documents.

Already have an account? Log in

Document Summary

Initialize a priority queue: start with an arbitrary node in the graph (base station, in this case), while we have not yet visited all the nodes, remove the first (cheapest) edge from the priority. Insert all of the edges connected to the node into the priority queue (i. e. the tunnel costs). queue. Add the node at the opposite end of that edge to our list of visited nodes. Now insert all of the other edges from that node into the priority queue. A b, 2 a c, 3 a d, 7. A c, 3 a d, 7 b c, 6 b g, 4. A d, 7 b c, 6 b g, 4 c e, 1 c f, 8. A d, 7 b c, 6 b g, 4 c f, 8 e d, 5 e f, 4. A d, 7 b c, 6 c f, 8 e d, 5 e f, 4 g f, 2.

Related Questions

29. Consider the Cocktail Sort (code 4) algorithm described in the appendix. What is the fewest number of lines of code that would have to be added, removed, or changed in order for this algorithm to sort from largest to smallest? (A) Everything inside the second for loop. (B) 3 (C) 1 (D) 2 (E) Everything inside both for loops. Binary answers For the following questions you are to use your choices as they were the representation of a binary number. More precisely, A = 24, B = 23, C = 22, D = 21, and E = 20 position in a base 2 number. For example if you wanted to answer the number 23, you would translate it first as base 2 number, which is 10111, you would blacken A, C, D and E.2 Lets look at this process on your answer sheet, we have these 5 circle you can blacken. Normally you only pick one, here you might have to blacken more than one! @ ® © D ® Following the previous example, the answer we want to input is 23, its binary representation is 10111, hence the circle you would blacken are the following:

1.Write a function encipher(s, n) that takes as inputs an arbitrary string s and a non-negative integer n between 0 and 25, and that returns a new string in which the letters in s have been "rotated" by n characters forward in the alphabet, wrapping around as needed. For example:

>>> encipher('hello', 1) result: 'ifmmp'

>>> encipher('hello', 2) result: 'jgnnq'

>>> encipher('hello', 4) result: 'lipps'

Upper-case letters should be "rotated" to upper-case letters, even if you need to wrap around. For example:

>>> encipher('XYZ', 3)

result: 'ABC'

Lower-case letters should be "rotated" to lower-case letters:

>>> encipher('xyz', 3)

result: 'abc'

Non-alphabetic characters should be left unchanged:

>>> encipher('#caesar!', 2)

result: '#ecguct!'

Hints/reminders:

You can use the built-in functions ord and chr convert from single-character strings to integers and back:

>>> ord('a')

result: 97

>>> chr(97)

result: 'a'

You can use the following test to determine if a character is between 'a' and 'z' in the alphabet:

if 'a' <= c <= 'z':

A similar test will work for upper-case letters.

We recommend writing a helper function rot(c, n) that rotates a single character c forward by n spots in the alphabet. We have given you a template for this helper function in ps3pr3.py that checks to ensure that c is a single-character string. We wrote rot13(c) in lecture; rot(c, n) will be very close to rot13(c)! You can test your rot(c, n) as follows:

>>> rot('a', 1)

result: 'b'

>>> rot('y', 2)

result: 'a'

>>> rot('A', 3)

result: 'D'

>>> rot('Y', 3)

result: 'B'

>>> rot('!', 4)

result: '!'

Once you have rot(c, n), you can write a recursive encipher function.

Once you think you have everything working, here are three more examples to try:

>>> encipher('xyza', 1)

result: 'yzab'

>>> encipher('Z A', 2)

result: 'B C'

>>> encipher('Caesar cipher? I prefer Caesar salad.', 25)

result: 'Bzdrzq bhogdq? H oqdedq Bzdrzq rzkzc.'

2.Write a function decipher(s) that takes as input an arbitrary string s that has already been enciphered by having its characters "rotated" by some amount (possibly 0). decipher should return, to the best of its ability, the original English string, which will be some rotation (possibly 0) of the input string s. For example:

>>> decipher('Bzdrzq bhogdq? H oqdedq Bzdrzq rzkzc.')

result: 'Caesar cipher? I prefer Caesar salad.'

Here are two more examples:

>>> decipher('Hu lkbjhapvu pz doha ylthpuz hmaly dl mvynla lclyfaopun dl ohcl slhyulk.')

result: 'An education is what remains after we forget everything we have learned.'

>>> decipher('python')

result: 'eniwdc'

------------------------------------

def rot(c, n):
""" your docstring goes here """
# check to ensure that c is a single character
assert(type(c) == str and len(c) == 1)

def letter_prob(c):
""" if c is the space character (' ') or an alphabetic character,
returns c's monogram probability (for English);
returns 1.0 for any other character.
adapted from:

"""
# check to ensure that c is a single character
assert(type(c) == str and len(c) == 1)

if c == ' ': return 0.1904
if c == 'e' or c == 'E': return 0.1017
if c == 't' or c == 'T': return 0.0737
if c == 'a' or c == 'A': return 0.0661
if c == 'o' or c == 'O': return 0.0610
if c == 'i' or c == 'I': return 0.0562
if c == 'n' or c == 'N': return 0.0557
if c == 'h' or c == 'H': return 0.0542
if c == 's' or c == 'S': return 0.0508
if c == 'r' or c == 'R': return 0.0458
if c == 'd' or c == 'D': return 0.0369
if c == 'l' or c == 'L': return 0.0325
if c == 'u' or c == 'U': return 0.0228
if c == 'm' or c == 'M': return 0.0205
if c == 'c' or c == 'C': return 0.0192
if c == 'w' or c == 'W': return 0.0190
if c == 'f' or c == 'F': return 0.0175
if c == 'y' or c == 'Y': return 0.0165
if c == 'g' or c == 'G': return 0.0161
if c == 'p' or c == 'P': return 0.0131
if c == 'b' or c == 'B': return 0.0115
if c == 'v' or c == 'V': return 0.0088
if c == 'k' or c == 'K': return 0.0066
if c == 'x' or c == 'X': return 0.0014
if c == 'j' or c == 'J': return 0.0008
if c == 'q' or c == 'Q': return 0.0008
if c == 'z' or c == 'Z': return 0.0005
return 1.0

olivemink636

Grade 9 Science – Lab Safety & Equipment Woksheet

Part A: Highlight ‘T’ for TRUE OR ‘F’ for FALSE for each of the following questions. (K - 35)

1. T F Broken glassware should be swept up immediately and placed in the garbage bin.
2. T F Eyeglasses or contact lenses are an acceptable substitute for googles during an experiment.
3. T F If you arrive at class to find a spilled liquid on your desk, you should assume it is water and wipe
it up with paper towels.
4. T F Students with long hair must tie it back when using Bunsen burners.
5. T F If you take too much of the chemicals needed for an experiment, put it back into the container you
got it from.
6. T F Class B fires are those related to electrical equipment.
7. T F Discard all solid waste by rinsing it down the sink.
8. T F You may consume food and drinks during a lab, as long as it is kept at a safe distance from
chemicals.
9. T F If asked to detect the odour of a chemical in the lab, the student should inhale a deep breath of the
chemical.
10. T F If your clothing were to catch on fire, your first step should be to STOP, DROP and ROLL.
11. T F When using a fire extinguisher, aim at the top of the fire. The chemical in the extinguisher will
fall and put out the flames.
12. T F When heating chemicals in a test tube, heat from the bottom up, aiming the test tube at the
ceiling, and keep the test tube still.
13. T F It is ok to take off my safety goggles if it’s just for a second while I write something down.
14. T F If any chemical makes contact with your eye, wash it immediately at the eyewash station for
fifteen minutes. If you should spill chemicals on your skin, place the affected area under water
immediately.
15. T F Always read through each activity before you begin.
16. T F If you are unsure about any part of the procedure for an experiment, you should figure it out
yourself. Asking the teacher for clarification will result in a lower mark due to lack of preparation.
17. T F It is acceptable to sit during very long experiments.
18. T F It is ok if I don’t know where the lab safety equipment is since I can just ask someone later.
19. T F Be sure to tell your teacher about any accident, broken equipment, or injury that occurs during
class; no matter how minor.
20. T F When working with chemicals, keep pens and pencils away from your mouth.
21. T F In warmer months, it is acceptable to wear sandals during an experiment.
22. T F Determine whether your equipment is cool enough to disassemble by placing the back of your
hand near it.
23. T F Loose-fitting, long-sleeved shirts should be worn during experiments to protect your arms from
burns and chemical splashes.
24. T F If you must retrieve materials during a lab, it is acceptable to leave your Bunsen burner unattended
as long as it is set to a yellow flame.
25. T F To avoid an injury when heating materials, always place a stopper or tight-fitting lid on the
container being heated.
26. T F If a student uses the last of the chemicals in an experiment, it is their responsibility to go into the
storeroom to retrieve an additional quantity of that chemical.
27. T F Always leave your work area clean and dry before leaving the lab and make sure equipment and
glassware is returned clean to its proper place.
28. T F Horseplay is O.K. during a lab as long as no one is getting hurt.
29. T F It is never advisable to place a thermometer in an open flame.
30. T F To cool hot glassware, run cold water over it.
31. T F Class A fires can be extinguished with water.
32. T F Class D fires must be extinguished with water.
33. T F Keep equipment away from the edge of the lab bench.
34. T F If your eye itches while you are working with chemicals, you should rub it with your hands.
35. T F WHMIS stands for warning hazardous materials information symbols.

jhonny

CP164 Study Guide - Midterm Guide: Priority Queue

Document Summary

Get access

Related Documents

CP164 Lecture Notes - Lecture 7: Priority Queue

CP164 Study Guide - Final Guide: Linked Data Structure, Priority Queue, Linked Data

CP164 Lecture Notes - Lecture 7: Priority Queue

Related Questions