University of Nevada Las Vegas
Howard R. Hughes College of Engineering
Department of Computer Science
My Home Page

Computer Science 477/677
Analysis of Algorithms
Fall 2015
Assignments

Revised April 30, 2015

Background.
It is important to have a good background in algorithms and data structures at the level of CSC 302.
There is background material in your textbook.
Thursday January 29, 2015.
Turn in Assignment 1 at the beginning of class today.
Tuesday February 10, 2015.
Turn in Assignment 2 at the beginning of class today.
The first lecture topic today will be loop invariants and recursion invariants
If time permits, we will start the subject of sorting today. A major part of the examination next week Monday will be on that subject.
  1. Lower Bound on Sorting in the Comparison Model of Computation.
  2. Sorting algorithms we will go over:
    1. Selection sort.
    2. Insertion sort.
    3. Bubblesort.
    4. Mergesort.
    5. Quicksort.
    6. Polyphase mergesort.
    7. Binary tree sort, which is actually a fast implentation of insertion sort.
    8. Heapsort, which actually a fast implementation of selection sort.
    9. Shell sort, named after Donald Shell. Very ancient. Hardly anyone understands it. Donald Shell probably didn't, since he implemented it in the worst of all possible ways.
    10. Radix or bucket sort, the only sorting algorithm in this list which does not use the comparison model of computation.
  3. When I (personally) need to write a sorting algorithm in a program, I usually pick one of my four favorites. Which do you think they are?
My sincere apologies for the interruption last Thursday, and any resulting confusion in the assignments. Clearly the version of hw3 that has been posted for over a week is not correct. I believe that the situation will be under control from now on.
Tuesday February 17, 2015.
Turn in Assignment 3 at the beginning of class today.
This assignment deals with loop invariants and recursion invariants.
Thursday February 19, 2015.
Examination today.
Explanation of heapsort and quicksort, with examples.
Practice examination in postscript format.
Practice examination in portable document format.
Possible score: 220
Highest score: 173
75 percentile score: 115
Median score: 105
25 percentile score: 85
Mean score: 95
Comments: I believe that we could have done better.
I have a plan.
The results of the examination indicate one of two things. I don't believe the first one is possible, since I know we have excellent students in our program. That leaves me to conclude that:
I have not assigned enough homework.
Tuesday March 3, 2015.
Turn in Assignment 4 at the beginning of class today.
This assignment deals with recurrences.
Tuesday March 5, 2015.
Assignment 5 is postponed.
Tuesday March 10, 2015.
Turn in Assignment 5 at the beginning of class today.
This assignment deals with dynamic programming
Thursday March 12, 2015.
Tuesday March 17, 2015.
Thursday March 19, 2015.
Assignment 6 is due today.
Thursday March 26, 2015.
Examination postponed.
Tuesday April 7, 2015.
Examination today.
Practice examination in postscript format.
Practice examination in portable document format.
Possible score: 235
Highest score: 215
75 percentile score: 158
Median score: 139
25 percentile score: 115
Mean score: 139
Thursday April 30, 2015.
Turn in Assignment 7 at the beginning of class today.
Tuesday May 5, 2015.
Turn in Assignment 8 at the beginning of class today.
Correction made Sun Apr 26 3pm
Thursday May 14, 2015.
Final Examination today. The final examination is scheduled for 3:10 - 5:10 PM. The examination will be comprehensive.
Fall 2013 Practice final in postscript form
Fall 2013 Practice final in pdf form
Spring 2011 Practice final in postscript form
Spring 2011 Practice final in pdf form
Topics to study in preparation for the final exam.
There may be questions on some of these topics that are not represented on the practice finals.

Back to Course Page