Information about

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)

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

- location: CL 130

- time: MWF 12:30pm - 1:20pm

- first class on Sep 06

Office hours

- location: CW 308.9

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

Prerequisites

- CS210 and MATH221

Text

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

Tentative topic outline

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

Grading

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)

Assignments

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

Midterm exam

- preliminary date: Oct 16, 2017

- time: 12:30pm - 1:20pm

- location: CL 130

- closed book

Final exam

- date: Dec 20, 2017

- time: 9:00am - 12:00pm

- location: TBA

- closed book

- comprehensive exam (covers the whole course)

design: raura