Computer Science CSC 199

This is the main webpage for the second half of CSC 199.

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.

Announcements

• Monday 21 February 2000:
  
  • We are back to the old meeting schedule. Tuesday 3-5 in WB144, Tutorial Thursday 3-4 WB144

General Information

Course Project

1. Investigate an interesting, current area in computer science. So you must pick an interesting topic, have a set of basic questions you want answered. Determine where to find relevent information.
2. Be able to present the area to your classmates in an interesting, complete way in 50 minutes (leave some time for questions). Please let me know if you need any special materials for your presentation.
3. Identify the key good (if not great) ideas in your topic.
4. Be able to answer questions about the area (we will not be testing you, you will make us interested in your topic and so we will naturally have some questions). You should anticipate some of these as well.
5. Write up your research and present copies to the class. Include references (both web and otherwise).
6. Include a set of 3-5 questions (small assignment) to drive home particularly relevent points.

• Theoretical computer science
  NP Completeness and Games magazine
  Why is RushHour difficult? (about complexity and relationships between problems) Upper and lower bounds.
  Zero knowledge proofs
  Randomized algorithms (how does flipping coins help you compute faster).
  Online algorithms (how well can you compute when you dont know the future input)?
  Algorithmic techniques (such as greedy algorithms, dynamic programming etc.).
• Other areas
  Computational geometry.
  What is a neural network?
  Computational biology (what is the human genome project?).
• Technology
  Wireless and the future?
  Java and Jini, what it means and how it will affect us.
  Combination of present ideas/trends and how they will affect our future (a day in the life of a person in year 2005).
  How web applications work (ie CGI, servlets, asp/jsp)? HTML, XML
• Law and technology and security
  Public key cryptography
  Hacking
  Scams/Schemes/Illegal uses of the web
  Legislation of what goes on in the web. Ie. quebec guy has consulting co required to advertise on web in english.
  Privacy and the information age (credit cards and how much is known about you and how can it be used to improve your life). What is the dark side and what should be done about it?
• People and Technology
  Does computers make our lives better? Earning a degree online, will it work? Do computers lead to stress in our lives. How stressfull is a programming job? Is computers/humans a natural fit?

Each project should include (covered both in class and in the writeup):
An introduction to the area
    What it is, including the basic ideas behind it and the good/great ideas behind it.
    Why it is interesting/relevent
What the present day impact is
What is the probable immediate/longterm future impact

A bibliography (set of references for the material presented) so that we can further our
education. Hypertext links are allowed here! Include some non-hypertext links.

Some short questions to drive home the ideas presented.

Dates and who is presenting

A list of people and their topics

Michael - Neural Networks

• What are they
• What they do (why do we need them)
• Applications
• What they cant do
• Do they work?

Naoyuki - Computer Viruses

• Legal aspects
• How do we detect them
• What effect they have
• How do they work (email macro virus, trojan horse)
• Famous Virus
• types of viruses

Sadeer - CGI

• What is it
• How does it work
• How web applications work
• future of CGI scripting
• security (is it secure, 128 bit encryption etc)
• Different back end languages, JSP, ASP
• internet commerce

Jason - Wireless and the Future

• cellphones, effect on society
• security
• analog vs digital, range
• PDAs and wireless
• GPS how it works and collaboration with wireless
• health aspects
• Effect of having fulltime wireless connectivity, social as well as neat applications
• You may want to look into the bluettooth initiative (including 3COM etc.)

Negar - Hacking

• What is it, different types of attacks, spoofing, spamming, denial of service, breakins (there is lots here)
• Preventing hackers attacks
• Hacking in the news
• Legal aspect

Ruslana - XML

Yan - Computer Games

Richard - Zero Knowledge proofs

Lectures and Tutorials

• Meeting places/times. We now meet on Tuesday 3-5pm in WB144 and Tutorial Thursday at 3 in WB144.

Course Handouts

Problem Sets

• Due in tutorial Thursday Feb 24:
  We discussed the problem of dealing a deck of cards fairly over the web and talked about applying cryptographic techniques to this problem. We came up with a partial scheme, but claimed that there were some significant problems with the scheme. Your task is to identify a few of these potential difficulties and suggest a solution. The difficulties can come from some obvious new requirements that were not yet considered or from holes in the proposed solution with respect to the originally defined requirements.
  
  One example brought up in class was that we could not re-use numbers we sent to the other player. The solution was to encode a number (say 7) by the difference between 2 other numbers (one of which is chosen randomly). For example 2399984-2399977=7, so the message wee send across is the encoded version of the string 2399984-2399977 (instead of 7).
• Due in Tutorial Thursday Mar 2:
  Write an algorithm which when given a polygon P=p1,p2,p3,...,pn (as the sequence of its edge vertices) and a point x in the plane, determines if x is inside P or not.
• Due in Tutorial Thursday Mar 9:
  Show that Distinct is in P while Partition is in NP.
  
  Distinct:
  Input: a1,...,an natural numbers
  Output: Yes if all of the numbers are different, no otherwise
  
  
  Partition:
  Input: w1,...,wn natural numbers
  Output: Yes if you can place some of the weights on one side of a balance and the reamining on the other side of the balance scale and have the scale balance. No otherwise
  
• Due in Tutorial Thursday Mar 16:
  
  1. Using the mapping I defined in class take the following 3SAT problem and produce the associated clique problem (we will call the clique problem (G,k))
     C= ( x1 or (not x3) or x5) and (x2 or (not x1) or x4) and ((not x1)or (not x3) or (not x5))
  2. Find a truth value assignment which makes the above formulae true. Then find an associated clique of size 3 in G
  3. Find a clique of size 3 in G and use this to find an associated truth value assignment which satisfies the above formulae