COMP 6783 -- Applied Algorithms, Winter 2013
- 24/4/2013 Test 2 marks posted on D2L.
- 19/4/2013 Please make sure you submit your project on D2L as well (just in case something happens with your wiki page). Please follow the instructions for the submission: submit the page as a text file, submit all other relevant files such as images you used, and in the comments make sure to write the name of your algorithm and put a link to your wiki page.
- 12/4/2013 OK, since you've asked for it: the deadline for the project is extended till 12pm (noon) on April 19th. After that date, projects will not be accepted. Also, I plan to be out of town (and away from email from the evening of Saturday, April 13th, to the morning of Wednesday, April 17th (longer if I again get stuck somewhere due to the weather).
- 12/4/2013 Note: your pages are "live" even if they are under your user space, and come up on the first page of google results when one enters the keywords. You might want to write the whole page elsewhere, and then copy it into your wiki page when it is ready to be displayed.
- 9/4/2013 Just to clarify one issue with the project: you have to edit a subpage under your username! . Not my template. And not the public page on the subject. If you do the latter, you will immediately see other people editing the page with you. If this is what you have done, you need to finish this page as quickly as possible, and, depending on the number of edits not done by you, you might have to start a different topic. Please, create the page with the name User:YourUserName/YourAlgorithm, as the instructions say!
- 7/4/2013 Instructions for the project: I have created a user page for the template of your algorithm page.
Essentially, do the following: 1) read some (at least 5) existing algorithm pages to get the general format (e.g., Floyd-Warshall algorithm page is nice). 2) create an account on Wikipedia (you don't have to use your real name) 3) read the tutorial 4) create a draft page as a user subpage 5) edit it (you might want to save a copy on your local system, just in case) 6) when ready, send me the link to this user page.
Let me know if you have any questions!
- 30/3/2013 A study guide for the second test is now posted.
- 22/3/2013 Assignment 3 is posted below. Due April 1st.
- 18/3/2013 The deadline for the project is tentatively set to be April 13th. (I still need to check the details with my deadline for submitting grades. )
- 17/3/2013 Note that you can refer to existing pages for background information rather than defining everything yourself. For example, if you mention Dijkstra's algorithm or wireless ad hoc network, just link to the corresponding wiki page.
- 17/3/2013 Courtesy of Dr. Chen, here are some possible topics from the
area of networks:
- Calculating ETX (expected transmission count metric): http://dl.acm.org/citation.cfm?id=939000. There is a very basic wiki page defining ETX, but with not much information about the algorithm (and with a link to an older paper).
- Calculating ETT (expected transmission time metric): http://dl.acm.org/citation.cfm?id=1023732
- Proactive source routing: http://www.cs.mun.ca/~yzchen/papers/globecom11.pdf
- 14/3/2013 A dropbox on D2L for project proposals is now available. Please submit your proposals by Wednesday, March 20th, 11:59pm. It could be just a short text file; please include the name of the problem, name or short description of the algorithm and references you are planning to use (at least one).
- 13/3/2013 With semester ending in less than a month, it's a good time to think about projects. Some of you already emailed me; I tried to reply to most of your emails today; if I didn't reply, please email me again!
The idea of the project would be to pick up an algorithm from any field of computer science, and write a wikipedia page for it. Pretty much any algorithm is OK, as long as there is no wiki page for it already. If you have taken or currently taking another computer science course (network, databases, bioinformatics, etc), you are welcome to use algorithms covered there. You can also look at conference papers for the best conferences in your area of choice; for algorithms, such conferences are SODA, STOC and FOCS; for networks SIGCOMM, Mobicom, SIGMOD/PODS for databases, SOGGRAPH graphics, etc...
Topics already taken:
Bioinformatics:
1) "RSMA Matching Algorithm for searching biological sequences"
Networks:
2) Shortest time on network transmission
3) Widest k-shortest path q-routing algorithm
Computer music:
4) Audio oracle algorithm.
- 4/3/2013 By popular demand, the date for the midterm test is now shifted to Monday, March 11th . Please make use of my office hours this week if you got any questions, and you are welcome to send me an email at any time!
- 4/3/2013 A study guide for the test is now posted.
- 4/3/2013 Reminder: today the class will be a review for the midterm test. The test itself will be this Wednesday, Mar 6th. I will have office hours tomorrow at 2pm, please make use of that time to ask questions; you are also always welcome to email me your questions.
- 01/3/2013 My flight coming into St. John's got canceled, so I don't know when I will arrive, sorry. It definitely will not happen in the morning, unfortunately. So if you have any questions about the assignment, please email me, and I will try to answer them when I am not on a plane.
- 28/3/2013 Clarification for question 3: the notation $P[0...k-2]\bar{p_k}$ means the first k-1 symbols of the pattern, followed by the complement of the kth element of the pattern. So if your pattern is 011110, and your k=4, then $P[0...k-2]\bar{p_k}$ is 0110.
- 25/2/2013 By popular demand, assignment 2 is now due on Friday, March 1st, at 11:30pm. This will give you a chance to email me if you have any questions or even catch me at the department on Friday (I should be back by then, weather permitting. Since this is a second extension, for every hour your assignment is late you will lose 10 points.
- 13/2/2013 Assignment 2 now due on Wednesday, Feb 27th.
- 11/2/2013 Assignment 2 is now posted.
- The assignment 1 is now due at 12 on Thursday. Use D2L system to submit it.
- If you would like to insert a picture into your latex file, the easiest way would be to save the picture as a .pdf, and include it with \includegraphics command. You need to add includegraphics to the list of packages in the \usepackage{...} area at the start of your file, too. Please let me know if you have any questions!
- 30/1/2013 By popular demand, the assignment 1 due date is now shifted to Wednesday, February 6th. I will have office hours on Monday (4-5pm) and Tuesday (2-3pm).
- New version of assignment 1 is now posted. The last problem is different; the rest are the same. Please make sure you solve this new version!
- 27/1/2013 Notes for Lecture 3 and on Kruskal's algorithm are now posted. I am still working on the notes for the other lectures. There are notes on greedy algorithms available under the previous year notes link; please refer to them when doing your assignment. The material from lectures 4, 5 and Dijkstra's algorithm part of lecture 6 is available in any algorithms textbook or online resources; please use them for now. I will post notes as soon as I can.
- 23/1/2013 Assignment 1 is now posted below
- 16/1/2013 Office hours this semester will be Mon 4pm, Tue 2pm and
Thur 12pm.
- 13/1/2013 Reminder: tomorrow (January 14th) we are already on the new schedule. The class will be at 7pm in EN-1054.
- 10/1/2013 The time change is now official. The lectures will be 7pm-8:15pm on Mondays and Wednesdays in EN-1054. Technically, we should still have the 11am lecture tomorrow (otherwise we miss an hour), but I doubt that the university will be open with the weather forecast the way it is. Please confirm this in the morning, though.
- 9/1/2013 The lecture notes for lecture 2 are now posted below. You can also read about this topic in Kleinberg/Tardos book.
- 9/1/2013 The new proposed times are Mondays and Wednesdays 7pm to 8:30pm (actually to 8:15 pm). The times have not been approved by the department yet, nor a room assigned. So until then, we will be meeting at the original time, M/W/F 11am. In particular, the next lecture (weather permitting) will be Friday 11am. I will post any news here as soon as I hear anything.
- 7/1/2013 The lecture notes for the first lecture are now posted below
- 7/1/2013 Seems that some people do not agree with the new time slot; we will discuss it again on Wednesday, 11am in the lecture. (I need every single person registered to the class to agree to the time change in order to even start the process of moving the class).
- 4/1/2013 The enrollment cap for the course has been increased; please email me if you are still trying to register and cannot get through.
- 12/12/2012 The first lecture is Monday, Jan 7th, at 11am in EN-1002. Please email me as soon as possible if you cannot make that time slot! We will be discussing moving the class to a different time during the first lecture.
Lectures: 7pm-8:15pm Monday/Wednesday in EN-1054 ( Note the new time and room! )
Instructor: Antonina
Kolokolova , email: [Your browser cannot view this email address]
, office ER-6033.
Instructor office hours: TBA
Textbook: There will be no official textbook for this course.
Reference book:
- J. Kleinberg, E. Tardos. Algorithm Design.
- Thomas H. Cormen , Charles E. Leiserson, Ronald L. Rivest, Clifford
Stein. Introduction to Algorithms.
- Michael Soltys: An introduction to the analysis of algorithms
We will also use other materials such as research papers.
Marking scheme: TBA (tentative!):
3 assignments 15% each, two tests 20% each, and a 15% project.
Description:
The goal of this course is to study both classical and advanced algorithm design techniques with emphasis on real-world applications. We will cover greedy algorithms, dynamic programming, backtracking as well as fast Fourier transform, etc. The applications would come from many fields, including Bioinformatics and Cryptogaphy. Time permitting, we will consider randomized, parallel and distributed algorithms, and/or streaming algorithms.
Please type up your submissions (including scans of handwritten illustrations, e.g. graphs, is OK). For typesetting I would strongly encourage you to use LaTeX (I will be posting the .tex sources for the assignments). A quick (although outdated) introduction to LaTeX is
"Essential LaTeX" .
Tentatively, we will be using MUN D2L system for submissions.
Policy on collaboration: The work you submit must
be your own. You may discuss problems from assignments with each
other; however, you should prepare written solutions alone.
Plagiarism is a serious academic offense and will be dealt with
accordingly.
When in doubt, check
How to avoid plagiarism (especially relevant for your projects).
I will be posting lecture notes here as we go along.
For now, please see lecture notes from the previous run of this course .
A brief list of topics for the second test (review sheet).
A brief list of topics for the midterm test (review sheet).