Advanced data structures and algorithms

COSC 302/307 - Spring 2023


Scott Emrich
Office: 608 Min Kao Hall
Phone: (865) 974-3891; E-mail: semrich at
Office hours: whenever my office 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 reinforces object-oriented programming (OOP), and covers 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 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/24/2023 (re)Intro to classes, const, interface vs. implementation   Challenge #1, due 1/30
Project #1, due 2/3
Reading 00/01 questions due 2/1
1/26/2023 Classes and operator overloading   [Github]
1/31/2023 Sorting: selection, bubble, insertion sort Challenge #2, due 2/6
Project #2, due 2/17
[Historical Notes]
2/2/2023 Sorting: merge sort, quicksort Reading 02, due 2/15 [Historical Notes]
2/7/2023 Sorting: shell sort, heap sort, STL algorithms   [Notes]
2/9/2023 Disjoint sets Challenge #3, due 2/13 [Historical Notes]
2/14/2023 Class choice #1: templating Reading 03, due 3/3
2/16/2023 Graphs Challenge #4, due 3/6
Project #3, due 3/10
[Historical Notes]
2/21/2023 DFS/BFS   [Historical Notes]
2/23/2023 Collaborative midterm review review; Dijkstra's shorest path Challenge #5, due 2/27 see Piazza
2/28/2023 Minimum Spanning Trees (MSTs) Project #4, due 3/31 [Historical Notes]
3/2/2023 In-class midterm Challenge #6, due 3/10  
3/7/2023 Intro to software eng/final projects   see Piazza
3/9/2023 Templates (review) Challenge #7, due 3/27 [PDF]
Spring Break!
3/21/2023 Topological sort Challenge #8, due 4/3  
3/23/2023 Network flow   [Notes]
3/28/2023 max-flow, min-cut Project # 5, due 4/21 [Notes]
3/30/2023 Special topic: Dynamic programming in bioinformatics Final project progress report #1 due [Notes]
4/4/2023 Dynamic programming (cont) Challenge #9, due 4/17 [Notes]
[HackerRank video]
4/11/2023 Computability and NP completeness [Notes]
[Add. video]
4/13/2023 Special topic: Parallel sorting (outside)    
4/18/2023 Class choice #2: dimensionality reduction for machine learning (guest lecture) Final project progress report #2 due  
4/20/2023 BYODS group presentations (set 1)    
4/25/2023 BYODS group presentations (set 2)    
4/27/2023 BYODS group presentations (set 3)    
5/2/2023 BYODS group presentations (set 4)    
5/4/2023 Exam review, final push inc. presentations if needed    
5/9/2023 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.