CSCI 3110 - Summer 2019
Design and Analysis of Algorithms I
|
|
| Class: |
TR |
2:35-3:55 |
in DUNN 117 |
| Tutorial: |
F |
11:35-12:25 |
in DUNN 117 |
| Office Hours: |
R |
1:00-2:00 |
in CS 315 |
| |
|
and by appointment |
| |
|
|
|
| Office Hours: |
M |
11:00-12:00 |
in Learning Centre |
| |
|
starting May 27 |
| |
|
|
|
| |
|
|
|
|
|
|
|
Online Syllabus:
http://www.cs.dal.ca/~whidden/CSCI3110/syllabus.pdf
Notes:
- As a reminder, the final exam will be Saturday August 3rd from 1:00 PM to 4:00 PM in the Scotiabank Auditorium (Aud-1) in the Marion McCain Building. Tuesday July 30th was the last day of classes and there will be no other lectures or tutorials. Good luck on your finals.
- SRIs can now be completed online. You will also have an opportunity to fill them out in class for the first 10-15 minutes of class on Tuesday, July 23.
- The midterm solutions and marks are now posted and we'll go over the midterm solutions next class. As we discussed in class on Thursday, July 18, both design questions were confusing and the rule that incorrect solutions to those questions received 0 points meant that the majority of the class received 0 or otherwise low marks on the design questions. After a class discussion and vote, we decided to curve the midterm marks by adding 25 points to each midterm. The marks listed on brightspace already include this adjustment. The design questions on the final will be more clear and will be marked similarly to assignment questions rather than following the 0 rule. In addition, as per class policy, your final exam mark will still replace your midterm mark if it is higher.
- As a reminder, please send me an email if you have any specific topics or problems you'd like me to review in the Midterm Review on Tuesday July 2.
- Thanks to Norbert Zeh for covering the June 25 lecture.
- Thank you very much to Meng He for covering the June 18 lecture. Yuhan Fu (our TA) will continue with dynamic programming on June 20.
- Thursday evening I had an emergency appendix removal surgery. I will be out for at least the next 1-2 weeks. Class will continue mostly as normal. Some details follow.
- Class on Tuesday June 18 will be taught by Meng He. Class on Thursday June 20 is currently TBA. Assume lectures will proceed as usual unless otherwise mentioned here.
- Assignments will continue as normal. I will not be able to accept early assignments in my office so if you can't make it to class then please pass it in during the tutorial or TA office hours.
- Tutorials will continue as normal. The midterm should not be affected. Email responses will be limited and delayed.
- The final exam will be Saturday August 3rd from 1:00 PM to 4:00 PM in the Scotiabank Auditorium (Aud-1) in the Marion McCain Building. Please note that this is during the long weekend and that I have no control over this date and time.
- Assignments without a cover sheet will not be marked, starting with assignment 4. I'd also like to remind everyone that obtaining solutions from outside your group or online is an academic integrity offense and will have harsh consequences.
-
A notetaker is required to assist your peers. An honorarium of $75 will be provided. If you are interested then see Note taking information
- As discussed in the Tutorial on May 17, the definition of Big-Oh and Big-Omega in the textbook requires that f(n) and cg(n) be nonnegative. You can get 1 bonus point in Assignment 1, Question 3 for correctly checking this condition.
- Question 1 of Tutorial 2 was updated at 2:20 PM on May 19. If the graph has an odd cycle then report the odd cycle and remove the alphabetically largest edge to obtain a graph without an odd cycle.
- Question 1(b) of Assignment 2 now clarifies that you only need to apply Topological Sorting on graph G2.
This class covers techniques for the design and analysis of efficient algorithms and data structures. Topics include asymptotic analysis, divide and conquer algorithms, greedy algorithms, dynamic programming, data structure design, optimization algorithms, and amortized analysis. The techniques are applied to problems such as sorting, searching, identifying graph structure, and manipulating sets.
There are two prerequisite courses, CSCI 2110: Data Structures and Algorithms
and CSCI 2112: Discrete Structures I, and you are expected
to know the basic data structures and proof techniques from those courses.
There is no real programming in this course. We will design
efficient algorithms in high-level pseudocode and then analyze these
algorithms to formally prove their correctness and efficiency.
The course is divided into 8 topics. The first one gives a general introduction to algorithm design, motivates it, and highlights a few central questions one can (and should) ask about a problem and an algorithm solving it. Along the way, we will review the mathematical skills you will need in this course and which you should have acquired in CSCI 2112. The next six topics introduce different paradigms for the design of algorithms, more or less in increasing order of difficulty. The final topic revolves around the question whether all problems can be solved efficiently using computers. More precisely, we will provide evidence that certain problems probably cannot be solved efficiently.
Introduction to Algorithms (3rd edition) by T. Cormen, C. Leiserson, R. Rivest, and C. Stein
MIT Press (ISBN 9780262033848)
Assignments are posted online on Tuesdays and are due
in class on the due dates. Unfortunately, the Faculty of Computer Science is no longer offering drop boxes.
The best 8 of 10 assignment marks are counted.
| Introduction |
|
May 7 |
|
| Fundamentals |
Annotated |
May 7, 9 |
|
| Graph Algorithms |
Annotated |
May 14, 16, 21, 23 |
|
| Greedy Algorithms |
Annotated |
May 23, 28, 30, Jun 4, 6 |
|
| Divide and Conquer |
Annotated |
Jun 11, 13, 18 |
|
| Dynamic Programming |
|
Jun 18, 20, 25, 27 |
|
| Midterm Review |
|
July 2 |
|
| Midterm Exam (in-class) |
|
July 4 |
|
| Data Structures |
Annotated |
July 9, 11, 16 |
Lecture Notes |
| Randomization |
Annotated |
July 16, 18 |
|
| NP hardness |
Annotated |
July 23, 25 |
|
| Final Review |
|
July 30 |
|
| Final Exam |
|
Early August |
|
These notes are from Dr. Norbert Zeh teaching this course in a previous term. They are provided for review or if you have difficulty taking notes of your own.
Stable Matching
Efficient Algorithms
Graph Algorithms
Greedy Algorithms
Divide and Conquer
Dynamic Programming
Tutorials are on Fridays. A TA will show solutions to some practice questions related to recent lectures and current assignments. About one week before each tutorial, these practice questions will be posted on the course web page. The solutions will not be posted so you are encouraged to attend the tutorials and discuss the practice questions with the TA.
| Assignments |
40% |
|
| Mid-Term |
20% |
July 4 (In-class) |
| Final |
40% |
Aug 3 1:00-4:00 McCain Scotiabank Auditorium |
There will be about 10 assignments but only the best 8
assignments count, each with equal weight.
The final exam will be 3 hours long in early August; it is scheduled
by the registrar.
If your final exam score is higher than the midterm exam score, your final exam score will be used in place of your midterm exam score. Then the final grade is A * 40% + max(M*20%+F*40%, F*60%)
The grade conversion scale in Section 17.1 of the Academic Regulations, Undergraduate
Calendar will be used to determine the letter grade. Note that as of 2015, a minimum grade of C must be achieved in all required CS courses.
Late assignments are not accepted because they delay posting and
discussing solutions and add extra time for marking.
If you are unable to write one or more assignments for valid, documented reasons such as a serious illness then your final exam score can be used to cover the marks for missing course work. Please contact the instructor if this applies to you.
If you miss an exam, you will be given the opportunity to sit the exam at a later date. You must, however, present a good reason why you were not able to sit the exam at the regular scheduled time. Also, unless there are a large number of students who missed the regularly scheduled exam, make-up exams are oral exams, during which you will be asked to use a whiteboard to show your solutions. A teaching assistant or additional faculty members may be present during any oral exam.
The last day to withdraw without a “W” is June 5th and the last day
to withdraw with a “W” is July 5th.
You are allowed (but not required) to form study groups to work on homework
assignments, and each group may have up to three students. Students in the same study group
must hand in a joint assignment. No form of collaboration, however, will be allowed between
students who are in different study groups. Collaboration between different groups will be
treated and handled as plagiarism. After each assignment, you are free to start/disband/switch
study groups for the next assignment, as long as you follow the above policy.
At Dalhousie University, we respect the values of academic integrity:
honesty, trust, fairness, responsibility and respect. As a student, adherence to the values of
academic integrity and related policies is a requirement of being part of the academic community
at Dalhousie University. You can find more details on Dalhousie University's Academic Integrity
web site: http://academicintegrity.dal.ca. More university required texts can be found in the
online syllabus of this course.