University of Nevada Las Vegas
Howard R. Hughes
College of Engineering
Department of Computer Science
My Home Page
Course Page
Computer Science 477/677
Analysis of Algorithms
Spring 2019
Assignments and Lecture Topics
Revised May 13, 2019
![](../../../../bluhorsa.gif)
-
Wednesday, January 23, 2019
-
We will begin by discussing asymptotic complexity.
-
Monday, January 28, 2019
-
38 students turned in the not-for-credit quiz. Of those:
-
28 answered the high school algebra problem correctly.
-
15 answered the calculus problem correctly.
-
34 answered the CS302 problem correctly.
-
Turn in Assignment 1 at the beginning of class today.
-
Monday, Februay 4, 2019
-
Turn in Assignment 2 at the beginning of class today.
-
Wednesday, February 13, 2019
-
Examination.
-
Practice Exam
-
Distribution:
113 25 %-ile
125 50 %-ile (median)
129 mean
145 75 %-ile
188 highest
200 possible
-
Monday, February 25, 2019
-
I was almost
right about the potential. The correct formula is
Φ =
hi − lo − 1 if
X[lo + 1] < pivot and X[hi] > pivot
hi − lo otherwise.
-
Thursday, February 28, 2019
-
Assignment 3 is now ready.
-
Monday, March 4, 2019
-
Read about
Double Rotation
in AVL trees.
-
Problems on loop invariants
-
Answers to problems on loop invariants
-
Wednesday, March 6, 2019
-
Turn in Assignment 3
at the beginning of class today.
-
Answers to Assignment 3
-
Wednesday, March 13, 2019
-
Examination.
-
Practice Exam
-
Some of the answers to the practice exam
Error in answer file corrected Tue Mar 12 14:53:41 PDT 2019
-
Distribution:
180 25 %-ile
204 50 %-ile (median)
200 mean
220 75 %-ile
highest 255
possible 260
-
Monday, March 25, 2019
-
Dynamic Programming.
-
Identify subproblems.
-
Solve the subproblems in topological order.
-
The simplest dynamic programming problem:
the shortest path problem in a weighted acyclic digraph
-
Rod cutting problem
Some other dynamic programming practice problems:
A tutorial on dynamic programming
Memoizing.
-
Identify subproblems.
-
Solve subproblems in top-down order using recursion,
storing each solution as a memo in a
search structure.
-
You don't solve all subproblems; only those that are used for the final
solution. Your recursive function determines which ones are needed.
Monday, April 1, 2019
Turn in Assignment 4
at the beginning of class today.
Revised March 27, 2019
Read This!
Wednesday, April 10, 2019
A* algorithm
A longer discussion
Wednesday, April 17, 2019
Examination.
Practice Exam
Distribution:
135 25 %-ile
153 50 %-ile (median)
152 mean
172 75 %-ile
210 highest
210 possible
One person did not put his/her name on his/her paper.
The Collatz problem.
Practice Exam
Monday, April 22, 2019
Longest Common Subsequence
Iterated logarithm>
Inverse Ackermann function
Computing the convex hull of a set of points in the plane:
Graham scan
Wednesday, April 23, 2019
Various reductions to prove NP-completeness
Wednesday, May 1, 2019
Turn in Assignment 5
at the beginning of class today.
Tuesday, May 14, 2019
I will be in my office most of the morning. I might have to take time to
meet a faculty candidate.
Wednesday, May 15, 2019
Final Examination. 8:00 to 10:00.
Practice Exam
Answers to Practice Exam
.
The most important correction is for Problem 6.
If you find any more mistakes, please email me immediately.
Distribution:
229 25 %-ile
250 50 %-ile (median)
254 mean
279 75 %-ile
335 highest
350 possible
![](../../../../bluhorsa.gif)
Back to
Course Page