AP Computer Science Principles with Swift
Unit 3. Algorithms
Introduction
Day 170
An algorithm is a set of instructions for accomplishing a task.
An algorithm is characterised by three processed: sequencing, selection and iteration.
Sequencing
Sequencing is the process through which a computer processes lines of code, going from top to bottom and executing each instruction in order.
Selection
At each decision point the sequence can travel one way or another based on a test that’s either true or false.
Iteration
When we want to repeat a section of code a certain number of times or until a certain condition is met, we use iteration.
A condition can be analysed to give a value of true or false.
3.1 Privacy and Cybersecurity
In this unit we will learn how our Internet data trail impacts our privacy, how to think critically about the data we are collecting or using and, finally, how to assess how the data we are collecting or using could impact an individual’s privacy.
Information that can be used to identify or contact a single person is known as Personally Identifiable Information (PII).
Social Engineering
By social engineering we mean the different scams used by data thieves to convince us to share our passwords and personal data. Phishing is an example of such a behaviour.
Hacking
Hackers look for weak spots in code, system or design so that an infiltration may be possible. White hat hackers do this to alert companies about their vulnerabilities, while black hat hackers exploit those vulnerabilities for their own benefit (selling data, disrupting systems, expose secrets etc.)
Public Information
The key to understanding digital privacy is to be aware of how our online activities contribute to our data trail.
When we post on social medias, we are fully aware of our intention to share some kind of information but, what about those things we share voluntarily but unintentionally?!
Day 171
Unnoticed Footprints
Analytics, sometimes referred to as data analytics, is the discovery, interpretation and communication of meaningful patterns in data. As individuals use the Internet and the apps on their mobile devices, they leave behind trails of data that companies can use for analytics to understand patterns in user behaviour.
All this data is gathered and owned by the websites we visits and the apps we use and it’s covered by privacy policies, which contain the terms and conditions for how companies will handle our information.
The problem is that when we check the box agreeing to an organisation’s privacy policy or to the Terms of Use of a company or app, we may be unintentionally permit those entities to use and share our data in specific ways. How many times we have just checked the boxes without reading the little lines at the bottom?
Businesses typically act in their own best interest but sometimes, their interests may not align with ours and some privacy policies don’t forbid companies from selling our data!
We should check if an organisation is transparent about how they handle our data and how they explain what they do with it. Through the Safari browser we can restrict how websites are able to track our activities as we browse.
A Developer’s Perspective
As developers, we need to understand how the systems we build and the code we write can impact the privacy of our users.
We need to be aware of legal requirements. Also, if we use one of the many popular frameworks for gathering analytics data, we need to be aware of what that code is doing with our user’s data!
Summary
Sharing our personal information is a personal choice and it should always remain so and never ever delegated to others.
A few extra interesting concepts
Copyright is a principle that grants the right of ownership over the particular expression of an idea.
3.2 Making decisions
The FizzBuzz playground is the activity proposed by the Teacher’s Guide here.
This is how it should be written in modern Swift code. Even though the proposed one is acceptable, it is not really nice to see.
for n in 1...100 {
if n.isMultiple(of: 3) && n.isMultiple(of: 5) {
print("FizzBuzz!")
} else if n.isMultiple(of: 3) {
print("Fizz!")
} else if n.isMultiple(of: 5) {
print("Buzz!")
} else {
print(n)
}
}
The most restrictive cases in an if-else statement should be listed first.
The proposed activity in the Student Guide is to build a program to determine if a given year is a leap year. We will learn how to compare values and how to use the results of comparisons to choose which lines of code to run in our apps.
Open the “MakingDecisions.playground” file and complete it.
Here is the leap year exercise, it was a nice one!
func isLeapYear(_ year: Int) -> Bool {
if number(year, isDivisibleBy: 4) {
if number(year, isDivisibleBy: 100) {
if number(year, isDivisibleBy: 400) {
return true
} else {
return false
}
} else {
return true
}
} else {
return false
}
}
3.3 Instances, Methods and Properties
Day 172
First we should complete the “Instances, Methods and Properties” playground.
In programming, we can create and use different instances of a given type. Each instance has its own set of property values, and each instance can perform behaviour independent of other instances.
Each value in a program is an instance of its type.
When there is an instance that looks like a function call but has a type name instead of the function name, that is called an initialiser. It is interesting to notice that the default value for a Boolean is
falseand for Int is0.Initializers and functions are similar in some ways:
But they also have differences:
- A property provides a way to get or set a value that’s part of an instance. Each instance can have a different value for that property.
- A function is useful for providing behaviour that can be repeated as needed. A method works in the same way, providing behaviour specific to that instance.
- If the work we want to perform needs extra information, then it must be a method, since we can’t pass arguments to a property.
- Properties are for getting values from an instance and for setting values on an instance. Properties don’t do any additional work.
This playground was OK but many parts of it had Xcode screenshots completely outdated, some even of about 2 years! Incredible!
Day 173
Now we should complete the “Dates.playground”
This was a potentially wonderful playground, but so incredibly poorly managed. The exercises were of those kind that you are not shown not even an example before you have to do them, classical American style and no, that doesn’t make you smarter.
The next proposed activity is to browse the Documentation for the following types: Integer, CGRect and URL. Let’s delve into it.
Integers
Needless to say that an integer is a signed integer number! Here is what I found of interesting.
mutating func negate(): replaces this value with its additive inverse, for example:x = 21,x.negate(), nowx == -21.- This image is most interesting, I wish I could find a book that explains this with examples:
func multipliedFullWidth(by:): returns a tuple containing the high and low parts of the result of multiplying this value by the given value.- I didn’t really understand how this work, even after looking at some examples, I would really need someone to explain to me how this works.
- I didn’t really understand how this work, even after looking at some examples, I would really need someone to explain to me how this works.
- This is also most funny!
Instance Property
magnitudeThe magnitude of this value.
Declaration
Discussion
For any numeric value
x,x.magnitudeis the absolute value ofx. You can use themagnitudeproperty in operations that are simpler to implement in terms of unsigned values, such as printing the value of an integer, which is just printing a ‘-’ character in front of an absolute value.The global
abs(_:)function provides more familiar syntax when you need to find an absolute value. In addition, becauseabs(_:)always returns a value of the same type, even in a generic context, using the function instead of the magnitude property is encouraged.
Then why are you making a new property which will almost never be used???
Then this:
Instance Method
signum()Returns
-1if this value is negative and1if it’s positive; otherwise,0.Declaration
Return Value
The sign of this number, expressed as an integer of the same type.
CGRect
Basic definition:
Structure
CGRectA structure that contains the location and dimensions of a rectangle.
Declaration
Overview
In the default Core Graphics coordinate space, the origin is located in the lower-left corner of the rectangle and the rectangle extends towards the upper-right corner. If the context has a flipped-coordinate space—often the case on iOS—the origin is in the upper-left corner and the rectangle extends towards the lower-right corner.
Good start! Now let’s analyse the methods and properties of this structure.
Creating Rectangle Values
Creates a rectangle with the specified origin and size.
Creates a rectangle with coordinates and dimensions specified as floating-point values.
Creates a rectangle with coordinates and dimensions specified as integer values.
Creates a rectangle with coordinates and dimensions specified as CGFloat values.
These methods are all very similar to each other and, in my very small experience, I have always found myself using the CGFloat version.
Other interesting elements are:
static let infinite: CGRect: a rectangle that has infinite extent.static var zero: CGRect: the rectangle whose origin and size are both zero.init(): creates a rectangle with origin (0,0) and size (0,0).func applying(CGAffineTransform) -> CGRect: applies an affine transform to a rectangle. This is wonderful for the work one usually does with Core Graphics.func insetBy(dx: CGFloat, dy: CGFloat) -> CGRect: returns a rectangle that is smaller or larger than the source rectangle, with the same center point.func offsetBy(dx: CGFloat, dy: CGFloat) -> CGRect: returns a rectangle with an origin that is offset from that of the source rectangle.func union(CGRect) -> CGRect: returns the smallest rectangle that contains the two source rectangles.func intersection(CGRect) -> CGRect: returns the intersection of two rectangles. Don’t you miss Sets from elementary school? I certainly do!func divided(atDistance: CGFloat, from: CGRectEdge) -> (slice: CGRect, remainder: CGRect): creates two rectangles by dividing the original rectangle.enum CGRectEdge: coordinates that establish the edges of a rectangle. Where does this great thing comes from?!
URL
Documentation:
Structure
URL
A value that identifies the location of a resource, such as an item on a remote server or the path to a local file.
Declaration
struct URLOverview
You can construct URLs and access their parts. For URLs that represent local files, you can also manipulate properties of those files directly, such as changing the file’s last modification date. Finally, you can pass URLs to other APIs to retrieve the contents of those URLs. For example, you can use the URLSession classes to access the contents of remote resources.
URLs are the preferred way to refer to local files. Most objects that read data from or write data to a file have methods that accept a URL instead of a pathname as the file reference. For example, you can get the contents of a local file URL as
Stringby callingfunc init(contentsOf:encoding) throws, or as aDataby callingfunc init(contentsOf:options) throws.
There are so many interesting things here, many of which I encountered during these last days when I worked on my first app (which is still very embryonal).
In the final summary for this unit we find the mention of a new CS Concept, that is the Model. Model is another word for “data”, and people use the term in a few different ways. When people talk about an “app’s model”, they are talking generally about all the data types a particular app defines and deals with. A phrase like “pass the model to the view” means that this view type has a method that takes a data instance as an argument, and that data will probably affect the view’s behaviour. We can also use the word model as a verb if we talk about “modeling a solution”. In this case, it refers to defining data types, and the operations on them, to handle the information our app needs.
3.4 QuestionBot
Day 174
At the start of this chapter we are getting our hands dirty with the MVC patter, the Model–View–Controller design pattern.
The Model represents the specific data (all of the types) that the application works with, the Controller is the “brain” that communicates events and changes between model and view objects and, finally, the View is made up of the objects that the user sees and interacts with, such as buttons, images and scroll views. Why then it is not called MCV if you present it to me in this way?!
Anyway, MVC is an abstraction for app design, allowing the programmer to face each problem on its own and to clearly define how each one interacts with the others. This pattern can be seen inside a bigger set of layers of abstraction: Storage Hardware, Storage Software, Model, Controller, View and UI Hardware (once more the controller comes before the view, so?!).
Now, for this unit’s activity we will (supposedly) build the brain of a chat bot that responds differently to different questions. I guess this was already in the first book in the same format, so let’s see if we can skip this.
Just to be sure, open the “QuestionBot.xcodeproj” project.
@IBActions inside a ViewController extension? o__O? Really?!
Whatever, go on and open the “QuestionAnswerer.playground” file and complete it.
In the end it was exactly as I remembered so, nothing really new there. I understand that people new to programming may find this useful but I recall not liking it myself back then.
3.5 Arrays and Loops
Day 175
CS CONCEPT: PREVENTING PASSWORD FRAUD
Computer scientists often classify the running time of algorithms as reasonable or unreasonable.
An 8-character password composed of a random sequence of uppercase and lowercase letters would take 22 minutes to hack. If that 8-character password also contained numbers, it would take 2 hours to hack. If it also contained special characters such as % or &, it would take 9 hours.
A 10-character password containing numbers, mixed case letters, and special characters would take 6 years to hack, which is an unreasonable amount of time for anyone hoping to discover your password using a brute force algorithm!
The first activity of this chapter is to recreated the selection sort algorithm in Swift. Let’s give it a try:
func selectionSort(_ array: [Int]) -> [Int] {
func findSmallestNumber(in array: [Int]) -> Int {
var smallestNumber: Int = array[0]
for number in array {
if number < smallestNumber {
smallestNumber = number
}
}
return smallestNumber
}
var sortedNumbers = [Int]()
var workingArray = array
for _ in array {
let smallestNumber = findSmallestNumber(in: workingArray)
if let numberIndex = workingArray.firstIndex(of: smallestNumber) {
let removedNumber = workingArray.remove(at: numberIndex)
sortedNumbers.append(removedNumber)
}
}
return sortedNumbers
}
This is my solution and I’m sure there will be a better one but, by now, why not?!
I then went here and found that the explanation of what the selection sort algorithm should have been was WRONG in Apple’s book! Here is a better explanation and a better solution, damn it!
Goal: To sort an array from low to high (or high to low).
You are given an array of numbers and need to put them in the right order. The selection sort algorithm divides the array into two parts: the beginning of the array is sorted, while the rest of the array consists of the numbers that still remain to be sorted.
It works as follows:
It is called a “selection” sort because at every step you search through the rest of the array to select the next lowest number.
This is how it is done in Swift:
func selectionSort(_ array: [Int]) -> [Int] {
// 1. If the array is empty or only contains a single element, then there is no need to sort.
guard array.count > 1 else { return array }
// 2. Make a copy of the array. This is necessary because we cannot modify the contents of the array parameter directly in Swift. Like the Swift's sort() function, the selectionSort() function will return a sorted copy of the original array.
var a = array
// 3. There are two loops inside this function. The outer loop looks at each of the elements in the array in turn; this is what moves the | bar forward.
for x in 0 ..< a.count - 1 {
var lowest = x
// 4. This is the inner loop. It finds the lowest number in the rest of the array.
for y in x + 1 ..< a.count {
if a[y] < a[lowest] {
lowest = y
}
}
// 5. Swap the lowest number with the current array index. The if check is necessary because you can't swap() an element with itself in Swift.
if x != lowest {
a.swapAt(x, lowest)
}
}
return a
}
This is a lot more abstract but at least it is correct!
In the Student guide we are told that we will build a vote counter that tallies whether a measure passes or fails, then a tracker that comments on one’s progress toward a daily goal and, finally, a filter that seeks out messages that contain a certain word. We will learn about grouping items together into a single collection and about how to perform functions on a whole collections of items at once.
The power of programming lies in the fact that our work is reusable, given the correct arguments. Open the “ArraysAndLoops.playground” file to discover more.
This for sure is Xcode’s fault but when you click on the Show Results button in the sidebar for an array, in Xcode 10.3 you do not see anymore the index in front of the elements… amazing, right? No, it isn’t…
Here are some other things we have learned about arrays:
- The first index of an array is zero, not one.
- Accessing arrays using the index can be dangerous. If the index used is outside the bounds of the array, our program will crash.
- We can find out the number of items in an array using the
countproperty. - We can use for…in loops to safely access each item in the array in order, without needing to know how many items the array contains.
- Mutable arrays allow us to add, remove, and replace items.
So far, so good…
Here is the code for the voting exercise:
func printResults(forIssue issue: String, withVotes votes: [Bool]) {
var yes = 0
var nos = 0
for vote in votes {
if vote {
yes += 1
} else {
nos += 1
}
}
print("\(issue) \(yes) yes, \(nos) no")
}
printResults(forIssue: "Should we change the mascot?", withVotes: shouldMascotChangeVotes)
Here is the code for the goal tracker:
var roundsWorked: [Int] = [8, 12, 16, 7, 10, 8, 5, 11, 14, 15, 11, 9, 7, 6, 8, 9, 10, 7, 4, 3, 5, 9, 10, 12, 14, 16, 5]
func achieved(dailyGoalOf roundGoal: Int, with dailyRound: Int) -> String {
if roundGoal - dailyRound <= 0 {
return "Congratulations! Goal reached!"
} else if roundGoal - dailyRound == 1 {
return "Almost there!"
} else if (2...4).contains(roundGoal - dailyRound) {
return "Not close, but not bad at all!"
} else {
return "You did nothing today, slacker!"
}
}
var reports: [String] = []
for (index, round) in roundsWorked.enumerated() {
let report = achieved(dailyGoalOf: 10, with: round)
reports.append("Day \(index + 1): \(report)")
}
print(reports)
The last exercise was pretty idiotic … really … it was just a loop over an array of strings that should be checked for whether they contained another string or not …
CS CONCEPT: COLLECTIONS
Day 176
Programmers work with collections of data and lists (arrays in this case) are one type of collections, which should always contain a well-defined number of items, should impose an order on all items by assigning sequentially numbered indexes to them — and these should be therefore used to refer to them — and, finally, it should support item insertion and deletion via those same indexes.
ABSTRACT DATA TYPES
The basic operations we can use with collections, also known as abstract data types, are: count, insertion, deleting and indexing.
Another abstract data type is a Dictionary which contains a defined number of items, a key type by which items (values) are referred to uniquely and which also allows items to be inserted and deleted.
It’s possible to have two identical items in a dictionary —as long as they each have a unique key.
COLLECTION ABSTRACTIONS
Sorting is probably the most common thing to do with lists and a lot of algorithms have been created in the past. Swift provides the .sort function for arrays.
Here we are introduced to the selection sort activity we found before in the Teacher’s Guide. In this case the big O notation for the duration of the algorithm is n^2, that is n squared.
We are then shown a few high-level functions that relate to arrays:
index(of:): searches the list for a specific item and returns its index (an integer).map: allows us to apply an operation to each item in the array. This is a shortcut for thefor-inloop.filter: given a criteria (also known in programming as a predicate), this method will keep inside the collection only items that satisfy said criteria. It indeed returns aBool, which is whether or not the item satisfies the predicate.reduce: it produces a single value from items in a list.
Below all these we are reminded of the continuous presence of the selection, sequence and iteration processes.
Now … look at this picture taken from the Student’s Guide, from the last question:
…and this is the result from my Playground … can you imagine how this passed proofreading? If there ever was one…
To complete this chapter we should open the “Password.playground” file and follow its instructions.
This is my solution to the password checking exercise:
func checkPassword(_ password: String) -> Bool {
if tenMostCommonPasswords.contains(password) {
print("The password is too easy to hack, please change it!")
return false
}
if password.count < 16 {
print("The password is too short.")
return false
}
var digitsCount = 0
var symbolsCount = 0
for letter in password {
if digits.contains(letter) {
digitsCount += 1
}
if punctuation.contains(letter) {
symbolsCount += 1
}
}
if digitsCount == 0 {
print("The password should contain at least one digit.")
return false
}
if symbolsCount == 0 {
print("The password should contain at least one symbol.")
return false
}
return true
}
I wonder if there is a quicker way, but this works.
This is the proposed solution, which is definitely cleaner:
if tenMostCommonPasswords.contains(password) {
print("This is a common password. Please choose another one.")
} else if password.count < 16 {
print("Your password must contain at least 16 characters.")
} else {
var numberOfDigits = 0
var numberOfPunctuationCharacters = 0
var numberOfRegularLetters = 0
for character in password {
if digits.contains(character) {
numberOfDigits += 1
} else if punctuation.contains(character) {
numberOfPunctuationCharacters += 1
} else {
numberOfRegularLetters += 1
}
}
if numberOfDigits == 0 {
print("Your password must contain at least one digit.")
} else if numberOfPunctuationCharacters == 0 {
print("Your password must contain at least one of these punctuation marks: \(punctuation).")
} else if numberOfRegularLetters == 0 {
print("Your password must contain at least one regular letter.")
} else {
print("Your password is secure.")
}
}
The next exercise if even more interesting because we need to refine our password checking further. We are now encountering an extension to the Character type to see if it is uppercased or not.
extension Character {
var isUpperCase: Bool {
get {
return Character(String(self).uppercased()) == self
}
}
}
This is using the .uppercased() method of the String data type before converting it back to Character. This is how I implemented the next part, learning from my mistakes:
func checkPassword(_ password: String, forUser name: String) -> Bool {
// Check for common passwords
if tenMostCommonPasswords.contains(password) {
print("The password is too easy to hack, please change it!")
return false
} else if password.count < 16 {
// Check for password length
print("The password is too short.")
return false
} else if password.contains(name) {
print("The password cannot be equal to the username!")
return false
} else {
// Check for digits and symbols presence
var digitsCount = 0
var symbolsCount = 0
var lowercaseCharacters = 0
var uppercaseCharacters = 0
for character in password {
if digits.contains(character) {
digitsCount += 1
} else if punctuation.contains(character) {
symbolsCount += 1
} else {
if character.isUpperCase {
uppercaseCharacters += 1
} else {
lowercaseCharacters += 1
}
}
}
if digitsCount == 0 {
print("The password should contain at least one digit.")
return false
} else if symbolsCount == 0 {
print("The password should contain at least one symbol.")
return false
} else {
if lowercaseCharacters == 0 || uppercaseCharacters == 0 {
print("The password needs at least one uppercased AND one lowercased character")
return false
}
}
}
return true
}
The last thing to do in this playground was to test an algorithm for password brute-force breaking.
As long as the password was only made up of digits and few numbers long, it took a few seconds to hack. I then tried to hack the password 4b@U … I have a 2016 MacBook Pro with a quad-core 2.7 GHz i7, 16GB of RAM and it is now starting to slow down after just two minutes of checking… the fans are howling like the winter wind in Norwegian fjords!
After about 2 millions attempts it managed to find it in 5-6 minutes.
This seems a lot of time but assuming that hackers have all the time in the world at their disposal if a complex non-logical password of 4 characters took “just” 6 minutes, then we should think better about adding a lot more characters. They say the suggested amount is 8, but I will always go for 15-16, very random characters!
3.6 Defining Structures
Day 177
It is often useful to group related information and functionality into a custom type. This is often done via a structure with accompanying properties and methods.
From the key vocabulary we learn more about the definition of methods, properties and structures. A method is a function defined inside a type and it can use the data stored in the type’s properties to perform work. A property is a piece of data held by a structure, a class or an enumeration. For example, each Array instance has a count property that’s different depending on the characteristics of the particular array. Finally, defining a struct is one of the ways to create our custom types in code. A struct can hold values as properties, define behaviour as methods and define initialisers to set up its initial state. Every instance of a struct has its own separate identity.
In this lesson we will build a data type that models information that’s important for us. We should now open the “Structures.playground” file and complete it. I have today downloaded the Xcode 11 beta 7 while waiting for my iPad Pro to restore its functionalities (I will never ever try again beta versions of operative systems on accounts and machines I use for work … NEVER!)
… anyway … the playground started to have a spinning beachball in the middle of a page…
After resuming the execution I could gladly notice how these later playgrounds put an emphasis on making the learner witness mistakes in the code and learn from them.
I now have to stop because it is impossible to continue using playgrounds on this beta … I will go back to Xcode 10 for the continuation of this article.
I apologise if this is taking so long but … I am having very little time to study and to write and, also, most important, I am spending more and more time on building my first app and … it is complicated to go beyond the tutorial version!
I will show it to you when I am close to completion…
Day 178
I should have been away until tomorrow, September 2nd, but had to come back because of a sudden departure of a family member for the realm beyond so, yeah, here I am, ready to continue.
I will now open that playground in Xcode 10 hoping I will be able to complete it.
Another incredible thing is that every time one launches Xcode 10 after launching Xcode 11 (and viceversa), you get asked to “Install additional components” … is this really the best Apple can do? I don’t think so…
Whatever, I completed the playground and it was not bad at all. I will now go on with the learning part.
The next thing is to extend on what was learned. For example, starting from a simple Ingredient struct with just a name and a foodType string properties, one could go on to create a MenuItem struct which is much more elaborated and that contains an array of ingredients objects as one of the properties. Then one could create another struct called Menu which would be an array of MenuItem. Finally, we could add a method to the Menu type so that it would access any level of the other types, which is incredibly interesting and with a lot of potential!
Day 179
CS CONCEPT: UNDECIDABILITY
Analysing programs is one of the important skills we should develop as programmers as it will help us decide how to solve the problems we will encounter.
People have already created systems for formally verifyingcode, that is to analyse it to see if it operates correctly. One could hope for a general-purpose solution to be available so that any code could be examined under any circumstances but, alas, such a solution is not available.
In Computer Science, a general-purpose software verification algorithm is an example of an undecidable problem.
ALGORITHMS: REVIEW
We finally came to the end of this very long unit. It was luckily better than the previous two ones even if many things could have been clearer.
I sincerely hope that the next unit will continue on this trend.
I also want to apologise for taking so long to finish and publish this article but since I completed Hacking with Swift I decided to dedicate about one hour to learning and half an hour to applying and building my app, which sometimes made me fall into the trap of full time building (yes, it’s fun!).
I hope to be able to share something about that soon enough but, with all the things I need to study before the SwiftUI workshop in October and all the crazy amount of work I have in these weeks I highly doubt I will be able to do that.
Thank you so much for keeping up with me, I hope it was not (too) boring!
If you like what I’m doing here please consider liking this article and sharing it with some of your peers. If you are feeling like being really awesome, please consider making a small donation to support my studies and my writing (please appreciate that I am not using advertisement on my articles).
If you are interested in my music engraving and my publications don’t forget visit my Facebook page and the pages where I publish my scores (Gumroad, SheetMusicPlus, ScoreExchange and on Apple Books).
You can also support me by buying Paul Hudson’s books from this Affiliate Link.
Anyways, thank you so much for reading!
Till the next one!
Music Preparation Services 