Comp 215 Homeworks and Reading

The CS 215 schedule is constantly undergoing updates as the Winter quarter progresses! Refresh this page often!

This page was last modified on .

IMPORTANT NOTE: The following schedule represents my current best guess concerning due dates (and everything else). I am providing this information to give you a general idea of the pace and timing of the class. THESE DATES AND ASSIGNMENTS MAY CHANGE. All reading assignments are from the Algorithms Illuminated textbooks, unless otherwise indicated.
HW = Homework. DQ = Discussion questions. PP = Programming project.

DAY	Reading/Watching (before class)	In-class Activities	To do after class
M1		Introductions to each other Introduction to course Integer Multiplication	Slides:Introduction First Day Watch the video Why Study Algorithms video as a follow up from class. Begin working on HW A
W1	Read Sections 1.1 - 1.3 Watch the videos on Integer Multiplication Karatsuba Multiplication	Discuss Karatsuba Multiplication	Slides:IntigerMultiplication Start on DQ #1
F1	Read Sections 1.4, 1.5, 1.6 Watch the videos on MergeSort Analysis Guiding Principles Submit to Kit by end of day: HW A	Discuss MergeSort MergeSort Analysis Guiding Principles for Analysis of Algorithms Finish DQ #1	Slides:MergeSort Watch the video discussion of DQ #1
M2	Read 2.1,2.2 Watch the videos on The Gist of Algorithmic Analysis Big-Oh Notation	Start into Asymptotic Notation Discuss Algorithm Analysis and Asymptotic Notation	Slides: Asymptotic Notation Practice quiz Asymptotic notation Start on HW #1 Complete the Concept Check #1 before W3
W2	Read Chapter 2. Watch the videos on Basic Examples Big Omega and Theta Additional Examples	Discuss Examples in Section 2.5 Discuss Quiz 2.5 Work on DQ #2	Keep working on HW #1 Work on Concept Check #1 before Wednesday W3
F2	Read Sections 3.1, 3.2 Watch the videos on Counting Inversions in O(nlogn) time, part 1 Counting Inversions in O(nlogn) time, part 2 Submit to Kit by end of day: HW #1	Discuss Divide and Conquer and some examples Start on Programming Project: Divide and Conquer	Slides:Divide and Conquer Make sure you've done the Concept Check #1 (You can do it more than once if you don't get a perfect score.) Finish and submit HW #1
M3	MLK
W3	Read Sections 4.1, 4.2, 4.3 Watch the videos on Motivation/Integer Multiplication Formal Statement of Master Method Examples of Master Method Proof of Master Method, Part 1 Proof of Master Method, Part 2"	Discuss Recurrences and Master Method Work on Problems 4.1, 4.2, 4.3, 4.4	Slides:The Master Method Start on HW #2
F3	Read Sections 5.1 - 5.4, 5.6 Watch the videos on Overview of Quicksort Partitioning Around a Pivot Choosing a Good Pivot QuickSort requires Omega(nlogn) comparisons	Discuss QuickSort Discuss limits on comparison-based sorts	Keep working on HW #2
M4	Read Chapter 7 and Section 8.1 (in book 2). Watch the videos on Graph Basics Graph Representations Graph Search Overview Submit to Kit by end of day:Divide and Conquer Project Part 1	Intro to graphs	Slides:Graphs Keep working on HW #2 Complete Concept Check #2 before end-of-day on Monday (Week 5). Submit Concept Check #2 Reflection after completing the concept check.
W4	Read Section 8.2 Watch the videos on Breadth-First Search Basics Breadth-First Search and Shortest Paths Submit to Kit by end of day: HW #2 Submit to Kit by end of day: Divide and Conquer Project Part 2	Discuss Problems 7.1 - 7.3 Discuss breadth-first search and shortest paths	Slides:Breadth-first search
F4	Read Sections 8.3 - 8.5 Watch the video on Breadth-First Search and Undirected Connectivity Depth-First Search Basics	Discuss Breadth-First Search and Undirected Connectivity Discuss Depth-First Search and Topological Sort	Start on Programming Project: Dijkstra Slides:Depth-first search
M5	Read Chapter 9. Watch the videos on From Chapter 8: Topological Sort The Structure of the Web From Chapter 9: Dijkstra's Shortest Path Algorithm Dijkstra's Algorithm Examples Correctness of Dijkstra's Algorithm (OPTIONAL) Dijkstra's Algorithm Implementation and Running Time	Work through Dijkstra's algorithm, pseudocode, and examples.	Work on Dijkstra Project and start on HW #3 Slides:Dijkstra's algorithm
W5	Read Sections 10.1-10.4, 10.5 is optional Watch the videos on Data Structures Overview Heap Operations and Applications Heap Implementation Details (OPTIONAL)	Discuss Heaps and Dijkstra	Read Section 10.5 Work on Project 2 and HW #3
F5	Catch up day
M6	Midterm Exam	Review Topics for Midterm
W6	Read Chapter 11 Watch the videos on Balanced Search Trees: Operations and Applications Binary Search Tree Basics, Part 1 Binary Search Tree Basics, Part 2 Rotations	Discuss Search Trees Work on projects	Check out these links to experiment with AVL Trees and Red/Black Trees (two kinds of balanced trees) Finish up HW #3 and continue working on Dijkstra Project Work on DQs for Friday: Problems 10.1-10.4
F6	Mid Term Break	Enjoy!
M7	Read Sections 12.1 - 12.4 Watch the videos on Hash Table and Operations Hash Tables Implementation Details, Part 1 Hash Tables Implementation Details, Part 2 Pathological Data Sets and Universal Hashing Motivation Submit to Kit by end of day: HW #3	DQs 10.1 - 10.4, 11.1, 11.2 Discuss Hash Tables	Continue to work on Project 2 Slides:Hash Tables
W7	Read Sections 12.5 - 12.6 Start to Read Chapter 13 Watch the videos on Bloom Filters:The Basics Bloom Filters Heuristic Analysis	Discuss Bloom Filters	Finish up Dijkstra project Work on Data Structures Reflection Slides:Bloom Filters
F7	Read Chapter 14 Watch the videos on Intro to Greedy Algorithms A Scheduling Application Developing a Greedy Application Scheduling: Correctness Proof, Part 1 Scheduling: Correctness Proof, Part 2 Scheduling: Correctness Proof, Part 3 Submit to Kit: Dijkstra Project	Discuss Greedy design paradigm	Slides:Greedy Algorithms
M8	Finish any reading from the week Watch the videos on Intro to Huffman Codes Codes as Trees Huffman's Greedy Algorithm, Part 1 Huffman's Greedy Algorithm, Part 2 Huffman's Algorithm: Correctness Proof, Part 1 Huffmans' Algorithm: Correctness Proof, Part 2 Submit to Kit:Data Structures Reflection	Discuss Huffman's greedy algorithm Work on 14.1 - 14.4	Start on Huffman Programming Slides:Huffman's greedy algorithm
W8	Read Chapter 15 Watch the videos on Minimum Spanning Trees: Problem Definition Prim's MST Algorithm Speeding up Prim's Algorithm via Heaps (Part 1) Speeding up Prim's Algorithm via Heaps (Part 2) (Optional) Prim's Algorithm: Correctness Proof (Part 1) (Optional) Prim's Algorithm: Correctness Proof (Part 2) Watch these for W8: Kruskal's MST Algorithm Speeding up Kruskal's Algorithm via Union-Find (Part 1) Speeding up Kruskal's Algorithm via Union-Find (Part 2) Lazy Unions (Optional) Kruskal's Algorithm: Correctness Proof	Discuss MST Greedy Algorithms	Start on HW #4 Slides:MST Greedy Algorithms
F8	Finish reading Chapter 15 Watch the application video: Clustering	Discuss MST implementations and runtimes Discuss clustering application	Keep working on HW #4
M9	Read Sections 16.1 and 16.2 Watch the videos on Introduction to Dynamic Programming A Linear-Time Algorithm for WIS in Path Graphs (Part 1) A Linear-Time Algorithm for WIS in Path Graphs (Part 2) A Reconstruction Algorithm Submit to Kit by end of day: HW #4	Quiz 2 Intro to Dynamic Programming	Start on HW #5
W9	Read Sections 16.3 - 16.5 Watch the videos on Principles of Dynamic Programming The Knapsack Problem (Part 1) The Knapsack Problem (Part 2) The Knapsack Problem (Part 3) Submit to Kit by end of day: Huffman program	Knapsack discussion Work on HW #5	Keep working on HW #5 Start on Knapsack Program
F9	Reading on backtracking. There is a document titled "Foundations of Algorithms - CH.5" in the Files folder of this course on Kit. The reading skips sections 5.3, 5.4, and 5.6.	Discuss backtracking with NQueens, M-coloring, and Knapsack	Continue working on HW #5 Continue working on Knapsack Program
M10	Introduction to Complexity Theory There is a reading titled "AlgsIllChap19.pdf" in the Files folder of the course on Kit. NP-Completeness (optional slides to look at)	Discuss NP Hardness	Work on finishing assignments
W10	Submit to Kit: HW #5, Knapsack Program	Catch up
F10	Review	Quiz 3

