Advanced data structures and algorithms

COSC 302/307 - Spring 2019


Scott Emrich
Office: 608 Min Kao Hall
Phone: (865) 974-3891; E-mail: semrich at
Office hours: Tues, 4-5pm; 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

Archived 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 [web]
Reading 02 out, due 1/29 [web]
1/24/2019 Sorting: selection, bubble, insertion sort Project #2 out, due 2/6 [web] [Notes]
1/29/2019 Sorting: merge sort, quicksort Reading 03 out, due 2/5 [web] [Notes]
1/31/2019 Sorting: shell sort, STL algorithms Challenge #3 out, due 2/8 [web] [Slides]
2/05/2019 Heaps and heap sort   [Notes]
2/07/2019 Disjoint sets Reading 04 out, due 2/14 before class [web]
Challenge #4 out, due 2/16 [web]
Project #3 out, due 2/25 [web]
2/12/2019 Intro to graphs   [Notes]
2/14/2019 Collaborative midterm review; Intro to graph traversals   [Notes]
2/19/2019 DFS/BFS traversals (cont.)   [Notes]
2/21/2017 In-class midterm Challenge #5 out, due 3/2 [web]  
2/26/2019 Dijkstra's shorest path Project #4 out, due 3/15 [web] [Notes]
2/28/2019 Minimum Spanning Trees (MSTs) Challenge #6 out, due 3/9 [web] [Notes]
3/5/2019 Topological sort   [Notes]
3/7/2019 Treaps Challenge #7 out, due 3/15 [web] see Piazza
3/12/2019 Intro to software eng/final projects   [Notes]
3/14/2019 Review: interview questions using graphs (mini)Challenge #8 out, due 3/29 [web]  
Midterm Break!
3/26/2019 Network flow   [Notes]
3/28/2019 max-flow, min-cut Project # 5 out, due 4/10 [web]
Final project progress report #1 due
4/2/2019 Special topic: Dynamic programming in bioinformatics   [Notes]
4/4/2019 Dynamic programming (cont) Challenge #9 out, due 4/17 [web] [Notes]
4/9/2019 Recursion (a re-review)   see TA resource
for add. problems
4/11/2019 Computability and NP completeness Final project progress report #2 due [Notes]
4/16/2019 BYODS group presentations (1)    
4/18/2019 BYODS group presentations (2)    
4/23/2019 Final review, presentations (if needed), finish up   see Piazza for
study guide
4/25/2019 Demo day release party!    

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.