Course Information

Moodle
Check grades and solutions

Happy Living
Advice for successful learning experiences

Dates

Topics

Related Readings

Announcements

Week 1
8/25 - 8/29

Comp 275 Introduction
Introduction to Algorithms

- Welcome to Comp 275! I hope you find it a rewarding learning experience.

- Be sure you look through this site. It contains important information.

M

- Class procedures
- Notion of an Algorithm
- Algorithms and Problem Solving

Slides

Homework: 1.1.3a, 1.1.4

- Levitin 1.1
- This article about algorithms in business from The Economist

W

- Problem Types
- Data Structures
- Understanding Algorithms

Homework: 1.3.1, 1.4.10.
For 1.3.1a, make a variable chart showing the progress in sorting the array.

Levitin 1.2-1.4

F

- Data Structures
- C++ Quick Review
C++Tips.ppt
C++Examples.zip

Homework: Begin a1

Levitin 1.4

Week 2
9/1- 9/5

Algorithm Analysis and Design

M

- C++ Quick Review
- Analysis
Slides

Homework:
2.1.1 c, d, e
2.1.8 a, b, e, f
2.1.9 a, c, e, f

Levitin 2.1

W

Class meets 8:55 - 9:40
(altered schedule for opening convocation)

- Worst, best, and average case analysis
- Formal definitions of O, Omega, Theta

Homework:
2.2.2 a, b
2.2.5 (try to simplify the formulas, get an intuitive idea of the Theta class, and plug in numbers as needed to check growth rate)

Levitin 2.1 - 2.2

F

- Formal definitions of O, Omega, Theta
- Comparing orders of growth

Homework:
- 2.2.3 a, b (prove using the definition of Theta on p. 55)
- 2.2.3 c, d (prove using the theorem on p. 57)
Note that in this book, lg is log base 2.  Also review log formulas on p. 469.

Levitin 2.2

Week 3
9/8 - 9/12

Algorithm Analysis

M

- Analysis of nonrecursive algorithms

Homework due Wed 9:10 AM:
- 2.3.2d
- 2.3.3
- 2.3.6 a, b, c, d
For c and d, do worst-case analysis
- 2.3.10 a, b
For a, simplify the summation fully

Levitin 2.3

W

- Analysis of nonrecursive algorithms
- Mathematica help
MathematicaTips.doc
RSolveTest.nb
Functions.nb

Homework due Fri 9:10 AM:
- Redo homework assigned on 9/5, as discussed in class

Levitin 2.4

F

Week 4
9/15 - 9/19

Algorithm Analysis

M

- Analysis of recursive algorithms

Homework:

- Redo any past assignments, due 4:00 PM Monday 9/22.

- 2.4.1 a, b, e
- 2.4.3 a (setup only, do not solve)
- 2.4.8 a, b (setup only, do not solve)
Due 4:00 PM Tuesday 9/23

- a2 due 11:55 PM Thursday 9/25 via Moodle

W

No Class

F

No Class

Week 5
9/22 - 9/26

Brute Force

M

- Selection and bubble sort
- Sequential search
- String matching

Chapter 3 slides

Redo of assignments due 4:00 PM

Levitin 3.1 - 3.2

W

- Closest pair
- Exhaustive search: TSP, knapsack

Levitin 3.3 - 3.4

F

- Exhaustive search: knapsack, assignment
- Divide and conquer: master theorem, merge sort

Chapter 4 slides

