| Instructor: |
Robbie Schweller EIEAB 3.220 956-665-2667 robert.schweller@utrgv.edu Office hours: MW 9-10:30am, T: 9-11am |
| Schedule: | EIEAB 2.207, MW 11:00am - 12:15 |
| 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 |
| 8/26 | Algorithm Analysis Heap Sort vs. Selection Sort Read: Chapters 1 and 2. sortTest.cpp | Binary Search vs. Linear Search | hw0 (due 8/26) hwTT1 (due 9/1) |
| 9/2 | Labor Day | Asymptotic Notation and Tools Merge Sort and Quick Sort | hwTT2 (due 9/8) |
| 9/9 | 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 9/15) |
| 9/16 | 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 | hwWRITTEN1 (due 9/22) |
| 9/23 | Bounded-Universe Sorting Reading: Section 7.11 Reading: Radix Sort CountingSort.pdf RadixSort.pdf | Binary Search Trees binarySearchTree.h driver.cpp Reading: 4.1,4.2,4.3 | hwWRITTEN2 (due 9/29) |
| 9/30 | AVL Trees Reading: 4.1,4.2,4.3 avl.h binarySearchTree.h driver.cpp avlRotations.pdf | Exam 1 | hwAC1 (10/6) |
| 10/7 | AVL Trees, Tries Reading: 4.4, 12.4.2 avlRotations.pdf wikipedia: Trie trieSlides1.pdf trie.h | Tries wikipedia: Trie trieSlides1.pdf trie.h driver.cpp words2.txt | hwAC2 (10/13) |
| 10/14 | Heaps lecHEAP-slides.pdf Reading: 6.1-6.4 heap.h driver.cpp | Hash Tables Reading: Chapter 5 STL map, unordered map, and set Reading: STL: unordered map STL: map STL: set mapDemo.cpp | hwPQ (10/20) |
| 10/21 | Challenge Problems | Graphs, Breadth-First Search BFS.pdf directedGraph.h driver.cpp | hwMZ1.pdf (due 11/3) |
| 10/28 | Graphs, Graph Searching, Breadth First Search BFS.pdf directedGraph.h driver.cpp | Shortest Paths: Dijkstra's Algorithm | hwMZ2.pdf (due 11/10) |
| 11/4 | Shortest Paths: Bellman-Ford Algorithm | Exam 2 | hwTILE.pdf (due 11/17) |
| 11/11 | Network Flows, Perfect Matching, Edmonds-Karp Algorithm lecFLOW.pdf | Network Flows, Perfect Matching, Edmonds-Karp Algorithm lecFLOW.pdf | |
| 11/18 | Dynamic Programming Reading: 10.3 | Dynamic Programming: Longest Common Subsquence Reading: 10.3 | hwBLND.pdf (due 12/4) |
| 11/25 | Dynamic Programming: Floyld-Warshall all-pairs shortest path | Dynamic Programming: Matrix Chains with Memoization matrixChain.cpp | |
| 12/2 | NP-completeness | NP-completeness | |
| 12/9 | Final Exam: 12/9 10:15am-12:00 |