COMP 6901 -- Applied Algorithms, Fall 2016

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:
1. A couple of other people who would work with you on the project.
2. 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).
3. 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.
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.
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).

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.

Assignments

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.

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).

Assignment 1. (LaTeX source) Due at 7pm on October 4th, 2016.	Assignment 2. (LaTeX source) Due at 7pm on October 27, 2016.
Assignment 3. (LaTeX source) Due at 7pm on Nov 15, 2016.	Assignment 4. (LaTeX source) Due at 7pm on Nov 29, 2016.

COMP 6901 -- Applied Algorithms, Fall 2016

Announcements

Course information

Assignments

Lecture Notes