Syllabus
This is a partially inverted class. Before each class, you will either watch presentations or read book chapters. There will be a quiz that needs to be done before class. There is also going to be a group quiz at the very beginning of class.
For the complete syllabus, click here.
Office Hours
- Thomas Schwarz, SJ, Monday, Wednesday, Friday: 15:00 - 16:00 Room 340B
Contents
Week 1
Module 1: Automata and Regular Expression
- Presentation for January 14 (mp4): -- click here --
- Presentation for January 16 (mp4): -- click here --
- Presentation for January 14 and 16 (pdf) -- click here --
- Quiz for January 14 (needs to be done before class). The quiz is on D2L, but you need the text. -- click here --
- Worksheet for January 14 -- click here --
- Worksheet for January 16 -- click here --
- Quiz for January 16 (needs to be done before class). The quiz is on D2L, but you need the text. -- click here --
- Programming Assignment: Due January 23 in printed and written form. click here
Week 2: Growth of Functions
Read the first chapter of Cormen, Leiserson, Rivest, \& Stein. Concentrate on subchapter 3. Repeat from your Discrete Mathematics class induction and recursion. Repeat from you Calculus class limits and L'Hôpital's Theorem.
- Worksheet: Landau O -- click here --
- Worksheet Solutions: Landau O -- click here --
- Worksheet: More on Landau notations -- click here --
- Worksheet: More on Landau notations -- Solutions -- click here --
- Wednesday: Lecture on the goals of analysis of algorithms
- Friday: Analysis of the Euclidean algorithm as both correct and efficient
Week 3: Growth of Functions and Divide and Conquer
Read the first chapter of Cormen, Leiserson, Rivest, \& Stein. Repeat from your Discrete Mathematics class induction and recursion. Repeat from you Calculus class limits and L'Hôpital's Theorem. Wednesday is a snow day, so the class moves to be virtual. You need to listen to the presentation and you need to do the homework for Friday in written form. You do not need to type it, but it needs to be neat.
- Wednesday: Divide and Conquer Algorithms and Recursion < -- click here for presentation-->
- Wednesday: Divide and Conquer Algorithms and Recursion < -- click here for text -->
- Homework for Friday: < -- click here for text --> < -- click here for solutions-->
- Friday: Exercises in Complexity
Week 4:
- Monday: Solving recursions
- Monday -- Towers of Hanoi example < -- click here for pdf -- >
- Wednesday: Master Theorem < -- click here for pdf -- >
- Solution to the Three Stooges Sort Quiz < -- click here for pdf -- >
- Second Programming Assignment < -- click here for pdf -- >
- Friday's presentation on decorators: < -- click here for pdf -- >
- Friday's Python code < -- click here for pdf -- >
- Friday's activity on the master theorem < -- click here for pdf -- >
- Friday's activity on the master theorem: Solutions < -- click here for pdf -- >
Week 5: Order Statistics
Read Chapter IX of the text book.
- Monday's lecture on order statistics. < -- pdf -->
Data Structures
- Lecture on B and B+ trees < -- pdf -->
- Linear Hashing < -- pdf -->
Homework
Homework on order statistics due Thursday, February 28 in nicely written way. < -- homework as pdf --> < -- solution as pdf -->.
Midterm Preparation
- Midterm preparation problem set. < -- click here for pdf -- >
- Midterm preparation solution. < -- click here for pdf -- >
Dynamic Programming
- Lectures < -- pdf -->
- Floyd Warshal Group work < -- pdf -->
Greedy Programming
- Lectures < -- pdf -->
Homeworks
- Programming Assignment due March 22, 2019 < -- pdf -->
- Homework 3 due March 22, 2019 < -- pdf -->
Graph Algorithms
- Programming Assignment due April 15, 2019 < -- pdf -->
- Homework due April 15, 2019 < -- pdf -->
Homework
- due April 17, 2019 (no extension) < -- pdf -->
Computability
- Lectures < -- pdf -->
Homework
- due May 3, 2019 (no extension) < -- pdf -->
- due May 5, 2019 (no extension) < -- pdf -->
Complexity Classes
- Lectures < -- pdf -->
Final Preparation
- Final Preparation 1 < -- pdf -->
- Final Preparation 2 < -- pdf -->
Last Chance Make-up Homework
- Make-up Homework < -- pdf -->