Instructor   /   TA

• Instructor:   Dr. Yusu Wang	TA:     Guoqiang Shu
  Office Hour:         MWF 10:30 - 11:00am      Room:                   DL 487     Phone:                   292-1309     Email:                   yusu at cse ...       URL  :                   www.cse.ohio-state.edu/~yusu/	Office Hours:           Tue 1--3pm    Room:                     DL274    Email:                     shug  at osu ...

  
  

   

Course Description

     
    This course introduces students to the design and analysis of computer algorithms. Various paradigms for algorithm design will be covered, such as divide-and-conquer, dynamic programming and greedy strategy. Several data structures will be introduced to help to design efficient algorithms. Different algorithm analysis techniques will be described. We will also apply these design and analysis techniques to develop efficient graph, numeric and geometric algorithms.

    This is a graduate level course. Undergrads interested in this class and with sufficient background please come and talk to me.

 
   

Textbook   /   Grading

•   Primary textbook: 

 Introduction to Algorithms by T. H. Cormen, C. E. Leiserson, R. Rivest and C. Stein.  MIT press / McGraw-Hill book company, 2001    

•   Reference book :

Algorithm Design by J. Kleinberg and E. Tardos. Addison-Wesley, 2005.

Algorithms by S. DasGupta, C. H. Papadimitriou and U. Vazirani, 2006.

•   Grading policy :

Assignments:   30%,    Midterm:   30%,    Final:   40%

   

Course Materials

• Schedule:
• High-level schedule PDF (tentative) 
• Midterm: Oct 24, 7-8:30pm, Location DL480. Final: Dec 4, 7:30 - 9:30 am, DL 0317.
• Oct. 12: class canceled.

• Lecture notes:
• Lec. 1 (ppt) : Introduction / course overview. Asymptotic complexity. (CLRS: Ch 1-3)
• Lec. 2-4/5 (ppt) : Divide-and-Conquer, Solving recurrences. (CLRS: Ch 3-4.3)
• Lec. 4.5 - 5.5 (ppt): Quick sort: deterministic and randomized version, indicator random variables. (CLRS: Ch 7)
• Lec. 5.5 - 6.5 (ppt): Lower bound for sorting. Selection algorithm. (CLRS: Ch 8.1, 9.1, 9.2)
• Lec. 6.5 - 7 (ppt1, ppt2): Basic data structures: Heap, priority queue, and binary search trees. (CLRS: Ch 6, 12.1 -- 12.3)
• Lec. 9 (ppt): Introduction to Dynamic programming technique. (CLRS: Ch 15)
• Lec. 10 - 11 (ppt, ppt): More examples to Dynamic programming technique. (CLRS: Ch 15)
• Lec. 12 (ppt): Greedy algorithm. (CLRS: Ch 16)
• Lec. 13-14 (ppt1, ppt2): Amortized analysis (aggregate and accounting methods), and Union-find data structure. (CLRS: Ch 17.1, 17.2, Ch 21.1 -- 21.3)
• Lec. 15-16 (ppt1, ppt2): Elementary graph algorithms: BFS, DFS, Topological sort. (CLRS: Ch 22.1-22.4)
• Lec. 17-18 (ppt): Minimum spanning tree : generic algorithm, Kruskals's alg, Prim's alg. (CLRS: Ch 23)
• Lec. 19 (ppt): Shortest path, properties of shortest path, Bellman-Ford algorithm. (CLRS: Ch 24)
• Lec. 20 (ppt): SSSP for DAGs, SSSP for graphs with non-negative weights (Dijkstra's algorithm). (CLRS: Ch 24)
• Lec. 21 (ppt): APSP (two methods). (CLRS: Ch 25.1, 25.2)

• Handouts / Homework:
• Pessimal Algorithm (pdf): interesting article opposite to what we learn
  
• Homework 1 (pdf): Due Oct. 5th (Friday) IN CLASS.
  
• Homework 2 (pdf): Due Oct. 15th (Monday) IN CLASS.
  
• Homework 3 (pdf): Due Oct. 24th (Wed) IN CLASS.
  
• Partial solution for Homework 1 (pdf).
  
• Fractional Knapsack problem solution (pdf).
  
• Homework 4 (pdf): Due Nov. 7 (Wed) IN CLASS.
  
• Homework 5 (pdf): Due Nov. 16 (Fri) IN CLASS.
  
• Homework 6 (pdf): Due Nov. 28 (Wed) IN CLASS.
  
• Homework 7 (pdf): You DO NOT NEED TO SUBMIT IT.
  

   

Announcements:

• The course news group is : cse.course.cse780. You need to subscribe to it.
  
• Oct. 12, 2007 class will be canceled.