University of Nevada Las Vegas
Howard R. Hughes
College of Engineering
Department of Computer Science
My Home Page
Course Page
Computer Science 477/677
Fall 2020
Analysis of Algorithms
Assignments and Lecture Topics
Revised December 6, 2020
-
Turning in Homework during the Covid Crisis
-
Your answers must be written in a pdf file and emailed to the graduate
assistant, Tandreana Chua
chuat4@unlv.nevada.edu
by 23:59 on the due date.
Your file must not exceed 5 megabyes, and must print out to at most 4 pages.
-
Monday, August 24, 2020
-
Welcome!
If you have registration issues today, see me right after class.
-
Wednesday, August 26, 2020
-
-
-
Monday, August 31, 2020
-
Turn in Assignment 1
by 23:59 tonight
-
Answers to Assignment 1
-
-
Wednesday, September 2, 2020
-
-
-
Wednesday, September 9, 2020
-
-
-
-
Thursday, September 10, 2020
-
Turn in Assignment 2 by 23:59 tonight
-
Answers to Assignment 2
-
-
Monday, September 14, 2020
-
Turn in Assignment 3 by 23:59 tonight
-
Answers to Assignment 3
Corrected
-
Wednesday, September 16, 2020
Correction
-
Examination today
-
-
-
195 Possible
-
101 Average
-
63 25 %-ile
-
100 50 %-ile (median)
-
133 75 %-ile
-
155 Highest
-
-
Monday, September 21, 2020
-
-
-
Wednesday, September 23, 2020
-
Turn in Assignment 4 by 23:59 tonight
-
-
-
Thursday, September 24, 2020
-
-
-
-
Monday, September 28, 2020
-
-
-
Wednesday, September 30, 2020
-
-
-
-
Thursday, October 1, 2020
-
Turn in Assignment 5 by 23:59 tonight
-
I plan to hold a Zoom office hour today from 3pm to 5pm.
-
-
-
Friday, October 2, 2020
-
I plan to hold a Zoom office hour today from 3pm to 5pm.
No one joined yesterday, although I know some students tried to get in.
Sorry abou that, I'll try to fix it.
-
-
Monday, October 5, 2020
-
Answers to Assignment 5
-
-
Tuesday, October 6, 2020
-
Office hour today 3-5. You will get an invitation on canvas, as usual.
-
-
Wednesday, October 7, 2020
-
-
-
-
Monday, October 12, 2020
-
Examination today
-
Answers for Practice Exam 2
Last and final update: October 10, 4:24 pm
-
Average
-
25 %-ile
-
50 %-ile
-
75 %-ile
-
highest
-
-
-
Wednesday, October 14, 2020
-
-
-
-
Thursday, October 15, 2020
-
I plan to hold a Zoom office hour today from 3pm to 5pm.
-
-
-
Monday, October 19, 2020
-
-
-
Wednesday, October 21, 2020
-
-
-
-
Thursday, October 22, 2020
-
-
I will hold an office hour from 3 to 5 today.
-
Turn in Assignment 6 by midnight today.
-
Problem 3
-
Thursday, October 23, 2020
-
-
I will hold an office hour from 3 to 5 today.
-
-
Monday, October 26, 2020
-
-
-
Wednesday, October 28, 2020
-
-
-
-
Thursday, October 29, 2020
-
I plan to hold a Zoom office hour today from 3pm to 5pm.
-
-
-
Monday, November 2, 2020
-
Comparison of recursion, dynamic programming, and
memoization
-
However, the above page does not explain how to use memoization to compute
fib(n) in O(log n) time and space. (Actually, O(log2n) if you
take into account that fib(n) has Theta(log n) digits.)
-
Wednesday, November 4, 2020
-
-
-
ng>Thursday, November 5, 2020
-
I plan to hold a Zoom office hour today from 3pm to 5pm.
-
-
-
Thursday, November 5, 2020
-
-
Office hour today 3-5
-
-
Friday, November 6, 2020
-
Turn in Assignment 7 by midnight
Monday November 9
-
Long version, with separate page for
each problem
-
Examples of AVL trees and Treaps
-
Example of double rotation of AVL tree
-
Clues to the Memoization Problem.
If you run the recursive program, there will be over 3000 recursive calls.
The memoization program makes about 500 calls. An additional cost
of the memoization program is searching the data structure for memos.
The problem cannot be
worked by standard dynamic programming, since there is no way to compute
the topological order of the subproblems in advance, nor even to know the
set of subproblems.
-
Office hour today 3-5
-
Monday, November 9, 2020
-
Office hour today 3-5
-
Answers to Homework 7
-
Wednesday, November 11, is Veterans' Day, a holiday.
-
Thursday, November 14, 2020
-
-
Office hour today 3-5
-
-
-
Friday, November 15, 2020
-
-
Office hour today 3-5 New
-
-
Monday, November 16, 2020
-
-
-
-
-
Tuesday, November 17, 2020
-
Office hour today 4:00 to 5:00
-
-
-
-
Wednesday, November 18, 2020
-
Examination today
-
Practice Exam
-
It is now ready.
-
-
Possible 210
-
Average 161
-
25 %-ile 110
-
50 %-ile 170 (median)
-
75 %-ile 185
-
Highest 208
-
-
-
Thursday, November 19, 2020
-
No office hour today.
-
-
-
-
Monday, November 23, 2020
-
-
-
Wednesday, November 25, 2020
-
-
-
-
Thursday, November 26, 2020
-
No office hour today because of the Thanksgiving holiday.
-
-
-
Friday, November 27, 2020
-
I plan to hold a Zoom office hour today from 4pm to 5pm,
even though, technically, we are still in the Thanskgiving recess.
-
-
-
Monday, November 30, 2020
-
Turn in Assignment 8
by 23:59 tonight
-
Answers to Assignment 8
-
I plan to hold a Zoom office hour today from 4pm to 5pm.
-
Saturday, November 28, 2020
-
-
I plan to hold a Zoom office hour today from 4pm to 5pm.
-
Wednesday, December 2, 2020
-
-
-
-
Thursday, December 3, 2020
-
-
I plan to hold a Zoom office hour today from 3pm to 5pm.
-
Friday, December 4, 2020
-
ABET Assessment Test
Corrected Fri Dec 4 16:00:08 PST 2020
-
The Accreditation Board of Engineering and Technology (ABET)
requires that we give an assessment test in each required course
for the Bachelor of Science degree in Computer Science.
Print out the above file, answer the questions, and email
a scanned copy to the TA. Do not write your name on the paper.
The requirement applies only to 477 students, not 677.
-
Wednesday, December 9, 2020
-
-
Final Examination 8:00 - 10:00
-
Practice Final
-
Answers to Practice Final
Unfinished
-
This version Sun Dec 6 13:12:24 PST 2020
-
There will also be a problem
on Dijkstra's algorithm.
Back to
Course Page