# COMP 554 – Analysis of Algorithms – Spring 2018

### Course Syllabus

• Course URL: http://prof.msoltys.com/?page_id=3130
(This course was taught previously in the Spring 2015, and in the Fall 2016)
• CI Catalogue URL
• Instructor: Michael Soltys <michael.soltys@csuci.edu>
• Course Outline: This course is an introduction to the analysis of algorithms. We are going to cover some basics of proving algorithm correctness (pre/post-condition, loop invariants, and termination), and then we are going to spend the bulk of the time on three classical categories of algorithms: Greedy, Divide-and-Conquer, and Dynamic Programming. We are going to see examples of problems that yield to these types of algorithms. We will discuss NP-completeness when we meet Dynamic Programming algorithms. We will also see three more advanced types of algorithmic approaches: Approximation, Online and Randomized. The last one is intimately connected to modern Cryptography, and so we will introduce the algorithmic foundations of Cryptography as well.
• Lectures: Tuesdays, 7-9:30pm, Location Bell Tower 1462.
• Textbook: An Introduction to the Analysis of Algorithms, by Michael Soltys.
• Grading: Three assignments worth 25% each, and a final take-home exam also worth 25%. The assignments will consist in a selection of problems from the textbook. The assignments have to be completed in groups of at least two, and no more than three. Please form a group at the beginning of the course, and worked on all the assignments with the same group. There is tremendous value in working on problems with your group; it amplifies the learning experience, and teaches teamwork. The final exam will be written individually.
• How to avoid plagiarism: As mentioned above, the assignments will be written in groups. Each group has to work independently of the other groups; verbal discussions of problems among groups are allowed, but you should not show written notes, and you should not leave such discussions with written notes. The same applies to the final individual exam.
• Attendance: Students are encouraged but not required to attend the lectures. The assignments will be posted online.
• Students with disabilities: Cal State Channel Islands is committed to equal educational opportunities for qualified students with disabilities in compliance with Section 504 of the Federal Rehabilitation Act of 1973 and the Americans with Disabilities Act (ADA) of 1990. The mission of Disability Accommodation Services is to assist students with disabilities to realize their academic and personal potential. Students with physical, learning, or other disabilities are encouraged to contact the Disability Accommodation Services office at (805) 437-8510 for personal assistance and accommodations. Please discuss your arrangements with the instructor as soon as possible.
• Check this web page regularly for announcements.

### Announcements and class diary

