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 2020
Course Page and Syllabus

Check the Assignments and Lecture Topics Page frequently.

Covid 19 and all that:
The University has issued instructions related to Covid 19. I won't repeat them here.
I will be teaching in person this Fall. I will take attendance. If you would prefer a virtual class, please switch to a different section.
Instructor:
Dr. Larmore
Office, TBE B378B.
Telephone ☎ 702-895-1096.
Email: lawrence "dot" larmore "at" unlv "dot" edu
Office Hours:
I will not schedule in-person office hours.
My plan is to hold virtual office hours using Zoom. I hope that everyone has a computer with speakers.
It would be best to also have a microphone and a camera.
Contacting Me:
You may telephone my office. Please do not leave a telephone message.
It's best to send me email. Be sure to write "CS477" in the subject field so that I know what the message is about. (I delete lots of messages without reading them, based on the subject fields.)
Please, never try to communicate with me by leaving notes on my door, under my door, or in my mailbox in the department office, as those notes get lost, and I can't retrieve them remotely.
If it is necessary to give me something, please leave it with the department staff, and then send me an email message saying that the item has been left for me.
Days of Instruction:
August 24, 2020 - December 4, 2020. Correction!
Graduate Assistant:
Tandreana Chua. Email: chua4 "at" unlv "dot" edu
Office Hours (through Webex): 2:00 - 4:00 Mon, Wed
Time of Instruction:
8:30 - 9:45, Monday and Wednesday.
Place of Instruction:
TBE-B 172.
Time of Instruction:
8:30 -- 9:45 Mondays and Wednesdays
Labor Day Recess:
September 7
Veterans Day Recess:
November 11
Textbook:
Algorithms, by Sanjay Dasgupta, Christos Papadimitriou, and Umesh Vazirani Change from Last Semester
CS 302 (Data Structures)
MAT 351 (Discrete Mathematics II).
Click here if you did not take both CSC 302 and MAT 351 at UNLV and receive a grade of "C" or better in each of those two courses.
Graduate Students:
If you want graduate credit, you must enroll in 677, not 477.
Each CSC 656 student must turn in at least one challenge problem and turn it in by the last week of class. CS 477 students are also permitted to work challenge problems, but I will not permit students to improve a poor grade in this manner. The reason for this policy is that I want students who are doing poorly in the course to devote their energy to mastering the regular material.
Written Homework:
will be assigned, collected, and graded. You are permitted to discuss homework.
Examinations:
First Examination: Wednesday, September 16.
Second Examination: Monday, October 12.
Third Examination: Wednesday, November 18.
Final Examination: 8:00 - 10:00 Either Monday or Wednesday of finals week. (To be announced)
Grading:
Your grade will be based on:
  • Three mid-term examinations. 60%
  • Homework. 10%
  • Final examination. 30%
Although the homework will take a substantial amount of time to work, and will actually be harder than the examinations, it counts for a smaller part of the grade. The reason for this is that I allow you to work together on homework. If you work the homework regularly, you should do well on the examinations.
Topics:
  • Modular arithmetic and RSA encryption
  • Sorting
  • Divide and Conquer
  • Dynamic programming
  • Trees, graphs
  • Depth first search
  • Breadth first search
  • Kruskal's and Prim's algorithms
  • Union/Find
  • Algorithm analysis
  • Recurrence relations: master theorem
  • Loop Invariants
  • Shortest path problem, including Dijksta's algorithm and the A* algorithm
  • NP-completeness