Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?

Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly 4 nodes O(n^a Log^bn ). Then the value of a + 10b is _________

Given the following statements:

S1: A foreign key declaration can always be replaced by an equivalent check assertion in SQL.

S2: Given the table R(a,b,c) where a and b together form the primary key, the following is a valid table definition.

CREATE TABLE S (
 a INTEGER,
 d INTEGER,
 e INTEGER,
 PRIMARY KEY (d),
 FOREIGN KEY (a) references R)

Which one of the following statements is CORRECT?

Given the following schema:

employees(emp-id, first-name, last-name, hire-date, dept-id, salary)

departments(dept-id, dept-name, manager-id, location-id)

You want to display the last names and hire dates of all latest hires in their respective departments in the location ID 1700. You issue the following query:

SQL> SELECT last-name, hire-date 
FROM employees WHERE (dept-id, hire-date) IN 
(SELECT dept-id, MAX(hire-date) 
FROM employees JOIN departments USING(dept-id) 
WHERE location-id = 1700
GROUP BY dept-id);

What is the outcome?