Advanced data structures and algorithms

COSC 302/307 - Spring 2020

Instructor

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

Overview

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

Schedule

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
[Github]
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
[Notes]
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
[Notes]
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   [Notes]
2/27/2020 Minimum Spanning Trees (MSTs) Challenge #6 out, due 3/7
Project #4 out, due 3/12
see Piazza
3/3/2020 Topological sort    
3/5/2020 Treaps Challenge #7 out, due 3/14  
3/10/2020 Intro to software eng/final projects    
3/12/2020 Review: interview questions using graphs (mini)Challenge #8 out, due 3/28  
Midterm Break!
3/24/2020 Network flow    
3/26/2020 max-flow, min-cut Project # 5 out, due 4/16
Final project progress report #1 due
 
3/31/2020 Special topic: Dynamic programming in bioinformatics    
4/2/2020 Dynamic programming (cont) Challenge #9 out, due 4/18  
4/7/2020 Recursion (a re-review)    
4/9/2020 Computability and NP completeness Final project progress report #2 due  
4/13/2020 BYODS group presentations (1)    
4/16/2020 BYODS group presentations (2)    
4/21/2020 Final review, presentations (if needed), finish up    
4/23/2020 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.