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: Monday January 14, Wednesday January 16
Main Ch. 1,2


Introduction
Main on Pre and Post Conditions
Basic Big O
Towers
Main on OOP
Old Videos Fall 2017 (May not apply during Spring 2018)
New Videos Fall 2018
Project 1 : Singly Linked Lists
Project 1 Javadoc (ObjectNode and SinglyLinkedList) after modifications
Project 1 ObjectNode.java prior to modifications

--
Week 2: Wednesday January 23, Monday January 28
Main Ch. 4

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

--
Week 3: Wednesday January 30, Monday February 4
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
Red Black Tree Project Javadoc
Project 2 : Red Black Trees
Short list of English words: shortwords.txt
Long list of English words: words.txt
Short list with some poorly spelled English words: badwords.txt
Project 1 Due Midnight, Monday February 4
Week 4: Wednesday February 6, Monday February 11
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 February 13, Monday February 18
Main Ch. 11,14

Cool Graph Applets

Floyd Warshall at Wikipedia
Graphs I
Graphs II
BigInteger Postfix Calculator Project 3

Project 2 due at midnight on Monday, February 18
Week 6: Wednesday February 20, Monday February 25
Main Ch. 11,14


Graphs III
Graphs IV

--
Week 7: Wednesday February 27, Monday March 4
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
Project 3 Due and Project 3 Topics covered on Midterm
Week 8: Wednesday March 6 Monday March 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 Fall 2017

Midterm Spring 2018

Midterm Fall 2018

Midterm Spring 2019
Midterm exam Wednesday March 6 - held at same time and place as class meeting - See Review for midterm

--
Week 9: Wednesday March 20, Monday March 25


Sorting demonstrations
Searching II
Lecture Notes
Main Ch.12
Sorting I
Sorting I (PDF)
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 Due Monday, March 25 11:59 PM
Week 10: Wednesday March 27, Monday April 1



Data Compression Huffman
Huffman explained
Data Compression LZW

--
Week 11: Wednesday April 3, Monday April 8
Main Chapter 12

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

--
Week 12: Wednesday April 10, Monday April 15


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)
Project 6 Turing Machines
FSA Exercises
Project 5 LZW due Monday April 15 at 11:59 PM
Week 13: Wednesday April 17, Monday April 22


The Chomsky hierarchy

P versus NP problems
Finite State Machines III
Finite State Machines III (PDF)
NP-Complete Languages

--
Week 14: Wednesday April 24, Monday April 29



Review for Final
Example Final Exam Question

Project 6 due Monday, April 29
Week 15: Wednesday May 1 Last Day of Class





--
Week 16: Final Exam Thursday May 9 1:00 - 4:00 HBH 1204





--

Last Update: January 2019
mm6@andrew.cmu.edu