Final Exam

Question 1

Given a pair of sequences of the same length, write a function that counts how many of the letters in the sequences match. For example, if we have the following sequences:

ACCTG
ATCGG

Answer 1

def countMatches(str1, str2):
count = 0
for i in range(str1):
if str1[i] == str2[i]:
count += 1
return count

Question 2

Symmetric Encryption

Answer 2

Also known as private key encryption – uses a single key to encrypt and decrypt a message. Used when one party is encrypting his/her own information or when sender and receiver of a message are able to secretly share the key.

Question 3

Asymmetric Encryption

Answer 3

Also known as public key encryption – uses two keys. The public key encrypts the message and the private key decrypts the message. Used when sender and receiver are not able to secretly share a key.

Question 4

Using the Shortest Job First (SJF) algorithm, and assuming that the processes are represented as [ProcessID, Execution Time], show the scheduling order of the following processes:

[P1, 6]
[P2, 7]
[P3, 3]
[P4, 3]
[P5, 4]

Answer 4

Time Executing Process
0 P3
1 P3
2 P3
3 P4
4 P4
5 P4
6 P5
7 P5
8 P5
9 P5
10 P1
11 P1
12 P1
13 P1
14 P1
15 P1
16 P2
17 P2
18 P2
19 P2
20 P2
21 P2
22 P2

Question 5

What is deadlock? What are 3 ways to prevent deadlock?

Answer 5

-Deadlock: Deadlock occurs when two or more processes are each holding a resource that the another process needs and none are willing to release the resources they have.
-You can prevent deadlock by:
-Having processes time out if they wait too long and then request resources again after waiting a random amount of time
-Requiring that processes request resources in a specified order
-Requiring that process request all resources they need and do not lock any resources unless they can get all.

Question 6

What are 3 things that make the digital signature algorithm useful in an investigation?

Answer 6

1. Produces a signature that is significantly smaller than the original data
2. Always produces the same result on the same input
3. Always produces different result on different input (avoids collisions)

Question 7

Python function that searches a given list of employee IDs for a specific ID, and returns the name of the employee with that ID. If the list of IDs you were searching through was sorted from lowest to highest, what algorithm might be used?

Answer 7

If the list of IDs were sorted, we could use a binary search.

This solution would be better because binary search is a more efficient algorithm – it does not need to consider every ID in the list.

Question 8

What is a potential worst case input for an algorithm that searches through a list?

Answer 8

if the item is not found in the list

Question 9

Describe two kinds of algorithms that are developed by computer scientists in the field of bioinformatics.

Answer 9

-Dot plot for visualization of similarities between sequences
-Alignment algorithm for determining the optimal alignment between a pair of sequences

Question 10

Given the following two sequences of nucleotides, show all of the possible ways that they can be aligned if 2 gaps are inserted in the second sequence? Assuming a +1 for a match, 0 for a gap and –1 for a mismatch, which alignment is best?

CGTTCA
ACTG

Answer 10

–ACTG Score = -4
-A-CTG Score = -4
-AC-TG Score = -4
-ACT-G Score = -2
-ACTG- Score = -2 Optimal
A–CTG Score = -4
A-C-TG Score = -4
A-CT-G Score = -2 Optimal
A-CTG- Score = -2 Optimal
AC–TG Score = -4
AC-T-G Score = -2 Optimal
AC-TG- Score = -2 Optimal
ACT–G Score = -2 Optimal
ACT-G- Score = -2 Optimal
ACTG– Score = -2 Optimal