• May 8, 2018: Last lecture on Cryptographic protocols: properties of Diffie-Hellman, and an overview of ElGamal, and RSA, with some examples of OpenSSL and GnuPG.
• May 1, 2018: Seminar by Marina Lepikhina: blog post.
• April 24, 2018: Proof of correctness of the Rabin-Miller algorithm, and an introduction to Cryptography, especially with the Diffie-Hellman key-exchange protocol.
• April 17, 2018: We started discussing randomized algorithms (chapter 6 in the textbook) in light of primality testing as applied to cryptography. We looked at the brute force algorithm, at the Sieve of Eratosthenes, and we presented the Rabin-Miller algorithm for primality testing, and two main ideas: how to generate large primes using a testing algorithm, and how to amplify the error away.
• April 10, 2018: Lecture by Ryan McIntyre (post)
• April 3, 2018: Online Algorithms, chapter 5. We showed in detail that the “Move to Front” (MTF) list accessing discipline is 2-competitive. We emphasized that our approach to online algorithms is competitive analysis of performance.
• March 27, 2018: Talk by Adrian Domanico.
• Mar 20, 2018: Spring break.
• Mar 13, 2018: We finished Dynamic Programming, with a discussion of the overwriting technique in Floyd’s algorithm, then a detailed discussion of the Simple Knapsack Problem, with a foray into NP-completeness and approximation algorithms – with an example of a greedy approximate solution to the SKS. We finished with Activity Selection with Profits.
• Mar 6, 2018: We started Dynamic Programming, chapter  4. We covered the Longest Monotone Subsequence Problem, and the All Pairs Shortest Path. Make sure that you fill in the matrix for the example presented in the slides in the class.
• Mar 6, 2018: Class plan:
• On Mar 6 and Mar 13 we are going to cover Dynamic Programming (Chapter 4).
• Mar 20: no class, Spring Break.
• April 10: no class, please attend seminar at 5pm (place to be announced), by Adrian Domanico, who is a developer at Facebook. This talk is interesting if you are considering a career as a programmer/software engineer.
• April 3: a special lecture (usual time and place) by Ryan McIntyre on our recent publication (post).
• April 10, 17, 24, May 1,8 we will be covering online and randomized algorithms.
• Feb 27, 2018: We covered Chapter 3, Divide & Conquer. We saw mergesort, fast multiplication, Savitch, and also very briefly quick sort and git bisect.
• Feb 20, 2018: Discussed Assignment 2 (posted below), and finished Greedy’s algorithm – finished the proof of Kruskal’s, then we discussed job selection with deadline and profit, and other examples of Greedy solutions. We will start Divide & Conquer next week, so please read chapter 3 ahead of the lecture.
• Feb 13, 2018: We started Greedy Algorithms, chapter 2, with Kruskal’s algorithm for computing minimum cost spanning trees. We still have to finish the proof of correctness, which we will do next week.
• Feb 13, 2018: This is what Startups in the Bay Area tells us they are looking for in students: grit, resilience/determination, and superior communication skills.
• Feb 6, 2018: Ranking algorithms: PageRank (Google search ranking) and the Gale-Shapley algorithm for the Stable Marriage Problem. You are now ready to do assignment 1.
• Jan 31, 2018: The assignments will be submitted online using Canvas. The solutions should by typeset in LaTeX, and submitted as a PDF file.
• Jan 30, 2018: Second lecture, we introduced the notions of algorithms correctness: pre and post conditions, loop invariants, partial correctness, termination and correctness. We examined two simple algorithms to demonstrate their proofs of correctness: the division algorithm (A1.1) and Euclid’s algorithm (A1.2). For the next lecture read the section on ranking algorithms in the first chapter.
• Jan 25, 2018: Please pick up your course materials (at cost of printing) from the Copy Center at the UGlen Town Center (email: copycenter@coast-repro.com) .
• Jan 25, 2018: Canvas is now set up; please form your groups there: https://csuci.instructure.com/courses/3800
• Jan 24, 2018: Room change again due to increased enrollment: BT 1462
• Jan 23, 2018: First lecture, introduced the course, the outline, the requirements, and we watched the documentary The secret rules of modern living: Algorithms.
• Jan 22, 2018: Room change: First lecture tomorrow (Jan 23) at 7pm in BT 2372.
• Dec 22, 2017: First lecture on January 23, 2018, at 7pm, in Sierra Hall 1111.

### Assignments

• Assignment 1: due on February 20, on the stable marriage problem. [Solution]
• Assignment 2: due on March 13, the Prim’s algorithm. Assignment 2, question 3, asks for a Python implementation of Prim’s algorithm, where you are to use a heap to keep track of the cheapest edge with one en point in B and the other not. We will test your algorithms on inputs which should be text files (`input.txt`) formatted as follows:
```0.0 0.8 1.0
0.8 0.0 9.0
1.0 9.0 0.0```

That is, a square $nxn$ matrix, where each entry is a float, the diagonal has 0.0s only, and the matrix is such that entry $(i,j)$ is identical to $(j,i)$, as the graph is undirected. A matrix not of that form should be rejected by your implementation. Each row consists of $n$ values, separated by a single space. [Solution, .py, .hs]

• Assignment 3: due April 10, Problem 4.28 in the textbook. The problem is asking you to propose a Dynamic Programming solution to the shuffle problem; that is, an array of subproblems, a recurrence, a pseudo-code solution and finally a Python3 implementation. A sample input to the assignment is as follows (a text file with x,y,w on consecutive separate lines):
```0000
1111
01011100```

[Solution, .py]

• Assignment 4 (final individual assignment): due May 8. Do problems 6.17 and 6.18 in the textbook. Also, run the following experiment: implement the Rabin-Miller algorithm where the input is assumed to be an integer given in binary (see Problem 6.11) – you may use the implementation given here.  Now, for as many inputs $(n)_b$, that is number $n$ given in binary, if $n$ is not prime, computer how many witnesses (of compositeness) are there. Plot the result, and hypothesize on a good asymptotic approximation to the function $f_w(n)=m$ where $m$ is the number of witnesses for a given $n$ (of course, $m=0$ if $n$ is prime). [solution]