Other Programming & Computer Science Answers

1) Describe, in pseudo-code, an O(n + m)-time algorithm for computing all the connected components of an undirected graph G with n vertices and m edges.

2) Say that an n-vertex directed acyclic graph G is compact if there is some way of numbering the vertices of G with the integers from 0 to n - 1 such that G contains the edge (i; j) if and only if i < j, for all i; j in [0; n - 1]. Give an O(n^2)-time algorithm for detecting if G is compact.

3) Computer networks should avoid single points of failure, that is, network nodes that can disconnect the network if they fail. We say a connected graph G is biconnected if it contains no vertex whose removal would divide G into two
or more connected components. Give an O(n + m)-time algorithm for adding at most n edges to a connected graph G, with n >= 3 vertices and m >= n - 1 edges to guarantee that G is biconnected.

1. Explain briefly how to insert a given key in a binary search tree

2. Find following questions are True or False? If false write the correct answer:
a. The insertion operation in a binary search tree has a running time of O(1) in the worst case.
b. In a stack implemented using an array, the push operation is O(log n) in the worst case.
(Assume the array is not full)
c. n^2 logm + n^3 is O(n^3)
d. n^2 + n^3 = O(n^3)
e. If we sort n numbers using quicksort, then the worst case running time is O(n).
f. A (2,4) tree is also a binary search tree.
g. The height of a red black tree with n entries, is always less than the height of every binary
search tree on the same set of entries.
h. An undirected graph with n vertices has at least n edges.
i. An undirected graph with n vertices and n + 2 edges must always contain a cycle.
j. The worst case running time of sorting n elements using heapsort is O(n log n)

1. An n-­‐vertex directed acyclic graph G is compact if there is some way of numbering the vertices
of G with the integers from 0 to n ­‐ 1 such that G contains the edge (i ; j) if and only if i < j, for all i;
j in [0; n ‐1]. Give an O(n^2) -­ time algorithm for detecting if G is compact.
2. Describe a recursive method that counts the number of leaves in a given binary tree.
3. Describe a non‐recursive method that counts the number of leaves in a given binary tree.

1. A desk can be modelled as a simple data structure with the following ADT Desk:
• add(x) puts item x on top of the desk
• process() processes the top item on the desk and removes it (either sending it to someone else or
just throwing it away!)
• find(x) finds and retrieves the item x if it’s somewhere on the desk
• scan() looks at the top item on the desk, but doesn’t remove it
i). What data structure can you think of that is most like the ADT Desk? Give reasons.
ii). Write out in pseudocode in the space below how you would implement the find(x)
method in the ADT Desk above, using only stacks. Assume the standard methods for a stack have
already been defined.
iii). What is the running time of your method above? explain.

1. The following code fragment operates on a stack S initially empty. What is the output of
this code fragment?
S.push(2);
S.push(4);
S.push(6);
S.push(8);
while (! S.isEmpty() )
System.out.println(S.pop());

2. The following code fragment operates on a queue Q initially empty. What is the output of
this code fragment?
Q.enqueue(2);
Q.enqueue(4);
Q.enqueue(6);
Q.enqueue(8);
while (! Q.isEmpty() )
System.out.println(Q.dequeue());

3.
i) Describe in detail (using pseudocode) the implementation of a priority queue based on a sorted
array. Show that your implementation achieves O(1) for operations min and removeMin, and O(n)
for insertions.
ii) Explain in a high-level way as well as in pseudo code how the removeMin operation works in
a min-heap.
iii). Explain in a high-­level way and also using pseudo-­code how to insert a key into a hash
table that uses linear probing for collisions. Assume the hash table is implemented using an array.

At which positions in a heap might the largest key be found?

Create a web page for User Validation and Authentication

http://pastebin.com/ZLBn9HVw

Problem 2 Part 1

A byte consists of how many bits?
7
8
7 or 8
None of the above

2 Which of the following defines a set of activities that begin at a specific date and end at another specific date in a software development lifecycle?
Program
Procedure
Process
Project

3 In a DBMS, predefined formats for entering data into one or more tables in a database is called which of the following?
Template
Form
View
Query

4 If 1000 bytes make 1KB, How many bytes are in 1 GB?
10E06
10E07
10E08
10E09

5 Which of the following is a major data collection method used in organizations?
Direct observation
Interviews
Questionnaires
All of the above

6 A comprehensive list of the data in the records of one or more data tables in a database?
Query
Report
Procedure
Query table

7 Which of the following is used to describe the information one is looking for in a data store?
Search term
Search language
Index
Key

8 When someone is looking for the name of a particular person, "Madu Okey", in a telephone directory, which data retrieval type is in use?
Subject retrieval
Topical search
Known-item
Key search

9 Which of the following refers to the process of decomposing data into separate data sets?
Data aggreggation
Data disaggregation
Data analysis
Data summarization

10 The process of reducing voluminous data into less voluminous data is called which of the following?
Data aggreggation
Data disaggregation
Data analysis
Data summarization

11 The process of investigating and identifying important attributes of a particular data set is called which of the following?
Data aggreggation
Data disaggregation
Data analysis
Data summarization

12 The process of planning or designing an information system is often referred to as which of the following?
SDLC
SLDC
SCLD
SLDC

13 The binary 101101 is equivalent to which of the following base 10 numbers?
43
46
45
55

14 77.44E04 is equivalent to which of the following?
774400
7744000
77440
77440000

15 Which of the following is a pre-defined way of displaying some or all the records and fields in a data table?
View
Model
Schema
Table

16 Which of the following is a statement that instructs a DBMS to find and display data from a database all data that meet some criteria?
Instruction
Query
Procedure
Function

17 The final stage of the software development lifecycle is which of the following?
Implementation of the new system
Operating the new system
Monitoring the new system
Analsis of the old system

18 When someone is searching for all economics books in the library catalogue but without having any specific book in mind, which data retrieval type is in use?
Subject search
Known-item
Key search
Query search

19 Which stage of the software development lifecycle is aimed at determining the kind of information that will be required by system users?
Feasibility study
user requirements analysis
design of new system
analysis of the old system

20 The first stage of the software development lifecycle is which of the following?
Feasibility study
user requirements analysis
design of new system
analysis of the old system

Shopping Spree is a leading departmental store in Shanghai. The store has a number of regular
customers who purchase bulk items. The store also conducts regular feedback sessions to
analyze customer satisfaction levels. Chen, the Customer Analyst of Shopping Spree, has to make
the ER diagram to represent the preceding situation, and then to map the ER diagram to the
corresponding tables. Help Chen to do the same.