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: Tuesday August 26, Thursday August 28
Main Ch. 1,2


Introduction
Main on Pre and Post Conditions
Basic Big O
Towers
Main on OOP

--
Week 2: Tuesday September 2, Thursday September 4
Main Ch. 4

Big Theta Video

Big O at Khan Academy
Big O
Big O (PDF version)
Linked Lists
Ch.4

--
Week 3: Tuesday September 9, Thursday September 11
Main Ch. 6,7

N Queens on U-Tube
Stacks/Queues
Main Ch.6,7
Trees
Main Ch.9 Binary Search Trees

Project 1 Due Tuesday September 9 at midnight
Week 4: Tuesday September 16, Thursday September 18
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: Tuesday September 23, Thursday September 25
Main Ch. 11,14

BFS

DFS

Floyd Warshall at Wikipedia
Graphs I
Graphs II

--
Week 6: Tuesday September 30, Thursday October 2
Main Ch. 11,14

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

--
Week 7: Tuesday October 7, Thursday October 9 MIDTERM EXAM ON Thursday, October 9
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

Midterm Fall 2021

Midterm Spring 2022

Midterm Fall 2022

Midterm Spring Key 2023

Midterm Fall Key 2023

Midterm Spring Key 2024

Midterm Fall Key 2024

Midterm Spring Key 2025
MIDTERM EXAM Review Topics

--
Week 8: Tuesday October 21, Thursday October 23
Main Ch. 6,7,12


Searching I
Main on Searching Using Hash Tables Ch.11
--
Week 9: Tuesday October 28, Thursday October 30


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

--
Week 10: Thursday November 6, Tuesday November 11



Data Compression Huffman
Huffman explained
Data Compression LZW
--
Week 11: Thursday November 13, Tuesday November 18
Main Chapter 12

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

--
Week 12: Thursday November 20, Tuesday November 25


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: Tuesday December 2, Thursday November 4


The Chomsky hierarchy

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

--
Week 14: Monday December 8 Through Friday December 12, FINAL EXAM WEEK, Final Exam Date and Time are TBA



Review for Final

--

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