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 Languages
Spring 2019
Assignments and Lecture Topics

Revised May 13, 2019

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:
  1. 28 answered the high school algebra problem correctly.
  2. 15 answered the calculus problem correctly.
  3. 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.
  1. Identify subproblems.
  2. Solve the subproblems in topological order.
  3. The simplest dynamic programming problem: the shortest path problem in a weighted acyclic digraph
  4. Rod cutting problem
  5. Some other dynamic programming practice problems:
  6. A tutorial on dynamic programming
Memoizing.
  1. Identify subproblems.
  2. Solve subproblems in top-down order using recursion, storing each solution as a memo in a search structure.
  3. 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

Back to Course Page