Announcements

  • 8/28: (Assignment 1) Clarifying edits have been made throughout the assignment. Also, problem 2 has been modified slightly.
  • 9/3: (Assignment 1) Point totals for each problem are now specified. Clarifications were added to problem 5b.
  • 9/4: (Assignment 1) Problem 1a has been corrected.
  • 10/2: (Assignment 2) Assignment 2 is due on 10/17 (NOT 10/10 as orginally indicated on the pdf and Sakai).
  • 10/2: (Exam Review) There are practice exams here and here. Note that one of the questions has already been given for homework. The rest should be good practice. We are trying to get a room in the evening next week to do a review where we will go over answers to these practice exams.
  • 11/4 (Assignment 3) The input graph in problem 4 has been changed to be a directed graph instead of undirected.
  • 11/13 (Assignment 4) The due date for Assignment 4 has been extended to 11/26/2014.

    Administration

    Instructor:  Debmalya Panigrahi
    TAs:  Sam Haney, Nat Kell
    UTAs:  Ang Li, Wenshun Liu, Yilun Zhou, Roger Zou

    Times & Locations

    Lectures:Tue, Thu 3:05-4:20 pm in Physics 128
    Recitations:Fri 11:45 am-1:00 pm in Social Sciences 139

    Office Hours

    Panigrahi:Tue 4:45-5:30 pm, Thu 11-11:45 am in LSRC D203
    Haney:Mon 4:00-5:00 pm in North 306
    Kell:Wed 4:00-5:00 pm in North 306

    We will use Piazza for all correspondence and discussions related to the course. If you have a question about the course material or want to initiate a discussion, post it on Piazza allowing the entire class to view and participate in it. If you want to contact the course staff only, send a message via Piazza that is visible only to the relevant course staff.

    Overview

    Algorithms are a cornerstone of computational sciences and the need for efficient algorithms is ubiquitous in modern technology. However, the primary goals of algorithm design, the resources that need to be optimized, and even the model of computation varies widely between application areas. In this course, we will study some of the fundamental principles of algorithm design that appear in multiple areas and have had broad impact. In addition, we will focus on the mathematical tools that are frequently used in the theoretical analysis of algorithms, and study how such analysis, in turn, influences algorithm design. The course will be at an undergraduate level and will aim to serve the following objectives:

    • provide basic training in algorithm design for a future computer scientist and/or programmer, and
    • expose future professionals in other disciplines to fundamental algorithmic paradigms.

    Topics

    The following is a tentative list of topics to be covered.
    • Basics: history of algorithms, asymptotic and worst-case analysis, time and space as resources, recurrences
    • Design techniques: divide and conquer, dynamic programming and memoization, greedy algorithms
    • Graph algorithms: graph representations, graph traversal and applications, shortest path, minimum spanning tree, network flows and cuts
    • Computational geometry: convex hull
    • Data structures: binary search trees, height and weight balanced trees, amortization and potential functions, union-find
    • Randomized algorithms: Monte Carlo and Las Vegas algorithms, hashing, primality testing
    • Linear programming:simplex algorithms, duality
    • Intractability: lower bounds, easy and hard problems, NP-completeness, polynomial time reductions
    • Approximation algorithms: greedy algorithms, LP rounding, approximation schemes
    • Online algorithms: rent or buy, paging

    Prerequisites

    There are two hard prerequisites: COMPSCI 201 Data Structures and Algorithms and COMPSCI 230 Discrete Math for Computer Science, or equivalent courses. If you do not satisfy these prerequisites, please contact the instructor.

    Textbooks

    Lecture notes will be uploaded on the course website after every lecture. In addition, the following books cover most of the syllabus:

    [DPV] S. Dasgupta, C. Papadimitriou, and U. Vazirani, Algorithms, McGraw Hill, 2006.

    [KT] J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005.

    [CLRS] T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Introduction to Algorithms, MIT Press, 2009.

    Additional References

    [AHU] A. Aho, J. Hopcroft, and J. Ullman. Design and Analysis of Algorithms. Addison Wesley 1974.

    [Ed] H. Edelsbrunner. CPS230 Lecture Notes. Duke University, 2008.

    [Er] J. Erickson. CPS473G: Algorithms Lecture Notes. UIUC.

    [Ta] R. E. Tarjan. Data Structures and Network Algorithms. Society for Industrial Mathematics, 1987.

    Grading

    • Assignments (five): 30%
    • Midterm exams (two): 40%
    • Final exam: 30%
    • Both the midterms and the final exam will be in-class closed-book exams.

    Assignments

    • Review the detailed guidelines on collaboration. Any violation of these guidelines will be reported without exception to the relevant authority.
    • You are allowed one late homework submission, which may be turned in up to one week after the original deadline. All other late submissions will receive no credit.
    • We will use Sakai for homework submission.
    • The answer to each homework problem has to be typed. It is strongly encouraged that you prepare your homework submissions in LaTeX.
    • Answers to all problems on an assignment must be submitted by 11:59 pm EST on the due date.
    • Solutions will be available on Sakai after the late submission deadline.

    page top