COMP 6901 -- Applied Algorithms, Fall 2014
- 9/12/2014 Grades for all coursework are now posted on D2L. If there is anything you find that is incorrect, please email me, and/or come to see me during the office hour (4pm today). I will be submitting the grades on Wednesday, so make sure to contact me today.
- 4/12/2014 To give more time to students involved in other course projects, the project is now due at 7pm on Saturday, Dec 6th (one day later).
- 4/12/2014 As a template for your project, you can use a standard LaTeX class such as "article" (that is, start your file with \documentclass{article}). For bibliography, put your references in a .bib file (Google Scholar is an excellent source for downloading references in BibTex format), and use \bibliographystyle{alpha} so that it is easier to see which paper you are referencing.
- 2/12/2014 Please make sure the latest version of your slides is available on D2L by 5pm (don't mind the "late submission" warnings. ) I will be using D2L to get them to the main computer.
- 26/11/2014 A hint for studying for the test, and a comment on assignments: please try to solve problems using the appropriate design techniques! That is, all problems in the last assignment were on network flows, so if you do not have a network flows solution, chances are something is amiss. This is even more true for dynamic programming, as there are steps outlined for the algorithm design. We studied these design techniques for a reason...
- 26/11/2014 The study guide for the test is now posted.
- 13/11/2014 Schedule for next several weeks:
- Next week, Nov 18 and 20, Lourdes Peña-Castillo will be teaching both lectures.
- On Monday Nov 24th I will have an office hour at 2:30pm. Assignment 4 is due Nov 24th at midnight, no extensions.
- On Tuesday Nov 25th we have a review before the test. Prepare your questions about the assignments.
- The test is on Nov 27th. Covers all the material in the course (including sequence alignment lectures next week).
- Project presentation slides are due Sunday, Nov 30th at 7pm. Then I can give you feedback before your talk.
- Presentations are on Tuesday, Dec 2nd. We will start the class at 5:30pm. Each presentation is 15 minutes (including questions).
- Projects are due at 7pm on Friday, Dec 5th.
- 13/11/2014 The problem "forming committees" in assignment 4 has been changed. Please download new version of the assignment.
- 10/11/2014 Assignment 4 is now posted. Due Nov 24th at midnight. There will be no extensions.
- 5/11/2014 As discussed in last class, assignment 3 is now due on Monday, by 23:59 (11:59pm).
- Assignment 3 is due Nov 10th, at midnight.
- Assignment 3 is now posted. Due Nov 6th.
- 21/10/2014 Assignment 2 is now due 7pm on Friday Oct 24th. Submit your LaTeX-typeset .pdf in the dropbox; you do not need to submit a hardcopy.
- 17/10/2014 By popular demand, assignment 2 is now due two days later, on Oct 23rd.
- 15/10/2014 There is now a dropbox on D2L where you can put the slides -- just to make it easier for you (I know some of you emailed the slides to me already, that is another option). Please send your slides to me today, and I will make the combined files tomorrow morning.
- 13/10/2014 Project presentations are scheduled for this coming Thursday, October 16th. We will be starting the class earlier, at 6:30pm. Please email me the slides for your presentation by Wednesday evening!
- 13/10/2014 I have posted the feedback and grades for your project proposals. Some of you did not get the full grade, mainly because of omitting some parts of the proposal that I wanted to see, such as naming at least some algorithms or restrictions and generalizations of the problem. I understand that some of you might not have been aware about that. So I am opening the submission server again till Wednesday 7pm, to give you a chance to submit an updated proposal.
- 9/10/2014 Assignment 2 is now posted. Due Oct 21st.Submit the assignment on D2L , as a .pdf typeset in LaTeX; use the LaTeX source file as your starting point.
- 7/10/2014 By popular demand, the project presentations have been postponed till Oct 16th. Reminder: we will start the class at 6:30pm on that day to give more time for the presentations.
- 1/10/2014 The following project topics have been taken (that is, you emailed me and we decided on a topic):
- Traveling Salesman Problem (P.P.)
- Deadlock detection (S. A.)
- Satisfiability (S. R. )
- Primality testing (S. J.)
- String search (D. S.)
- Public-key crypto (S. A. )
- Hamiltonian Cycle (A. B.)
- Search engine optimization (S. Z.)
- Graph colouring (N. M.)
- n-queens (A. T)
- Multidimensional scaling (D. Z.)
- Image morphing (A.M.)
- String compression (D. N.)
- Clustering (L. R.)
- Planarity testing (A. K.)
If you emailed me, and your topic+initials are not in the list, please emal me again -- sorry if this happened!
- 29/9/2014 There will be no class this Thursday, Oct 2nd (I am out of town for the programming contest). As we discussed last class, to make up the time we will have an extra class period reserved during the last week of classes, for the course project presentations. The assignment is still due at 7pm on Thursday, but you only need to submit an electronic copy then. Also, as my flight is early morning, there will be no office hours on Thursday, either.
- 29/9/2014 By popular demand (and to make sure you have the time to typeset it in LaTeX), the assignment deadline is postponed till Thursday Oct 2nd, 7pm. You will need to submit your typeset .pdf on the D2L by that time. As we might not have a class that day, only submit the electronic version, no hard copy.
- 29/9/2014 Make sure you include your name in the file! The updated source file now includes a space for your name, though anywhere on the first page is good.
- 25/9/2014 Submissions for assignment 1 are now accepted on D2L . Make sure you submit an electronic copy (a LaTeX-typeset .pdf), in addition to bringing a hard copy to class.
- 24/9/2014 Assignment 1 problem 5 changed. The original problem was not what I intended it to be (and as stated, it was not solvable efficiently). Please download new assignment 1. The goal there is to design a linear-time algorithm for the task described.
- 16/9/2014 Assignment 1 is now posted. Due Sep 30th. Please use the LaTeX source file as your starting point. Submit the assignment on D2L .
- 16/9/2014 As we need more time for project presentations, the next two lectures will be back to the normal duration (ending at 8:15pm); however on October 9th we will start at 6:30pm. Please email me as soon as possible if you have a time conflict with this.
- 16/9/2014 For the project proposal, there will be three deadlines:
- by October 2nd, email me describing the problem which you will analyse for your project.
- by October 7th, submit on D2L a short (half a page) project proposal, describing the problem, restrictions you will be considering and some of the algorithms for this problem you will be comparing.
- On October 9th, everybody will give a 5-minute presentation on the proposal. Please send me your slides beforehand, preferably by October 8th.
- 4/9/2014 There will be no lecture on Thursday September 11th. To make up the time, the next four lectures will finish ~20 minutes later (at about 8:35pm).
- 4/9/2014 Office hours will be on Tuesdays and Thursdays, at 4pm, in my office (ER-6033).
- 1/9/2014 The first lecture is Thursday, September 4th. Please email me if you plan to take this course, but did not yet have a chance to register, or will be coming after the classes start.
Lectures: 7pm-8:15pm Tuesday/Thursday in EN-1051
Instructor: Antonina
Kolokolova , email: [Your browser cannot view this email address]
, office ER-6033.
Instructor office hours: Tuesdays and Thursdays 4-5pm.
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: (tentative!):
4 assignments 10% each, a test 25%, and a 35% project (includes project proposal 5%, project proposal presentation 5% and a final presentation 10%).
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 in LaTeX and submit the resulting .pdf. Use the source files provided as your starting point. Including scans of handwritten illustrations, e.g. graphs, into your LaTeX file is OK.
There is a number of LaTeX editors such as TeXMaker (if you have not used it before and are looking for user-friendliness), or a ShareLatex , which is an excellent online editor that I use to write papers with others. TeXWorks, which I use, comes preinstalled with many LaTeX distributions.
Please use MUN D2L system to submit your assignment.
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 .