代写Data Structures, Algorithms & Databases Main Spring Examinations 2023代做SQL语言

Data Structures, Algorithms & Databases

Main Spring Examinations 2023

Answer ALL questions.  Each question will be marked out of 20.  The paper will be marked out of 80, which will be rescaled to a mark out of 100.

Question 1 Analysis of Algorithms and Tree Data Structures

Part 1 Consider  a function  named arrayToBST that takes an array of integers a and inserts the elements of a in an AVL tree T.  Therefore, function insert has re-balancing.

Tree   arrayToBST( int    []   a)   {

Tree  T  =  ✄ ;

for   ( int   i  =   0;   i   < a . length; i++) {

T  =  insert(T,  a[i]);

}

return   T;

}

Is it possible to construct an input array a of any arbitrary length n that results in the outcomes described below?  When it is possible to construct an input, give an example with length n = 8.

(a) Algorithm arrayToBST runs in time O(n).                                                [4 marks]

(b) Algorithm arrayToBST runs in time O(n log n).                                         [4 marks]

(c) Algorithm arrayToBST returns a perfectly balanced tree.                          [4 marks]

Brie  y explain your construction.  Note that your construction should apply to arrays with any arbitrary length n; you cannot choose the length.  Your  input array may or may not have repetitions.

Part 2 Consider a tree data structure where every node has at most three children:  left child l , middle child m and right child r. We call it a ternary tree.

(d)  Give the maximum possible number of nodes of a ternary tree of height 4?     [4 marks]

(e)  Give the minimum possible number of nodes of a ternary tree of height 4?     [4 marks]

Brie  y explain how you compute these numbers.  In particular, be clear about the de  nition of height you are using.

Question 2 Entity-Relationship modelling

A company operates an online store where customers can place orders for various products, and has the following description of their requirements for a database:  Customers  need to provide details such as their name, email address, and shipping address to create an online account.   Each customer may have multiple orders, and each order is associated with only one customer.  An order contains one or more order items, where each order item represents a single  product ordered  by the customer.   An order  item  includes the quantity of the product ordered and its price at the time of purchase.  Each  product has a unique product  ID, a name, and a description.  Additionally, the company may track reviews for each product.  A review includes the name of the reviewer, a rating, and a comment.  Each  review is associated with only one product, and each product may have multiple reviews.  Finally, each order is associated with a payment.  Each payment has a payment ID, an amount, a date and a payment method.

(a)  Develop an Entity-Relationship model for the application.  Explain the key design decisions made in your choice of entities, relationships and any other (ownership or hierarchical) aspects.                [8 marks]

Annotate it with multiplicities and hierarchy annotations, as required.   [4 marks]

(b)  Carry  out  logical  design  for  the  model,  representing  the  design  with  relational schemas for tables.              [4 marks]

(c) Write SQL CREATE  TABLE statements for 2{3 tables.   Include  among them a ta- ble that represents a relationship or incorporates a relationship, a weak entity or a subclass entity. The other tables can be for the adjoining entities.            [4 marks]

Question 3 Graphs and Max-Heap Trees

Part 1 Consider the following weighted directed graph (with 7 vertices and 16 edges):

(a)  Calculate the shortest path from A to G using the Dijkstra's algorithm.  ("Shortest" means the path with the lowest total weight.)      [10 marks]

You are expected to show your work using a table of the following form and also list the shortest path (e.g. A- >B- >C) and and specify the resulting weight:

Total Weight:

Shortest Path:

Part 2 Consider the complete binary tree below.  Answer the following questions

(b)  In the  process of building a  Max-Heap Tree, the    rst swap is  between and (write down the two numbers).           [2 marks]

(c)  And the second swap is between and (write down the two numbers).     [2 marks]

(d)  Draw the   nished Max-Heap Tree (intermediate work is not required).      [6 marks]

Question 4 Relational algebra and normalisation

Consider the following schema for product sales for an online shop.

product(pid, cat, price)

customer(cid, cname)

sale(pid, cid, date, qty)

(\cat"  is short for category and  \qty"  for  quantity).   For  estimating e   ciency,  assume around 100 products, 10,000 customers and several million sale records.

(a)  State in English what the following relational algebra expression computes:

[2 marks]

(b)  The expression given above is considered ine   cient.  State all the ways  in which  it is ine   cient.     [4 marks]

(c)  Give a more e   cient version of the expression.  Make it as e    cient as you can, and explain how it achieves e   ciency.                                         [6 marks]

(d)  Consider  a  schema  T(A, B, C, D)  with  the  functional  dependencies  AB  -→  C , AB -→ D and BC -→ D.

If we decompose the schema into (A, B, D) & (B, C, D), is it a lossless decompo- sition?  If yes, explain why.  If not, try to produce a counterexample.

Are the two subschemas in Boyce-Codd normal form?  Explain.             [8 marks]