CPI 220: Applied Data Structures and Algorithms
CIDSE at Arizona State University
Fall 2017 * T & TH 3:00 - 4:15am * CDS15
Instructor: D. Hansford, Ph.D.
dianne.hansford@asu.edu
Office: BYENG 346
Office Hours: T, TH 10:30-11:30 and by appointment
Home Page Class Log
| Date | Topics | Materials | Homework |
| 17 Aug | Introduction to course + DCH Introduction to resources Why study algorithms? |
Review course website: homepage=syllabus WhyStudyAlgorithms.pdf (Trading article) Review textbook website Eclipse + Java |
1) Install Java and Eclipse 2) Watch The Secret Rules of Modern Living - Algorithms (51 minutes) 3) Start reading Sections 1.1 and 1.2 |
| 22 Aug | Movie Discussion Programming Model Data Abstraction |
00Exercise_AlgorithmsMovie.pdf Sec 1.1 Fundamentals: Java Sec 1.2 Fundamentals: ADT Resource: Libraries and Clients 11Exercise_JavaTopics.pdf Counter.java (This code uses algs4.jar) |
1) Edit, compile, run HelloWorld 2) download algs4.jar and add to Eclipse (Windows-Preferences-Java-ClassPath-New) 3) Demo: Hello World (make sure you can run this) 4) Read Sec 1.3 |
| 24 Aug | Q&A on Java material Collections: Stacks, Queues, Bags |
13StacksandQueues.pdf (59 slides) Resource: Stacks 13DemoDijkstraTwoStack.mov |
1) Review today's slides 2) Read Sec 1.4 3) Be able to run Counter.java (This code uses algs4.jar) |
| 29 Aug | Stacks and Queues con't | (See 24 Aug) Quiz 1 |
|
| 31 Aug | Stacks and Queues wrap-up Discuss HW 1 Analysis of Algorithms |
13Exercise_StacksQueues.pdf Intro video: Computer Innovators |
HW 1 Assigned Review Quiz solutions Review S&Q Exercises |
| 5 Sep | HW 1 Q&A Quiz 2 Analysis of Algorithms con't |
14AnalysisOfAlgorithms.pdf (65 slides) 14DemoBinarySearch.pdf |
This video is a lot of fun! In the end it all adds up to... Falsifiability |
| 7 Sep | Analysis of Algorithms con't | Quiz 2 Solution | |
| 12 Sep | Fundamentals Application: Union Find | 15UnionFind.pdf Demo movies |
HW 1 Due 14Exercise_AnalysisOfAlgorithms.pdf 15Exercise_UnionFind.pdf |
| 14 Sep | Introduction to Sort Discuss HW 2 |
21ElementarySorts.pdf Demo movies |
HW 2 Assigned (Updated 9/16) Deque.java |
| 19 Sep | Quiz: Analysis of Algorithms Elementary Sort con't |
Watch Demo movies for Sec 2.1 Quiz 3 Questions and Solutions |
|
| 21 Sep | Merge Sort | 22MergeSort.pdf |
Watch Demo movie for Sec 2.2 Recurrence Relation Review Comparable/Comparator |
| 26 Sep | Quick Sort | 23QuickSort.pdf 23DemoQuickSelect.pdf 23DemoPartitioning.pdf |
HW 2 Due |
| 28 Sep | Priority Queues | 24PriorityQueues.pdf See Demo movies under Section 2.4 |
21Exercise_ElemSort.pdf (updated 9/29) 22Exercise_MergeSort.pdf 23Exercise_QuickSort.pdf 24Exercise_PriorityQueue.pdf |
| 3 Oct | Midterm Review | MockMidterm.pdf | |
| 5 Oct | Midterm Exam | ||
| 10 Oct | No class - Winter Break | ||
| 12 Oct | Search | 31ElementarySymbolTables.pdf |
**Uploaded 10/17 31Exercises_ElemSymbolTables.pdf |
| 17 Oct | Search | 32BinarySearchTrees.pdf + demo |
32Exercises_BinarySearchTrees.pdf |
| 19 Oct | Search | 33BalancedSearchTrees.pdf + 4 demos |
|
| 24 Oct | Search con't HW 3 Discussion Exercises Sec 3.2 |
33BSTApplication_GeometricSearch.pdf | HW 3 Assigned 33Exercises_BalancedSearchTrees.pdf Quiz 4 (Symbol Table) Solution |
| 26 Oct | HW 3 Q&A Search |
34HashTables.pdf + demo |
Quiz 5 (BST) Solution |
| 31 Oct | Search wrap-up | 35SearchingApplications.pdf | |
| 2 Nov | Graphs - Intro | 41UndirectedGraphs.pdf + Demos | HW 3 Due 3 Nov (Friday) by midnight Work on Exercise sheets 34Exercises_HashTables.pdf |
| Quiz 6: Hash Tables | |||
| 7 Nov | Graphs - Undirected | 41Exercise_GraphAPI.pdf 41Exercise_GraphBasics.pdf 41Exercise_UndirectedGraphs.pdf |
|
| 9 Nov | Graphs - Directed | 42DirectedGraphs.pdf + Demos | |
| 14 Nov | Graphs- MST | 43MinimumSpanningTrees.pdf Greedy Demo.pdf Prim Demo pdf Kruskal Demo pdf |
HW 4 Assigned Quiz Hash Solutions Quiz Graph Basics |
| 16 Nov | Graphs - MST | 41DFS_BFS Paths comparison jpg 43Kruskal jpg 43Prim jpg |
42Exercise_DirectedGraph.pdf 43Exercise_MST.pdf |
| 21 Nov | Graphs | 44ShortestPaths.pdf Bellman Ford Demo pdf Dijkstra Demo pdf AcyclicSP Demo pdf 44Dijkstra Shortest Example jpg |
44Exercise_ShrotestPaths.pdf Work on Exercise Sheets!!! |
| 23 Nov | No class - Thanksgiving Break | ||
| 28 Nov | Review Mock HW 4 Q&A |
MockFinal.pdf | HW 4 Due |
| 30 Nov | Review Mock | ||
| 5 Dec (Tues) |
Final Exam 3:00 - 4:20 (Start 1/2 hour after scheduled time) Location: CDS 15 |
