Complexity of Algorithms (COMP202) Home Page (Winter/Spring 2012)

Lectures

Class lectures are held at the times and locations below:
   Mondays 2-3pm Ashton Lecture Theatre
   Thursdays 11am-12 Mathematical Sciences Building, Room 105
   Fridays 3-4pm Brodie Tower, Room 404

Tutorials/Practicals
Tutorials are held Tuesdays 12:30-2pm, starting on week two of the term.
They are held in the George Holt Building, Room 105.
Please bring your questions, concerns, and ideas to the practicals.
You can run the show (meaning this is the time for me to try to answer all your questions and clear up the mysteries).

Office Hours

Mondays 1-2pm (provisionally).

My office is room 319 in the Ashton Building. If you would like to see me outside of my office hours, please e-mail me and/or talk to me at the start/end of class to make such arrangements.


Lecture Notes

The online lecture notes provided here are given in PDF, in formats of one or four slides to a page. If you print the notes yourself, it is strongly recommended that you use the version with four slides to a page. PDF files require the Adobe Acrobat reader.

  1) Introductory Lectures   1 slide per page   4 slides per page
           Introductory problem sheet (problems we will consider)
  2) Lists, Binary Searching, and Search Trees   1 slide per page   4 slides per page
           Online AVL Tree demonstration (Java applet)
  3) Sorting (MergeSort, QuickSort, Radix sorting, etc.)   1 slide per page   4 slides per page
           Counting inversions (Java source code template)
           Counting inversions (my Java source code)
  Sample input   Sample output
           Pancake sorting (Java source code template)
           Pancake sorting (my Java source code)
  Sample input   Sample output
  4) Greedy Algorithms   1 slide per page   4 slides per page
  5) Divide-and-Conquer Algorithms   1 slide per page   4 slides per page
  6) Dynamic Programming   1 slide per page   4 slides per page
           {0,1} Knapsack problem (Java source code template)
           {0,1} Knapsack problem (my Java source code)
  Sample input   Sample output
  7) Some (Basic) Number Theory and the RSA Algorithm   1 slide per page   4 slides per page
           The Extended Euclidean algorithm (Java source code)
  8) A Review of Some Graph Theory and Dijkstra's Algorithm   1 slide per page   4 slides per page
  9) The Maximum Flow Problem   1 slide per page   4 slides per page
  10) NP-Completeness   1 slide per page   4 slides per page

Exercises/Assignments

Note:
  1. These exercises are not going to be collected for assessment. However it is very strongly recommended that you attempt each and every question as they serve to reinforce the material that is taught in the course, and they are a model of questions that could appear on the exams.
  2. The date following each assignment is the class date in which they were assigned. I intend to post the solution online to each exercise approximately one week after it is given in class.
  3. You should also understand that the solutions I provide need not be the only solutions and yours might be perfectly valid too. My solutions are only suggested as one approach.
  4. Please feel free to contact me if you think there is an error in one of my solutions. While I strive for correctness, it's possible that I slipped up somewhere.
  1) Asymptotic notation
  2) A question of some depth
  3) AVL trees
  4) Exercises on Sorting
  5) A Heap(ing) portion
  6) Greedy Algorithms
  7) Divide-and-conquer Algorithms
  8) Dynamic Programming
  9) The Euclidean algorithm and the RSA method
  10) Shortest paths and Dijkstra's Algorithm
  11) Max Flow/Min Cut

Possible links of interest

Here are some links which I think are worthwhile exploring. A few of them are links to classical examples that are used to describe an algorithmic paradigms or to illustrate somee solution method. And there are also a few that are just plain interesting (like Robozzle).

  1. The Secretary Problem    Also try here or here too.    (Note: This is essentially equivalent to the "Who Wants to be a Millionaire?" problem on the problem sheet that I gave out on the first day of class. Requires a bit of probability theory.)
  2. Monotone Sequences    (Also related to one of the problems on the sheet I gave out on the first day of class.)
  3. Creating Living Hardware Using Synthetic Biology A discussion of using DNA computing to solve the so-called "Burnt Pancake Problem". (Related to the Pancake Sorting Problem mentioned above under "Sorting".)
  4. The Monty Hall Dilemma    (Not an algorithmic question, but a rather famous problem inspired by an old American game show.)
  5. The Algorithmist Wiki homepage    (Advertised as "a resource dedicated to anything algorithms - from the practical realm, to the theoretical realm.")

Back to Russ's teaching home page

Back to Russ's home page

Valid XHTML 1.0 Strict
   Validate