CSC373 Home Page (Winter 2013)


Please send any comments or questions to the instructor:


Announcements for week of May 6

I have calculated tentaive grades. I still must reread the exams of students who did not pass the course. In some cases, there are some missing assignments/tests that might make a difference so please check the CDF site for your grades. The exam had 150 points and was graded out of 130. As agreed, for those students (which is most of the class) who did better in the final exam than in term test 2, the grading scheme is to count term test 2 as 10% and the final as 45%. For students whose term test 2 was better than the final exam, the grading scheme will be the initial grading scheme counting term test 2 as 15% and the final exam as 40%. NOTE: Grades are not official until approved by the Faculty.

IMPORTANT: You must save all graded work in case there is any inconsistency in what we have recorded and what you have.

The slides are a reasonably accurate reflection of the course. The text reading assignments thus far (in more or less the order discussed) were the following : Chapter 0 (for motivation and to recall some basic notation and concepts); Chapter 5 (Greedy Algorithms); Chapter 6 (Dynamic Programming); Chapter 7 (sections 7.2 and 7.3); Chapter 8 (starting the week of February 4) Chapter 7 Section 7.1 (during week of March 4) Chapter 9 (for approximation algorithms and local search)


The following grading scheme will be used for this course: 3 assignments (worth 5% each), 3 term tests (closely related to the assignments and worth 15% each) and a final 3 hour exam worth 40%. (NOTE: See above comment as to the chnage in the gradin g scheme for those who did better in the final exam than in term test 2.) As will be discussed in class, every (sub) problem in any assignment or test will be worth some multiple of 5 points. You will receive 1/5 points for any (sub) problem for which you state "I do not know how to answer this question". You will receive .5/5 if you leave a question blank. If instead you submit irrelevant or erroneous answers you will lose the 1/5 points. That is, you will receive some credit for knowing what you don't know. You can also receive some additional credit for partial work that is clearly "on the right track". Even if the assignments are worth only 5% each, you are still obliged to submit your own work. I will give a pragmatic definition for distiguishing between genuine learning together and plagarism. If you have any questions please see the instructor immediately! Any cases of plagarism will be reported to the Faculty.


Schedule for assignments and term tests: Assignments are due at the start of the lecture held on the indicated date. I will answer questions about the assignments as soon as the assignments are submitted and hence I will not accept late assignments.
  • Assignments: February 1, March 1, April 1
  • Term Tests: February 4, March 4, April 3
  • IMPORTANT NOTE: I allow one page (double-sided) handwritten notes as an aid in all my tests and exams.

    Slides from lectures will be posted here. My slides are just an overview of the lectures and in particular they will usually not contain proofs.

    ACKNOWLEDGEMENT: Dai Tri Man Le has helped prepare these slides and the vast improvement over my rough slides from last year is due to him and is greatly appreciated.

  • Lecture 1 Outline Course introduction; start of greedy algorithms; interval scheduling
  • Lecture 2 Outline Two proof of optimlaity of EFT for interval scheduling; JISP problem
  • Lecture 3 Outline More on charging arguments; maximal matching algorithm for vertex cover; m-machine interval scheduling; interval colouring
  • Lecture 4 Outline Interval graphs; MIS and graph colouring; Kruskal and Prim's MST; Dijkstra least cost paths; Huffman coding; chordal graphs
  • Lecture 5 Outline Huffman coding reviewed; makespan problem; some general remarks on greedy algorithms
  • Lecture 6 Outline Start dynamic programming (DP); The weighted interval scheduling problem; the knapsack problem
  • Lecture 7 Outline An FPTAS for the knapsack problem; DP for least costs paths
  • Lecture 8 Outline All pairs least cost problem; chain matrix multiplication; edit distance; some concluding remarks on DP
  • Lecture 9 Outline Flow networks; Ford-Fulkerson
  • Lecture 10 Outline Augmenting paths; max flow-min cut theorem
  • Lecture 11 Outline Choosing augmenting paths; max flow applications
  • Lecture 12 Outline Proof of max flow-min cut theorem; Dinitz algorithm; metric labeling
  • Lecture 13 Outline Begin complexity theory
  • Lecture 14 Outline NP; the P vs NP hypothesis; polynomial time reduction ; NP completeness
  • Lecture 15 Outline Polynomial time transformation; some NP complete problems
  • Lecture 16 Outline Continued discussion of NP completeness; integer factorization;
  • Lecture 17 Outline More polynomial time transformations; Turing machine model
  • Lecture 18 Outline Cook's theorem
  • Lecture 19 Outline Interger programming (IP) and Linear Programming (LP); Rounding an LP
  • Lecture 20 Outline Continue LP relaxation and rounding; integrality gap; set cover; makespan problem for unrelated machines
  • Lecture 21 Outline Makespan continued; duality
  • Lecture 22 Outline Local search; max cut; exact max-2-sat
  • Lecture 23 Outline Continue exact max-2-sat; non-oblivious local search; local search for makespan; begin randomized algorithms
  • Lecture 24 Outline Probabilistic method; polynomial identities
  • Lecture 25 Outline Weighted max-sat problem; randomized rounding for max-sat and set cover
  • Lecture 26 Outline De-randomizing the naive randomized max-sat (Johnson's algorithm); set packing problem as an LIS problem
  • Lecture 27 Outline k-set packing; greedy and local search for MIS on k+1 clawfree graphs;
  • Lecture 28 Outline Chordal graphs; inductive k-independence graphs
  • Lecture 29 Outline Walksat algorithms
  • Lecture 30 Outline Primality testing
  • Problem Sets, Tests and Other Handouts will be posted here.

  • Problem set 1
  • Solutions for Q6 and Q7 of Problem set 1
  • Problem set 2
  • Solutions for Q3 and Q4a in Problem set 2
  • Problem set 3
  • Solutions for Q3, Q6 and Q8a in Problem set 3

  • Here are the
  • old lecture notes
  • that have been used previously in CSC364 and CSC366.

    You may also find it helpful to look at the problem sets and other handouts for the most recent versions of CSC373 and CSC375 that I have taught.

    And here is a link to the fall 2012 course taught by Professor Pitt.

    I am providing links here to Professor Allan Jepson's lecture notes and demos used in his Fall 2010 CSC373 class. Many of these documents are password protected. I will provide the password during the first week of lectures.

  • Greedy algorithms
  • Greedy graph algorithms
  • Dijkstra demo
  • flow networks
  • Ford Fulkerson demo
  • Applications of network flow
  • Local Search
  • Linear Programming