| Instructor: |
Robbie Schweller EIEAB 3.220 956-665-2667 robert.schweller@utrgv.edu Office hours: MW 11:15-12:15, 1:45-3:15pm |
| Schedule: | Section 05: EIEAB 1.206, MW 9:30am - 10:45 Section 06: EIEAB 2.203, MW 12:30 - 1:45pm |
| Books: | Main: "Data Structures and Algorithm Analysis in C++", 4th edition by Mark A. Weiss. Recommended: "Introduction to Algorithms", any edition, by Cormen, Leiserson, Rivest, Stein. | Syllabus: | CSCI3333_syllabus |
| Week | M | W | Homework |
| 1/20 | Algorithm Analysis Heap Sort vs. Selection Sort Read: Chapters 1 and 2. | hw0 (due 1/24) hwTT1 (due 1/26) | |
| 1/27 | Binary Search vs. Linear Search | Asymptotic Notation and Tools Merge Sort and Quick Sort | hwTT2 (due 2/2) |
| 2/3 | Comparison Based Sorting Read: 7.6 (mergesort) 7.7 (quicksort) 7.8 (lower bound) | Master Theorem Karatsuba's algorithm Reading: Chapter 10.2 Reading: Karatsuba algorithm | hwLLmergeSort (due 2/9) |
| 2/10 | Divide & Conquer Algorithms Reading: Chapter 10.2 Reading: Strassen algorithm Reading: Linear Time Selection Reading: Multiple-Size Divide-and-Conquer Recurrences | Bounded-Universe Sorting Reading: Section 7.11 Reading: Radix Sort CountingSort.pdf RadixSort.pdf | |
| 2/17 | Bounded-Universe Sorting Reading: Section 7.11 Reading: Radix Sort CountingSort.pdf RadixSort.pdf | Binary Search Trees Reading: 4.1,4.2,4.3 | |
| 2/24 | AVL Trees Reading: 4.1,4.2,4.3 avlRotations.pdf | Exam 1 | |
| 3/3 | AVL Trees, Tries Reading: 4.4, 12.4.2 avlRotations.pdf wikipedia: Trie trieSlides1.pdf | Tries wikipedia: Trie trieSlides1.pdf | |
| 3/10 | Heaps lecHEAP-slides.pdf Reading: 6.1-6.4 | Hash Tables Reading: Chapter 5 STL map, unordered map, and set Reading: STL: unordered map STL: map STL: set | |
| 3/17 | Spring Break | Spring Break | |
| 3/24 | Challenge Problems | Graphs, Breadth-First Search BFS.pdf | |
| 3/31 | Graphs, Graph Searching, Breadth First Search BFS.pdf | Shortest Paths: Dijkstra's Algorithm | |
| 4/7 | Shortest Paths: Bellman-Ford Algorithm | Exam 2 | |
| 4/14 | Network Flows, Perfect Matching, Edmonds-Karp Algorithm lecFLOW.pdf | Network Flows, Perfect Matching, Edmonds-Karp Algorithm lecFLOW.pdf | |
| 4/21 | Dynamic Programming Reading: 10.3 | Dynamic Programming: Longest Common Subsquence Reading: 10.3 | |
| 4/28 | Dynamic Programming: Floyld-Warshall all-pairs shortest path | Dynamic Programming: Matrix Chains with Memoization | |
| 5/5 | NP-completeness | NP-completeness | |
| 5/12 | Final Exam 5/14: Section 05: 8:00am-9:45am Section 06: 10:15am-12:00pm |