COMP 6901 -- Applied Algorithms, Fall 2016
- 1/12/2016 The deadline for submitting the project has been extended till Saturday Dec 3rd, 7pm, same as assingment 4, to allow groups presenting today to incorporate my feedback during the presentations. Make sure you give yourself enough time to do the assignment.
- 28/11/2016 Schedule of presentations:
Tuesday Nov 29
Adebayo Adeoya, Minhaj Shunjaruff, Nnamdi Ozah: Singular Value Decomposition
Mahesh Gupta, Maulik Rawal and Ajay Vijayakumar: Interval scheduling
Alaa Zaid Alhowaide, Majid Beheshti Mohtasham: Pattern matching on compressed text
Faramarz Dorani, Mehrzad Almasi and Ghassemi Alaee Khangha: Sequence alignment
Bina Javed, Oscar Lozano Perez: Min cut on small world networks
David Gilbert: Extended traversable region
Thursday Dec 1
Karoliina Oksanen: Approx mathing in DNA
Zhenxin Zhao: Automatic symbolic analysis
M. Ozair Shafiq: Line of sight
Jennifer Hendler: MST with repeated patterns
Farhad Kazemi: Image segmentation
Navid Shekoufa, Yasaman Bahrami Samani: Elogistics
Yubin Li, Huizhong Liu: Organic chemistry
Osarobo Ogbeide, Sanusi Musa: Primality testing
Samson Ugwuodo, Frieda Musa, Stanley Godfrey: Growing degree day
- 27/11/2016 Test results are now available on D2L. The average was 76.7, median 81.65. If you have any questions, please come see me in the office hour on Tuesday.
- 26/11/2016 I have at least 9 groups scheduled for Thursday Dec 1st by now, which will likely extend the class well past 5pm. So if you have not emailed me yet, I will schedule you for Tuesday -- please let me know if this does not work at all for you! Also, if you emailed me, and did not hear back, please email me again (and forward previous message); the email system has been a bit unreliable recently.
- 24/11/2016 The deadline for assignment 4 has been postponed till 7pm on Saturday, Dec 3rd, as discussed in class. The projects are still due on Friday, Dec 2nd.
- 23/11/2016 Project presentations: We have 15 groups, and thus 15 talks. Talks will be on either Nov 29th or Dec 1st. Each talk is 10 minutes; there, you will describe the outcome of your projects. In order to schedule the talks, please email me whether you would like to talk on Nov 29th or Dec 1st. If one of the dates proves to be more popular, I will schedule the first 8 groups that contact me with that preference on that date, and the rest on the other. The slides are due at 2pm on the day of your talk on D2L.
- 23/11/2016 There have been groups created on D2L for your project presentations and project slides. Please double-check that you are in the correct group! You will be submitting both your project slides and the actual project as a group.
Lectures: 15:30-16:45pm Tuesday/Thursday in EN-1051
- 21/11/2016 Reminder: test is tomorrow, in our usual class time. Please come and see me in the office hours tomorrow, 12-2pm, if you have any questions. If you cannot make this time, please email me and we'll arrange something; also email me if you have any questions.
- 21/11/2016 Assignment 3 has been marked. Please check your feedback on D2L. And email me and/or come to see me in the office hours tomorrow if you have any questions/concerns!
- 17/11/2016 Assignment 4 is now posted, with its LaTeX source. Due at 7pm on November 29th.
- 15/11/2016 Reminder: next lecture is a review for the test; the test itself is next Tuesday, Nov 22nd. Here is a study guide for the test.
- 15/11/2016 As discussed in class, assignment 3 is now due at 12pm (noon) tomorrow, Wednesday Nov 16th.
- 14/11/2016 Reminder: I have office hours tomorrow from 12pm to 2pm. If you have any questions about your assignment, please email me or come to see me in the office hours!
- 14/11/2016 Clarification on question 4c: given what you have computed in part 4a, you need to explain (give an algorithm) how to return an actual list of "course i is assigned to instructor j" pairings.
- 3/11/2016 A correction in question 3 of assignment 3: in the first two lines, it should be max weight independent set, rather than max size. That is, the goal is to find a set S of vertices such that sum of weights of vertices in S is maximal, and no two vertices in S are connected by an edge. Updated assignment is now posted.
- 1/11/2016 Assignment 3 is now posted, with its LaTeX source. Due at 7pm on November 15th.
- 26/10/2016 Clarification for assignment 2 question 2: you can assume that the houses are given in order from the start of the road. For 2b, the structure of your proof would be very similar to the proof of Kruskal's algorithm correctness.
- 25/10/2016 Clarification for assignment 2 questions 1b and 1c: your algorithms should actually produce the new connection scheme, if they decide to go with the offer (1b) or rebuild a link elsewhere (1c).
- 18/10/2016 Project proposal presentations will be on Thursday, Oct 20th and on Tuesday, Oct 25th. If you'd like to present on Thursday, please upload your slide on D2L by 2pm on Thursday, Oct 20th (see a template and an example .) Otherwise, upload your slide by 2pm on Tuesday, Oct 25th. You will have about 2-3 minutes for the presentation.
- 18/10/2016 Assignment 2 is now posted, with its LaTeX source. Due at 7pm on October 27 on D2L.
- 18/10/2016 Here is a powerpoint template for your proposal presentation, and an example slide .
- 12/10/2016 I will have office hours tomorrow (Thursday) from 12pm to 2pm. Especially if you have not contacted me yet about your project, please make sure to come in the office hours and discuss your project ideas with me.
- 10/10/2016 A clarification on the project. Your task right now is to come up with:
And please email me with your ideas on the projects! The earlier you email me, the easier it is for me to give you feedback.
- A couple of other people who would work with you on the project.
- An algorithmic problem you plan to study. Stable matching, sorting, shortest path in graph, minimal spanning trees are examples we covered in class. It can be clustering, it can be graphics problems, etc, nearly anything of the form "data goes in, answer comes out", with one additional caveat that there should be some algorithm that solves the general problem already relatively efficiently (e.g., it has a quadratic or a cubic algorithm).
- For that problem, a restriction on the data. For example, for sorting it can be that input numbers only come from a certain small range, or are already nearly sorted. For graphs, there are plenty of restrictions to consider: bounded degree, bounded weights, positive weights, grid graphs, sparse graphs, acyclic graphs, trees... Some of them are not quite realistic: if you are talking about planning a route in a city, your graph is unlikely to be a tree. But bounded degree is certainly a realistic assumption for this scenario. And it should not be something already well-known: finding a shortest path in unweighted graphs is certainly easier than in weighted (BFS is faster than Dijkstra's algorithm), but there is nothing left to do for this example, as the answer is already in any textbook.
- 29/9/2016 By popular demand: even though your assignment should be submitted by 7pm on Tuesday, October 4th, I will keep submission open up to Thursday, October 6, 7pm. Since we will be going over assignments with the TA on Tuesday after 7pm, make sure that you submit at least a partial solution to each problem. The goal of the extension is for you to have a chance to improve your solutions if you wish to do so, not to postpone doing the assignment till Thursday.
Note also that I will be out of town from the night of Thursday October 4th until Sunday Oct 9, and might not be able to respond to your emails during this time.
- 29/9/2016 I will be in my office from 12:30pm on Thursday, Sep 29th, for an extra office hour.
- 27/9/2016 For a project: please work in groups up to 3 people. For each project, find an algorithmic problem which is already polynomial-time solvable. For that problem, come up with a realistic restriction on the data (i.e., give a scenario when such a restriction indeed occurs often in a real life situation). Choose a restriction that you think makes the problem easier, by either making some existing algorithms run faster (preferably), or allowing for a different kind of algorithm which solves the problem faster. The restriction should not be already published in the literature, and should not be trivial (e.g., a road graph that is a tree is unrealistic, and bubble sort working in linear time on almost-sorted input is already known, but similar kinds of restrictions for other problems might be a good choice).
For your proposal, you will need to give me a one-two paragraph description of the problem (mentioning existing algorithms and their running time) and restriction(s) on the data you are going to consider.
- 20/9/2016 Assignment 1 is now posted, with its LaTeX source. Due at 7pm on October 4th (upload it on D2L before that time).
- 16/9/2016 The first two lectures are now posted (see below).
- 16/9/2016 Several of you asked me for a reference to review background for the course. You could check study guides for courses on logic and on algorithms for a list of topics; I will also try to cover in class all the topics that many people did not remember according to the questionnaire.
- 13/9/2016 The next 5 lectures (Sep 15, 20, 22, 27 and 29) will go till 5:15pm, to make up for the class last week and for Oct 6th class I will miss.
- 13/9/2016 As decided in class, our office hours will be on Tuesdays, from 12 to 2pm (in my office).
- 25/8/2016 The first lecture is Tuesday, September 13th. That is, we will not have a lecture on September 8th (as I am out of town).
Kolokolova , email: [Your browser cannot view this email address]
, office ER-6033.
Instructor office hours: Tuesday 12-2pm
Textbook: There will be no official textbook for this course.
We will also use other materials such as research papers.
- 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
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%).
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.
Assignments will be posted here.
Please type up your submissions, preferably 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
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 .
- Lecture 1 (Sep 13): Introduction and Stable Matching Problem .
Also see: 2012 Nobel Prize in Economics for the Stable Matching problem.
- Lecture 2 (Sep 15): Stable Matching: algorithm correctness and analysis .
- Lecture 3 (Sep 20): Basic graph algorithms .
- Lecture 4 (Sep 23): DFS, topological sort, strongly connected components .
- Lecture 5 (Sep 27): Minimum spanning trees. Also, see the paper by Nesetril, Milkova, Nesetrilova on history of Boruvka's work and translation of his papers.
- Lecture 6 (Sep 29): Correctness of Kruskal's algorithm.
- Lecture 7 (Oct 4): Single-source shortest path with positive weights
- Lecture 8 (Oct 13): Bellman-Ford algorithm.
- Lecture 9 (Oct 18): Difference constraints.
- Lecture 10 (Oct 20): Dynamic programming: intro.
- Lecture 11 (Oct 25): Dynamic programming: longest common subsequence.
- Lecture 12 (Oct 27): Dynamic programming: all pairs shortest path (Floyd-Warshall algorithm).
- Lecture 13 (Nov 1): Network flows: Ford-Fulkerson algorithm, bipartite matching
- Lecture 14 (Nov 3): Network flows: Mincut/maxflow theorem, open pit mining appication.
- Lecture 15 (Nov 8): Network flows: survey design, circulations.
- Lecture 16 (Nov 10) Scheduling case study: dynamic programming
- Lecture 17 ((Nov 15) Scheduling case study: NP-hardness, knapsack, approximation algorithms.
- Lecture 18 (Nov 17) Review for the test