MATH 354 – Analysis of Algorithms – Fall 2016

Course Syllabus

  • Course URL: http://prof.msoltys.com/?page_id=1687
  • CI Catalogue URL: http://bit.ly/1tsBzi1
  • 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. Depending on the time, we may also see some modern types of algorithms: online, random, string, etc.
  • Lectures: MW 3:00-4:15 in Sierra Hall 2344
  • Textbook: An Introduction to the Analysis of Algorithms, by Michael Soltys.
  • Grading: Six assignments worth 10% each, and a final exam worth 40%. 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. It would be best if you formed 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 instructor will grade one or two “random” problems from the assignment. 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.
  • Attendance: Students are encouraged but not required to attend the lectures. The assignments will be posted online. The final exam will be written in class.
  • 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

Assignments

The assignments to be submitted as PDFs with Blackboard. Consider learning LaTeX for the course.

  • Assignment 1: Due on Monday September 26
    Problem 1.22 in the textbook: Write a Python program that implements Euclid’s extended algorithm. Then perform the following experiment: run it on a random selection of inputs of a given size, for sizes bounded by some parameter N; compute the average number of steps of the algorithm for each input size n ≤ N, and use gnuplot to plot the result. What does f(n)—which is the “average number of steps” of Euclid’s extended algorithm on input size n—look like? Note that size is not the same as value; inputs of size n are inputs with a binary representation of n bits. Document your experiment as a pdf and submit it, together with the Python 3 code, on Blackboard.
  • Assignment 2: Due on Monday October 10
    Write a program in Python which computes the ranks of all the pages in a given network of size N. Let the network be given as a 0-1 matrix, where a 1 in position (i,j) means that there is a link from page i to page j. Otherwise, there is a 0 in that position. Use the page rank formula that we saw in class to compute the page rank, starting with a value of 1/N. You should stop when all values have converged — does this algorithm always terminate? Also, keep track of all the values as fractions a/b, where gcd(a,b)=1 (so you will have to implement some basic fraction operations).
  • Assignment 3: Due on Monday October 24
    Problem 2.14 in the textbook.
  • Assignment 4: Due on Monday November 7
    Problem 3.8 in the textbook, but here is a more precise description of what is required. Essentially, you have to produce the description of the stack of Savitch’s algorithm as it executes the search of the path on an 2^nx2^n complete grid (so n is the only input). For example, consider the 4×4 grid graph that was discussed in Assignment 3, where s=1, and t=16 (i.e., s is the node in the upper-left corner, and t is the node in the lower-right corner). Here are the first few steps of the output we want:

    R(1,16,4)
---------
R(1,1,3)
R(1,16,3)
R(1,16,4)
---------
T
R(1,16,3)
R(1,16,4)
---------
R(1,16,3)
R(1,16,4)
---------
R(1,1,2)
R(1,16,2)
R(1,16,3)
R(1,16,4)
---------
...
---------
T
  • Assignment 5: Due on Monday November 21
    Problem 4.23 in the textbook: given a set of activities, each described by a tripe (start, finish, profit), your program should output the most profitable schedule. For example, given

    (0,3,20),(2,6,30),(3,6,20),(2,10,30)

    your program should output {1,3} which is the most profitable schedule consisting of activities 1 and 3 and total profit 40.

  • Assignment 6: Due on Monday December 5
    Consider the ciphertext given here. Your mission is to decrypt this text; here is some context that should help you in this task (it is reasonable to assume that the “adversary”, which is you, is aware of the context):

    The corresponding plaintext is an ASCII text; in fact, a chapter from a book — classical literature. I used the command:

    xxd -b plain.txt

    to obtain a binary “dump” of the file. That is, each ASCII character (including “space” and “newline”) is now encoded as an 8-bit byte, where each byte encodes the standard ASCII number of the corresponding character.

    I applied an “8-bit long one-time pad key” to obtain cipher.txt; that is, each group of 8-bits was “xored” with the same 8-bit long key k. Of course, this is a very flimsy “recycled one-time pad encryption scheme,” and hopefully one that you can break.

    For this assignment, your group is to submit the corresponding plain.txt