Posted 01-29-2020:
The fast elevator method is better known as "exponentiation by squaring" or
"binary exponentiation",
see here.
The page explains how this fast exponentation is applied in the context of Fibonacci numbers, see the short paragraph "Matrix exponentiation (fast)" (third bullet on the page.)
Posted 01-29-2020:
- Room change: Our class CS 477/677 will meet in CHE 101 for the rest of the semester.
-My office hours are changed 11:45 am - 1;45 pm and 4:00 pm to 6:00 pm tomorrow only (Thursday, January 30, 2020).
Posted 01-30-2020:
To review recursion we will look at the Towers of Hanoi game.
Posted 02-03-2020:
Current reading is chaper 2 and 3.1, 3.2, 3.3, 3.6.
Posted 02-06-2020:
Here is the Master Theorem.
Posted 02-13-2020
Counting Sort and
Radix Sort.
Posted 02-13-2020:
Current reading is chaper 4: 4.1-4.5, 4.7.
Posted 02-24-2020:
Reading: 7.3, 7.4, 12.1, 12.2.
Posted 02-24-2020:
Reminder: The first test is on Friday, March 6.
Reading (study guide) for the test.
Study Guide
(A) Recommended Reading:
Chapter 1: Focus on 1.6 and 1.7.
Chapter 2: Focus on 2.1, 2.2, 2.3, 2.4, 2.5, 2.6, 2.7.5
Chapter 3: Focus on 3.1, 3.2, 3.3, 3.6
Chapter 4: Focus on 4.1, 4.2, 4.3, 4.4, 4.5 and especially on 4.7
Sorting: 7.3, 7.4, 12.1, 12.2
(B) Review assignment sheets 1-4.
One page of notes (front and back) is allowed to bring to the test.
Posted 02-27-2010:
Nice video about Fermat's Little theorem.
Posted 02-27-2020:
Here is the Encryption Example.
Here is background on how to find a
modular multiplicative inverse or you can simply use
the
modular multiplicative inverse calculator.
Posted 03-11-2020:
The following message was sent through MyUNLV to all students in this class. If you did not receive this message, make sure to have your email address updated in MyUNLV so that you will receive future messages.
You may have seen a communication from UNLV President Marta Meana for faculty to prepare for transition to remote/virtual instruction. I can well imagine that after the Spring break most classes will be held online. However, as of this moment we are still meeting in class on Friday 13, 2020.
The situation is fluid and if anything changes I will send another email tomorrow Thursday. We may, for example, move to a much larger classroom so that everyone can sit far away from everyone else.
As you know, I normally hold regular office hours tomorrow and Friday. Considering the situation, I would ask that instead of coming to the office in person to send email instead. If we determine it necessary, we can initiate a one-on-one teleconference.
The current assignment 6 is only due on Saturday, March 28. And please check the announcement page frequently.
Posted 03-12-2020:
There is a typo in some of the Assignment 6 sheets, question 4: The table size is 5 not 7.
Posted 03-12-2020:
Here is a nice explantion why factoring is hard.
Posted 03-12-2020:
Tomorrow’s class (Friday, March 13):
Please come to the Great Hall TBE-A Building at 10:00 am. Please, keep 6 feet from one another. From there we will go to a large auditorium to be determined, so that everyone can sit far from one another. (It is important for you not to come late for this to work.) For tomorrow’s meeting, I will not take attendance.
I am currently working to transition to online lectures after the Spring break.
Posted 03-19-2020:
Starting Friday, March 27, classes will meet virtually via WebEx.
An invitation has been sent out to your email address on March 17.
(See my earlier post about email addresses posted on 03-11-2020.)
Unless you have dropped the class, please accept the invitation ASAP.
If did not receive the invitation,
please contact me through your official rebelmail by March 24.
Posted 03-21-2020:
A video welcome:
Class Meetings: Starting Friday, March 27, classes will meet virtually via WebEx. An invitation has been sent out to your email address on March 17. (See my earlier post about email addresses posted on 03-11-2020.) Unless you have dropped the class, please accept the invitation ASAP.
If did not receive the invitation, please contact me through your official rebelmail by March 24.
Office Hours: I will hold virtual office hours during the same time slots as before. (Thursday 1:30 pm – 6:30 pm; Friday 12:40 pm – 1:40 pm.)
This means during that time if you want to meet with me, you send me an email at
that time. Then we can continue with email or, if desired I will open a video session with you over WebEx.
The TA's office hours are also as before (Tuesdays: 4:00 pm - 5:30 pm, Wednesdays: 9:30 am - 11:00 am) and the same procedure applies, except he may be using a simple phone call or Skype (Skype id: mahajiali) instead of WebEx.
Homework Assignments:
Email homework in the same way as before, but we will not print out the pdf file. Instead we will use the sticky note commenting function in Adobe to mark up the PDF, and then email it back to you.
Exams:
Exams will be moved from in-class to online. Details will follow.
Syllabus:The syllabus has been augmented, please reread the syllabus.
Posted 03-25-2020:
Here is Assignment 6 (given out before the Spring break) due on March 28 and
Assignment 7 (given out March 27) due on April 11.
Slides for March 27:
Linear Median Find,
Fast Multiplication,
Dynamic Programming.
Posted 03-26-2020:
I will hold office hours today (3-26-2020) only until 5:00 pm and then increase them tomorrow (3-27-2020) 12:50 pm - 3:00 pm.
Posted 04-02-2020:
Current Reding: Chapter 7 and 8.1 - 8.6.
Sides for April 10: Algorithms on Graphs.
Posted 04-03-2020:
An interesting article on the Knapsack problem.
Posted 04-10-2020:
Assignment 8.
Posted 04-10-2020:
Reading, to be done before April 17 lecture:
Brassard: 6.1 - 6.3.
Papadimirtiou: Chapter 3 and 4.1-4.5 and 7.2.
Posted 04-16-2020:
Linear Programming Slides.
Assignment 9 due April 25.
Papadimirtiou: Reading: 7.1, 7.4.
Posted 04-23-2020:
Reminder: The second test is on Friday, May 1. It covers the material from the last test until the lecture on April 17 (including).
Reading (study guide) for the test.
One page of notes (front and back) is allowed to bring to the test.
Posted 04-23-2020:
Assignment 10, due on May 9.
The small simplex example in detail.
Posted 04-30-2020:
NP-completeness slides.
Posted 05-06-2020:
This is a reminder that the final for our class CS 477/677-1001 will be Friday, May 15 10:00 am to 12 pm.
We will be using the same test portal as in test 2.
You need to connect using your camera, such that I see your face.
If you do not have a camera attached to your computer, you can connect using your computer as well as using the phone.
Make sure to attend this Friday’s lecture for further guidance.
Study Guide
(A) Recommended Reading:
Papadimitriou Chapter 1 (Cryptography): 1.1 - 1.5
Papadimitriou Chapter 3 and 4 (Graphs): Complete Chapters
Brassard: Chapter 1 (Math Review): Focus on 1.6 and 1.7.
Brassard: Chapter 2 (Efficiency of Algorithms): Focus on 2.1, 2.2, 2.3, 2.4, 2.5, 2.6, 2.7.5
Brassard: Chapter 3 (Asymptotic Complexity, Big-Oh, etc): Focus on 3.1, 3.2, 3.3, 3.6
Brassard: Chapter 4 (Loops and Recurrences): Focus on 4.1, 4.2, 4.3, 4.4, 4.5 and especially on 4.7
Brassard: Chapter 5: (Advanced Data Structures): 5.8 (Binomial Heaps), 5.9 (Disjoint Set Data Structures)
Brassard Chapter 6 (Graphs): 6.3 (Prim, Kruskal), 9.2 Traversing graphs
Brassard Chapter 7 (Divide and Conquer, Sorting): 7.1, 7.2, 7.3, 7.4, 7.5, 7.6, 7.7, 7.8
Brassard Chapter 8 (Dynamic Programming): 8.1.1, 8.2, 8.3, 8.4, 8.5, 8.6
Brassard Chapter 12 (Sorting):
12.1, 12.2
Papadimitriou Chapter 7 (Linear Programming and Network Flows): 7.1, 7.2, 7.4, 7.6.
Papadimirtiou Chapter 8 (NP-completeness): Complete Chapter.
(B) Review assignment sheets 1-10.
(C) Review all Powerpoint presentations posted on the announcement page.
Three pages of notes (front and back) is allowed to bring to the test. Additionally there can be one sheet (front and back) of scatch paper.
Posted 05-08-2020:
For your review:
Test 2
Posted 05-13-2020:
Solutions to Assignment 10.
Link for final meeting: https://unlv.webex.com/unlv-en/j.php?MTID=m7c4657a0340d4b6179687984e63130c9
