Scribd
Upload
332 views

Design and Analysis of Algorithms: CSE 5311 Midterm Exam Practice

This document provides information about an upcoming midterm exam for a Design and Analysis of Algorithms course. It outlines the chapters and topics that will be covered in the exam, including growth functions, divide-and-conquer algorithms, sorting algorithms, and binary search trees. It advises students to review homework assignments, lectures, and textbooks to prepare as 60% of exam questions will come from homework problems. Sample exam questions on true/false, multiple choice, and algorithms are provided with explanations to help students practice.

Uploaded by

Rajat Sharma
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
332 views

Design and Analysis of Algorithms: CSE 5311 Midterm Exam Practice

This document provides information about an upcoming midterm exam for a Design and Analysis of Algorithms course. It outlines the chapters and topics that will be covered in the exam, including growth functions, divide-and-conquer algorithms, sorting algorithms, and binary search trees. It advises students to review homework assignments, lectures, and textbooks to prepare as 60% of exam questions will come from homework problems. Sample exam questions on true/false, multiple choice, and algorithms are provided with explanations to help students practice.

Uploaded by

Rajat Sharma
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/ 11

Design and Analysis of Algorithms

CSE 5311
Midterm Exam Practice

Junzhou Huang, Ph.D.


Department of Computer Science and Engineering

Dept. CSE, UT Arlington


Dept CSE5311 Design and Analysis of Algorithms 1
Midterm Exam
• Covered Contents
– Chapter 1-3, Introduction & Growth Functions
– Chapter 4 Divide-and-Conquer & Master Theorem
– Chapter 30, FFT
– Chapter 6-7, Heapsort & Quicksort
– Chapter 8, Sorting in Linear Time
– Chapter 9, Median & Order Statistics
– Chapter 12-13, Binary Search Tree & Red-black Tree

• Questions
– PART I. False and True (10 x 1pts=10pts)
– PART II. Multiple Choices (10 x 3pts=30 pts)
– PART III. Algorithm Questions (6 x 10pts=60pts)

Dept. CSE, UT Arlington


Dept CSE5311 Design and Analysis of Algorithms 2
How to review
• Questions
– 60% of questions come from the questions in Homework Assignments

• How
– Homework Assignments
– Lectures
– Textbooks

Dept. CSE, UT Arlington


Dept CSE5311 Design and Analysis of Algorithms 3
Practices
• True and False
– Binary insertion sorting (insertion sort that uses binary search to nd each
insertion point) requires O(n log n) total operations.

Solution: False. While binary insertion sorting improves the time it takes to find
the right position for the next element being inserted, it may still take O(n) time
to perform the swaps necessary to shift it into place. This results in an O(n2)
running time, the same as that of insertion sort.

– In a BST, we can find the next smallest element to a given element in O(1)
time.

Solution: False. Finding the next smallest element, the predecessor, may require
traveling down the height of the tree, making the running time O(h).

Dept. CSE, UT Arlington


Dept CSE5311 Design and Analysis of Algorithms 4
Multiple Choices
• You are running a library catalog. You know that the books in
your collection are almost in sorted ascending order by title,
with the exception of one book which is in the wrong place. You
want the catalog to be completely sorted in ascending order.
– (a) Insertion Sort
– (b) Merge Sort
– (c) Radix Sort
– (d) Heap Sort
– (e) Counting Sort

[a]

Dept. CSE, UT Arlington


Dept CSE5311 Design and Analysis of Algorithms 5
Multiple Choices
• Which of the following complexity analysis is/are correct.
– (a) The worst case running time for building a binary search tree is O(n lg n).
– (b) The worst case running time for building a red-back tree is O(n lg n).
– (c) The worst case running time for building a binary search tree is O(n2).
– (d) The worst case running time for building a red-back tree is O(n2).

[b,c]

Dept. CSE, UT Arlington


Dept CSE5311 Design and Analysis of Algorithms 6
Algorithm Questions
• Give asymptotic upper and lower bound for T(n) in each of
the following recurrences. Assume that T(n) is constant for n
<=2. Make your bounds as tight as possible, and justify your
answers.
1. T(n) = 2T(n/2) + n4
2. T(n) = T(n-2) + n2

Dept. CSE, UT Arlington


Dept CSE5311 Design and Analysis of Algorithms 7
Algorithm Questions
• Give asymptotic upper and lower bound for T(n) in each of
the following recurrences. Assume that T(n) is constant for n
<=2. Make your bounds as tight as possible, and justify your
answers.
1. T(n) = 2T(n/2) + n4
2. T(n) = T(n-2) + n2

Dept. CSE, UT Arlington


Dept CSE5311 Design and Analysis of Algorithms 8
Master Theorem
The master method applies to recurrences of the form
T(n) = a T(n/b) + f (n) ,
where constants a ≥ 1, b > 1, and f is asymptotically positive function

1. f (n) = O(nlogba – ε) for some constant ε > 0, then T(n) = Θ(nlogba)


2. f (n) = O(nlogba ) for some constant ε > 0, then T(n) = Θ(nlogba lgn)
3. f (n) = O(nlogba + ε) for some constant ε > 0, and if a f (n/b) ≤ c f (n)
for some constant c < 1, then T(n) = Θ( f (n) ) .

Dept. CSE, UT Arlington CSE5311 Design and Analysis of Algorithms 9


Algorithm Questions
1. T(n) = T(n-2) + n2

• Solution:

T(n)=n2+ T(n-2)= n2+ (n-2)2 +T(n-4)

Dept. CSE, UT Arlington


Dept CSE5311 Design and Analysis of Algorithms 10
Algorithm Questions
• T(n) = 2T(n/2) + n4

• Solution:

a=2, b=2, n log b a =n,

f(n)=n4

a f (n/b) ≤ c f (n)??? 2(n/2)4 =1/16 ∗(n)4


Case 3.

T(n)=Θ(n4 ) .

Dept. CSE, UT Arlington


Dept CSE5311 Design and Analysis of Algorithms 11

You might also like