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 January 16, Thursday January 18
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: Tuesday January 23, Thursday January 25
Main Ch. 4

Big Theta Video

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

--
Week 3: Tuesday January 30, Thursday February 1
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 Tuesday at midnight
Week 4: Tuesday February 6, Thursday February 8
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 February 13, Thursday February 15
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 Tuesday at midnight
Week 6: Tuesday February 20, Thursday February 22
Main Ch. 11,14

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

--
Week 7: Tuesday February 27, MIDTERM EXAM ON Thursday February 29
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 EXAM Review Topics

Project 3 Due Tuesday at midnight
Week 8: Tuesday March 12, Thursday March 14
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
--
Week 9: Tuesday March 19, Thursday March 21


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

--
Week 10: Tuesday March 26, Thursday March 28



Data Compression Huffman
Huffman explained
Data Compression LZW

Project 4 Due Tuesday at midnight
Week 11: Tuesday April 2, Thursday April 4
Main Chapter 12

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

--
Week 12: Tuesday April 9, Tuesday April 16


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: Thursday April 18, Tuesday April 23


The Chomsky hierarchy

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

Project 5 Due Tuesday at midnight
Week 14: Thursday April 25, Note: DSA Final Exam is TBA



Review for Final

--

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