CSE logo University of Washington Computer Science & Engineering
 CSE326 Winter 2006
  CSE Home    326 Home   About Us    Search    Contact Info 

 Project 1
 Project 2 - phase A
 Project 2 - phase B
 Project 3
 Homework 1
 Homework 2
 Homework 3
 Message Board
 Annoucement ArchiveCSE only
 Class List ArchiveCSE only
 Anonymous Feedback
 Mail Instructor & TAs
 Calendar & Slides
 First Day Handout
 General Guidelines
 Grading Policies
 Programming Guidelines
 Writeup Guidelines
 Unix Basics

Homework 1

Asymptotic Analysis and Priority Queues

Due: Wednesday, Jan 25, at the beginning of class

Please put your quiz section (AA, AB, BA, BB) at the top of your paper in addition to your name.

This assignment is designed to give you practice with the mathematical concepts behind algorithmic analysis as well as to introduce working with various implementations of priority queues, which will be useful in the next programming project.

Note: This is a written assignment, so late homework will not be accepted. There is no electronic turn-in. Problem numbers refer to the Weiss textbook.

Total: 80 points.

1)      [Basic math] (10 points) Problem 1.8, parts (a), (b)

2)      [Big-O notation] (10 points) Simplify the following expressions as much as possible using the Big-O notation, expressing each as big-O of some function of n, e.g. 3 n + log n = O(n). You don't need to give the constants c and n0 for this problem, but for practice, try finding them for some of your answers.

  a. n3 + 100 n
  b. 2 n2 - n + 2100
  c. 3 log log n + log2 n
  d. 10 n2 - 5 n + n3 log n
  e. 2.5n + n100

3)      [Program analysis] (10 points) Problem 2.7, part (a) only, fragments (2) to (6). Briefly justify your answer.

4)      [Recursive equations] (5 points) Estimate the running time of the following function using the Big-O notation. Make sure to state the recursive equation for running time, and solve it using your favorite method (such as expansion, induction).

int fun_a(int n) {
  if (n<=1) return 100;
  else return 2*fun_a(n-1);

5)      [Binary Min Heaps] (5 points total)

a)      Show the result of inserting: 10,12,1,14,6,5,8,15,3,9,7,4,11,13,2 one at a time into an initially empty  binary heap. Check your work!

b)      Show the result of performing two deleteMin operations on the heap you created in part a).

6)      [d-Heaps] (10 points) Problem 6.14. Also indicate the index of the array that contains (a) the root, (b) the next available location for insert. (Remember the root is stored in position 1)

7)      [Leftist Heaps] (10 points) Problem 6.19

8)      [Skew Heaps] (10 points) Problem 6.27. Show the result for the intermediate skew heap resulting after adding 1-3 and 1-6, and the final heap after adding 1-15. (You may show all 15 heaps if it's easier; although we will look at only the above 3 for grading.)

9)      [Binomial Qs] (10 points) Problem 6.32

CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to cary]