Discussion Questions

DQ #1: Questions for middle/end of First Week
- Write an algorithm that finds the largest number in a list (an array) of \(n\) numbers.
- Write an algorithm that prints out all the subsets of three elements from a set of \(n\) elements. The elements of this set are stored in a list that is input to the algorithm.
- Write an algorithm that finds both the smallest and largest numbers in a list of \(n\) numbers. Try to find a method that does at most \(1.5n\) comparisons of array items.
DQ #2:
- Work on Problems 2.1, 2.3, 2.4 from your text
- Work through the Practice Quiz on Comparing function growth (from F1)
- Work through the Practice Quiz on Asymptotic notation (from F1)
DQ #3: Still More Questions for Second Week:
- Exercise 15 in Chapter 1.
- Exercise 19 (Exercise 22 in 5th edition) in Chapter 1.
- Exercise 19 from 5th edition: The function f(n) = 3n² + 10nlogn +1000n + 4logn + 9999 belongs in which of the following complexity categories:
  1. θ(lgn)
  2. θ(n²logn)
  3. θ(n)
  4. θ(nlgn)
  5. θ(n²)
  6. None of these
- Parts a, b, and c of Exercise 1 in Appendix B.
DQ #4: Questions for Friday of Second Week:
- Parts a, b, and c of Exercise 12 in Appendix B.
- Parts a and b of Exercise 24 in Appendix B.
DQ #5: Questions for Wednesday of Third Week:
- Exercises 1, 2, 5, 6, 7, 8, 13 in Chapter 2.
DQ #6: Questions for Friday of third week:
- Exercises 19-20 and 24 in Chapter 2.

