95-771 Data Structure and Algorithms for Information Processing

[ Home | Schedule | Syllabus | Course description ]

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



DateReading(s)SlidesOutIn
Week 1: Wednesday August 30
Main Ch. 1,2


Introduction
Main on Pre and Post Conditions
Basic Big O
Towers
Main on OOP
Videos Fall 2017
Project 1 Lists
Project 1 Javadoc
--
Week 2: Wednesday September 6
Main Ch. 4

Big Theta Video
Big O
Big O (PDF version)
Linked Lists
Ch.4

--
Week 3: Wednesday September 13
Main Ch. 6,7

N Queens on U-Tube

Sedgewick on Kd Trees
Stacks/Queues
Main Ch.6,7
Trees
Main Ch.9 Binary Search Trees
Lecture - On Silverlight

2d trees Project 2
CrimeLatLonXY.csv
Project 1 Due Wednesday September 13
Week 4: Wednesday September 20
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: Wednesday September 27
Main Ch. 11,14

Cool Graph Applets

Floyd Warshall at Wikipedia
Graphs I
Graphs II
Red Black Tree Postfix calculator Project 3
Red Black Tree Project Javadoc
Project 2 Due Wednesday Midnight
Week 6: Wednesday October 4
Main Ch. 11,14


Graphs III
Graphs IV

--
Week 7: Wednesday October 11
Main Ch. 6,7,12


Searching I
Main on Searching Using Hash Tables Ch.11

Project 3 Due Wednesday Midnight
Week 8: Wednesday October 18
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 exam Wednesday October 18 - See Review for midterm
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: Wednesday October 25


Digital Search Tree and Radix Trie

Sorting demonstrations

Correctness proof discussion
Searching II
Lecture Notes
Main Ch.12
Sorting I
Sorting I (PDF)

--
Week 10: Wednesday November 1



Data Compression Huffman
Huffman explained
Data Compression LZW

Project 4
Week 11: Wednesday November 8
Main Chapter 12

Radix sort
Sorting II
Sorting II (PDF)
Radix Sort
Slide Edits
Lecture Notes


--
Week 12: Wednesday November 15 No class next Wednesday


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: Wednesday November 29


The Chomsky hierarchy

P versus NP problems
Finite State Machines III
Finite State Machines III (PDF)
NP-Complete Languages
NP-Complete Languages Lecture (Part 0)
NP-Complete Languages Lecture (Part 1)

--
Week 14: Wednesday December 6



Review for Final
Example Final Exam Question

--
Week 15: Wednesday December 13 Final Exam during regular class time and place





--

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