95-771 Data Structure and Algorithms for Information Processing

[ Home | Schedule | Syllabus | Course description ]

Look for frequent updates to the topics, slides and readings.

Date	Reading(s)	Slides	Out	In
Week 1: W. August 31	Main Ch. 1,2	Introduction Main on Pre and Post Conditions Basic Big O Towers Main on OOP	Project 1 : Singly Linked Lists Project 1 Javadoc (ObjectNode and SinglyLinkedList) after modifications Project 1 ObjectNode.java prior to modifications	--
Week 2: W. September 7	Main Ch. 4 Big Theta Video Big O at Khan Academy	Big O Big O (PDF version) Linked Lists Ch.4		--
Week 3: W. September 14	Main Ch. 6,7 N Queens on U-Tube	Stacks/Queues Main Ch.6,7 Trees Main Ch.9 Binary Search Trees	Project 2: 2d Trees CrimeLatLonXY.csv Sedgewick on Kd Trees	Project 1
Week 4: W. September 21	Main Ch. 9,10 Red Black Tree Video B-Tree Video B+ Tree Video	Heaps and B-Trees Main on Heaps Ch.10 Notes on 2-3 Trees Red Black Trees		--
Week 5: W. September 28	Main Ch. 11,14 BFS DFS Floyd Warshall at Wikipedia	Graphs I Graphs II	Project 3: Graph coloring and Red Black Trees Red Black Tree Javadoc	Project 2
Week 6: W. October 5	Main Ch. 11,14 Dijkstra Shortest Path	Graphs III (optional) Graphs IV (optional)		--
Week 8: W. October 12	Old Midterm exams Old Midterm Fall 2011 Midterm Spring 2012 Midterm Fall 2013 Midterm Spring 2014 Midterm Fall 2014 Midterm Spring 2015 Midterm Fall 2015 Midterm Spring 2016 Midterm Fall 2016 Midterm Spring 2017 Midterm Fall 2017 Midterm Spring 2018 Midterm Fall 2018 Midterm Spring 2019 Midterm Fall 2019 Midterm Spring 2020 Midterm Fall 2021 Midterm Spring 2022 Midterm Fall 2022	October 12 Midterm Exam		Project 3
Week 7: W. October 26	Main Ch. 6,7,12	Searching I Main on Searching Using Hash Tables Ch.11	Traveling Sales Person Problem Project 4 TSP and MST from CLR Traveling Sales Person Help Crime Data X Y Lat Lon Pittsburgh 1990	--
Week 9: W. November 2	Sorting demonstrations	Searching II Lecture Notes Main Ch.12 Sorting I Sorting I (PDF)		--
Week 10: W. November 9		Data Compression Huffman Huffman explained Data Compression LZW	Project 5 LZW Compression Video File (binary) for compression testing words.html for text compression testing shortwords.txt for text compression testing CrimeLatLonXY.csv	Project 4
Week 11: W. November 16	Main Chapter 12 Radix sort	Sorting II Sorting II (PDF) Radix Sort Slide Edits Lecture Notes		--
Week 12: W. November 30	Finite State Machines Pushdown Automata Linear Bound Automata Turing Machines Google Doodle Turing Machines	Finite State Machines I Finite State Machines I (PDF) Finite State Machines II Finite State Machines II (PDF)		--
Week 13: W. December 7	The Chomsky hierarchy P versus NP problems	Finite State Machines III Finite State Machines III (PDF) NP-Complete Languages		Project 5
Week 14: W. December 14 Final exam begins at 5:30 PM HBH 1004, 1005		Review for Final Example Final Exam Question		--

Last Update: August 2022
mm6@andrew.cmu.edu