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 | see Piazza | ||
| 2/27/2020 | Minimum Spanning Trees (MSTs) | Challenge #6, due 3/7 Project #4, due 3/12 |
[Notes] | |
| 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 | |||
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.