CSCI 422: Advanced Algorithms

by Gara Pruesse
Fall 2021

Course Outline

Topics:

1. Recursion
2. Backtracking
3. Dynamic Programming
4. Greedy Algorithms
5. Hashing
6. Disjoint Sets ("union-find")
7. Graph Algorithms
   • Representations, Traversals
   • Depth-First Search
   • Network Flows
8. Poset Algorithms
   • Topological Sort
   • Scheduling
9. NP-hardness

   Contact information, materials
   

   • Professor: Gara Pruesse, 753-3245 ext 2337, Gara dot Pruesse at viu dot ca
   • Office hours (in Bldg 315, Rm 218): Wed 10:00-11:00am, Thu 4:00-5:00.
     If you need to see me outside office hours please send me an email to arrange a suitable time.
     
   • Textbook: Jeff Erickson Algorithms
   • Web material: lecture notes, assignments, tutorials, sample programs, practice problems, etc, when available will be accessible through http://csci.viu.ca/~gpruesse/teaching/422/notes.html

   Timetable and assessment
   

   • Lectures: Tue, Thurs 11:30 -- 1:00 Bldg 210, Room 240
   • Tests: October 14 and November 16, in lecture
   • Labs/Tutorials are held in Bdlg 210, Rm 240

     Tutorials
     You are expected to fully participate in the weekly tutorial/lab sessions. Except in the case of class/tutorial missed due to illness, you should not expect to use the instructor's office hour to make up for skipping class or tutorial. Missed material is the responsibility of the student to make up. The textbook and classmates notes are your first resource when class/tutorials are missed.
     Each tutorial may involve study questions, and may be specifically geared towards helping solve the current assignment.

     Computer accounts
     To work on your tutorials and assignments, you will be given accounts for the computing science labs.
     There is a user id and password associated with each account (to prevent others from reading your mail).
     The appropriate use of these accounts will be discussed in your first tutorial.

     Assignment notes
     Each assignment has a due date and time. Assignments must be submitted before the due date and time, using the submission process which will be discussed in the class and lab sessions. No other method of submission will be accepted. Late assignments will be accepted for up to two days after the deadline, with 10% penalty for each day late.
     Assignment marking will be based on the correctness of your solutions, the quality of your code and supporting documentation, and adherence to standards and restrictions which will be specified on an assignment-by-assignment basis.
     You are required to cite any works you used in constructing the solution you submit, including helpful discussions with other students, online sources, emails, etc.

     Grading
     Each assignment will have a weight, so that longer or more challenging assignments can be given weight in accordance with the amount of effort I believe they take.
     
     
     40% Assignments
     40% Midterms x 2
     15% Paper/Project
     5% Presentation/Oral interview
     
     
     Appeals of Grades: Any exercise or examination grade may be appealed. However, the appeal must be made to the instructor, in writing and attached to the work in question, and within 7 days of the graded work being returned or available. The instructor reserves the right to re-grade the entire piece of work submitted on appeal, not necessarily just the component that the student believes is in error. An appeal of the course grade is a matter of University Policy.

     Grade Conversion: The following scale will be used.
     

     90-100	85-<90	80-<85	76-<80	72-<76	68-<72	64-<68	60-<64	55-<60	50-<55	<50
     A+	A	A-	B+	B	B-	C+	C	C-	D	F

     Guidelines Concerning Fraud
     These guidelines concern the type of fraud where a student presents another's work as his or her own, or allows another to do so.

     • As fraud invalidates the evaluation of a student's progress, it is the duty of instructors, teaching assistants, and laboratory assistants to take measures to prevent fraud and to be vigilant towards symptoms of fraud.
     • Students are encouraged to discuss the material of the course together. Students may discuss assignments but no written material or record of any kind shall leave such discussions with any party.
       This includes emails and texts -- by their nature, they leave a written record, so are not permitted. Questions put to the course Discord channel are acceptable, with the following caveat: students answering other students' queries should answer with guidance rather than cheating. Answer as if you are an instructor or a help-centre staffperson -- answer as if the goal is that the questioner learn, not get marks.
       If your submitted work has been impacted by readings, videos, or discussions with others, you must reference such influences in your work.
       
       All submitted work in this course is to be executed individually. You must understand your submitted work; if you don't, it cannot be considered your work, and your grade on the work can be changed accordingly.
       
       As in all academic endeavour, due credit must be given to all reference material. Students should consult the course instructor if they are not certain which outside material is appropriate for use in a course.
       
     • In case fraud is detected, credit is withheld from the work affected. The students involved are reported to the Chair of the Department and to the Dean of Science and Technology, who may take additional disciplinary action commensurate with the severity of the fraud and the past records of the students.