DQ #7: Questions for Monday of fourth week:

Exercises 4 and 7 in Chapter 3.

Use Floyd's algorithm to determine the shortest paths matrix for the graph whose adjacency matrix is:

0	2	4	3
3	0	∞	3
5	∞	0	3
∞	1	4	0

DQ #8: Greedy algorithms
- Exercises 4, 6, and 9 in Chapter 4.

DQ #10: Additional Greedy Approach Questions

Exercise 7 in Chapter 4.
Exercise 12 in Chapter 4.

Use Huffman's algorithm to create an optimal binary prefix code for the following letters:

LETTER:	a	c	k	l	m	o	s	z	SPC
FREQUENCY:	80	30	10	40	20	70	60	1	90

Use your code to encode the string "kalamazoo cs".
Exercise 32, and 34 in Chapter 4.
Exercise 46 in Chapter 4.

DQ #10.5: Real World Applications
- Find a real-world application of minimum spanning trees.
- Find a real-world application of the knapsack problem.
DQ #11: Backtracking/N-Queens Questions
- Exercises 1, 2 in Chapter 5
DQ #12: Additional Backtracking Discussion Questions
- Exercise 13 in Chapter 5.
- Exercise 18 in Chapter 5.
- Exercise 33 in Chapter 5.
DQ #13: Discussion Questions on Branch-and-bound, heaps, sorting
- Exercises 1 and 4 in Chapter 6.
- (Use W=10 for all.)
- Exercises 26 and 32 in Chapter 7
- Exercise 2 in Chapter 8. (I think S and T must be sorted for this to work, but I could be wrong.)
- Radix sort the following numbers: 329, 457, 39, 657, 839, 79, 436, 8, 720, 355.
- Insert the letters K, A, L, A, M, A, Z, O, and O one at a time into an initially empty 3-2 tree. Show the actions step-by-step.
DQ #14: Questions for Friday of Ninth Week:
- Apply the Selection Algorithm (Algorithm 8.5) to find the sixth-smallest value in the list 30, 80, 20, 100, 50, 40, 90, 60, 70, 10. Notice that Algorithm 8.5 is the algorithm that uses the first value as the pivot, not the one that uses the median of medians. You do not need to step through the partition algorithm: just partition the values yourself, leaving the values in each partition in the same order relative to the other values in the partition.
DQ #15: Questions for Wednesday of Tenth Week:
- Exercise 15 in Chapter 9.
- Double-CNF-SAT is the problem of determining whether a CNF formula has at least two satisfying assignments. Show that Double-CNF-SAT is NP-complete by showing a reduction from CNF-SAT.
- We define the MIN-ELEMENT decision problem as follows: given an unsorted list of n integers, and an integer k, determine whether the minimum integer in the list is smaller than k. Show that min-element is polynomial time many one reducible to CNF-SAT. Does this mean than min-element is NP-Complete?