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 notforcredit 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 topdown 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 NPcompleteness


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