95-771 Data Structure and Algorithms for Information Processing

[ Home | Schedule | Syllabus | Course description ]

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

Week 1: Wednesday January 17, Monday January 22
Main Ch. 1,2

Main on Pre and Post Conditions
Basic Big O
Main on OOP
Old Videos Fall 2017 (May not apply during Spring 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 24, Monday January 29
Main Ch. 4

Big Theta Video
Big O
Big O (PDF version)
Linked Lists

Week 3: Wednesday January 31, Monday February 5
Main Ch. 6,7

N Queens on U-Tube

Sedgewick on Kd Trees
Main Ch.6,7
Main Ch.9 Binary Search Trees
Lecture - On Silverlight
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 Monday February 5
Week 4: Wednesday February 7, Monday February 12
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 14, Monday February 19
Main Ch. 11,14

Cool Graph Applets

Floyd Warshall at Wikipedia
Graphs I
Graphs II
Red Black Tree Postfix Calculator Project 3
Project 2 Due Monday February 19
Week 6: Wednesday February 21, Monday February 26
Main Ch. 11,14

Graphs III
Graphs IV

Week 7: Wednesday February 28, Monday March 5
Main Ch. 6,7,12

Searching I
Main on Searching Using Hash Tables Ch.11

Project 3 Due Monday March 5
Week 8: Wednesday March 7 (next week is spring break no classes)
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 exam Wednesday March 7 - held at same time and place as class meeting - See Review for midterm

Week 9: Monday March 19, Wednesday March 21

Sorting demonstrations
Searching II
Lecture Notes
Main Ch.12
Sorting I
Sorting I (PDF)
Traveling Sales Person Problem Project 4
TSP and MST from CLR
Traveling Sales Person Help
Crime Data X Y Lat Lon Pittsburgh 1990
Week 10: Monday March 26, Wednesday March 28

Data Compression Huffman
Huffman explained
Data Compression LZW

Week 11: Monday April 2, Wednesday April 4
Main Chapter 12

Radix sort
Sorting II
Sorting II (PDF)
Radix Sort
Slide Edits
Lecture Notes
Project 5 LZW Compression
Video File (binary) for compression testing
words.html for text compression testing
shortwords.txt for text compression testing

Project 4 Due Monday night
Week 12: Monday April 9, Wednesday April 11

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: Monday April 16, Wednesday April 18

The Chomsky hierarchy

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

Project 6 Turing Machines
FSA Exercises
Project 5 Due Monday night
Week 14: Monday April 23, Wednesday April 25

Review for Final
Example Final Exam Question

Week 15: Monday April 30, Wednesday May 2 - Final Exam Friday May 11, 2018 08:30AM HBH A301

Project 6 Due Monday night, April 30

Last Update: January 2018