An algorithm solves a problem of size n recursively by breaking it down into two subproblems of size n/2

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

An algorithm solves a problem of size n recursively by breaking it down into two subproblems of size n/2 with the same structure, until the size of a subproblem is one or zero. It takes O(1) time to solve a (sub)problem of size one or zero. It takes O(n) time to convert a problem of size n into two subproblems and it takes O(n) time to combine the results of these subproblems into the result of the problem of size n. What is the time complexity of this algorithm? Justify your answer.

Write your answer in q1.txt.

Submission

Submit via the give command

Consider the following algorithm, which converts a positive integer n to its binary representation.

 

What is the time complexity of the algorithm? Assume that creating a stack and pushing an element onto a stack are both

O(1) operations (i.e., constant). Justify your answer.

Write your answer in q2.txt.

Submission

Submit via the give command

Consider the the following 2-3-4 tree :

(a) (2 marks) What value(s) would be stored in the root node of the above 2-3-4 tree after the insertion of the value 8? What value(s) would be stored in the node that now contains 8? Note: if you need to promote a value, you must promote the smaller of the two middle values. Justify your answer.

(b) (3 marks) What value(s) would be stored in the root node of the above 2-3-4 tree after the insertion of the value 50? What value(s) would be stored in the node that now contains 50? Note: if you need to promote a value, you must promote the smaller of the two middle values. Justify your answer.

Write your answers in q3.txt.

Submission

Submit via the give command

 

Consider the following trie. Finishing nodes are shown in red.

(a) (1 mark) How many words are stored in this trie?

(b) (2 marks) Which nodes would be visited in searching for "deeds"?

(c) (2 marks) What new nodes would be created if the word "bogus" was added to the trie? Justify your answer.

(d) (2 marks) What new nodes would be created if the word "do" was added to the trie? Justify your answer.

Write your answers in q4.txt.

Submission

Submit via the give command

 

 

 

 

(a) (2 marks) What is the difference between an Euler path and a Hamilton path?

(b) (2 marks) Does the graph below have any Euler paths? If so, give one of them. If not, explain why.

(c) (2 marks) Does the graph below have any Hamilton paths? If so, give one of them. If not, explain why.

 

Write your answers in q5.txt.

Submission

Submit via the give command

 

This question is about the array-based implementation of a max heap.

(a) (3 marks) Suppose the original state of the heap is:

Show the state of the heap after performing each of the following operations:

 

Note that the "join(pq, P)" operation should be performed on the state of the heap obtained after performing the "join(pq, S)" operation.

(b) (3 marks) Suppose the original state of the heap is:

Show the state of the heap after performing each of the following operations. What are the values of it1 and it2?

 

Note that the "it2 = leave(pq)" operation should be performed on the state of the heap obtained after performing the "it1 = leave(pq)" operation.

Write your answers in q6.txt.

Submission

Submit via the give command

 

 

Consider a hash table of integer keys with 11 slots and a primary hash function of h(k) = k % 11. Consider the following sequence of values:

 

(a) (4 marks) Suppose the hash table described above uses linear probing for collision resolution. Show the final contents of the hash table after the values above have been inserted into an initially empty table in the order given. Give the cost, in terms of the number of keys examined, when searching for the key value 6 in the resulting table.

(b) (4 marks) Suppose the hash table described above uses double hashing for collision resolution, with a secondary hash function of h2 (k) = 1 + (k % 5). Show the final contents of the hash table after the values above have been inserted into an initially empty table in the order given. Give the cost, in terms of the number of keys examined, when searching for the key value 6 in the resulting table.

Write your answers in q7.txt.

Submission

Submit via the give command

 

bubble sort insertion sort merge sort naive quicksort

Describe in detail the steps you would perform to tell the sort programs apart. Note: It is not known whether the bubble sort scans from left to right or from right to left.

Write your answer in q8.txt.

Submission

Submit via the give command

 

 

Implement the function totalTextSize in q9/totalTextSize.c, which takes a pretend file system (represented by linked lists) and returns the total size of all the text files in the pretend file system. The size of a text file is simply the length of the text in the file.

The pretend file system contains two types of files: directories (also known as folders) and text files (yes - directories are a type of file).

The data structures used to implement the pretend file system are defined in Fs.h. Each file is represented by an instance of struct File, where the type field is used to distinguish between file types (directory or text file).

Each directory has a linked list of files that are contained within that directory. Each text file contains some text, represented by a string. The file system as a whole is represented by an instance of struct Fs, which contains a pointer to the root/top-level directory.

Constraints

All general constraints and assumptions at the top of this exam paper apply

You must not open any files - you are given a pretend file system represented by linked lists, not a real file system. The given pretend file system must not be modified

You must not use arrays or any variant of malloc (malloc, calloc or realloc). If you do, you will receive zero for this question.

Files

 

Makefile A Makefile to compile your code

Fs.c Contains the implementation of some in-memory file system functions

Fs.h Contains the definition of the in-memory file system data structure and function prototypes

testFs.c A testing program. This program takes a test number as a command-line argument, sets up the file system corresponding to that test number, calls totalTextSize, and outputs the result to stdout.

totalTextSize.c Contains totalTextSize, the function you must implement. This is the only file you should modify

(except when adding your own tests in testFs.c).

tests/ A directory containing the expected outputs for some basic tests

 

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of