(1) Like divide and conquer, dynamic programming (DP) solves problems by combining solutions to subproblems: true or false?___; unlike divide and conquer, DP subproblems are independent: true or false?_. (2) For a graph G=, the total running time of BFS is ?(); the total running time of DFS is ?(). If G is an undirected graph, ∑? ∈ ???????(?) = ; if G is a directed graph, ∑? ∈ ???????(?) = ______. (3) Heap sort algorithm is stable or not? _ , in-place or not? . Its worst case time complexity is ?(). The height of a heap A[1..n] is . (4) For a sorting algorithm for an array of n elements, in the worst case the number of inversions is _ , the average number of inversions is _. Shell sort algorithm is stable or not? , in-place or not? _ . (5) The worst case time complexity of BuildMaxHeap is ?(_). The worst case time complexity of MaxHeapify is ?(__). The worst case time complexity of Heap- Extract-Max is ?(_). The worst case time complexity of Heap-Insert is ?(). (6) Dynamic programming has four steps: (1) ; (2) ____ ; (3) Compute optimal solution values either top-down with caching or bottom-up in a table; (4) Construct an optimal solution from computed values.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

(1) Like divide and conquer, dynamic programming (DP) solves problems by combining
solutions to subproblems: true or false?_______; unlike divide and conquer, DP
subproblems are independent: true or false?_______.

(2) For a graph G=<V, E>, the total running time of BFS is ?(____); the total running time
of DFS is ?(____). If G is an undirected graph, ∑? ∈ ???????(?) = ; if G is a
directed graph, ∑? ∈ ???????(?) = __________.

(3) Heap sort algorithm is stable or not? _____ , in-place or not? ______. Its worst case time
complexity is ?(____). The height of a heap A[1..n] is ____.

(4) For a sorting algorithm for an array of n elements, in the worst case the number of
inversions is _______ , the average number of inversions is _______.
Shell sort algorithm is stable or not? ______ , in-place or not? _______ .

(5) The worst case time complexity of BuildMaxHeap is ?(_______). The worst case time
complexity of MaxHeapify is ?(______). The worst case time complexity of Heap-
Extract-Max is ?(___). The worst case time complexity of Heap-Insert is ?(____).

(6) Dynamic programming has four steps:
(1) ____________________ ;
(2) ____________________ ;

(3) Compute optimal solution values
either top-down with caching or bottom-up in a table;

(4) Construct an optimal solution
from computed values.

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 4 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions