Advanced data structures and algorithms

COSC 302/307 - Spring 2020


Scott Emrich
Office: 608 Min Kao Hall
Phone: (865) 974-3891; E-mail: semrich at
Office hours: Tuesday 12:30-1:30pm; walk ins if door is open and by appointment


This course is a third-semester programming course 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, minimum spanning trees, network flow / minimum cut, and dynamic programming. For the algorithms listed above students are expected to design and implement C++ programs that solve related problems. All programming will take place in a Unix environment and will be reinforced by weekly assignments.

Text and syllabus

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

The syllabus can be found here


Date Topic Homework Notes
1/09/2020 (re)Intro to classes, const, interface vs. implementation   Challenge #1, due 1/17
Project #1, due 1/22
Reading 00/01 questions due 1/22
1/14/2020 Classes and operator overloading   [Github]
1/16/2020 Templates   [Github]
1/21/2020 Sorting: selection, bubble, insertion sort Challenge #2, due 2/1
Project #2, due 2/6
1/23/2020 Sorting: merge sort, quicksort Reading 02, due 2/4 [Notes]
1/28/2020 Sorting: shell sort, STL algorithms   [Notes]
1/30/2020 OOP Challenge #3, due 2/8 [Link]
2/04/2020 Heaps and heap sort   [Notes]
2/06/2020 Disjoint sets Reading 03, due 2/13 before class
Challenge #4, due 2/15
2/11/2020 Intro to graphs Project #3, due 2/27 [Notes]
2/13/2020 Collaborative midterm review; DFS Challenge #5, due 2/22 [Notes]
2/18/2020 BFS/Dykstra's   [Notes]
2/20/2020 In-class midterm    
2/25/2020 Dijkstra's shorest path   see Piazza
2/27/2020 Minimum Spanning Trees (MSTs) Challenge #6, due 3/7
Project #4, due 3/12
3/3/2020 Topological sort   see Piazza
3/5/2020 Intro to software eng/final projects (mini)Challenge #7, due 3/14 [PDF]
3/10/2020 Class choice: templates    
3/12/2020 Class choice: interview questions using graphs Challenge #8, due 3/28  
Midterm Break!
3/24/2020 Network flow   [Lecture]
[Add. video]
3/26/2020 max-flow, min-cut Project # 5, due 4/16 [Lecture]
3/31/2020 Special topic: Dynamic programming in bioinformatics Final project progress report #1 due [Lecture]
4/2/2020 Dynamic programming (cont) Challenge #9, due 4/18 [Lecture]
[HackerRank video]
4/7/2020 Computability and NP completeness   [Lecture]
[Add. video]
4/9/2020 No class
(spring recess)
4/13/2020 Final push review (exam, project) Final project progress report #2 due [Exam review]
4/16/2020 BYODS group presentations (1, on your own)   see Piazza post
4/21/2020 BYODS group presentations (2, on your own)   see Piazza post
4/23/2020 BYODS questions (all), finish up    

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.