CSCI 429: Advanced Algorithms

by Gara Pruesse
Fall 2021

Course Outline

• abstraction (into graphs and other combinatorial objects}
• trade-offs: space vs time, preprocessing vs query time, exact vs approximate, deterministic vs randomized
• developing an algorithm
• algorithm correctness
• algorithm analysis (space and time)

• Familiarty with main approaches to algorithm development;
• sufficient background and facility to prepare the student to read and assimilate current research publications in algorithms;
• tools for design and analysis of new algorithms;
• ability to select algorithms for problem solving, with judgement as to the trade-offs amongs different choices.
  
  
  
  The course includes a selection of the following topics. Some of these topics have already been introduced to the students in earlier courses, in which case we will be deepening and expanding on the problems and their solutions.

  Topics:

  1. Analysis: Big-O, Ω, ω, Θ, worst case running time, amortized running time, lower bounds
  2. Recursion
  3. Data Structuring for efficient access
  4. Dynamic Programming
  5. Greedy Algorithms
  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 1:00--2:00 pm
  If you need to see me outside office hours please send me an email to arrange a suitable time.
  
• Textbook: There is no textbook for the course. The following may be of use to students:
  • Jeff Erickson Algorithms
  • Tim Roughgarden, "Algorithms Illuminated"
  • Corman, Leiserson, Rivest and Stein,
  • Web material: lecture notes, assignments, tutorials, sample programs, practice problems, etc, when available will be accessible through the week-by-week page

  Timetable and assessment
  

  • Lectures: Tue, Thurs 11:30 -- 1:00 Bldg 210, Room 260

  • Tutorials
    You are expected to fully participate in the weekly tutorial/lab sessions.

  • Labs/Tutorials are held in Bdlg 315, Rm 115 Alternative room is Building 210, Rm 255. See the the week-by-week page if you missed the announcement in class about where the Lab/Tutorial will be in a given week.

  Assessment
  

  • Project: 15% paper (which could include a software project), 5% presentation Modules: 4 x 20% each. A module consists of submitted work and an in-class test. The breakdown of test and submitted work will be either 5% submitted work, 15% test, or 15% submitted work, 5% test, but the latter will only be applied if the submitted work is original to the student, the student is able to make a short (10 minute) teaching presentation to the class on the original work, and the alternative breakdown is advantageous to the student.
    If your submitted work has been impacted by readings, videos, interactions with Chat GPT, or discussions with others, you must reference such influences in your work.
    
    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.