Advanced data structures and algorithms

COSC 302/307 - Fall 2021

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
8/19/2021 (re)Intro to classes, const, interface vs. implementation   Challenge #1, due 8/27
Project #1, due 8/30
Reading 00/01 questions due 8/31
[Github]
8/24/2021 Classes and operator overloading   [Github]
8/26/2021 Templates   [Github]
8/31/2021 Sorting: selection, bubble, insertion sort Challenge #2, due 9/3
Project #2, due 9/15
[Notes]
9/2/2021 Sorting: merge sort, quicksort Reading 02, due 9/14 [Notes]
9/7/2021 Sorting: shell sort, STL algorithms   [Notes]
9/9/2021 Heaps and heap sort Challenge #3, due 9/17 [Notes]
9/14/2021 Disjoint sets Reading 03, due 9/28 before class
Challenge #4, due 9/24
[Notes]
9/16/2021 Collaborative midterm review review; Graphs   [Notes]
9/21/2021 Class choice #1: inheritance Project #3, due 10/6  
9/23/2021 In-class midterm    
9/28/2021 DFS/BFS Challenge #5, due 10/8 [Notes]
Fall Break!
10/5/2021 Dijkstra's shorest path   see Piazza
10/7/2021 Minimum Spanning Trees (MSTs) Challenge #6, due 10/15
Project #4, due 10/25
[Notes]
10/12/2021 Topological sort   see Piazza
10/14/2021 Intro to software eng/final projects (mini)Challenge #7, due 10/22 [PDF]
10/19/2021 No class (Engineer's day in ML)    
10/21/2021 Class choice #2 (TBA) Challenge #8, due 10/29  
10/26/2021 Network flow   [Notes]
10/28/2021 max-flow, min-cut Project # 5, due 11/15 [Notes]
11/2/2021 Special topic: Dynamic programming in bioinformatics Final project progress report #1 due [Notes]
11/4/2021 Dynamic programming (cont) Challenge #9, due 11/12 [Notes]
[HackerRank video]
11/9/2021 Computability and NP completeness   [Notes]
[Add. video]
11/11/2021 TBD Final project progress report #2 due  
11/16/2021 BYODS group presentations (set 1)    
11/18/2021 BYODS group presentations (set 2)    
11/23/2021 Exam review, final push inc. presentations if needed    
11/30/2021 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.