Scott Emrich
Office: 608 Min Kao Hall
Phone: (865) 974-3891; E-mail: semrich at utk.edu
Office hours: Tues, 4-5pm; 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
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] |
[Code] | |
| 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] |
[Notes] | |
| 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 |
[Notes] | |
| 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] [Video] |
| 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! | |||
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.