ECE 358 Winter 2013 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

Tuesday

Thursday

Jan 8th 

Admin, Re-Introduction to Algos

Handouts

Reading

  • DPV Chapter 0 (Review)

Jan 10th 

Review of numbers & arithmetic; fast multiplication 

Handouts

Reading

  • DPV Sections 1-1.2 (Review), 2.1

Jan 14th 

Recurrence review, sorting 

Handouts

Reading

  • DPV Sections 2.2, 2.3

Jan 15th 

Sorting in linear time & Selection

Handouts

  • Continuing Lecture Notes 3

Reading

Jan 17th 

More Divide and Conquer -- Review of heaps 

Handouts

Reading

Jan 21st 

More Divide and Conquer -- Convex Hull 

Handouts

  • Parts of KT Section 4.1, 4.2

Reading

Jan 22nd 

Intro to Greedy Algorithms 

Handouts

Reading

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

Jan 24th 

QUIZ1

Greedy Algorithms for Scheduling.

Handouts


Reading

  • KT 4.2

Jan 28th 

Greedy Algorithms for Huffman Codes

Handouts

Reading

  • DPV Section 5.2

Jan 29th

Greedy Algorithms on Graphs:

Minimum Spanning Trees 

Handouts

Reading

  • DVP Sections 4-4.5, 5-5.1

Jan 31st

Greedy Algorithm for the Fab4 Puzzle & Shortest Paths

Handouts

Reading

Feb 4th
Bellman-Ford algorithm for shortest paths
Recursion Trees
Memoization
Handouts

Reading

  • DPV Section 4.6
  • KT Section handout

Feb 5th

All-pairs Shortest Paths

HW1 Due February 6th!

Handouts

Reading

  • DPV 6.6

Feb 7th

QUIZ2

Allpairs Shortest Paths continued
Handouts
Reading

Feb 11th
Even more Shortest Paths

Feb 12th 

Dynamic Programming: LIS and Weighted Scheduling 


Handouts

Reading

  • DPV 6.2

Feb 14th 

Term Test 1

Reading Break!

Feb 25th 

Longest Common Subsequence

Handouts


Reading

  • DPV 6.3

Feb 26th 

Reduction: LCS -> LIS

Handouts

Reading

  • DPV 6.3, KT 6.6-7 (Handout)

Feb 28th 

QUIZ3

Network Flow -- Residual graph, augmenting paths 


Handouts

  • Handout on Network Flow from KT


Reading

  • Handout on Network Flow from KT

March 4th 

Network Flow -- Ford Fulkerson, Cuts 


Handouts

Reading

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

March 5th 

Network Flow -- Reductions 


Handouts

Reading

KT -- Image Segmentation

March 7th  

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



Handouts

Reading

March 11th

Linear Programming -- Introduction


Handouts


Reading

  • DPV 7.1

March 12th

Linear Programming -- Simplex


HW2 Due March 13th!

Handouts

Reading

  • DPV 7.6

March 14th 

QUIZ4

Linear Programming -- Examples 


Handouts

Reading

March 18th 

Linear Programming -- More examples


Handouts

Reading

March 19th 

HW2/TT2 Review

March 21st 

March 25th 

NP-Hardness 


Handouts


Reading

  • DPV 8-8.2

March 26th 

NP Hardness Continued  


Handouts

Reading

March 28th 

QUIZ5

Speeding up search: Branch & Bound


Handouts

Reading

  • DPV 9.1

April 1st 

Approximation Algorithms 


Handouts

Reading

  • DPV 9.2

April 2nd 

More Approximation Algorithms 


Programming Project Due on April 3rd!

Handouts

Reading

April 4th 

Dealing with NP-hardness: Special cases


Handouts

Reading

April 8th 

Local Search 


Handouts

Reading

  • DPV 9.3

April 9th 

HW3 Due April 10th!

Local Search Continued 


Handouts

Reading

April 11th

Review 

QUIZ6

April 15th

Review 

    HW3 Due April 15th!