Computer Science CSC 366:
"The Theory of (Efficient) Computation"
St. George Campus -- Sections L0101 and L0102
Spring Term 2000

This is the main webpage for CSC 366S. It contains information on both sections (L0101 and L0102 of the course.

This page contains copies of all the important documents for the course. To retrieve a document, simply click on the corresponding link (if there is no link, the document is not available yet). To send me e-mail (for suggestions, comments, questions, etc.), click on my e-mail address at the bottom of the page.

Note that extra copies of all course handouts (including problem sets) will always be kept in envelopes by the door of the instructor's offices.

NOTE: Many of the following documents are in PostScript format. You can get "ghostview", a program to view and print PostScript files, by clicking here.

Announcements

• Tuesday 18 April 2000:
  
  • Unofficial marks now appear on the web page.
• Monday 10 April 2000:
  
  • Some PS6 solutions are now posted.
• Sunday 9 April 2000:
  
  • It would be a mistake to not study a particular part of the course because of a rumor that it would not appear on the final. This applies to computability as well as any other sections of the course.
  • Thanks to Ying and Zongpeng, your marks for t6 are now available. Please pick up all your tests and quizzes from sf1101 tomorrow.
• Saturday 8 April 2000:
  
  • Test 6 solutions for both sections are on the web (with minor corrections to yesterdays section 1 solutions (typos etc.))
  • Test 5 Marking scheme is on the web.
• Friday 7 April 2000:
  
  • Test 6 solutions are on the web (section 1 only)
• Tuesday 4 April 2000:
  
  • Lots of marks have been posted to the web page! Check yours!
  • There will be office hours on Sunday 1-5 in SF3207. If too many people show up there, then Alan will put a note on the door and move the office hours to another room. There will be a question and answer session on Monday 9-1 (Pitt) and 1-5 (Rosenbloom) in SF1101.
• Tuesday 4 April 2000:
  
  • There will be an all day review session given by TAs on Monday April 10 in SF 1101 9-12, 1-5.
  • Problem set 6 is available on the web, but you got copies of this in class.
  • I have posted an old 364 exam (reviewed in class) to the problem sets section of this page.
  • Thursday we will have a review class (L0101).
  • Test 5 marking should be done by tomorrow. You will be able to pick this and other things up from my office.
• Monday 3 April 2000:
  
  • Marks, and solutions for Tests 1-5 are all available on the web page. Not all marks are in for test 5 yet.
  • Come by and pick up your tests, quizzes in my office if you are around today.
• Wednesday 29 March 2000:
  
  • Check out your latest marks as well as solutions to tests and marking schemes.
• Monday 27 March 2000:
  
  • There will be a quiz in tutorial this week covering basic definitions and theorem statements etc. for the computability section of the course.
• Wednesday 22 March 2000:
  
  • You can now find partial solutions to a5 on this web page
  • Section 1 will have a test on Friday at 1
  • Mike Hutton from Altera will be giving a guest lecture Friday 3-4 in SF1105. The abstract appears below, you are all encouraged to attend
    
    

    Hard Problems and Heuristic Algorithms in CAD

    Though it sometimes seems that NP complete problems are outside the realm of problems solved every day by computer scientists, this is not the case for many disciplines, notably computer-aided design. CAD solves the problem of implementing or compiling a hardware designers high-level hardware description languages into gates and wires for implementation on a computer chip. The entire software flow of CAD is filled with NP-hard graph and combinatorial problems that are both challenging and interesting.
    
    Algorithm designers in CAD apply the theoretical knowledge from algorithms and data-structures to solve these practical problems. This can involve using well-known deterministic algorithms such as network flows as approximate or heuristic solutions to a problem, or devising an entirely new algorithm. Randomized algorithms are sometimes used to lower the worst-case of a problem. And just as we are using heuristics to solve provably hard problems, we often find that the well-known "easy" problems are not that easy after all, because their polytime algorithms are too difficult to implement, take too long in practice or don't deal well with special cases. In order to do any of this, a strong grasp of algorithmic fundamentals is crucial to avoid months of wasted effort on a problem by taking an inefficient approach.
    
    This talk will overview some of these issues with examples of several different problems in CAD which and how they are solved in practice.
• Monday 20 March 2000:
  
  • You can find quiz 5 marks on the web page as well as test 4 solutions and marking scheme
  • Attendence in tutorials has been low. I realize that you have a lot of work (you have an OS project due soon) but the best and easiest way to learn is to do it slowly and continuously. This tutorial will be the last one on NP, NP-Completeness. Those who attend will probably add considerably to their understanding and allow their brain to grow before the test. If there is any additional reason that attendence is not great, please let me know.
  • I still have lots of copies of Assignment 5 on my door, grab them if you need them.
  • The TAs will be scheduling some all day office hours before the final exam. Please check your schedule and have some dates in mind.
• Friday 17 March 2000:
  
  • Test 5 will take place in class on Thursday (section 2) and Friday (Section 1).
  • Test 4 marking scheme and solutions are available.
  • Professor Pitt has written up some notes about the reduction from SubsetSum to Partition as well as Clique to 1/2Clique. You can find them in the Lecture notes for week 10. By the way, more lecture notes are available online.
  • How do I know if I know?
    

    Worth	Ability	What should I do to prepare
    1/5	Knowing the definitions, theorem statements, procedures	Memorize the statements
    2/5	Simple applications of definitions and theorem statements, procedures	Make up simple questions, examples and apply the definition, theorem statement, proof technique (ie for 1/2Clique, to better understand the proof, do an example)
    3/5	Understanding the reasoning behind the theorem statements, the intuition behind definitions, why procedures do what they do	Explain the concepts to someone, come up with a short english summary statement which captures the main idea
    4/5	Complex applications of ideas (ie given a problem can you combine ideas to solve the problem)	Do problem sets, come up with your own problems, ask each other questions.
    5/5	Good Problem solving ability (able to approach a problem, make an attempt, learn from it etc.)	Do lots of problems, think about things.

    Remember a couple of things, learning is a physical process. You have to give your brain a chance to grow to understand the ideas, to add new abilities to yourself. This takes time, both for practise and for growth. Start early and give your brain a chance to adapt. Starting late is like training for a marathon the day before the race. Finally, the goal is always to add new abilities and understanding to yourself. The symbols on the paper is not the goal, it is evidence of your success at the goal.
  • About tests etc. Your job is to show the TA that you understand. Simplicity is the mark of truth (I believe it is also the mark of understanding). Keep things short and simple. They can not tell what you are thinking, they can only see what you are writing.
  • Symbols in mathematics have meaning. This is important, the symbols give you a concise way to describe a proof. For example: Consider the question, Do you know the Canadian National Anthem?, if you answeer, yes of course, here it is

    Oh say, can you see Canada?  Our home and native land?
    We hail true patriot love in all they sons.  
    Command, with glowing hearts!   
    We see thee rise o'r the ramparts!
    The true north strong and free -- the bombs bursting in air!
    From far and wide, oh Canada, we gave proof through the night.
    We stand on guard for thee!
    Oh say God, keep our land glorious and free.
    Oh canada, by the dawn's early light we stand on guard for thee.
    Oh canada, by the dawn's early light we stand on guard for thee!
    

    This is not correct, the words are the same, but there is clearly different meaning (Thanks Diane for your example!!).
  • Tutorials are for you to ask questions, get answers, interact, check if your ideas are correct, argue your intuition. Please take advantage of them. Your participation in the tutorial can only improve them. If you have a question, chances are someone else does also.
  • Work early, put problems into your head early so you can think about them without any paper in front of you.
  • Practise early
  • Learning is knowing what you know, knowing what you dont, figuring out how to cover the difference and then covering it. (My famous quote)
  • If you do something, something happens, if you do nothing nothing happens. (Yet another famous quote)
  • In retrospect, I saw the wizdom in it. (My last famous quote)
• Tuesday 14 March 2000:
  
  • As stated in tutorial, there will be some adjustment to Test 4 marks for the Wednesday section. I may want to see some of your assignments, so please bring them to class.
• Tuesday 14 March 2000:
  
  • You can find copies of assignment 5 on my door (sf2302a) as well as on the web page (see the 11 March note below).
  • The quiz is checking whether you remember problem definitions, theorem statements and the reduction function used in showing that Clique is NP-complete. For example, you should be able to state the following problems 3SAT, Clique, SubsetSum. You should be able to define NP-complete, polytime reducability (in both senses). You should be able to state theorems.
• Monday 13 March 2000:
  
  • You can find a handout detailing why SubsetSum is NP-complete in the Lectures and Tutorials section below.
• Saturday 11 March 2000:
  
  • I have added a note from one of my friends. He outlines why NP-completeness is important for his companies well being. He gives some examples of NP-complete problems they want to solve etc. You can find this in RealWorld.txt
• Friday 10 March 2000:
  
  • Assignment 5 is now on the web page. You should be able to do questions 1a,1b, 2a,2b and 3a,3b currently.
  • Quiz 5 will again take place in tutorial, you should be able to apply the transformation function used in showing that Clique is NP-complete as well as know all definitions.
• Old Announcements : <HTML>

General Information

• Unofficial Current Course Marks. Note: The last 2 digits on the right is an adjusted mark!! ():
  Section L0101: <ASCII (plain text)>
  Section L0102: <ASCII (plain text)>

Lectures and Tutorials

• Outline of lecture topics: <ASCII (plain text)>
• NO tutorials during week 1...
  Lecture notes for week 1, section L0102: <ASCII (plain text)>
• Lecture notes for week 2, section L0102: <ASCII (plain text)>
• KruskalsMST algorithm and proof of correctness in ps or in pdf
• Dynamic Programming Handout ps or in pdf
• ALL-PAIRS-CHEAPEST-PATHS ps or in pdf
• Turing Machines ps or in pdf
• P, NP ps or in pdf Note These are not my lecture notes. There may be slight differences in presentation.
• A handout for the March 3 lecture showing that Clique is NP-Complete in ps or in pdf
• A handout showing that SubsetSum is NP-Complete in ps or in pdf

Course Handouts

• Course Information for Section L0101: <PostScript>
• Course Information for Section L0102: <PostScript>

Problem Sets

• Problem Set 1: <PostScript>
• Problem Set 2: <PostScript> Partial solutions available in ps or in pdf.
• Problem Set 3: in <ps> or <pdf> Problem set 3 solutions available on it's web page
• Problem Set 4: in <ps> or <pdf> Partial solutions available in ps or in pdf
• Problem Set 5: in <ps> or <pdf> Partial solutions available in ps or in pdf
• Problem Set 6: in <ps> or <pdf> Partial solutions available in ps or in pdf
• Fall 99 364 exam: in <ps> or <pdf>

Term Tests

• Test 1, section 1, solution in ps or pdf, Marking Scheme
• Test 1, section 2, solution in ps or pdf, Marking Scheme
• Test 2, section 1, solution in ps or pdf, Marking Scheme
• Test 2, section 2, solution in ps or pdf, Marking Scheme
• Test 3 Solutions, Marking Scheme
• Test 4, Solution in ps or pdf or Marking Scheme
• Test 5, Solutions, Marking Scheme
• Test 6, section 1, solution in ps or pdf,
• Test 6, section 2, solution in ps or pdf,

Course-Related Web Sites

• Spring 2000 CSC 364 home page.
• Spring 1999 CSC 366 home page.

Other Web Resources

• Real world examples of where NP-completeness and other topics of this course are important.