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 January 17, Monday January 22
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)

--
Week 2: Wednesday January 24, Monday January 29
Main Ch. 4

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

--
Week 3: Wednesday January 31, Monday February 5
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

Project 1 Due Wednesday January 31
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

--
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

--
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 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

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

--
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


--
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

--
Week 14: Monday April 23, Wednesday April 25



Review for Final
Example Final Exam Question

--
Week 15: Monday April 30, Wednesday May 2 - Next week is final exam week. Time and day TBA






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