itc revision

i fucking hate this mod

wow

question 1

consider the UML diagram below. which of the following statements is true? (DEVICE points to SIMULATE, AGENT points to LOGIN and SIMULATE).

uml

  • an AGENT cannot CREATE SCHEMA.
  • an AGENT can SYNTHESISE DATA, but they must FILE RECORD too.
  • a DEVICE can LOG IN, and they can decide whether or not they want to EXECUTE ACTION.
  • a DEVICE cannot LOG IN, but they can SIMULATE without CREATING SCHEMA.

explanation: for include / extends relations, the arrow is always pointing towards the base case. in the case of SYNTHESISE DATA, its base is LOG IN, so you need to LOG IN before you can SYNTHESISE DATA, but to LOG IN you must FILE RECORD.

question 2

two algorithms are implemented. one of them is constant time, and the other is linear time. both are executed on the same input, on the same computer. which of the following is true, assuming both will eventually terminate?

  • the constant time algorithm will always finish before the linear time algorithm.
  • the linear time algorithm will always finish before the constant time algorithm.
  • it is impossible to tell which one will finish first based on the given information
  • both will take the same amount of time

explanation there are indeed algorithms which are “theoretically” constant time but the constant term is so large that other non-constant time algorithms will outperform it, but in the majority of cases constant time will outperform linear time. you can’t say for sure, though. more info

question 3

what time complexity is the following algorithm?

def func(n):
  for i in range(4):
    for j in range(n):
        for k in range(n):
          print([i*j*k*l for l in range(n)])
  • O(4n^2)
  • O(4n^3)
  • O(n^2)
  • O(n^3)

explanation: it’s three nested loops reliant on n, the constant scaling factor of 4 doesn’t matter.

question 4

consider the following query. assuming the query executes successfully, which of these statements can be assumed to be true with 100% certainty?

SELECT student_id FROM students WHERE module_id in 
(SELECT module_id FROM modules WHERE professor_id = 
(SELECT professor_id FROM professors WHERE years_experience > 10);
  • if you delete a given professor_id, all modules they teach will be removed from the modules table.
  • more than 3 tables exist in the schema.
  • module_id is the primary key of the modules table.
  • only one professor has more than ten years of experience.

explanation: very tricky question. in SQL the syntax of ‘=’ indicates that the subquery only returns one row, and if it did, it would error out, but the question states that it executes successfully.

question 5

a music fan wants to create an entity-relationship diagram of their favorite bands. assume a band can create many albums, an album can contain many songs, and a song can ‘feature’ exactly one other band. which of the following is an incorrect assumption, based off of the information provided?

  • we can create a Feature table to model the relation, using the primary key of Band and the primary key of Song as foreign keys
  • we can add a Feature column to the Songs table to model the relation, specifying that the Feature column must not be NULL
  • the cardinality of the Feature relation is many to one
  • a Band can Feature in multiple songs off of the same Album

explanation: note that we say a song can feature another Band, not that it must. therefore, our Feature column can be NULL.

question 6

which of the following algorithms would have exponential time complexity?

  • iterating through all memory addresses on an N-bit processor
  • iterating through all I rows and J columns of a database with K tables
  • iterating through each number less than N to test for the primality of N
  • locating an element in a hashmap with 2^N elements

explanation: remember your comarch! an N-bit processor will have 2^N memory addresses.

question 7

alice wants to send bob a message, and both alice and bob have valid RSA keypairs. alice and bob also share a secret K which no other people know. eve is a malicious eavesdropper who can read their transmissions. which of the following is true?

  • if alice encrypts her message with her private key and transmits it, eve cannot read it but bob can.
  • if eve receives a message digitally signed with the secret K, she can be sure it is from alice.
  • if alice encrypts her message with her public key and transmits it, only bob can read it.
  • if bob is able to decrypt a received message with alice's public key, he can be sure it is from alice.

explanation: option 1 is wrong because eve can decrypt with alice’s public key. option 2 is wrong because the message could be from bob too (both share the secret K). option 3 is wrong because nobody except alice would be able to decrypt it. option 4 is correct because if bob can decrypt the message with alice’s public key, that means the message was encrypted with alice’s private key.

question 8

program A takes 10 seconds to compute 100 inputs, 50 seconds to compute 500 inputs, and 200 seconds to compute 2000 inputs. program B takes 1 second to compute 100 inputs, 4 seconds to compute 200 inputs. and 16 seconds to compute 400 inputs. for what number of inputs will their running times coincide? (ignore the trivial solution of 0 inputs)

  • it will never coincide
  • 1000
  • 10000
  • 500

explanation: program A is linear while program B is quadratic. running time of each program can be expressed as some f_i(n) where n is the number of inputs. f_a(n) = n/10, f_b(n) = n^2/10000. you can solve this as a quadratic or whatever but option 2 is correct here

question 9

which of these is true (assume that we want our resulting scheme to be secure and functional)?

  • you can pick any size matrix to use as a hill cipher key, as long as it is square
  • you cannot pick any plaintext to encrypt for RSA
  • you can pick any number N to use in RSA, as long as it is above what can be feasibly factored (typically >512 bit)
  • you can pick any length of key for AES or DES, as long as it is at least 64 bit

explanation: option 1 is wrong - the key must be an invertible matrix. option 3 is wrong - N must consist of two large primes, (consider the case where N is 2x3x5x7… very trivially factorable). option 4 is wrong - it has to be 64 bit. option 2 is correct, because if the plaintext is larger than the modulus, you lose data.

question 10

what is the time complexity of the following program? take m as the length of the string, and n as the length of the substring.

def find_substr(substring, string, index):
    if len(substring) + index > len(string): return False
    else:
        for i in range(len(substring)):
            if substring[i] != string[index+i]:
                return find_substr(substring, string, index+1)
    return True
  • O(mn^2)
  • O(n*m)
  • O(nm^2)
  • O(n+m)

explanation: it will iterate through the inner loop of length m at worst n times, so the answer is O(n*m).