CS 1501 Syllabus for Summer 2006 (206-7)

Information without a CLASS # is tentative and may be significantly altered. Reexamine this page frequently, as additional references, Web links, examples and other information may be added throughout the term. Please also see the Algorithm Animations page (thanks to Jonathan Beaver), which demonstrates many of the algorithms covered throughout the course.

CLASS #	DATE	REFERENCES	TOPICS/OTHER INFO
1	May 15	Sedgewick Chapter 6, 7	Intro to the course and course information sheet, converting algorithms to programs, comparing algorithm implementations, algorithm analysis
2	May 17	Sedgewick Chapter 44	Intro to Exhaustive Search, pruning, recursion and backtracking -- 8 Queens Example
3	May 22	Sedgewick Chapter 14, 17	Review of simple searching methods; intro. to digital search trees; radix search tries, multiway radix search tries; Patricia trees
4	May 24		De la Briandais (DLB) trees – idea, examples and detailed implementation; comparison to regular multiway radix search tries
5	May 31	Sedgewick Chapter 16, 36	Finish DLB trees Intro to Hashing – idea; collisions; avoiding collisions and the Pigeonhole Principle; reducing collisions with good hash functions; Horner’s method to hash strings
6	June 5		Linear Probing, Clustering and its effects, Double Hashing, Problems with delete using open addressing, closed addressing using Separate Chaining Hashing Handout
7	June 7	Sedgewick Chapter 19	Intro to String Matching; Brute force algorithm; KMP algorithm; Rabin Karp algorithm; Boyer-Moore mismatched character heuristic String Matching Handout
8	June 12	Sedgewick Chapter 22	Finish Boyer-Moore String Matching Intro. to Compression, Lossy vs. Lossless compression Huffman Compression: idea, block codes vs. variable length codes (and the prefix property), entropy and compressibility, building the Huffman tree, correctness (satisfies prefix property), quality, encryption and decryption Wikipedia article on entropy: http://en.wikipedia.org/wiki/Information_entropy Very useful Compression info: http://www.cs.sfu.ca/cs/CC/365/li/squeeze/ Interesting site regarding GIF controversy: http://burnallgifs.org/ Interesting article about JPEG patent: http://www.jpeg.org/newsrel1.html
9	June 14		Finish Huffman Compression Compression using Self-Organizing Search – idea, compression, decompression, details More info: http://www.arturocampos.com/ac_mtf.html http://www.rebolforces.com/articles/compression/2
10	June 19		Finish self-organizing search – quality of compression, run-time issues Start LZW compression: basic idea
11	June 21	lzw.txt lzw2.txt lzw3.txt	LZW Compression: encryption, decryption LZW implementation issues: Dictionary implementation, bits for codewords, action when out of codewords, I/O of byte fragments Comparison of compression schemes MIDTERM EXAM MATERIAL DOWN TO HERE
12	June 26		MIDTERM EXAM
13	June 28	Sedgewick Chapter 36	Integer arithmetic: Gradeschool multiplication algorithm; simple divide and conquer algorithm; recursive algorithm analysis; Karatsuba integer multiplication
14	July 3	Sedgewick Chapter 23	Finish Karatsuba multiplication; exponentiation (simple and divide and conquer); linear in value of a number vs. linear in number of bits; ); gcd (simple and Euclid's algorithm); extended gcd (general idea only) gcd.txt Intro to Encryption, simple encryption algorithms (Caesar cipher, substitution cipher), better block encryption algorithms (Vigenere cipher, Vernam cipher) http://astro.ocis.temple.edu/~dhill001/vigenere/vigenere.html http://www.pro-technix.com/information/crypto/pages/vernam_base.html
15	July 5		Public Key encryption: Need for, basic idea of, RSA as the most common example, RSA key generation http://www.cs.pitt.edu/~kirk/cs1501/notes/rsademo/index.html, RSA use and its runtime. Random prime number generation and testing (Miller-Rabin Witness), Security of RSA http://www.ecst.csuchico.edu/~atman/Crypto/cryptoindex.html http://mathworld.wolfram.com/news/2005-05-10/rsa-200/
16	July 10	Sedgewick Chapter 29 graphs1.txt	Uses of RSA (digital envelope, digital signature). http://www.rsasecurity.com/rsalabs/node.asp?id=2152 http://www.youdzone.com/signature.html Intro the Graphs, graph definitions, limits on number of edges, graph representations (adjacency matrix vs. adjacency list)
17	July 12	Sedgewick Chapter 30 graphs2.txt	Depth-First Search and Breadth First Search in detail DFS and BFS Biconnectivity and Articulation Points Articulation Points
18	July 17	Sedgewick Chapter 31 PFS.cpp	Weighted graphs, Minimum Spanning Trees, Priority First Search (PFS) , Implementation of Prim's MST algorithm – naïve implementation, better implementation using PFS – details of PFS implementation
19	July 19	Sedgewick Chapter 11 pq.h pqtest.cpp pqtest.out	Priority Queues and Heap Implementation
20	July 24	Sedgewick Chapter 33	Finish Heaps and PQs Network Flow: Ford-Fulkerson approach using augmenting paths, implementation details, augmenting paths with "backward flow", Edmonds-Karp approach of BFS or PFS to find an augmenting path, trace algorithm flownew.cpp flowtest1.txt flowtest2.txt flowtest3.txt flownew.out flownew.exe
21	July 26	Sedgewick Chapter 45 twoopt.c	Unsolvable problems, intractable problems, P, NP and NP-completeness Local Search Heuristics for NP-complete problems; Ex: 2-OPT for TSP problem
22	July 31	Sedgewick Chapter 42 fibo.java subset.java	Finish 2-OPT algorithm Idea of Dynamic Programming, Fibonacci Example, Subset Sum Example
23	Aug. 2		FINAL EXAM