Scribd
Upload
5 views

Week 1 Assignment 1 with solution final

The document contains a series of questions and answers related to VLSI Physical Design and Timing Analysis, covering topics such as geometrical level synthesis, time complexity, standard algorithms, heuristic algorithms, standard cell design, Dijkstra's algorithm, BFS, Minimum Spanning Trees, VLSI design styles, and interval graphs. Each question is followed by the correct answer and explanations where necessary. The assignment serves as a review of key concepts in VLSI design and algorithm analysis.

Uploaded by

rishiKumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views

Week 1 Assignment 1 with solution final

The document contains a series of questions and answers related to VLSI Physical Design and Timing Analysis, covering topics such as geometrical level synthesis, time complexity, standard algorithms, heuristic algorithms, standard cell design, Dijkstra's algorithm, BFS, Minimum Spanning Trees, VLSI design styles, and interval graphs. Each question is followed by the correct answer and explanations where necessary. The assignment serves as a review of key concepts in VLSI design and algorithm analysis.

Uploaded by

rishiKumar
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 8

VLSI Physical Design with Timing Analysis

Week 1 Assignment -1
Qns 1: What is the geometrical level synthesis?
a. Schematic gate level netlist to Layout
b. RTL to Layout
c. HDL to schematic gate level netlist
d. RTL to schematic gate level netlist

Ans: (a) (refer lecture slide)

Qns 2: Consider the following code


int fun(int n)
{
int count = 0;
for (int i = 0; i < n; i++)
for (int j = i; j > 0; j--)
count = count + 1;
return count;
}
What is the time complexity of fun in terms of Θ ?
a. Θ(n)
b. Θ(n2)
c. Θ(nlog(n))
d. Θ(nlog(nlogn))

Ans: (b)
The time complexity can be calculated by counting the number of times the expression
"count = count + 1;" is executed. The expression is executed 0 + 1 + 2 + 3 + 4 + .... + (n-
1) times.
Time complexity = Θ(0 + 1 + 2 + 3 + .. + n-1) = Θ (n*(n-1)/2) = Θ(n2)
Qns 3: In the following table, the left column contains the names of standard algorithms
and the right column contains the time complexities of the algorithms. Match each
algorithm with its time complexity.

1. Binary Search A. O(nlogn)


2. Linear Search B. O(n)
3. Merge Sort C. O(n2)
4. Bubble Sort D. O(logn)

a. 1→ B, 2 → A, 3 → D, 4 → C
b. 1→ D, 2 → B, 3 → C, 4 → A
c. 1→ D, 2 → B, 3 → A, 4 → C
d. 1→ B, 2 → A, 3 → C, 4 → D

Ans: c (refer lecture slide)

Qns 4: Heuristic algorithms are generally used for which kind of problem?
a. P
b. NP
c. NP-complete
d. NP-hard

Ans: (c) (refer lecture slide)

Qns 5:Which option is/are corrects related to standard cell design ?


a. Standard cell design comes in full custom category.
b. Standard cell design comes in the semi-custom category.
c. Connections between cells can go through channels or over cells.
d. Predefined rectangular cells of different height are used in standard cell design.

Ans: (b, c)
Standard Cell Design uses predefined rectangular cells of the same height.
Qns 6: Using Dijkstra's algorithm, find the shortest distance from ‘s’ to ‘x’ in the
following graph.

a. 8
b. 9
c. 11
d. 14

Ans: (b)
The shortest distance from s to x is 9.
Qns 7: The following graph was given as input to the BFS algorithm, and the starting
node is s. How many levels are possible in the BFS tree of the given graph?

a. 2
b. 3
c. 4
d. 5

Answer: 4

The BFS algorithm:


The BFS tree:

Qns 8: Consider the following graph with edge weights indicated on the edges. Which of
the following is/are the Minimum Spanning Tree/s(MST) of the given graph?

a.

b.
c.

d.

Answer: (a, c)
MST generated using Kruskal’s algorithm.
We can generate similar MST by connecting nodes b and c instead of a and h. It
generates the following MST.

Qns 9: Which of the following is/are true regarding VLSI design styles?
a. Standard cell design occupies less chip area than a full-custom design style.
b. An uncommitted gate array is a prefabricated chip where routing layers are added
on top in a fabrication facility.
c. FPGAs are the pre-diffused type of gate array-based design style.
d. In the macro cell-based design style, all macro cells must have the same height.

Answer: (b)
Qns 10: Consider the following arrangement of lines.

The number of edges in the interval graph of the given arrangement of lines is ___.
a. 11
b. 10
c. 9
d. 12

Answer: 10
The interval graph is the union of the Overlap and Containment graphs. The Overlap,
Containment, and interval graphs of the given arrangement of lines are given below.

The number of edges in the interval graph = 10.

You might also like