Week 8 – Modelling, Abstraction and Algorithms
[ad_1]Weekly Topics
• In this weeks lecture and lab we will look at the following areas:
• Using abstraction to identify the key aspects of real world objects,
• Modelling solutions to problems using:
• Activity diagrams,
• Use cases,
• State charts, and
• Class diagrams.
• What algorithms are and how we can represent them,
• Some common algorithms for sorting data,
• How we can efficiently search for data.
3
Abstraction
• When we talk about abstraction – what we’re really talking about is
simplification.
• So when designing a computer program or working with data, what we want to
concentrate on are just the important parts with all of the ‘fluff’ taken away.
• Or to put it another way, we want to focus on only the information that is
relevant to the task at hand.
• When we simplify something, our brains are better able to deal with it – because
there’s less to think about!
• This makes life easier for us, and makes it less likely that we’ll make a mistake
or error.
4
Abstraction (Cont’d)
• If we wanted to write a program to store the record the progress of a student
in a course – here are some of the student attributes that we could store:
…and so on.
• But which of these attributes are the most important ones to store student
scores?
Family status
Middle name
Last name
Age
Date of Birth
Religion
Hair colour
Program
Institution
Student ID
Photograph
Next of Kin
Email address
Home address
Semester address
Home telephone
Semester telephone
Mobile phone
Eye colour
Medical history
Work history
Qualifications
Education
Nationality
Marital Status
Citizenship
Hobbies
First name
Grade Point Average
Volunteer experience
Awards
Criminal history
Drivers License
Income
Skin colour
Courses
5
Abstraction (Cont’d)
• Taking that big list of attributes of a Student, we can abstract away the ones
we don’t need to handle student scores, leaving us with something like this:
• So we’ve crunched down our list of 30+ attributes to just three – which are the
only ones required to uniquely identify a student, and we’ve added a few
attributes to track the student’s scores.
Question: Could we crunch our three attributes down any further? If so, should we?
First
Name
Last
Name
Student
ID
Task 1 Task 2 Task 3 Task 4
Jess Smith 30001111
John Brown 30001122
Jack Singh 30001133
James White 30001144
Joy Green 30001155
Model of a student AFTER abstraction
6
Abstraction (Cont’d)
• What about if we were going to write a program that stored information about
Books – what are the attributes that we could store?
7
Abstraction (Cont’d)
• Okay, now which attributes are the most important?
• Probably:
• Author,
• Title,
• ISBN, and
• Publisher.
• Then if we take a look at a website that sells books, these are the kind of
attributes they keep (asides from price!) so we know we’re on the right track:
Off-topic: Basic financial literacy is important and can have a enormous impact on your life and that of your family. If
you only ever read one book on finance in your entire life, then I’d recommend you read this one. -Al
8
Process Abstraction
• There are a few different types of abstraction that we commonly use. We’ve just
looked at data abstraction…
• …but there is also process abstraction – which is where we wrap up a series
of steps into a single step, for example, I could ask someone to:
- Find a clean mug,
- Find and boil approximately 250ml of water,
- Find some instant coffee and put one teaspoon of it in the mug,
- When the water has boiled pour it into the mug,
- Add ~20ml of milk,
- Stir the contents of the mug and bring it to me.
• Or… I could ask them to: Make me a cup of coffee, please! =D
• The end result is the same, but make me a cup of coffee abstracts away all the
steps required into a single statement which is easier to work with!
9
Modelling
• Modelling is the process where we look at a problem or situation and analyse it
so that we can unambiguously describe it.
• Once we have a model of a system, we can implement the model in software.
• So what we’re really saying is that modelling helps us to:
• Determine requirements and functionality,
• Communicate these requirements between all stakeholders (i.e. clients,
programmers, managers etc.), and
• Ensure consistency of work.
• To model a system there are a number of commonly used tools and formats
which we can use, and which you should be familiar with.
10
Unified Modelling Language (UML)
• UML is an industry-standard approach to modelling computer systems and
programs.
• UML standardises the models used to visually describe the design of a system.
• Also, UML is methodology-independent, so it doesn’t matter if you’re using a
waterfall model or agile methodologies to develop the program / system – UML
can unambiguously describe it.
Further reading: http://www.uml.org/
11
Unified Modelling Language (UML) (Cont’d)
• UML specification defines two major kinds of UML diagram:
• Structure diagrams, and
• Behavior diagrams.
• Structure diagrams show the static structure of the system and its parts on
different abstraction and implementation levels and how they are related to each
other.
• The elements in a structure diagram represent the meaningful concepts of a
system, and may include abstract, real world and implementation concepts.
• Behavior diagrams show the dynamic behaviour of the objects in a system,
which can be described as a series of changes to the system over time.
12
Unified Modelling Language (UML) (Cont’d)
• It turns that there are quite a few different types of diagrams that can be used to
model a system at various levels*:
- = but thankfully in this class we only care about a small number of them – phew!
13
Activity Diagrams / Flowcharts
• Activity Diagrams show the decisions / branching of a program or system
based on the state of the system.
• For example, a Process Order activity diagram could look something like this:
14
Activity Diagrams / Flowcharts (Cont’d)
• Meanwhile…
Note: The symbols used in this flowchart are not the correct ones, but if you’re Meat Loaf you probably don’t care…
15
Activity Diagram / Flowchart Notation
• When creating activity diagrams / flowcharts we use a standard series of symbols:
Source: Riley, D., Hunt, Kenny A, & ProQuest. (2014). Computational thinking for the modern problem solver (Chapman & Hall/CRC
textbooks in computing). Boca Raton, FL: CRC Press. pp165,169.
16
Activity: Activity Diagram / Flowchart
• Create an activity diagram that models your routine for getting up in the
morning.
• You might also want to think about:
• Does your routine vary based on it being a week day or a weekend?
17
State Charts
• State charts are used to show the states, and transitions between states, for a
system. Transitions are triggered by events.
• State charts are comprised of: states, events and transitions. For example:
18
State Chart Notation
• A state chart for an ATM might look like this:
Source: Riley, D., Hunt, Kenny A, & ProQuest. (2014). Computational thinking for the modern problem solver (Chapman & Hall/CRC
textbooks in computing). Boca Raton, FL: CRC Press. pp175,179.
19
Activity: State Charts
• Create a state chart diagram that models the behaviour of a mobile phone
making a phone call.
• Base it on a “dumb” phone – ignore internet browsing capabilities
Fun fact: Chuck Norris once kicked a horse in the chin. Its descendants today are known as giraffes.
20
Class Diagrams
• Class diagrams are used to describe classes (i.e. objects – collections of data
and the operations that can be performed on the object).
• We’ll be looking more at Classes and Objects later on in the course.
21
Class Diagram Notation
• We typically draw class diagrams in a box listing the class name, the
attributes / properties of the class, and the methods (i.e. operations we can
perform) using objects of this class.
Source: Riley, D., Hunt, Kenny A, & ProQuest. (2014). Computational thinking for the modern problem solver (Chapman &
Hall/CRC textbooks in computing). Boca Raton, FL: CRC Press. p.118.
21
Name of the class
Attributes / Properties
Methods / Operations
22
Activity: Class Diagrams
• Create a class diagram to represent books in a library cataloguing system we
discussed earlier when we were talking about abstraction.
• The features we identified are our attributes / properties.
• What behaviours are important to a library book?
23
Use Case Diagrams
• Use Cases are a way to describe the actors in a system (i.e. people or entities
that perform actions), along with the possible actions they can perform.
24
Use Case Diagram Notation
• Although use cases imply the sequence of events, they do so in a loose
fashion (unlike flowcharts which have specific start and end points to the flow).
• An «extend» relationship occurs whenever one action is an extension or
specialised version of another. An «include» relationship results from one
action making use of another as part of its own function.
Source: Riley, D., Hunt, Kenny A, & ProQuest. (2014). Computational thinking for the modern problem solver (Chapman &
Hall/CRC textbooks in computing). Boca Raton, FL: CRC Press. p.122.
System boundary
Relationship
Function / Action
Actor (may be a
person or
different system)
25
Use Case Diagrams (Cont’d)
• Each use case can also have a more detailed written description of the
behaviour it represents.
• For example, the verify age of customer behaviour when buying liquor
from a shop could be expanded to explain exactly how this process is
achieved.
• ID card?
• Drivers license?
• Paper documents?
• Use cases can also include alternative behaviours and exceptions.
• Use cases are particularly valuable when used as a requirements document to
share with a client.
• It ensures that your understanding of how the system works, and as such
how you’re going to build the system, reflects how the system actually
works in the real world (which is something the client will know).
26
Sample Use Case
• Name: Verify age of customer
• Brief Description: Confirm customer legal age to purchase drinks.
• Actors: Checkout clerk, Customer.
• Preconditions: Purchase liquor.
• Basic Flow: Customer presents id. Checkout clerk confirms 18+.
• Alternate Flows: Customer presents alternative id. Checkout clerk confirms
18+.
• Exception Flows: Customer is not 18+. Purchase rejected.
• Post Conditions: Age of customer is verified.
27
Activity: Use Case Diagrams
• Create a use case diagram to represent a student borrowing a book from the
library.
• You can assume the student has a library card and is registered in the
library system as a user.
28
Algorithms
• Algorithms are sequences of steps which are carried out in a specific order to
produce a desired outcome.
• Although you might not have any ‘book knowledge’ of algorithms, you actually
use them every single day.
• You already have an algorithm to:
• Brush your teeth,
• Make a phone call,
• Watch a DVD or BluRay,
• Wash the dishes, etc.
• All that makes these processes algorithms is writing down the series of steps
you perform, along with any branch conditions (can’t find toothpaste? phone is
flat, TV is switched off, etc.).
• Once you have the steps and their sequence worked out the desired outcome
will be the same every time!
29
Algorithms (Cont’d)
• Computers use algorithms for absolutely everything. They control what
happens when you switch your computer on, log in, launch an application etc.
• Really, you can think of all computer programs as algorithms – they’re just
sequences of steps along with branching points that determine the state of the
machine at any given time. So in this way, you can think of algorithms as the
text-only version of flowcharts!
EEqquuiivvaalleenntt
30
Pseudocode
• When creating or writing down algorithms, we commonly use pseudocode instead
of a specific programming language.
• Pseudocode is just a straight-forward plain-English description of what’s happening
that’s intended to be easy to comprehend and unambiguous.
• We indent sections of our pseudocode based on any branching criteria. For
example, if we wanted to print out whether each student in a class had passed or
failed an assignment then we might write out our algorithm in pseudocode like this:
For each student in class
If student assignment grade is greater than or equal to
50
Print student name + “Pass”
else
Print student name + “Fail”
31
Sorting Algorithms
• A very common activity for computers is to sort data into a specific order.
• For example, if we had the following list of numbers:
7, 2, 5, 9, 3, 4, 0, 1, 8, 6
• Then if we sorted them into ascending order (getting higher as we go along),
then they’d look like this:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
• And if we sorted them into descending order (getting lower as we go along),
then they’d look like this:
9, 8, 7, 6, 5, 4, 3, 2, 1, 0
32
Sorting Algorithms – Bubble Sort
• Probably the simplest sorting algorithm we can implement is called a bubble
sort.
• In this algorithm we work from left to right comparing two adjacent numbers.
• If the number on the right is lower than the number on the left then we swap
their positions.
• We then move across one and compare the next two numbers doing the
same thing.
• When we get to the last pair of numbers we go back to the beginning.
• If we make it all the way through the set of numbers without having to swap
any of them then we know the numbers are now sorted.
• Let’s take a look at this in action…
Off-topic: Sorting algorithms are worth knowing. I once got accepted for a job at Nortel Networks (which I thankfully didn’t take) partially
because I was able to write down the pseudocode for a couple of different sorting algorithms during the interview. True story. -Al
33
Sorting Algorithms – Bubble Sort (Cont’d)
• Here’s our starting list of un-sorted values:
• We compare the left-most two values (14 and 33) and see that they’re already
sorted, so we leave them alone:
• We move to the right and compare the next two values (33 and 27) and see
that they are not sorted, so we swap them:
• We move to the right again and compare the next two values (33 and 35) and
see that they’re sorted, so we leave them alone:
14 33 27 35 10
14 33 27 35 10
14 27 33 35 10
14 27 33 35 10
34
Sorting Algorithms – Bubble Sort (Cont’d)
• We move on to the final pair of values (35 and 10) and see that they aren’t
sorted so we swap them:
• Now that we’re at the end of the list we go back to the beginning and see that
14 and 27 are still sorted:
• We move across and 27 and 33 are still sorted so that’s fine:
• We move across again and see that 33 and 10 not sorted though, so we need
to swap them:
14 27 33 10 35
14 27 33 10 35
14 27 33 10 35
14 27 10 33 35
35
Sorting Algorithms – Bubble Sort (Cont’d)
• We look at the final 33 and 35, and as they’re sorted we leave them alone:
• Now we go back to the beginning again – 14 and 27 are in order:
• But 27 and 10 aren’t so we swap them:
• Carrying on through the list, 27 and 33 are now fine:
• As are 33 and 35 so again we leave them alone:
14 27 10 33 35
14 27 10 33 35
14 10 27 33 35
14 10 27 33 35
14 10 27 33 35
36
Sorting Algorithms – Bubble Sort (Cont’d)
• Back at the beginning, 14 and 10 are in the wrong order so we swap them:
• Moving along, 14 and 27 are fine:
• 27 and 33 are fine:
• And 33 and 35 are fine:
• Finally, we go all the way through the list again from the beginning and this time
we don’t make ANY swaps at all – this indicates that our list is now sorted!
Visualisation of process: https://www.youtube.com/watch?v=RT-hUXUWQ2I
Hungarian folk dance version (I kid you not): https://www.youtube.com/watch?v=lyZQPjUT5B4
10 14 27 33 35
10 14 27 33 35
10 14 27 33 35
10 14 27 33 35
10 14 27 33 35
37
Sorting Algorithms – Bubble Sort (Cont’d)
• As we’ve just seen – Bubble Sort works…
• …but it’s not very efficient at all, because it passes over and over the same sets
of values (although there are a couple of minor optimisations you can make).
• In fact, Bubble Sort typically works in O(n2) time – which means that for each
value we add to the list, the total number of operations we need to perform to
sort the list increases exponentially! (we’ll talk about performance and Big-O
notation in week 11).
• To see how badly this scales, let’s do a quick table:
Elements in List Operations req’d for Bubble Sort
10 100
100 10,000
1000 1,000,000
10,000 100,000,000
100,000 10,000,000,000 (Ten billion! Lol!)
38
Sorting Algorithms – Selection Sort
• Our next sorting algorithm is called selection sort and it works a little
differently – with selection sort, you essentially take the smallest entry from the
unsorted portion of an array and build a sorted array at the start, entry by entry.
• Let’s start with the same list of numbers we had before:
• We take the first element and assign it to be our lowest value:
• Then we compare it to the next value, and the next – and so on – until we either
find a value that is lower than our current lowest value, or we hit the end of the
list:
14 33 27 35 10
14 33 27 35 10
14 33 27 35 10
14 33 27 35 10
14 33 27 35 10
NNooppee!!
39
Sorting Algorithms – Selection Sort (Cont’d)
• When we get to the 10 it is lower, so that becomes our lowest value:
• As we’ve now hit the end of the list, we swap our current lowest value with the
first element, so now we have one sorted element:
• Then we start from the next index along and make that our lowest:
• 27 is smaller than 33 so that becomes our new lowest:
• 27 is not smaller than 35, but 14 is smaller than 27 – so 14 is our new lowest:
10 33 27 35 14
10 33 27 35 14
10 33 27 35 14
10 33 27 35 14
14 33 27 35 10
10 33 27 35 14
40
Sorting Algorithms – Selection Sort (Cont’d)
• As we’ve now hit the end of the list we swap our lowest value (14) with the
value in index 1 (i.e. the 2nd location – so 33 and 14 swap places):
• Next up we’re starting at index 2 (3rd location) and marking that as our lowest:
• Neither 35 nor 33 are lower than 27, so when we get to the end of our list 27 is
still our lowest value:
10 33 27 35 14
10 14 27 35 33
SSoorrtteedd sseeccttiioonn UUnnssoorrtteedd sseeccttiioonn
10 14 27 35 33
10 14 27 35 33
10 14 27 35 33
41
Sorting Algorithms – Selection Sort (Cont’d)
• Technically we swap our lowest value (27) with index 2 (3rd location) here – but
it’s already in index 2 so doing so doesn’t change anything:
• Moving on to start at index 3 (4th location) we take 35 as our lowest:
• 33 is lower than 35 so that then becomes our lowest:
• Aaaand we’ve hit the end of the list again so we swap the first unsorted index
(i.e. 35) with our current lowest (33), then as there’s only a single ‘unsorted’
value at the right-hand side, it’ll be our largest and we’ve get a sorted list!
Visualisation of process: https://www.youtube.com/watch?v=3hH8kTHFw2A
10 14 27 33 35
10 14 27 35 33
10 14 27 35 33
10 14 27 35 33
SSoorrtteedd sseeccttiioonn UUnnssoorrtteedd sseeccttiioonn
42
Sorting Algorithms – Merge Sort
• Sometimes we want to merge two lists together into a single sorted list – what
we could do is just append (i.e. join together) both lists and then sort that…
• …but there’s a much nicer way of doing it called a merge sort:
Source: https://www.youtube.com/watch?v=Pr2Jf83_kG0
43
Sorting Algorithms – Quick Sort
• The final sorting algorithm we’ll look at today is called a quick sort. This works
differently to the previous bubble and selection sorts that we’ve just seen, and
is more like a divide-and-conquer approach:
- Quicksort first picks a point at which to divide an array into two smaller subarrays
which it calls the low elements and the high elements. As you might
imagine, this is the divide step. - Then, once we have two arrays, we reorder the array so that values less
than the pivot value sit on the left of the pivot, and values larger than the
pivot sit to the right of the pivot. - Then we go back to step 1 for each sub-array until each sub-array is
sorted!
• When all of our sub-arrays are sorted, our entire array is sorted!
44
Sorting Algorithms – Quick Sort (Cont’d)
• Let’s quicksort our standard list of numbers – we start by selecting the pivot as
the middle value (which we’ll colour blue):
• Now we’re going to start from the left moving across until we find a value that is
higher than our pivot:
• We found that 33 is on the left of our pivot, but should be on the right-hand side
because it’s larger. So now we work from the right-hand side to find a value
that’s lower than our pivot – and we immediately find the value 10.
• Now we swap the left and right values we identified:
14 33 27 35 10
14 33 27 35 10
14 33 27 35 10
14 33 27 35 10
14 10 27 35 33
45
Sorting Algorithms – Quick Sort (Cont’d)
• We can still move across on the right-hand side, but 35 isn’t lower than our
pivot value of 27 so we leave it where it is:
• Now we’re going to do the exact same thing we did to the entire array to just
the low section – we’ll pick 10 as our pivot, and then move from the left to the
right:
• We immediately see that 14 should be on the right of our pivot, and there’s
nothing (that we care about) on the right of our pivot, so we swap them:
14 10 27 35 33
14 10 Don’t care!
LLooww sseeccttiioonn HHiigghh sseeccttiioonn
14 10 Don’t care!
10 14 Don’t care!
SSoorrtteedd!!
46
Sorting Algorithms – Quick Sort (Cont’d)
• Now we’ll work on the high section and pick the middle value 35 as our pivot:
• Working from the left we’re looking to find a value which is higher than our pivot,
but 27 isn’t bigger than 35 so we leave it alone and there’s nothing else to the
left of the pivot for us to check:
• Working from the right-hand side we’re now looking to find a value that’s lower
than our pivot, and we immediately find 33. Because there’s nothing out of
order to the left of the pivot we can only swap with the pivot itself:
• And finally, because our sub-arrays can’t be subdivided any further we’re done!
Another way of looking at it: https://www.youtube.com/watch?v=XE4VP_8Y0BU
Sorted 27 35 33
Sorted 27 35 33
Sorted 27 33 35
LLooww sseeccttiioonn HHiigghh sseeccttiioonn
10 14 27 33 35
47
Searching
• We can sort numbers, words, colours – absolutely anything where we can say
that one thing is bigger than or smaller than another thing.
• But why is this such a big deal? Who cares?!
• WE CARE! Because the other thing that we often need to do is (you guessed
it):
Searching!
48
Searching (Cont’d)
• On the next slide there’ll be a list of animals.
• From the instant I swap to the next slide I want you to find the text Giraffe…
• …and then when you’ve found it raise your hand up high!
49
Searching (Cont’d)
Monkey Jaguar Elephant Cat
Tiger Rabbit Lima Vole
Penguin Yak Frog Salamander
Dog Mouse Zebra Baboon
Hamster Aardvark Ostrich Turtle
Kangaroo Shark Newt Iguana
Gorilla Beetle Seagull Spider
Hawk Cow Yak Budgie
Lion Seal Tortoise Ant
Squid Crow Giraffe Dolphin
Camel Goldfish Koala Horse
Herring Antelope Badger Seal
Fox Flea Crow Donkey
Alpaca Chimpanzee Snake Trout
50
Searching (Cont’d)
Monkey Jaguar Elephant Cat
Tiger Rabbit Lima Vole
Penguin Yak Frog Salamander
Dog Mouse Zebra Baboon
Hamster Aardvark Ostrich Turtle
Kangaroo Shark Newt Iguana
Gorilla Beetle Seagull Spider
Hawk Cow Yak Budgie
Lion Seal Tortoise Ant
Squid Crow Giraffe Dolphin
Camel Goldfish Koala Horse
Herring Antelope Badger Seal
Fox Flea Crow Donkey
Alpaca Chimpanzee Snake Trout
51
Searching (Cont’d)
• So what strategy did you use to find the giraffe?
• Did you start from one side and go up/down each column, or across each row?
• If so then you were performing a linear search where you started at some
point and went through each one in turn until you found the one you were
after.
• Did you kind-of unfocus your eyes and skim over it hoping to recognise the
word in your peripheral vision?
• Handy-hint: Computers don’t have peripheral vision!
52
Searching (Cont’d)
• Okay – let’s try that again with the same list of animals, but this time they’ll be
sorted into ascending order.
• When I swap to the next slide I want you to find the text Snake…
• …just like before, when you’ve found it raise your hand up high!
Before we start round 2: Were there any doubles of animals in the previous table?
53
Searching (Cont’d)
Aardvark Dog Iguana Seal
Alpaca Dolphin Jaguar Seal
Ant Donkey Kangaroo Shark
Antelope Elephant Koala Snake
Baboon Flea Lima Spider
Badger Fox Lion Squid
Beetle Frog Monkey Tiger
Budgie Giraffe Mouse Tortoise
Camel Goldfish Newt Trout
Cat Gorilla Ostrich Turtle
Chimpanzee Hamster Penguin Vole
Cow Hawk Rabbit Yak
Crow Herring Salamander Yak
Crow Horse Seagull Zebra
54
Searching (Cont’d)
Aardvark Dog Iguana Seal
Alpaca Dolphin Jaguar Seal
Ant Donkey Kangaroo Shark
Antelope Elephant Koala Snake
Baboon Flea Lima Spider
Badger Fox Lion Squid
Beetle Frog Monkey Tiger
Budgie Giraffe Mouse Tortoise
Camel Goldfish Newt Trout
Cat Gorilla Ostrich Turtle
Chimpanzee Hamster Penguin Vole
Cow Hawk Rabbit Yak
Crow Herring Salamander Yak
Crow Horse Seagull Zebra
Quicker this time? Easier this time?
55
A Brief Aside
• Do you think I sat down with a pen and paper and sorted all those animals into alphabetical
order manually?
• Of course I didn’t! I copied the words for each animal into a document, then sorted and printed
them, then copied and pasted them back! Here’s the code:
animal_list = [“Monkey”,
“Jaguar”,
“Elephant”,
— etc —
“Chimpanzee”,
“Snake”,
“Trout”]
animal_list.sort()
for animal in animal_list:
print(animal)
• From next week onwards we’ll be learning Python and doing all sorts of neat stuff with it =D
56
Searching Algorithms – Binary Search
• One we have a bunch of data, we often want to search for specific parts of it.
• Think of it this way – if you wanted to find the word Lumberjack in a dictionary,
you wouldn’t start at Aardvark and read each and every word on each and
every page until you got to ‘Lumberjack’…
• …you’d flip the dictionary to somewhere near the middle and see if you were
before the L section or after the L section.
• If you were before it, you’d flip ahead by a chunk of pages – and if you were
ahead you’d flip back by a chunk of pages.
• If you were ahead (on, say, N) and flipped back you might get to K – so now
you’re before L and you flip forward a little bit, but not as much as you first
did… and so on until you find the L section – and you can keep going until you
find Lumberjack!
• This is basically how a binary search works.
57
Meanwhile…
Lumberjack
ˈlʌmbədʒak/
noun: lumberjack; plural noun: lumberjacks; noun: lumberman; plural noun:
lumbermen
(especially in North America) a person who fells trees, cuts them into logs, or
transports them to a sawmill.
58
Searching Algorithms – Binary Search (Cont’d)
• Binary searches are fast – which is great!
• BUT they only work on data which has been sorted!
Note: This search returns 5 because that’s the index of the value it was searching for.
59
Wrap up
• We’ve looked at how we can model systems using abstraction to keep things
clean and simple.
• We shown how we can represent systems, or parts of systems using:
• Activity Diagrams / Flowcharts,
• Use cases,
• State diagrams, and
• Class diagrams.
• We’ve seen that algorithms are just a series of steps…
• …and that we can use various algorithms to sort data…
• …which makes it fast and easy for us to search for data!
• Next week we start learning Python and getting our code on! =D
[Button id=”1″]
[ad_2]
Source link
"96% of our customers have reported a 90% and above score. You might want to place an order with us."
