CSCI 1570 - Design and Analysis of Algorithms

CSCI 1570 - Design and Analysis of Algorithm Instructors:  Claire Mathieu (claire at cs.brown.edu), CIT 555, x36066.
TAs: Al Urim is HTA and we're looking for two UTAs. Apply now!
Lecture Location and Time:  T,Th 10:30-11:50am, room TBA
Office hours:  TBA.

A single algorithmic improvement can have a greater impact on our ability to solve a problem than ten years of incremental improvements in CPU speed. In CS157, we study techniques for designing and analyzing algorithms.

  • What is CS157 all about? We study algorithms and data structures for a wide variety of problems in Computer Science.
  • Why study algorithms? The goal is to build a deep(er) understanding of fundamental algorithmic paradigms such as Divide and Conquer, Dynamic Programming, Greedy Approaches, and Approximation.
  • How are we going to do that? We emphasize rigor in our proofs of correctness and runtime.
  • Are there any prerequisites? The prerequisites are: ((CS16 or CS18) and CS22) (or equivalent). This is targeted to approximately junior undergraduates who have enjoyed basic data structures and algorithms and want to go beyond that, in particular the problem solving and rigorous analysis perspective.

    New textbook! Algorithms by Sanjoy Dasgupta, Christos Papadimitriou and Umesh Vazirani, McGraw Hill 2008, ISBN 978-0-07-352340-8. Copies have been ordered at the Brown bookstore. (Alternatively, students may try the following website, created by a Brown student, that supposedly makes it easy to search Amazon, Half.com, and Abebooks.com to find the lowest prices for textbooks.)

    Grades

    Homeworks(weight: .1), problem sets(weight: .2), 2 midterms(weight: .2 each), and final(weight: .3) form the basis of your final grade. The expectation is that the grades will be at least 1/3 A's, about 1/3 B's, and at most 1/3 C's.
    Homeworks: every other week, done individually
    Problem sets: every other week, discussed in 4-person groups, each student writes up solution of one problem so that together the group has given solutions to all problems. Meetings will be set up for those discussions.
    Midterm: in class, 2 hours.
    Final: at home.

    For the writeup of problem sets, the organization and the reasoning should be clear, ideally textbook quality: not just a correct solution, but the simplest and most elegant possible. For presentation, you will probably make your life easier if you use Latex but it's up to you. See here for help on Latex.

    Schedule

    Date Topic Chapter OUT IN SOL
    Th 1/22 Introduction 0      
    T 1/27 Arithmetic, Sorting 1.1,1.2 HW 1 & PS 1    
    Th 1/29 Sorting, lower bound 2      
    T 2/3 Randomized median 2   HW 1  
    Th 2/5 Strassen 2      
    T 2/10 FFT 2   PS 1  
    Th 2/12 Midterm 1   HW 2 & PS 2    
    T 2/17 No class        
    Th 2/19 Dijkstra 4      
    T 2/24 Priority queues. MST: Prim 4/5   HW 2  
    Th 2/26 MST: Kruskal 5      
    T 3/3 Union-Find 5 HW 3 & PS 3 PS 2  
    Th 3/5 Huffman 5      
    T 3/10 Longest increasing subsequence 6   HW 3  
    Th 3/12 Edit distance 6      
    T 3/17 All-pairs shortest paths 6   PS 3  
    Th 3/19 Midterm 2   HW 4 & PS 4    
    T 3/24 Spring recess        
    Th 3/26 Spring recess        
    T 3/31 Flows 7   HW 4  
    Th 4/2 Flows 7      
    T 4/7 Linear programming 7 HW 5 & PS 5 PS 4  
    Th 4/9 Linear programming 7      
    T 4/14 NP-completeness 8   HW 5  
    Th 4/16 Reductions 8      
    T 4/21 Approximation algorithms 9.2   PS 5  
    Th 4/23 Randomized algorithms?   Final?    
    T 4/28 Reading period (no class?)        
    Th 4/30 Reading period (no class?)     Final?