Class Notes (834,986)
Canada (508,846)
York University (35,167)
ITEC 2620 (2)
Lecture

Assignment1.pdf

5 Pages
444 Views
Unlock Document

Department
Information Technology
Course
ITEC 2620
Professor
Stephen Chen
Semester
Winter

Description
York University AP/ITEC 2620 3.0 INTRODUCTION TO DATA STRUCTURES Assignment Prof. S. Chen Surname: __________________ _________________ Given Names: ___________________________________ Student Number: ___________________________________ 1 Total 2 3 Page 1 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 dele te 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(n 2) for an array in sorted order. Explain how this is possible/how this version of quicksort was implemented. Page 2 of 5 Question 2 (10 marks) Complexity Analysis/Estimation: Assume that an a
More Less

Related notes for ITEC 2620

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit