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: M. Febuary 1, W. February 3
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: M. Febuary 8, W. February 10
Main Ch. 4

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

--
Week 3: M. Febuary 15, W. February 17
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 due Monday at midnight
Week 4: M. Febuary 22, W. February 24
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: M. March 1, W. March 3
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 Due Monday, March 1, at Midnight
Week 6: M. March 8, W. March 10
Main Ch. 11,14

Dijkstra Shortest Path
Graphs III (optional)
Graphs IV (optional)

--
Week 7: M. March 15, W. March 17
Main Ch. 6,7,12


Searching I
Main on Searching Using Hash Tables Ch.11

Project 3 Due Monday, March 15, at Midnight
Week 8: M. March 22, W. March 24
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
Review
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: M. March 22, W. March 24


Sorting demonstrations
Searching II
Lecture Notes
Main Ch.12
Sorting I
Sorting I (PDF)

--
Week 10: M. March 29, W. March 31



Data Compression Huffman
Huffman explained
Data Compression LZW

--
Week 11: M. April 5 No classes, W. April 7, M. April 12
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
CrimeLatLonXY.csv
Project 4 Due Wednesday, April 7, at Midnight
Week 12: W. April 14, M. April 19


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. April 21, M. April 26


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 Wednesday April 21 at midnight
Week 14: W. April 28, M. May 3, W. May 5



Review for Final
Example Final Exam Question

Project 6 Due Wednesday, May 5, at Midnight
Week 15: Tuesday, May 11, Final Exam 05/11/2021 08:30AM





--

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