Advanced data structures and algorithms

COSC 302/307 - Spring 2019

Instructor

Scott Emrich
Office: 608 Min Kao Hall
Phone: (865)974-3891; E-mail: semrich at utk.edu
Tentative office hours: TBD; and by appointment

Overview

This course is a third-semester programming course in C++ that focuses on fundamental data structures and associated algorithms. The course covers basic object-oriented programming (OOP), sorting algorithms, disjoint sets, basic graph algorithms including toplological sort, depth-first search, and breadth-first search, shortest path (Dijskreta's algorithm), minimum spanning trees, network flow / minimum cut, and dynamic programming with memoization. For the algorithms listed above students are expected to design and implement C++ programs (and classes) that solve related problems. All programming will take place in a Unix environment and will be reinforced by weekly assignments centered in the specific lab period for which a student is registered.

Text and syllabus

Data Structures and Other Objects using C++ by Main and Savitch.

The syllabus can be found here

Draft schedule

Date Topic Homework Notes
1/10/2019 (re)Intro to classes, interface, const vs. implementation   Challenge #1 out, due 1/18 [web]
Project #1 out, due 1/23 [web]
Reading 00/01 out, questions due 1/22 [web]
[Notes + code]
1/15/2019 Classes and operator overloading   [Notes + code]
1/17/2019 Templates (cont.)   [Notes + Code]
1/22/2019 Making our own list sequence container Challenge #2 out, due 2/1
Reading 02 out, due 1/29
[Code]
1/24/2019 Sorting: selection, bubble, insertion sort Project #2 out, due 2/6  
1/29/2019 Sorting: merge sort, quicksort    
1/31/2019 Sorting: shell sort, STL algorithms Challenge #3 out, due 2/8  
2/05/2019 Heaps and heap sort    
2/07/2019 Disjoint sets Challenge #4 out, due 2/18
Project #3 out, due 2/19
 
2/12/2019 Intro to graphs (in C++)    
2/14/2019 Collaborative midterm review; Intro to graph traversals    
2/19/2019 DFS/BFS traversals    
2/21/2017 In-class midterm Challenge #5 out, due 3/1
Project #4 out, due 3/15
 
2/26/2019 Minimum spanning trees (MST)    
2/28/2019 Dijkstra's shorest path Challenge #6 out, due 3/8  
3/5/2019 Topological sort    
3/7/2019 B-trees, red-black trees (inc. sorting) Challenge #7 out, due 3/15  
3/12/2019 Catch up / Special Topic    
3/14/2019 Review: interview questions using graphs (mini)Challenge #8 out, due 3/27
Project #5 out, due 4/3
 
Midterm Break!
3/26/2019 Network flow    
3/28/2019 max-flow, min-cut Final project progress report #1 due
Challenge #9 out, due 4/5
 
4/2/2019 Dynamic programming    
4/4/2019 Special topic: DP used in bioinformatics applications Project #6 out, due 4/12  
4/9/2019 Computability and NP completeness    
4/11/2019 TBD    
4/16/2019 TBD Final project progress report #2 due  
4/18/2019 BYODS group presentations (1)    
4/23/2019 BYODS group presentations (2)    
4/25/2019 Final review, presentations (if needed)    

Academic dishonesty

All are required to abide by the EECS and University honor code. Discussions are encouraged, but all answers/programs must be written/developed individually. Final projects will be performed as a group.