CSC 373 Winter 10 Syllabus


This is a more of a "What's Happened" than a "What's Coming Up" syllabus. In particular, lectures more than a week in advance are subject to adjustment depending on the pace of the class. In the assigned reading, DPV indicates the main Dasgupta, Papadimitrou and Vazirani Algorithms text. KT stands for the optional Kleinberg and Tardos book.


Monday

Wednesday

Friday

Jan 4th 

Admin, Re-Introduction to Algos

Handouts

Reading

  • DPV Chapter 0 (Review)

Jan 6th 

Review of numbers & arithmetic; fast multiplication 

Handouts

Reading

  • DPV Sections 1-1.2 (Review), 2.1

Jan 8th 

Recurrence review, sorting 

Handouts

Reading

  • DPV Sections 2.2, 2.3

Jan 11th 

Sorting in linear time & Selection

Handouts

  • Continuing Lecture Notes 3

Reading

Jan 13th 

More Divide and Conquer -- Convex Hull 

Handouts

  • Parts of KT Section 4.1, 4.2

Reading

Jan 15th 

Intro to Greedy Algorithms 

Handouts

Reading

  • KT Section 4.1 (the part that is in your handout)

Jan 18th 

Greedy Algorithms for Scheduling.

Handouts


Reading

  • KT 4.2

Jan 20th 

Greedy Algorithms for Huffman Codes

Handouts

Reading

  • DPV Section 5.2

Jan 22nd

Greedy Algorithms on Graphs:

Minimum Spanning Trees 

Handouts

Reading

  • DVP Sections 4-4.5, 5-5.1

Jan 25th

Greedy Algorithm for the Fab4 Puzzle & Shortest Paths

Handouts

Reading


Jan 27th
Bellman-Ford algorithm for shortest paths
Recursion Trees
Memoization
Handouts

  • HW1 Due on Jan 28th!

Reading

  • DPV Section 4.6
  • KT Section handout

Jan 29th

All-pairs Shortest Paths

Handouts

Reading

  • DPV 6.6

Feb 1st
Allpairs Shortest Paths continued
Handouts
Reading

Feb 3rd
HW1/TT1 Review

Feb 5th 

Term Test 1

Feb 8th 

Dynamic Programming: LIS and Weighted Scheduling 


Handouts

Reading

  • DPV 6.2

Feb 10th 

Knapsack

Handouts


Reading

  • DPV 6.4

Feb 12th 

Dynamic Programming: Edit Distance, Combining Techniques

Handouts

Reading

  • DPV 6.3, KT 6.6-7 (Handout)

Reading Break!

Feb 22nd 

Network Flow -- Residual graph, augmenting paths 


Handouts

  • Handout on Network Flow from KT


Reading

  • Handout on Network Flow from KT


Feb 24th 

Network Flow -- Ford Fulkerson, Cuts 


Handouts

Reading

Francois Pitt's notes (only on Matching and Teaching Assigment)

Feb 26th 

March 3rd 

Network Flow -- Reductions 


Handouts

Reading

KT -- Image Segmentation

March 1st  

Network Flow -- Max Flow Min Cut Theorem, Running time of FF



Handouts

Reading

March 3rd

Linear Programming -- Introduction

HW2 Due March 4th!


Handouts


Reading

  • DPV 7.1


March 5th

Linear Programming -- Simplex


Handouts

Reading

  • DPV 7.6

March 8th 

Linear Programming -- Examples 


Handouts

March 10th 

Linear Programming -- More examples


Handouts

Reading

March 12th 

HW2/TT2 Review


March 15th 

March 17th 

NP-Hardness 


Handouts


Reading

  • DPV 8-8.2

March 19th 

Approximation Algorithms 


Handouts

Reading

  • DPV 9.2

March 22nd 

Dealing with NP-hardness: Special cases

Programming Project Due on March 23rd!


Handouts

Reading

March 24th 

Local Search 


Handouts

Reading

  • DPV 9.3

March 26th 

Local Search Continued 


Handouts

Reading

March 29th 

Speeding up search: Branch & Bound


Handouts

Reading

  • DPV 9.1

March 31st 

The Real World: Speeding up code 

HW3 is due April 1st


Handouts

Reading


April 2nd

  • NO CLASS