Welcome to the Home Page of the CS141 Class
Intermediate Data Structures and Algorithms
Fall 2008
- Course grades
- Class syllabus
- Lectures (very tentative)
- Friday, September 26
Review of prerequisite topics
- Monday, September 29
Review, cont.
- Wednesday, October 1
Yet more review ...
- Friday, October 3
Quiz 1 .
Algorithms and running time
- Monday, October 6
Algorithms and running time
- Wednesday, October 8
Number theory, basic algorithms: exponentiation, Euclid's algorithm
(pages 28-32)
- Friday, October 10
Cryptography, overview, RSA
(pages 39-43)
- Monday, October 13
RSA, cont.
- Wednesday, October 15
RSA, cont.
- Friday, October 17
Quiz 2 .
RSA, cont.
- Monday October 20
Divide-and-Conquer: integer multiplication (pages 55-58)
- Wednesday, October 22
Divide-and-Conquer: Strassen's algorithm for matrix multiplication
(pages 66-67)
- Friday, October 24
Divide and Conquer:
Fast Fourier Transform (pages 68-79)
- Monday, October 27
Fast Fourier Transform.
- Wednesday, October 29
Fast Fourier Transform.
- Friday, October 31
Quiz 3 .
Dynamic programming:
intro, shortest/longest paths in DAGs
(pages 169-170)
- Monday, November 3
Dynamic programming: edit distance
(pages 174-178)
- Wednesday, November 5
Dynamic programming: 0-1 knapsack (page 182)
- Friday, November 7
Dynamic programming: matrix chain multiplication
(page 184-186)
- Monday, November 10
Graphs, graph representations (pages 91-93)
- Wednesday, November 12
Graph exploration, DFS, connected components (pages 93-100)
Example:
DFS on undirected graphs
Example:
DFS on directed graphs
- Friday, November 14
Quiz 4 .
DFS in directed acyclic graphs, linearization (pages 100-101)
- Monday, November 17
DAGs, linearization
Shortest paths, BFS (pages 116-118)
- Wednesday, November 19
Single-source shortest paths,
Dijkstra's algorithm
(pages 118-124)
- Friday, November 21
All-to-all shortest paths, Floyd-Warshall algorithm
(pages 187-188)
Single-source shortest paths, negative weights,
Bellman-Ford algorithm
(pages 128-130)
- Monday, November 24
Bellman-Ford algorithm.
Greedy algorithms:
Kruskal's algorithm for minimum spanning trees (pages 139-144)
- Wednesday, November 26
Minimum spanning trees.
- Friday, November 28
No class. Gobble, gobble.
- Monday, December 1
Union-Find data structures and its use in Kruskal's algorithm
Greedy algorithms: Huffman coding (pages 153-155)
- Wednesday, December 3
Huffman coding.
- Friday, December 5
Lower bound for comparison sorting. Limits of computation.
- Homeworks
-
Homework 1, Due Friday, October 10.
Sources: hw1.tex,
macros.tex (place in the parent directory)
Solutions.
-
Homework 2, Due Friday, October 24.
Due date postponed to October 27.
Sources: hw2.tex,
macros.tex (place in the parent directory)
Solutions.
-
Homework 3, Due Friday, November 7.
Sources: hw3.tex,
macros.tex (place in the parent directory)
Solutions.
-
Homework 4, Due Friday, November 21.
Due date changed to Wednesday, November 26.
Sources: hw3.tex,
macros.tex (place in the parent directory)
hw4_dfs_graph1.pdf,
hw4_dfs_graph2.pdf,
hw4_dfs_warshall.pdf,
hw4_dfs_graph1.graffle,
hw4_dfs_graph2.graffle,
hw4_dfs_warshall.graffle
Solutions.
-
Homework 5 (corrected Dec. 3), Due Friday, December 5.
Sources: hw5.tex,
macros.tex (place in the parent directory)
Solutions.
- Quizzes
- Quiz 1. Friday, October 3.
- Quiz 2. Friday, October 17.
- Quiz 3. Friday, October 31.
- Quiz 4. Friday, November 14.
Final. Friday, December 12, 11:30 AM - 02:00 PM.
Projects
-
Project 1:
First part due October 29, second part due November 5.
-
Project 2:
Progress report due November 26,
complete project due December 3.
CS141 Lab Home Page (on Moodle)
CS141 Study Group. TBA.
CS141 Academic Excellence Workshop. TBA.
Honor's credit.
It is possible to receive honor's credit for CS141 by
completing additional work. Please contact the instructor,
if you are interested.
LaTeX help
Some other books (and there are plenty more)
- Introduction to Algorithms,
by Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest
- Fundamentals of Data Structures,
by Ellis Horowitz and Sartaj Sahni
- Data Structures and Algorithms,
by Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman
- Computer algorithms : introduction to design and analysis,
by Sarah Baase
- Algoritmics: Theory and Practice,
by G. Brassard and P. Bratley
- Graph Algorithms, by S. Even
- The Design and Analysis of Algorithms,
by D.Kozen
- Introduction to Algorithms, by U.Manber
- Algorithms, by R. Sedgewick
- The Algorithm Design Manual, by S.Skiena
Useful links: lecture notes, tools, toys, and applications
Good causes (not related to class)