| Instructor: |
Robbie Schweller EIEAB 3.220 956-665-2667 robert.schweller@utrgv.edu Office hours: MW 12:45 pm-3:15 pm |
| Schedule: | Section 01: EIEAB 2.207, MW 11:00 am - 12:15 pm Section 05: EIEAB 2.207, MW 3:30 pm- 4: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 |
| Sorting and Searching | |||
| 9/1 | Labor Day (no class) | Algorithm Analysis Heap Sort vs. Selection Sort Read: Chapters 1 and 2. sortTest.cpp | hw0 (due 9/5) hwTT1 (due 9/7) |
| 9/8 | Binary Search and Asymptotic Notation | Comparison Based Sorting Merge Sort and Quick Sort Read: 7.6, 7.7, 7.8 quickSort.cpp | hwTT2 (due 9/14) |
| 9/15 | Comparison Based Sorting: Lower Bound Read: 7.6, 7.7, 7.8 | Bounded-Universe Sorting Reading: Section 7.11 CountingSort.pdf RadixSort.pdf | hwLLmergeSort (due 9/21) |
| Data Structures | |||
| 9/22 | Binary Search Trees | AVL Trees Reading: 4.1-4.3, 4.4, 12.4.2 avlRotations.pdf | |
| 9/29 | AVL Trees (cont.) | Exam 1 | |
| 10/6 | Tries wikipedia: Trie trieSlides1.pdf | Tries (cont.), Heaps | |
| 10/13 | Heaps lecHEAP-slides.pdf Reading: 6.1-6.4 | Hash Tables Reading: Chapter 5 STL map, unordered_map, set | |
| Graph Algorithms | |||
| 10/20 | Graphs | Graphs, Graph Searching, BFS BFS.pdf | |
| 10/27 | Shortest Paths: Dijkstra | Shortest Paths: Dijkstra | |
| 11/3 | Shortest Paths: Bellman-Ford | Network Flows | |
| 11/10 | Network Flows, Perfect Matching, Edmonds-Karp lecFLOW.pdf Reading: 10.3 | Exam 2 | |
| Algorithm Design | |||
| 11/17 | Divide and Conquer Algorithms Master Theorem Reading: Chapter 10.2 Karatsuba algorithm | Divide & Conquer Algorithms Reading: Chapter 10.2 Strassen algorithm Linear Time Selection | |
| 11/24 | Dynamic Programming: LCS, Floyd-Warshall | Dynamic Programming: Matrix Chains | |
| Complexity | |||
| 12/1 | NP-completeness | NP-completeness (cont.) | |
| 12/8 | Review / Buffer | ||
| 12/15 | Final Exam: Section 01: 10:15am-12:00pm | Final Exam: Section 05: 1:15pm-3:00pm | |