Homework due Mon 4:00 PM:
3.1.7
3.2.1 (Hint: Do something similar to p. 49.)
3.2.4
3.2.9a (Describe in precise English and/or pseudocode)
3.2.9b (Make a linear-time algorithm.  Hint: The number of desired substrings ending with a B in position i is the number of A's to the left of it.)
3.4.7 (Precise English and/or pseudocode)

Levitin 3.4, 4.1

Week 6
9/29 - 10/3

Divide and Conquer

M

- Quicksort

Levitin 4.2

W

- Quicksort
- Average case analysis

Homework due Friday 9:10 AM
4.1.1 a, b, c (setup but do not solve), d
4.1.5 (Use Master Theorem)
4.2.1 (Answer should look like fig 4.3)
4.2.6

Levitin 4.2

F

- Binary Search
- Trees

Levitin 4.3 - 4.4

Week 7
10/6 - 10/10

Decrease and Conquer
Midterm Review

M

- Integer and Matrix Multiplication

Levitin 4.5

W

- Discuss homework
- Insertion Sort
Chapter 5 slides

Notify me by email by end of the day on Thursday (earlier if possible) of specific concepts you want reviewed on Friday!

Levitin 5.1

F

- Midterm review
- New material (not on midterm) as time allows

Week 8
10/13 - 10/17

Decrease and Conquer
Midterm

For the midterm:
- Bring a calculator
- Bring one 3x5 notecard, with whatever notes you want handwritten in your handwriting on a single side of the card.  (The other side should be blank.)
- You may photocopy p. 469 and 470 in the book and bring that with you.  No extra writing is allowed on your photocopies.

M

Midterm exam

W

- Depth first and breadth first search
- Topological sorting

Levitin 5.2 - 5.3

F

- Topological sorting
- Generating combinatorial objects
- The selection problem

Midterm makeup due 9:10 AM

Levitin 5.3 - 5.4
Levitin 5.6 (selection problem only)

Week 9
10/20 - 10/24

Transform and Conquer

M

Fall break

W

- Wrap up decrease and conquer
- Transform and conquer
- Presorting

Chapter 6 slides

Levitin 6.1
Levitin 6.2 (skim)

F

- Balanced trees

Homework due Monday 4:00 PM:
6.3.3 (like p. 217, not 216)
6.3.4 a, c
6.3.7 a

Levitin 6.3

Week 10
10/27 - 10/31

Transform and Conquer
Space and Time Tradeoffs

M

- Heaps

Homework due Wed 9:10 AM:
6.4.1
6.4.6 c

Levitin 6.4

W

- Counting paths in a graph
- Distribution counting
- Hashing

Chapter 7 slides

Homework due Fri 9:10 AM:
7.3.1 (separate chaining)
7.3.3
7.3.6b (Careful - no binary search on linked lists!)
7.3.7 (Give worst case and average case.  Intuitive reasoning with theta is fine.  You don't need to use precise probabilities and summations.)

Levitin quick skim 6.5, 6.6, 7.1, 7.2
Except full read of:
- "Counting Paths in a Graph" p. 239
- Distribution counting p. 252 - 253

Levitin 7.3

F

- B-Trees (last new material for quiz)
- Dynamic Programming (overview)

Homework due Mon 4:00 PM:
7.4.4
7.4.5

Daylight Saving Time ends this Sunday at 2:00 AM.  Set clocks one hour earlier!

Levitin 7.4
Levitin 8.1 (overview)

Week 11
11/3 - 11/7

Dynamic Programming Methods
Greedy Methods

For the quiz:
- Bring a calculator
- Bring one 3x5 notecard, with whatever notes you want handwritten in your handwriting on a single side of the card.  (The other side should be blank.)
- You may photocopy p. 469 and 470 in the book and bring that with you.  No extra writing is allowed on your photocopies.

M

- Warshall's Algorithm
- Floyd's Algorithm
- Optimal Binary Search Trees (overview) 

Chapter 8 slides

Homework due Wed 9:10 AM:
8.2.7 (Take it slow!)

Levitin 8.2
Levitin 8.3 (overview)

W

- Quiz (includes through chapter 7)
- Prim's algorithm
- Kruskal's algorithm

Chapter 9 slides

Levitin 9.1
Levitin 9.2 (Kruskal only)

F

Class canceled

Week 12
11/10 - 11/14

Limitations of Algorithm Power

M

Class canceled

W

F

- Decidability
- P, NP, and NP-Complete

Chapter 11 slides

Homework due Monday 4:00 PM:
Rework any quiz problems for up to 50% credit back.

Levitin 11.3

Week 13
11/17 - 11/21

Parallel Algorithms and Architectures

M

- Quick overview: approximation algorithms for backtracking, branch and bound
- The WARP cluster

Parallel intro slides
serial.cc, serial.job

11:55 PM a4 due via Moodle

Levitin 12.1 - 12.2 (skim)

W

- Flynn's taxonomy
- Shared memory and message passing
- Data and functional parallelism

11:55 PM a5 part 1 due

WARP p. 1 - 56

F

WARP (remainder of notebook - see comments in sample code for corresponding WARP pages)

Week 14
11/24 - 11/28

Message-Passing Programming

M

- MPI
chain.cc
deadlock.cc
completionTest.cc
bcast.cc
scatter.cc
gather.cc
- Principles of Parallel Algorithm Design

(Last day of new material for quiz)

11:55 PM a5 part 3 due via Moodle

WARP (remainder of notebook - see comments in sample code for corresponding WARP pages)
Quinn 3.3

W

Thanksgiving break

F

Thanksgiving break

Week 15
12/1- 12/5

Parallel Programming

For the quiz:
- Bring a calculator
- Bring one 3x5 notecard, with whatever notes you want handwritten in your handwriting on a single side of the card.  (The other side should be blank.)
- You may photocopy p. 469 and 470 in the book and bring that with you.  No extra writing is allowed on your photocopies.

M

- Principles of Parallel Algorithm Design - reductions, the n-body problem
slides

Quinn 3.5 - 3.6

W

- Quiz
- Example: circuit satisfiability
sat1.c, sat2.c, sat3.c

Quinn 4.4 - 4.6

Quinn 5

Week 16
12/8 - 12/12

M

W

F

Finals Week