Information about CS 340 (Advanced Data Structures and Algorithm Design), Fall 2017. This page might be updated during the term.

• location: CL 130
  
• time: MWF 12:30pm - 1:20pm
  
• first class on Sep 06
  

• location: CW 308.9
  
• time: MWF 1:25pm - 2:20pm (exceptions will be announced in class)
  

• CS210 and MATH221
  

• Mark Allen Weiss, Data Structures and Algorithm Analysis in C++, Fourth Edition, Addison Wesley, 2014.
  

However, we may sometimes deviate slightly from the material presented in this textbook.

1. Algorithm Analysis
basic notions of asymptotic analysis (big O, Omega, Theta)
best case, average case, and worst case behaviour of algorithms
analysis of algorithms vs analysis of problems

2. Priority Queues
binary heaps, d-heaps, leftist heaps, binomial queues

3. Sorting
insertion sort, shellsort, mergesort, heapsort, quicksort
indirect sorting
lower bound
external sorting

4. Graph Algorithms
topological sort
shortest path algorithms
network flow problems
minimum spanning tree
applications of depth-first search

5. Complexity and unsolvability
the complexity classes P and NP
NP-complete problems and the P versus NP question
unsolvable problems

6. Algorithm Design Techniques
greedy algorithms, divide-and-conquer algorithms, dynamic programming, randomized algorithms, backtracking algorithms
parallel algorithms
25% assignments
25% midterm exam (probably Oct 16; participation required)
50% final exam (Dec 20; grade of at least 50% in the final exam required; if less than 50% is achieved on the final exam, then the final exam grade will be the grade for the whole course)

• All solutions to programming problems on assignments must be in C++. Please make sure your code compiles both with Visual C++ and with g++.
  
• Instructions on how to submit solutions to programming assignments will be given in class.
  
• Solutions to non-programming assignments have to be submitted either in class or in 308.9. Your solutions must be stapled. The first page of all assignments must show your name, student number, assignment number, and date submitted.
  
• All assignments have to be submitted on or before the due date indicated on the assignment sheet. Late assignments will not be accepted.
  
• NOTE: Both the solutions to programming assignments and the solutions to non-programming assignments must represent your own original work. Discussing assignment problems with other students is encouraged, but it is not allowed to share or copy solutions, partial solutions, or programming code.
  
  

• preliminary date: Oct 16, 2017
  
• time: 12:30pm - 1:20pm
  
• location: CL 130
  
• closed book
  
  

• date: Dec 20, 2017
  
• time: 9:00am - 12:00pm
  
• location: TBA
  
• closed book
  
• comprehensive exam (covers the whole course)