CMSI 2130 - Algorithms & Analysis

Professor Andrew Forney • Andrew.Forney[at]lmu.edu • Spring 2024


Welcome to CMSI-2130 1 / 9 / 24

If you're reading this then you've successfully found the course page for CMSI 2130! Check this page frequently for announcements that are relevant to the course, including notes, homework assignments, and practice problems.

First things first, please read through the course syllabus located here (or in the Materials tab above).


Lecture Notes
Date Lecture Subject
Lecture 12-2
4 / 4 / 24
Taking Notes from Jack and Jill
Local Search, Hill Climbing, Simulated Annealing, and Genetic Algorithms -- all in one quivering mass!

  Lecture Video (13-2)
  Lecture Video (13-1)
  Recitation (Week 13)
Lecture 12-1
4 / 2 / 24
Graphs are Constraining
Ordering and Structure heuristics for CSPs!

  Lecture Video (12-2)
  Lecture Video (12-1)
  Recitation (Week 12)
Lecture 10-2
3 / 21 / 24
Turning up the AC
Filtering, constraint propagation, and AC-3 make their grand debut!

  Lecture Video (11-1)
  Lecture Video (10-2)
  No Recitation Week 11 -- Easter Break!
Lecture 10-1
3 / 19 / 24
Coloring Books for Computer Scientists
Introduction to Constraint Satisfaction Problems (CSPs): map coloring never looked so technical!

  Lecture Video (10-1)
  Recitation (Week 10)
Lecture 9-1
3 / 12 / 24
In Not So Many Words
Greedy programming gets its day in the sun with a look at compression and Huffman Coding!

  Lecture Video (9-2)
  Lecture Video (9-1)
  Recitation (Week 9)
Lecture 8-1
2 / 5 / 24
Blooming Imaginations
Bloom filters -- data structures meet probabilistic programming!

  Lecture Video (8-2)
  Lecture Video (8-1)
  Recitation (Week 8)
Lecture 7-1
2 / 20 / 24
The Red Squiggly Underline - A Biography
The magic behind many spelling correctors and checkers!

  Lecture Video (7-1)
  Recitation (Week 7)
Lecture 6-1
2 / 13 / 24
Changing from Changemaking
Another example of Dynamic Programming on the LCS problem -- good for comparison!

  Lecture Video (6-2)
  Recitation (Week 6)
Lecture 5-1
2 / 6 / 24
From A* to Coinstar
Changemaking makes another appearance in this discussion of Dynamic Programming!

  Lecture Video (6-1)
  Lecture Video (5-2)
  Lecture Video (5-1)
  Recitation (Week 5)
Lecture 3-2
1 / 25 / 24
Foiled Again!
Adversarial search and α-β pruning!

  Lecture Video (4-2)
  Lecture Video (4-1)
  Lecture Video (3-2)
  Recitation (Week 4)
Lecture 2-2
1 / 18 / 24
Here-istics
Best-First, Informed search, and heuristics (get it? heuristics here? hereistics?).

  Lecture Video (3-1)*
  Consistency Example*
  Lecture Video (2-2)
  Recitation (Week 3)
* Botched consistency example in L3-1 patched in this supplemental video.
Lecture 1-1
1 / 9 / 24
Search and Ye Shall (Hopefully) Find
Problem solving, uninformed searches, and memoization!

  Recitation (Week 2)
  Lecture Video (2-1)
  Lecture Video (1-2)
  Lecture Video (1-1)*
* This is the Fall 2023 recording of L1-1 because my laptop lost power during this semester's recording -- same content, but apologies!

Homework
Number Date Assigned Date Due (@ midnight)
Homework 5 - Arc Nemesis 3 / 26 / 24 4 / 30 / 24
Homework 4 - Huff and Puff
 Grading Tests [.py]*
3 / 14 / 24 4 / 11 / 24
Homework 3 - Distle'd Knowledge
  Grading Tests [.zip]*
2 / 19 / 24 3 / 21 / 24
Homework 2 - Tic'd Off
  Grading Tests [.zip]*
2 / 1 / 24 2 / 22 / 24
Homework 1 - A*-y Night
 Grading Tests [.py]*
1 / 18 / 24 2 / 8 / 24

* To execute grading tests, place all files in the given zip into your own src folder, then run the grading unit test file using pytest name_of_grading_tests.py. If any config files are included (e.g., pytest.ini, include these in the directory as well)


Classwork
Number Date Assigned Date Due (@ midnight)
Classwork 6 - The Queen's Domain
4 / 4 / 24 4 / 16 / 24
Classwork 5 - Trie, Trie Again
 Solution
3 / 14 / 24 3 / 26 / 24 * (Extra time to complete!)
[Bonus] Classwork 4 - Weighting Tables
 Solution
2 / 15 / 24 2 / 20 / 24 (no late submissions accepted)
Classwork 3 - Mini Classwork, Maximal Gains
 Solution [.pdf]
2 / 1 / 24 2 / 9 / 24
Classwork 2 - A Breadth of Fresh Air
 Solution [.py]
1 / 16 / 24 1 / 23 / 24
Classwork 1 - Finding your (algo)Rhythm
 Solution [.py]
1 / 9 / 24 1 / 16 / 24