COMP 554 – Analysis of Algorithms – fall 2019

Course Syllabus

  • Course URL: http://prof.msoltys.com/?page_id=4952
    (This course was taught previously in the Spring 2015, in the Fall 2016, and in the Spring 2018)
  • Canvas Page: https://cilearn.csuci.edu/courses/10409
  • CI Catalogue URL
  • Course Syllabus
  • Instructor: Michael Soltys <michael.soltys@csuci.edu>
  • Twitter: @MichaelMSoltys
  • 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: Wednesdays, 6-9pm, Location: Sierra Hall 1422.
  • Textbook: An Introduction to the Analysis of Algorithms, by Michael Soltys.
  • Grading: A midterm worth 25% and a final exam worth 25%, both to be written without aids and individually in class. There will also be 10 short assignments, each worth 5%. The assignments have to be completed in groups of three one group of 2 or one group of 4 will be allowed if not possible otherwise. 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.
  • 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

  • November 27, 2019: A previous post on Rabin Miller.
  • November 13, 2019: The final exam will be similar to the midterm; it will be written on December 4th, 6pm to 7pm, and it will consists of 25 multiple-choice questions covering the entire course.
  • October 3, 2019: The midterm will be “take home”, in the sense that it will be available on Canvas on October 16, from 6pm until 7pm – to be opened at 6pm and submitted by 7pm. Please note that the midterm has to be written individually (not in groups) and submitted individually. There will be no lecture on the day of the midterm. Assignment 5 is due on October 9, but assignment 6 will be given on October 23, and it will be due on October 30. This will give you time to prepare for the midterm; for the midterm you are responsible for chapters 1, 2 and 3. Chapter 3, Divide and Conquer, is short, and it will be covered during the October 9th lecture.
  • August 28, 2019: There is going to be no class on Wednesday September 4th, as the instructor is away at a conference (KES 2019 in Budapest). Please read book section 1.1, What is Correctness?, pp. 1-10, and do all the exercises; this is important foundations to the rest of the course. On September 11th, we will continue with section 1.2, Ranking Algorithms.
  • August 28, 2019: First class today at 6pm in Sierra Hall 1422.
  • June 26, 2019: Page set up.

Assignments

  • Assignment 1: Show that for any integer $latex k\ge 1$, if $latex a>b\ge 1$ and $latex b<F_{k+1}$ (where $latex F_i$ is the $latex i$-th Fibonacci number), then Euclid’s algorithm on $latex a,b$ takes fewer than $latex k$ iterations of the while loop. (Ignore swaps or use $latex 2k$ instead.)
  • Assignment 2: in 2004, Google ran a recruitment campaign where they posted the following billboard along the main freeway (101) running through Silicon Valley, and later at other locations in the country. Would you be able to apply for this position? You can test yourself by doing this assignment. Please submit the correct URL, as well as a description of how you achieved it. In particular, your algorithm has to be from scratch meaning that you should find a way to generate the digits of e and do a search through them for the appropriate prime. Please do not look up the solution online.
  • Assignment 3: In the paper distributed in class on September 11, Approximating consistency in pairwise comparisons, by Christopher Kuske, Konrad Kułakowski and Michael Soltys, one of the algorithms proposed is Algorithm 4, which effectively uses a type of binary search to approximate an inconsistent matrix with a consistent one. Implement this algorithm in Python 3. The input to the algorithm should be a text file containing a matrix with rational entries of the form $latex x/y$. The operations should be on quotients, i.e., numerator and denominator – the numbers should not be treated as floats, but as pairs of integers. An important questions is: when should the algorithm stop; provide a justification in your writeup. Also prove that if a matrix is consistent, then it is the case for all $latex k$ that $latex a_{ip_1}a_{p_2p_3}\cdots a_{p_{k-1}p_k}a_{p_kj}=a_{ij}$.
  • Assignment 4: This is a theoretical assignment, so please only submit a PDF. Show the following: given a graph G, and given any MCST T for G, there is a valid ordering of the edges of G (according to cost) so that on input G, Kruskal’s algorithm yields exactly T.
  • Assignment 5: Here is the text of chapter 29 of Jane Austen’s Pride and Prejudice. The file has 269 lines, 2379 words and 13773 characters – which also corresponds to the number of bytes in the file as it is encoded in ASCII, which means that the file has 110,184 bits. Implement Hoffman’s greedy algorithm to compress the file – let’s see who can get away with the smallest number of bits 🙂 In case you are interested, you can use the following utilities to examine the internals of the file:
    1. od: octal dump
    2. xxd: a more developed version of od
    3. wc: word count
    4. file: type of file
  • Assignment 6: Our first dynamic programming assignment, on dynamic alignment (i.e., measuring differences between strings). [pdf]
  • Assignment 7: Our second dynamic programming assignment, on the shuffle problem (used to model concurrency, and many other applications). [pdf]
  • Assignment 8: Problem 5.10 in the textbook – implement an experiment in Python comparing OPT and MTF. Submit the Python code, as well as the graph displaying your result.
  • Assignment 9: Part of Problem 5.30 – chose just one of the disciplines on figure 5.2.
  • Assignment 10: The first item in the textbook’s bibliography is a paper by Agrawal, Kayal and Saxena, titled Primes is in P. That paper, published in 2004, and gives the first polytime deterministic algorithm for primality. Please write a one page explanation why OpenSSL, and other tools, still use the randomized Rabin-Miller instead of the deterministic polytime algorithm.