CS3217 Problem Set 1

Name: Ang Wei Neng

Matric No: A0164178X

Tutor: Herbert Ilhan Tanujaya

Instructions for Students

1. Clone this repository to begin working.
2. Do not modify the AppDelegate.swift, LaunchScreen.xib, Main.storyboard, Images.xcassets files (you do not have to).
3. Write your answers to non-coding questions in this file (README.md).
4. Question can be found at https://cs3217.gitbooks.io/problem-sets/content/ps/PS1/PS1.html

Tips

1. CS3217's Gitbook is at https://www.gitbook.com/book/cs3217/problem-sets/details. Do visit the Gitbook often, as it contains all things relevant to CS3217. You can also ask questions related to CS3217 there.
2. Take a look at .gitignore. It contains rules that ignores the changes in certain files when committing an Xcode project to revision control. (This is taken from https://github.com/github/gitignore/blob/master/Swift.gitignore).
3. A Swiftlint configuration file is provided for you. It is recommended for you to use Swiftlint and follow this configuration. Keep in mind that, ultimately, this tool is only a guideline; some exceptions may be made as long as code quality is not compromised.
4. Do not burn out. Have fun!

Problem 1: Swift Collections

Dictionary keys must conform to the Hashable protocol as we want to hash the dictionary keys to allow retrival of its items in O(1) time.

Hashing the keys allow us to retrieve the "basket" that the key-value item is in. Compared to looping through all items in the collection, we can now leverage on the fact that we can find the "basket" that the key-value item is in in O(1) time. Assuming SUHA, retrival of an item should take O(1) time.

Problem 3: Graph Traversal

Problem 3.3

Since we can recover from the error, we should not throw an exception that will terminate the program. If we cannot recover from the error, we should use assert/guard to check for the issue.