ITEC 2620 Lecture Notes - Quicksort, Binary Search Algorithm, Linked List

456 views5 pages
Published on 14 Apr 2013
School
York University
Department
Information Technology
Course
ITEC 2620
Professor
Page 1 of 5
York University
AP/ITEC 2620 3.0
INTRODUCTION TO DATA STRUCTURES
Assignment
Prof. S. Chen
Surname: ___________________________________
Given Names: ___________________________________
Student Number: ___________________________________
1
2
3
Total
Unlock document

This preview shows pages 1-2 of the document.
Unlock all 5 pages and 3 million more documents.

Already have an account? Log in
Page 2 of 5
Question 1 (15 marks) Short Answer (maximum 20 words):
Answer all five parts below.
Part A (3 marks): What is the worst case time complexity for binary search on a BST with n
elements? Explain.
Part B (3 marks): The first time you run algorithm A on a dataset of n elements; it is faster than
algorithm B. The second time you run algorithm A on a dataset of n elements; it is slower than
algorithm B. Explain how this is possible. Give an example for algorithm A and algorithm B.
Part C (3 marks): If both have n nodes and are sorted smallest to largest, will it be faster to find
the largest value in a sorted linked list or a minimum-level BST? Explain.
Part D (3 marks): What is the time complexity to delete the root of a minimum-level BST with
n nodes? Explain.
Part E (3 marks): An implementation of quicksort has its worst case of O(n2) for an array in
sorted order. Explain how this is possible/how this version of quicksort was implemented.
Unlock document

This preview shows pages 1-2 of the document.
Unlock all 5 pages and 3 million more documents.

Already have an account? Log in

Document Summary

Question 1 (15 marks) short answer (maximum 20 words): Part b (3 marks): the first time you run algorithm a on a dataset of n elements; it is faster than algorithm b. The second time you run algorithm a on a dataset of n elements; it is slower than algorithm b. Give an example for algorithm a and algorithm b. Part e (3 marks): an implementation of quicksort has its worst case of o(n2) for an array in sorted order. Explain how this is possible/how this version of quicksort was implemented. Assume that an array has n random values. What is the time complexity of the following method that makes every element in the array equal to the largest element in the original array. Write a recursive function that will calculate the height of a binary tree. Note: root1 and root2 are instances of the class binnode: root2.

Get OneClass Grade+

Unlimited access to all notes and study guides.

YearlyMost Popular
75% OFF
$9.98/m
Monthly
$39.98/m
Single doc
$39.98

or

You will be charged $119.76 upfront and auto renewed at the end of each cycle. You may cancel anytime under Payment Settings. For more information, see our Terms and Privacy.
Payments are encrypted using 256-bit SSL. Powered by Stripe.